This is an alternate proposal to BIP32.
Version History:
- 12-7-2102: Addition of chain code (much as BIP32 uses).
- 12-3-2012: Initial Proposal (version 1)
There are several problems with the current system of key generation for Bitcoin wallets and services.
- Randomly generated unique keys can be lost due to negligence or hardware failure. Keys require a careful backup strategy once they are used. A lapse in backup procedures can lead to irrevocable loss of funds that are protected by those keys.
- If a user has a need for a large number of public keys, they must be generated in a secure manner - possibly on an offline computer. If an online service needs access to only the public portion of a key (for monitoring of transactions, without the ability to spend the balances held by the private key), each of the generated public keys need be exported to the online service. This list must be updated as new keys are generated so that the balances visible in the online service, match those of the offline wallet.
A heirachical deterministic key system addresses these issues by enabling the creation of an unlimited number of keys from a single seed value or starting key (called the root key). Only a holder of a root key can generate child keys. Yet the holder of a root key can generate other "parent keys" for use in diverse services. The sharing of a parent key derived from a root, leaks no information about the root key.
- seed - A high-entropy ("random") piece of information that can be used as the basis to produce a root key (think of a very long "password"). A seed must be stored safely and securely as all private and public keys generated in this system depend on it.
- root key - A master key that forms the basis of an entire namespace of child keys. A root key would typically be kept as private information to a single person or organization.
- parent key - A parent key is one generated from a root key (or other parent key), that is intended to be used to create a sub-tree of keys underneath it. A parent key should be considered secret, and should not generally be used itself to receive transactions. Note that knowledge of a parent key's public key, enables anyone to calculate the public keys of all of it's children.
- Heirarchical deterministic key generation for Bitcoin wallet or services.
- Keys can be exported supporting private key distribution or public-key only (the latter can be used for monitoring addresses, while do not allow for funds to be transfered).
- Ensure that generated keys are nearly impossible to collide with other generated keys.
- Allow for easy mnemonics and labeling of keys to identify where in the namespace heirarchy they reside (using strings, not just numbers).
- Enable repeatable sequences of keys to be generated from a single parent key.
- Support seed-based root-key generation.
Bitcoin transaction signing uses Eliptic Curve cryptopgraphy. The unique property of ECDSA is that private keys can be chosen at random (256 bit numbers). The associated public key is the product of that key and a Generator of the eliptic curve:
k - Private Key
K = k * G - Public Key (a "point" on the curve - consisting of parts K(x), K(y))
Knowing only K it is not computationally tractable to discover the private key, k.
An interesting property of the keys, is that they can both be multiplied by a multiplier and they maintain their relationship as private and public key pair:
k' = M * k (mod n)
K' = M * K (same as (M * k) * G)
Where n is the "order" of the eliptic curve.
This allows us to chain any number of multipliers, to derive new keys from a parent key, whether we start from private or public keys only.
Define a mapping of strings to a selection of multipliers that can be used to modify a parent key, to a deterministic key corresponding to the string.
We define a string to be a heirarchical key:
K.<part1>.<part2>. ... .<partN>
for example:
coinlab.store
We use a hash function to transform a seed with high entropy into a 256 initial private key:
k = hmac_sha256('generate', seed) (interpreted as a 256 bit integer)
K = k * G
C = hmac_sha256('chain', seed)
In order to identify a key, we assign it an identifiable checksum (so we can be confident we have entered the seed correctly when we next use the key generator).
Note the addition of a "chain code", C. The multipliers we compute are functions of the chain code for all the child keys of the current key. This extra entropy is added so that revealing the public or private keys is not sufficient information to be able to calculate all the multipliers for all ancestor keys.
For a given parent key, (k, K), and next part of a path string, p, we define:
M(C, p) = hmac_sha256(C, 'mult' + p) (interpreted as a 256 bit integer mod n)
C(p) = hmac_sha256(C, p) (new chain code function of parent and string part)
so that the child ECDSA key is (M * k (mod n), M * K).
An extended heirarcy of multipliers allows for any depth of nesting of keys:
M1 = M(C, 'store')
K.store = (M1 * k (mod n), M1 * K)
M2 = M(C('store'), 'east')
K.store.east = (M1 * M2 * k (mod n), M1 * M2 * K)
Any sequence of keys can be generated in the heirarchy by using the string representation of the integers in the key part:
K.store.east.1, K.store.east.2, ..., K.store.east.N
Proper use of this system requires some care in dealing with the chain code of a key.
While it is obvious that a user's seed and root key must be kept secret and secure, some care is needed in dealing with any parent key if you intend to share the key with another entity or in a relaxed security context.
-
If a users knows BOTH the chain code, C, and the public key, K, they will be able to recover ALL public keys of all child keys of K - enabling monitoring of all transactions that use those child keys now and into the future (note that knowing the public key alone of a parent key DOES NOT allow an attacker to monitor any child key addresses).
-
Knowlege of BOTH the chain code, C, and the private key, k, will allow recovery of the private key of all child keys of the parent key. Note also that knowledge of ONLY a parent key's chain code as well as ANY private key of an ancestor key, will allow a user to recover the original private key of the parent. (since all the multipliers can be reconstructed, we can reverse calculate the parent private key from knowledge of any child's private key).
For example, if I know the chain code for K.store.secure - but only know the private key for K.store.secure.order.12345, I will be able to back-calculate all private keys for K.store.secure.* and their child keys.
$ make-keys -g -n 1
Preparing to generate seed. Ensure computer disconnected and no one can read over your
shoulder. Hit return when ready...
Seed = 'DAMI8PENGN5U6TH78AP7'
Seed checksum: hd2-9bc2fa57-c07e1d2c
Sub-key:
Key generation code (Python):
----------clip here----------
from hdwallet import HDKey
parent = HDKey.create_from_seed('DAMI8PENGN5U6TH78AP7')
for i in range(1, 2):
print parent.create_from_path(i).get_private_bc_address()
----------end clip-----------
Private keys:
hd2-9bc2fa57-c07e1d2c.1. 5K2sGWd5ez8KYxE5XaDnsDKpXTEttBqxNqpWixXoNtQjUzd7UTV
Public addresses:
hd2-9bc2fa57-c07e1d2c.1. 19vZ2FJCuAhbdwd3mNd1keqsWNQhKtDp23
$ make-keys -n 10
Seed (or raw hex private or public key): DAMI8PENGN5U6TH78AP7
Seed checksum: hd2-9bc2fa57-c07e1d2c
Sub-key: store
Subkey checksum: hd2-29b7d927-23a83061
{'chain': '3AJ1iAGKnnBkUfRLuWzkfwX19V6ZEZokSECMg4uy16jm',
'name': 'hd2-9bc2fa57-c07e1d2c.store',
'private': 'ff50f712b8f968ecf461c6c60b4e1a90fe21b941301f21c7bc4308c22757575c',
'public': '1PdaJHEvyHV9tjbACSFxwNiqbGN77z3h51',
'version': 'hd2'}
..........
hd2-9bc2fa57-c07e1d2c.store.1. 1Q3R1rR3FtJdpXydeYJ9NoJFUSAEW9fipK
hd2-9bc2fa57-c07e1d2c.store.2. 1Azr73qkC1dtjp4GLNaMzbdnoQ5GW4qjbP
hd2-9bc2fa57-c07e1d2c.store.3. 1DZs8fjgxRCLgQvbTV8nBGz3gW1R676Bqr
hd2-9bc2fa57-c07e1d2c.store.4. 1G7iJJP4VAKPcxpm3brZsZSphSZfrPQGbJ
hd2-9bc2fa57-c07e1d2c.store.5. 1Gv89e1dsss6YKdHBNB3Reiz2goxQ5xYcd
hd2-9bc2fa57-c07e1d2c.store.6. 1HnJ8n7zxDRojxH7cDmTsQ1qmdoWzFHe66
hd2-9bc2fa57-c07e1d2c.store.7. 1L8CuhQroYtU1R6YuW8ggTsngCQ6NGm2tU
hd2-9bc2fa57-c07e1d2c.store.8. 1NtsoSfTVyGM5S7NvB8k9yp3Q6NAAn2FpK
hd2-9bc2fa57-c07e1d2c.store.9. 1K67HLKohUmfrg2a1pufjfL9T7gJVvBy8s
hd2-9bc2fa57-c07e1d2c.store.10. 1LJ9WgRQSExxtczAgqRsrXUg3C9sMhEUsc