Key Derivation in Bitcoin Wallets as defined in BIP-0032

What is key derivation and why would we need it?

Public Key Cryptography refresh

It is assumed that the reader is somehow familiar with Asymmetric Key Cryptography: that is, the body of knowledge that deals with encryption algorithms that use pairs of values (called asymmetric keys) to encrypt and decrypt content. For a refresh on the subject, please check [i]

In any case, let us start with a quick reminder: Bitcoin and its blockchain has got is technical foundations rooted – amongst other mathematical principles and techniques – in cryptography, the art of hiding information from unauthorized disclosure using mathematical algorithms and small pieces of information that we call keys. The combination of the algorithm and the key is what protects the confidential data by making it unusable in its transformed form, by encrypting it.

More specifically, in asymmetric key cryptography we work with pairs of two different keys that are related to each other and that work together. Keys are generated in pairs and are specific to each other. What one key does encrypt using one algorithm, only the other key is able to decrypt using the same algorithm. And vice versa. Then we proceed to keep one of the keys secret – we call it the private key – while the other we make it available publicly – the public key -.

After this quick refresh, what usage do we give in bitcoin to asymmetric cryptography? In Bitcoin world, we use our public key to receive bitcoins. They are – sort of – the destination address where the bitcoins are sent. We use our private key to prove that we are the owners of the public key were the bitcoins were sent.

How does this work? Well, we first generate our private key. Then its corresponding public key is obtained from the private key through a mathematical process based on Elliptic Curve mathematics. The mathematical process ensures that it is practically impossible to guess the private key from the public key. So, if we keep the private key secret, we will be the only ones that are able to decrypt what the public key encrypts because

Nobody else knows our private key
Nobody can deduce our private key from our public key.
What our public key encrypts, only our private key can decrypt.

This way we can implement a “proof of ownership” as follows:

When someone sends bitcoins, they link them to a specific public key and to a message that is encrypted by that specific public key
Remember the keys in bitcoin are always generated in pairs, first the private and then from the private key we obtain the public key. Only the owner of the correspondent private key knows the private key. And it is nearly impossible to guess the private key from the public key. Hence only the person who first created the private and public key will know the private key and then will be the only one able to use it to decrypt that message.
By decrypting the message, the bitcoin core nodes recognize you as the owner of the public key and allow you to claim the bitcoins that were sent to the public key / public key associated message.
As the recognized owner of the bitcoins eventually you can do something with them such as send them to someone else. Well to be more precise we would be sending them to someone else’s public key and link them to a message encrypted by that public key.

In summary, to receive and send Bitcoins and register these transactions on the blockchain, we need just two “related-to-each-other keys”, one public (to receive bitcoins) and one private (to prove we own the received bitcoins). And that would be it.

The need for key derivation

However, it is usually more practical to have several pairs of private/public keys. We might want to have more than 1 destination address for receiving bitcoins. It would be like having several bank accounts, where we would be using different addresses for different purposes.

We could generate different pairs of private/public keys independently and use each pair for different purposes. For example, to deal with different providers, or with different customers.
- One downside of this approach would be that the management of these key pairs can become unpractical as the number of key pairs increases. We would need to back up our private keys individually (remember our privatekeys.org mantra: “Your keys, your bitcoins, not your keys, not your bitcoin”) and maintain a registry of where did we put the backed up private keys, make sure they can be restored, etc.
- On the positive side, if the private keys are generated independently, there is no relationship between them, and if one of the private keys is compromised, and the funds it controls are at danger, our other private keys are not at risk. This is because the private keys are not related in any way and exfiltration of a private key does not represent a danger for the exfiltration of the other (unrelated) private keys
Or we could generate an initial pair of private/public keys and have every other private/public key pairs derived from the original pair through mathematical processes. This, you have guessed, is more practical from the operations point of view, but we must make sure that we keep sufficient barriers between derived and original keys, in order to prevent that a single exfiltration of a private could cause a massive exfiltration our private keys.
A method for doing so is described in BIP-0032 [ii] and the purpose of this article is to explain how this key derivation is done.

Cryptography Nomenclature for this article

Before we start diving into dissecting BIP-0032, let me first talk about what abbreviations and variable names I am going to use in this article. I need to talk about this because it is unfortunate that “Private” and “Public” words both start with the same letter: letter P. Hence when we try to put in formulas a variable that represents of our keys and the different relationships between private and public keys such as how ones are derived or related to the others, we face the problem of choosing a variable name that represents them unambiguously.

In other words, how do we shorten “Public Key”? With an uppercase “P”? With an uppercase “K”? If so, what about “Private Key”? With a lowercase “p”? With a lowercase “k”? Unfortunately, these options, although very common, are poor choices, as uppercase and lowercase versions of the same letter may have got different size but they have a very similar shape. When reading formulas, it is sometimes difficult to tell if we are talking about a private key or a public key, since it may be too ambiguous to be able to distinguish between uppercase “K” and lowercase “k” at first sight.

