Exploring HD Wallets: Everything You Need to Know about BIP-32 and BIP-39
Wallets are where private keys, public keys and addresses are kept securely. To generate bitcoin addresses or use a saved private key to sign a transaction in order to spend an unspent transaction output(UTXO).
Generally reusing one address to receive bitcoin is bad for privacy in the network, bitcoin transactions are not anonymous but pseudonymous hence using one address can lead to the linking of transactions to a particular pseudonym and that pseudonym can be tracked. https://en.bitcoin.it/wiki/Address_reuse
Before the bip32 proposal which we will get to later, wallets generate hundreds of private keys, which will be used to generate public keys and bitcoin addresses to avoid address reuse, backing up these keys is not easy and can sometimes be difficult.
In 2012 Pieter Wuille and other bitcoin core developers came up with a bitcoin improvement proposal for a deterministic wallet (bip32) whereby one key (seed) will generate unlimited private keys, public keys and addresses.
In a deterministic wallet, the seed needs to be backed up, because the seed together with a derivation path can generate all the private keys, public keys and addresses again. how? we will get to it also.
The seed can be created from a random number generated from an entropy (source of randomness) and that random number can also be encoded as 12 or 24 mnemonic words as defined in the bip39 https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki as it’s easy for people to use.
The random number is 128 bits or 256 bits, which can be mapped to either 12 or 24 words.
In 128 bits of entropy. The 128 bits entropy will be hashed with sha256 and the first 4 bits of the hashed entropy will be taken as a checksum.
128 bits entropy + 4 bits checksum = 132 bits
132 bits will be split by 11 which will generate twelve 11 bits each and will be mapped to a word in a list of 2048 chosen words.
E.g imitate, depend, fragile, half, nephew, trial, head, outside, super, ketchup, lunar, expand.
while in a 256 bits entropy, The 256 bits entropy will be hashed with sha256 and the first 8 bits of the hashed entropy will be taken as a checksum.
256 bits entropy + 8 bits checksum = 264 bits
264 bits will be split by 11 which will generate twenty-four 11 bits each and will be mapped to a word in the list of 2048 chosen words.
E.g mom, person, nuclear, brisk, chimney, olive, orphan, detect, good, organ, involve, social, wave, way, palace, good, sentence, slogan, title, library, acquire, rug, ladder, glare.
Users can keep their mnemonic words safe, and it will be needed in other for them to regenerate all other keys and addresses in their wallet.
How does that work….
Well, the Mnemonic words will be added to an optional passphrase or salt and then stretched to a 512-bit seed, the passphrase is optional and is used to increase security such that even when an attacker tries to get hold of the user mnemonic they cannot be able to generate the seed, a mnemonic phrase without a salt generate different seed from a mnemonic with salt, the salt can be any sequence of characters the user wants and hence brute force is infeasible. The stretching of mnemonic to seed is 2048 rounds of HMAC-SHA512 hash function (which basically means applying HMAC-SHA512 function on the mnemonic phrase to generate a hash and also performing the HMAC-SHA512 function on the resulting hash, repeated for 2048 rounds).
The seed will then be split into two, the left 256 bits is the master private key and the right 256 bits is the master chaincode. The private key then is used to generate a master public key (264 bits) with the secp256k1 algorithm with a generator point on the curve https://en.bitcoin.it/wiki/Secp256k1. With those three values, master private key, master chaincode and master public key we can generate billions of child keys (child private key, child chaincode and child public key), and the children can also generate their children keys continuously.
A public key with chaincode and an index number from (0 to N). will be an input of an HMAC-SHA512 algorithm to generate a 512 bits hash.
The 512 bits hash will be split into two left(256 bits)and right 256.
The child chaincode is the right 256 bits
The left 256 bits will be concatenated to the 256 bits' parent private key which generates the child private key. wait a minute is that not 512 bits, no it’s not a scalar addition 256 bits + 256 bits is another 256 bits number, which will be the child private key, and using the secp256k1 function we will generate the child public key, the same for other children but with a different index number.
With this feature you can generate thousands of keys/pairs which is fascinating, another amazing feature is you can be able to generate child public keys without the private key, wait how………
The public key, chaincode and index number will be input to an HMAC-SHA512 to generate a 512 bits hash.
The 512 bits will be split into two left 256 bits, and right 256 bits.
The right 256 bits hash is the child chaincode.
The left 256 bits hash will be concatenated with the parent public key (256 bits) to generate a 256 bits public key.
How is that possible????.
well, it is just some maths, k is the private key, C is the chaincode, an index number i,
hash(K+C+i) = h
h+k = the child private key (child k)
G is the elliptic curve generator point, the elliptic curve algorithm generates the public key by multiplying the generator point by the private key k.
K = G*k
G*(k+h) = the child public key
G*k + G*h = G*(k+h)
With normal child derivation,
In public key child derivation.
K is the parent public key.
K + G*h = child public key
However K = G*k
G*k + G*h.
Hence the two public keys are the same.
The combination of a public key and chaincode is called an extended public key. Which can be used with an index number to generate child public keys. The combination of the private key and the chaincode is the extended private key, which can be used to generate a child's private key.
When an extended public key’s child private key is leaked, the master private key can be known and worse all its descendants as well.
K is the parent public key, C is the chaincode and I is the index number, and k is the parent private key (256).
h = Hash(K+C+I)
h is split into two left 256 bits, right 256 bits
The child's private key is k+left 256 bits.
Since the extended public key is given we have chain code and the public key can brute force to find the index of the child.
The hash of the extended public key (parent public key and chain code)with index number will be subtracted from the leaked child private key and the number is the parent private key.
k = h-k (child private )
the parent’s private key and the chaincode will generate the extended private key.
Hence we can generate all other child private keys.
We use hardened derivation to generate the private key without the public key and generate the public key with secp256k1.
In hardened derivation hash(h) = HMAC-SHA512(parent private key(k) +chain code (C)+ index number(I)).
hash will be split into two left(256 bits) and right(256 bits)
child private key = parent private key(256 bits) + left 256 bits.
child public key K = G*k .
Hence the child keys can be generated without the risk of their extended private key being exposed when a child's private key is leaked.
And you can safely save the public key as an extended public key with the chaincode, and hence any leaked child key will not lead to the vulnerability of revealing the parent public key.
We can use the hardened extended key to derive the extended private key and extended public key. which we will use in hierarchical deterministic (HD) wallets.
The use of bip32 and bip39 reduces the stress of managing hundreds of keys in a wallet, whereby only a set of mnemonic words will generate all the addresses one needs in a lifetime and more.
References
https://medium.com/@robbiehanson15/the-math-behind-bip-32-child-key-derivation-7d85f61a6681
