Georgi Spasov from æternity’s Elixir team has penned a blog post about his experience in creating an AE wallet, written in Elixir.

Hello everyone!

My name is Georgi Spasov and I am an Elixir developer working for æternity. As one of the leads of the Elixir wallet project, I would like to share my experience and the insights I gained along the way.

Who is this post for?

As this blog post is a bit technical, and I’ll assume that you are already familiar with BIP-32 and you have previously already stumbled upon some problems when implementing the extended keys.

Let’s dive in!

When generating a wallet, one of the main features that it should have is the implementation of Hierarchical key pairs. In short — it must use the Bitcoin Improvement Proposal — BIP32. This is one of the most important and perhaps one of the most difficult features to implement correctly.

That is why I think it is a good idea to start off by implementing a Bitcoin wallet and get a feeling of how it is done. Then one can move forward by adapting it to a specific cryptocurrency.

Although this is a good starting point for future wallet implementations, do not expect a smooth process. I still stumbled upon some issues when generating the extended keys particularly — their children. That is why I thought that sharing my experience will be helpful for some of you and you may even learn from my mistakes.

Extended Keys

In the Bitcoin developer guide, extended keys are described as the key and chain code together, but there is actually more to them than that. In reality, the extended keys are a Base58 encoded version of serialized data that is concatenated in a specific order. This is it:

[ version ] + [ depth ] + [ parent fingerprint ] + [ index ] + [ chain code ] + [ serialized key ]

Version

The version is the 4 bytes (sometimes referred as ‘magic’ bytes) that indicate to the network that the key belongs to: testnet or mainnet (t or x), and the type of key it is (pub for public or prv for private). So in Bitcoin the version bytes are tprv / xprv for private keys and tpub / xpub for public keys.

Depth

The depth is the 1 byte that indicates how deep an xprv or xpub is in a path, starting from 0 of the master key, and incremented by one each time we derive one level/branch above the parent keys.

Parent Fingerprint

A parent’s fingerprint is the first 4 bytes of the hash160 of the compressed parent public key (a little further into this post I will explain what a compressed public key is). This means that if you are deriving xprv and xpub on the same path (for example “m/10”) they will have the same fingerprint, because they both have the same parent public key.

Index

The index is the number of the child key we are deriving. It is helpful to think of it as a leaf on a branch, where each leaf has a number and they are ordered from the start to the end of the branch. The range of the index can be from 0 to 4294967295 (or 2³²-1) where anything in the [0–2147483647] range follows non-hardened derivation, and indexes between [2147483648–4294967295] follow the hardened derivation. If you want to read more about the hardened derivation and why we need it, this is a good place to start.

Chain Code

Just use the key’s chain code, generated together with the key through the generation of the child.

Serialized Key

The serialized key can be either public or private, depending on what type of key you deriving from.

A normal public key looks like this:

04E15562229C322768D90A00B3803A4946328CA3B4943CBA7A27D37D26A066AC7CDC01F9E13136D4477D14F3E82593B9876D991E55C4A3B0D49AE9CD5AE0FBD1B0

It is a 65 bytes-long key, where the 0x04 byte prefix states that it is a normal public key. The next 32 bytes are on the “x” coordinate of the elliptic curve graph and the following 32 bytes are on the “y” coordinate.

To serialize the public key you need to compress it to a 33 byte version, where the prefix of the public key changes from 0x04 to 0x02 or 0x03 depending on whether the “y” point of the public key (on the elliptic curve graph) is an even or odd number. That is how you can differentiate a public key from its compressed version. This picture explains this serialization quite well:

The private key on the other hand is a bit different. Because the private key size is 32 bytes, it should be concatenated with 0x00 byte prefix. This is done so that the size of the private key is exactly 33 bytes, the same as the compressed public key.

From here on the extended private key will be represented as xprv and the extended public key as xpub.

A path is a couple of indexes separated by a forward slash “/”. An example of a path could look like this: m/0/13h/3, where the h stands for hardened and is an index that should be treated as i + 2147483648. In some places you might see it represented in hex number i + 0x80000000. Sometimes the “h” is notated as a single quotation mark “ ‘ “ instead, so 1’ == 1h, but for now I will stick with “h” for readability.

The first letter that we see in the showcased path tells us what type of key we are deriving. A small “m” means that we are deriving xprv and a big “M” that we are deriving xpub respectively.

Demo!

We are going to use “000102030405060708090a0b0c0d0e0f” as our seed. Looking at the path m/0/13h/3 again, it could be represented as m > a > b > c where the letters {a, b, c} are derived keys from their respected parent. For key “a” the parent is “m”, for “b” the parent is “a” and so forth. Since we already know that the number of each letter is representing the index of the child key, the fingerprint for each child is going to be derived from his corresponding parent key.