Having that in mind, in this blog entry I have decided to name private keys with an “S” as in Secret. Public keys will go with a “P”. Our chain code – see my previous article “Private Key Generation in Bitcoin as defined in BIP-0039” [iii] – will go with a “C”. For completeness

S₀ represents our initial Private Key. The “0” represents “level 0”, or the root private key.
C₀ represents our initial Chain code. The “0” represents “level 0”, or the root chain code
P₀ represents our initial Public Key, level 0, derived from S₀ through the application of the Elliptic Curve point multiplication used in Bitcoin – see next point -.
EC[S₀] represents the application of the EC point multiplication (repeated application of the EC group operation) of the secp256k1 (see [iv]) base point with the integer S₀. This technique is used in Bitcoin to derivate the corresponding public key from the private key. For example EC[S₀]=P₀ means that we have applied the Elliptic Curve function to our initial private key S₀ (that is: we have applied the EC group operation to the sec256k1 origin point a total amount of S₀ times) and we have then obtained our initial public key P₀. For more details about the Elliptic Curve point multiplication and the origin point please check [v]
In deterministic hierarchical wallets, all other keys will be derived from S₀ and C₀ in a way or another.
N is the primer number used in secp256k1. It is equal to 2²⁵⁶ – 2³² – 2⁹ – 2⁸ – 2⁷ – 2⁶ – 2⁴ – 1. The coordinates of points that belong to the secp256p1 elliptic curve are defined over the field Z_N so they cannot be bigger than this number. Bitcoin uses it as a high limit for valid private keys. If by a small chance we randomly generate a private key bigger than N, it gets discarded and a new one gets generated. The probability of such occurrence is small as N is “almost” as large as 2²⁵⁶-1 (256 bits all set to 1). To visualize the difference, please consider both numbers written in hexadecimal
- 2²⁵⁶ = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFFFF
- N = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

Private Key Derivation: Hardened vs. Non-Hardened

Now let’s see how BIP-0032 describes two ways to derive first level private keys from level-0 private key S₀, chain block C₀ and public key P₀.

We can derive our first level private key using our zero-level private key S₀ and zero level chain code C₀. That means we would not be using our zero level Public key P₀ to obtain a derived private key. We will call this method “Hardened Secret Key Derivation” or HSKD for short and we will describe how it works later in this article. HSKD first level private keys will be named S’₁.
Or we could derive our first level Private key using a combination of our zero-level private key S₀, our zero-level chain block C₀ and our zero-level public key P₀. We will call this method “Non-Hardened Secret Key Derivation” or NSKD for short and we will describe how it works later in this article as well. NSKD first level private keys will be named S₁.
As you can see we use the “ ’ ” to distinguish between HSKD keys and NSKD keys.

Multiple Key Derivation

Also in deterministic hierarchical wallets, it has been considered that we can derive multiple times the initial private key. All these derived keys will be located at level 1. To obtain multiple level-1 derived keys we will use a 32-bit integer in our calculations (a 32-bit integer is a number between 0 and 2³² -1, a number rather large). We will use this number into the mathematical process involved in the derivation, in a fashion that we can use the same S₀ and C₀ , and by changing this number we will be changing the resulting key.

We will call that integer “i” and it has been stated in BIP-0032 that.

For NSDK keys we will use values of “i” between 0 and 2³¹-1
For HSDK keys we will use values of “i” between 2³¹ and 2³² – 1.

To distinguish between these multiple level-1 keys we will use an additional sub index. Hence S’_1,0 would be the first HSKD derived level-1 private key. And S’_1,m would be our m+1 HSKD derived level-1 key.

As you can see for the first HSDK key m= 2³¹ = 2147483648 and in that case our first level-1 HSDK would be written S_1, _2147483648. Well, this is impractical. So, let’s say that for both HSDK and NSDK our index “m” goes from 0 to 2³¹-1 (that is a 31-bit number).

For NSDK, the integer “i” that is used in the calculations equals “m”.
But for HSDK the integer “i” that is used in the calculations equals 2³¹ + “m”

Or in other words,

If the variable that represents the key has not got the “ ’ ”, then the integer “i” that was used to obtain equals the variable index “m”
if the variable that represents the key has got the “ ’ ”, then the integer “i” that was used to obtain it is the result of adding 2³¹ to the variable index “m”

Original Private Key	Key Derivation Method	Integer Value “i”	Index Value “m”	Derived Private Key
S₀	NSDK	0	0	S_1,0
S₀	NSDK	1	1	S_1,1
S₀	NSDK	2	2	S_1,2
…	…	…
S₀	NSDK	2³¹ – 1 (=2147483647)	2³¹ – 1 (=2147483647)	S_1,2147483647
S₀	HSDK	2³¹ (=2147483648)	0	S’_1,0
S₀	HSDK	2³¹ +1 (=2147483649)	1	S’_1,1
S₀	HSDK	2³¹ +2 (=2147483650)	2	S’_1,2
…	…	…	…	…

