Our bitcoin wallets contain the most important piece of information when it comes to our cryptocurrency: the private keys that can unlock the UTXOs that were encumbered to the corresponding public keys and public key hashes. In other (maybe simpler) words, when we receive bitcoins, a transaction gets recorded on the blockchain indicating that these bitcoins were assigned to our public key. Only our corresponding private key can unblock these bitcoins and have them sent to a different public key (for example, when we sell them, or when we exchange them for some other good) by generating a new transaction where:
- We need to prove that we are the “owners” of the public key where the bitcoins were assigned
- We assign these bitcoins to a new owner (to a new public key)
In a few words, our private keys are the proof of ownership of our bitcoins, and only through them we can transfer them. Or as we say at privatekeys.org “Your (private) keys, then your bitcoins. Not your (private) keys, then I’m sorry pal, but not your bitcoins”.
That’s why keeping the private keys safe has become truly important, especially after the unfortunate episodes where private keys – and then bitcoins – where stolen from Coin Exchanges that were custodians of their customers keys and coins. Since the notorious Mt Gox crash in 2013 [i] the popularity of hardware-based personal bitcoin wallets where end users can securely store their private keys have grown exponentially and companies such as Trezor or Ledger have become important players in this field.
Initial Random Sequence Generation
In any case, a secured hardware device where private keys are stored is not a new concept. They have been called Hardware Security Modules (a.k.a. HSMs) and they have been manufactured (and sold) for decades.
However, while every HSM manufacturer has its own proprietary way to generate and store keys, the bitcoin community has standardized how keys are created from a random value, or from older keys in a hierarchical structure. When it comes to the initial creation of a private key, everything is very clearly explained in BIP0039 [ii]. Let us just summarize the process here
- An initial amount of (pseudo) random bits are generated. How this random value is generated is not standardized, even in bitcoin. Usually the hardware wallet chooses which entropy source to use and which deterministic random bit generator (DRBG) uses that entropy to generate our sequence of random bits. A good implementation would contain the following characteristics
- A good entropy source, preferably hardware based.
- Have more than one source of entropy if possible.
- Capable of generating 256-bits of entropy.
- Entropy should not be controlled by human.
- Rate of entropy must be sufficient to handle the workload.
- DRBG (Deterministic Random Bit Generator) should be standardized and validated. For example, by using a NIST SP800-90A compliant method (say, CTR-DRBG (AES-256 bits))
- If we comply with the above, then we would get good random bit sequences that would not be duplicated.
Mnemonic Words Generation
Ok, say we have got a good random sequence, what do we do with it and how do we get to our private key? In the simplest of schemas, we could simply take this random sequence and make it our private key. That would work indeed but it has several practical disadvantages when it comes to its backup and restoration
- A random bit sequence is very alien to human beings: very difficult to remember and even if remembered it very error-prone to recovery
- Whenever we want to generate a new private key – and eventually its associated public key – we’d be increasing the backup and restore difficulty: we would need to remember an additional bit sequence and make sure that we don’t make mistakes recovering it
BIP-0039 has defined a way to map the random bit sequence to something closer to human beings, that would allow us easier and less error-prone private key backup and restoration. The method consists on mapping chunks of the random sequence to mnemonic words. And then from these words through a deterministic process into a private key.
The rationale behind this process is that mnemonic words (such as “restore” or example) are easier to remember than bit sequences (such as “01110010110”). This would ease up the backup and restore of the keys as we people we would just need to remember a list of words instead of a succession of bits.
Let me make a comment here: top-of-the range key managers have got sophisticated ways to store, backup and restore keys. But these systems costs range in the tenths of thousands of Euros/dollars as of 2017, and are intended for enterprise usage. So before to fall upon me saying “there are better ways to backup and restore keys”, let me tell you that yes, I agree. However, the beauty of BIP-0039 is that it is a simple way that fits very well the use case of an individual taking care of his very few private keys with a 100 Euros device and a bout of paper and a pen.
Having said that let’s look on how BIP-0039 describes the mnemonic words generation
- The initial sequence of random bits is hashed with SHA256. The following picture shows the process
- Why do we hash our random sequence? Well, it has two purposes
- Hashing and storing the hash or part of it serves as error control mechanism. If, by mistake, we change one of the bits of our random sequence, the hash will change completely, and we will be more likely to detect the change in the hash than in the random sequence itself, as a single bit change in the random sequence – difficult to sport – would result in a complete change in the hash – immediate to spot -.
- In our case – BIP 0039 – we will be using as well the last part of the hash and we will be appending it to our original random sequence as part of the process to generate our mnemonic words.
- Then we will have an extended random bit sequence, by concatenating our original Random Sequence to the last part of the SHA256 hash, that we will call the “checksum”. We will calculate the length of the checksum so that the extended bit sequence is a multiple of 11.
- That extended bit sequence will be divided then in an integer 11-bit chunks
- and these chunks will be mapped to a dictionary of mnemonic words. Since each chunk has 11 bits, we will have 211 possibilities, so we will need a dictionary of 2048 words (since 211 = 2048)
|Random Sequence Length in Bits (RSLB)||Last part of the hash that will be used as random sequence checksum (CHKS)||Total length of mnemonic generator||Amount of 11-bit words|
|RSLB||CHKS = RS / 32||RSLB + CHKS||(RSLB+CHKS)/11|
- You can see in the table above that the length of the checksum depends on the length of the random sequence and that it is calculated to make sure that the extended random sequence (random sequence concatenated with checksum) is an exact multiple of 11.
- The final step would be to map these 11-bit chunks to a 2048-large word dictionary. In other words (pun not intended), we would have a table with correspondence between the 2048 possible combination of 11 bits and 2048 prechosen words
- There exist sets of 2048 words for several languages – see [iii] -.
Private Key Generation
We are now ready to choose our private key. What should it be?
We could very well use our original 256 random sequence. The mnemonic word generation would simple be a human-readable way to encode it, easier for us people to remember and store offline
This approach works great if we plan to have a single private key. Or if we are ready to go through all the same process – and generate another set of 24 words – whenever we need a new private/public key pair. This way we would have total independence between our different private keys, although it would require us to store a set of 24 word for every private key. The bitcoin wallets that work this way are called “non-deterministic wallets” because given one private key, there is no way to obtain other private keys, as there is no deterministic method to derive one key from the others: all private keys are obtained through independent application of freshly generated entropy with a DBRG.
However, in current bitcoin wallets the community prefers and has standardized an alternative approach more practical for the everyday work which can be summarized as follows:
- Use BIP-0039 method to obtain an extended random sequence
- Choose a mnemonic sentence (a bunch of words in the fashion of a password)
- Combine that extended random sequence with the mnemonic sentence through the PBKDF2 function. The iteration count is set to 2048 and HMAC-SHA512 is used as the pseudo-random function. If this sounds like Klingon to you, then I’ve gone too far but you can still check the details at [iv]. But at least let me say that PBKDF2 is an algorithm that
- takes our extended random sequence and the “mnemonic” text as inputs
- runs these inputs through a pseudorandom function (HMAC-SHA512 in our case) that is very difficult to reverse. That function is executed a large number of times (2048 in our case)
- as a result of that process produces a random value that has a strong resistance to brute force attacks
- The result of this combination in our case is a 512-bit sequence.
This 512-bit sequence is what the BIP-0039 calls the “seed” and it is then simply splitted into two parts
- A 256-bit string that we will finally call our “initial private key”
- A second 256-bit string that we will call our “initial chain code”
Why do we want to obtain 512 bits instead of 256? After all, private keys in bitcoin are 256 bits long. Well the answer is that we want something more than just a private key. We want an initial private key from which, in a deterministic way, we can derive further private and public keys, in a hierarchical way. If we want more that a private key, we need to start with more than just a private key. That is the role of the chain code. But this will be the subject of another article.
This article was written by ignacio. You can contact him at firstname.lastname@example.org