To derive the bitcoin private key on the mainnet, we are going to use the xprv prefix. To make this exact prefix happen, after the Base58 formatting, we must set the version to the hex value 0x0488ADE4. All of the following keys are going to use the same version value because all of them will be bitcoin private keys.

m:
[version] — 0488ADE4
[depth] — 00000000
[finger print] — 00000000
[child num] — 00000000
[chain code] — 873DFF81C02F525623FD1FE5167EAC3A55A049DE3D314BB42EE227FFED37D508
[serialized key] — 00E8F32E723DECF4051AEFAC8E2C93C9C5B214313817CDB01A1494B917C8436B35

a:
[version] — 0488ADE4
[depth] — 00000001
[finger print] — 3442193E
[child num] — 00000000
[chain code] — D323F1BE5AF39A2D2F08F5E8F664633849653DBE329802E9847CFC85F8D7B52A
[serialized key] — 004E2CDCF2F14E802810E878CF9E6411FC4E712EDF19A06BCFCC5D5572E489A3B7

b:
[version] — 0488ADE4
[depth] — 000000002
[finger print] — 9CC81B61
[child num] — 8000000D -> (13+2147483648)
[chain code] — 6FF0F23F3DC1E8A4275BE467939F55C9D12C7C307BF149F4046945DBF5EF6B39
[serialized key] — 000F0C43E84C328DDEF64AD15D379D6313B1AE74F7CAB63251FB0CA0753108599E

c:
[version] — 0488ADE4
[depth] — 00000003
[finger print] -93C37678
[child num] — 00000003
[chain code] — 3824503ACED2ABE547E6B5A7C2AA4587B7A15DD9FFD5A0C1086BD2AC2A2997FB
[serialized key] — 00135C785452F0E3153B67874B95F2148E0996697E5FAE544AA7B7DD0587D46206

But how do we create the child key and chain code? I found the instructions were a bit unclear in this section of the BIP-32.

For the private key what we need to do is add the decimal version of the IL (you find this from the derivation process explained in the BIP) to the decimal version of the parent private key. From there take the result and make a modular operation using the number ’n’ which is equal to:

(FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141)

We are not finished yet. In order to make the structure of key ‘c’ look like this:

xprv9ykQk99RM1ihJkrSMmfn28SEZiF79geaDvMHGJz6b2zmSvzdmWmru2ScVujbbkJ9kVUrVNNhER5373sZSUcfJYhNSGyg64VB9jm5aP9oAga

We must go one step further.

First, we must add a checksum to the end of the already built structure. You need to get only the first 4 bytes of the double hash (SHA-256) of the concatenated structure above. Then simply concatenate the bytes to the end of the structure and format the whole result to Base58 and you are done.

To get the corresponding public child key is quite easy at this point. You need only to change 3 elements of the structure. First, you need to derive the public key using the last child private key. In our example, this means to derive the public key using the private key of ‘c’. Compress it, replace it, then change the version, because we want it to be xpub not xprv, so instead of 0x0488ADE4 you will use 0x488B21E. Finally, take this new structure, find its checksum, add it to the end and format the whole thing in Base58.

The structure will look like this:

[version] — 0488B21E
[depth] — 00000003
[finger print] -93C37678
[child num] — 00000003
[chain code] — 3824503ACED2ABE547E6B5A7C2AA4587B7A15DD9FFD5A0C1086BD2AC2A2997FB
[serialized key] — 03138BD7C05C021FCBE7DB7EE1D75BFD06D00320CCA405A802937F28C2FD24BB62

And the encoded result is this:

xpub6Cjm9egKBPGzXEvuToCnPGNy7k5bZ9NRb9Gt4hPi9NXkKjKnK467Spm6MCiBwmudbYVfEyhG4LwXLxfNBcheRwMgRe2wQA5ce1jBHwV7isR

Bear in mind that all of the elements in the structure, as well as the checksum, should be kept in binary format. In the Demo I’ve used the hex values only for readability purposes. I experienced a problem when I got to the point of making the derivation of a child public key from a parent public key. This is where you need implementation of the Elliptic curve point addition, which turned out to be quite the hassle. I still haven’t managed to implement it myself. That’s why for now I’m using the C implementation done by Bitcoin itself. Perhaps most people won’t need to make their own implementation, as it has been already done in several languages. Basically, what you need to do is follow the explanation in the BIP-32 document and when you get to the point of adding the two points, use the elliptic curve point addition functionality to do so.

I hope reading this post has helped you get a deeper understanding, in how extended keys are created. If you want to checkout æternity’s Elixir wallet implementation, follow our repo at GitHub.

Thank you for reading!

Interested in æternity? Get in touch:

GitHub | Reddit | Telegram | Twitter | Facebook | Mail