As you can see, we simplify the nomenclature of the first HSDK keys and we resolve the ambiguity for the index value “m” by adding a “ ‘ “ to the variable name, that indicates us if “i” = “m” or if “i” = 2³¹ + “m”

Now that we have got all the names clarified, what is the logic that allows us to derive a 1-level key from a 0-level key? Let us see what are the options

Hardened Private Key Derivation (HSKD)

The process is as follows

We take S₀, C₀ and i, and apply them to a HMAC-SHA512 (more info here [vi] and here [vii] ) function as follows
- We concatenate S₀ and i and use them as “Data” on the HMAC-SHA512 algorithm
- We use C₀ as “Key” on the HMAC-SHA512 algorithm
As a result of that process we obtain a 512-bit string that we will divide into two 256-bit parts. The left part will be notated I_L and the right part will be notated I_R
- We will make the addition modulo N of the left part I_L and the original private key S₀. The result will be our newly HSDK derived level-1 private key, called S’_1,m
- Our right part I_R will be our level-1 chain code C’_1,m

Obtaining the Hardened Public Key (HS2P)

When it comes to obtain level-1 public keys of the corresponding HSDK derived level-1 private key we use that level 1 private key S’_1,mand apply the Elliptic Curve group function to it to obtain its corresponding public key P’_1,m by applying EC[S’_1,m]= P’_1,m. We call this process Hardened Secret Key to Public Key Calculation or HS2P.

Non-Hardened Private Key Derivation (NSKD)

The process is as follows

We apply the Elliptic Curve point multiplication (repeated application of the EC group operation) of the secp256k1 base point with the integer S₀. In other words, we obtain our level-0 public key P₀ from our level-0 private key S₀.
We take P₀, C₀ and i, and apply them to a HMAC-SHA512 function as follows
- We concatenate P₀ and i and use them as “Data” on the HMAC-SHA512 algorithm
- We use C₀ as “Key” on the HMAC-SHA512 algorithm
As a result of that process we obtain a 512-bit string that we will divide into two 256-bit parts. The left part will be notated I_L and the right part will be notated I_R
- We will make the addition modulo N of the left part I_L and the original private key S₀. The result will be our newly HSDK derived level-1 private key, called S_1,m
- Our right part I_R will be our level-1 chain code C_1,m

Obtaining the Non-Hardened Public Key (NS2P)

When it comes to obtain level-1 public keys of the corresponding NSDK derived level-1 private key, we can use the NSKD level-1 private key S_1,mand apply the Elliptic Curve group function to it to obtain its corresponding public key P_1,m by applying EC[S_1,m]= P_1,m. We call this process Non-Hardened Secret Key to public Key Calculation or NS2P

That would be all, right? Well, no. BIP-0032 defines a very interesting alternative, let’s look into it

Non-Hardened Public Key Derivation (NPKD)

Yes, we can use Non-Hardened key derivation to obtain … another public key. Remember that for non-hardened key derivation we were using the level-0 public key as input. Well, why would we want to derive a level-1 public key directly from a level-0 public key without involving a level-0 private key in the process?

The answer is that level-0 public keys are, well, public. There is nothing secret in them. If we combine P₀ with C₀ and the index i, we could obtain level-1 public keys without involving the private key S₀. That is a good feature for less secure environments, where we cannot or don’t want to use and store the level-0 private key S₀. Say for example online-shopping web servers that would be creating a new public key (a.k.a. a new bitcoin address where we receive the payments) for every new customer, without the hassle to handle the level-0 private key S₀ every time.

The process is as follows

We apply the Elliptic Curve point multiplication (repeated application of the EC group operation) of the secp256k1 base point with the integer S₀. In other words, we obtain our level-0 public key P₀ from our level-0 private key S₀.
We take P₀, C₀ and i and apply them to HMAC-SHA512 function as follows
- We concatenate P₀ and i and use them as “Data” on the HMAC-SHA512 algorithm
- We use C₀ as “Key” on the HMAC-SHA512 algorithm
As a result of that process we obtain a 512-bit string that we will divide into two 256-bit parts. The left part will be notated I_L and the right part will be notated I_R
- We take I_L and apply the Elliptic Curve point multiplication (repeated application of the EC group operation) of the secp256k1 base point with the integer I_L. As if we were obtaining our level-1 public key P₁ from I_L. We will call this PRE_1,m as it is a previous step before obtaining the level-1 public key
- We will make the addition modulo N of PRE_1,m and the original public key P₀. The result will be our newly NPDK derived level-1 private key, called P_1,m
- Our right part I_R will be our level-1 chain code C_1,m

The question that remains to be answered is as follows: where is the corresponding level-1 private key S_1,m? Remember we will need that private key to claim the bitcoins that are going to be sent to our newly NPKD public key. And we cannot derive it from its corresponding newly NPKD derived public key P_1,m.

In fact, the question can be formulated differently: is this NPKD P_1,m key the same as the one we would obtain by applying Elliptic Curve to the NSKD level-1 S_1,m private key? If so, then our problem is solved, because if we have two methods that produce the same public key (either NSKD plus Elliptic curve of the result, or NPKD), then the corresponding private keys are the same too, because there is a 1-to-1 relationship between private and public keys (the Elliptic Curve group function takes care of that).

I so, we could use NPKD to derive level-1 public keys P_1,m from level-0 public key P₀, without involving the level-0 private key S₀, in a non-secured web server for example. And when we need the corresponding level-1 private key S_1,m (to claim the bitcoins that we have been sent to P_1,m), then we apply NSKD to derive and find our corresponding private key S_1,m from S₀ and P₀

Well, the good news is that

whether we use NSKD + EC to calculate P_1,m
or that we use NPKD to calculate P_1,m,

the resulting P_1,m is the same. Let me show you.

Non-Hardened Private or Public Key Derivation?

Let’s start with NSKD. We are applying NSKD to a level-0 private key and we are obtaining a level-1 private key. Then we can apply Elliptic Curve group function to that level-1 private key and we would obtain the corresponding lelvel-1 public key. Graphically is as follows.

And in formulae, NSKD would be first calculating HMAC-512 of P₀, C₀ and i, taking the left part and adding it modulo N to S₀, to obtain S_1,m.

S_1,m = HMAC_L (P₀,C₀,i) + S₀

Then, we apply Elliptic Curve group function to S_1,m and obtain P_1,m

P_1,m = EC [ HMAC_L (P₀,C₀,i) + S₀ ]

Let’s look at NPKD now. We are applying Elliptic Curve Group function to a level-0 private key and we are obtaining a level-0 public key. We are then applying NPDK to our 0-level public key and we obtain our level-1 public key.

And in formulae we would be applying Elliptic Curve group function to S₀ and we would be obtaining P₀.

P₀ = EC [ S₀ ]

Then we apply NPKD to that result, that is we use our P₀ key in HMAC-512 together with C₀ and i, take the left part, we apply Elliptic Curve to that left part and finally we add it to P₀

P_1,m = EC [ HMAC_L (P₀,C₀,i) ] + P₀ = EC [ HMAC_L (P₀,C₀,i) ] + EC [ P₀]

Are these two level-1 public keys the same P_1,m? In the first case, we first do key derivation and then we do Elliptic Curve to obtain P_1,m. In the second case, we first do elliptic curve and then we us (a slightly different) key derivation to obtain P_1,m. So let me insist, are they the same?

If we replace HMAC_L (P₀,C₀,i) by letter “A”, and S₀ by letter “B”, then our first key

P_1,m = EC [ HMAC_L (P₀,C₀,i) + S₀ ] = EC [ A + B ]

Our second key

P_1,m = EC [ HMAC_L (P₀,C₀,i) ] + EC [ P₀] = EC [ A ] + EC [ B ]

So, is EC [ A + B ] equal to EC [ A ] + EC [ B ] ? The question resrts to: Is the Elliptic Curve point multiplication associative? Don’t forget to ask that to the next mathematician you cross on the street. Otherwise you can go check it for yourself at, for example, here [viii] (Hint: the answer is Yes).

Security Consideration for Non-Hardened Key Derivation (NSKD and NPKD)

NPKD is very practical way of securely deriving level-1 public keys from level-0 public keys. But it must be accompanied with NSKD, that is, from deriving our level-1 private keys from our level-0 public keys. And deriving private keys from public keys is considered bad security practice by some cryptography professionals. Let’s look at the NSKD diagram once again and let’s see why

Modulo N addition is a reversible operation. If you know the result (S_1,m) and one of the operands you can obtain the other operand. So if you know S_1,m and C₀, they you can calculate S₀. So, we see that a good part of the secrecy of the private keys resides as well on the secrecy of the chain code. If someone happens to know C₀, then he can calculate all the I_R and I_L iterations, as P₀ and i are public and known. All children chain codes would be exfiltrated as well. If by some unfortunate mistake one of the S_1,m is exfiltrated too, then S₀ could be calculated. Disaster ensues. Exfiltration of S_1,m (or any child private keys) should not put S₀ (father private keys) at risk under any circumstances. Purists would say that exfiltration of a private key should not put at risk any other private key. This is not the case of NSKD and that’s why seasoned cryptography architects frown upon Non-Hardened key derivation.