BIP 32: Hierarchical Deterministic Wallets

Once upon a time, people using Bitcoin had to generate brand new private key for every new Bitcoin address. And remember all the private keys they generated. It was inconvenient and dangerous. Then in 2012, hierarchical deterministic wallets described in BIP 32 came to save the mankind. Now one has to remember only one value, the seed, and everything else can be calculated from it. This article attempts to bring understanding how BIP 32 functions by implementing it.

The article is part of BIP by BIP series. The complete Haskell code is located in fossil repository that can be viewed online or obtained locally by following these steps. You need to have cabal and GHC installed for it:

fossil clone https://jirijakes.com/code/bip-by-bip
cd bip-by-bip
ls src/BipByBip/Bip32.hs
cabal run bip32-test

Cryptography Link to heading

Throughout the implementation, we will need a few basic cryptographic functions. Let us delegate them all to cryptonite library.

-- | Calculates HMAC-SHA512 for secret key and message.
hmacSha512 :: BS.ByteString -> BS.ByteString -> HMAC SHA512
hmacSha512 = hmac

-- | Calculates SHA256(SHA256(.)) of the message.
doubleSha256 :: (ByteArrayAccess a) => a -> Digest SHA256
doubleSha256 = sha256 . sha256

-- | Calculates SHA256(.) of the message,
sha256 :: (ByteArrayAccess a) => a -> Digest SHA256
sha256 = hash

-- | Calculates RIPEMD160(SHA256(.)) of the message.
hash160 :: (ByteArrayAccess a) => a -> Digest RIPEMD160
hash160 = hash . sha256

Data types Link to heading

At the end of this endeavor, we want to have a data type representing an extended key and some operations on it. But first we will need a few basic building blocks. Specification of the serialization format will help us understand what types we have to define:

Serialization format

Extended public and private keys are serialized as follows:

4 bytes

version bytes (mainnet: 0x0488B21E public, 0x0488ADE4 private; testnet: 0x043587CF public, 0x04358394 private)

1 byte

depth: 0x00 for master nodes, 0x01 for level-1 derived keys, ….

4 bytes

the fingerprint of the parent’s key (0x00000000 if master key)

4 bytes

child number. This is ser₃₂(i) for i in x_i = x_par/i, with x_i the key being serialized. (0x00000000 if master key)

32 bytes

the chain code

33 bytes

the public key or private key data (ser_P(K) for public keys, 0x00 || ser₂₅₆(k) for private keys)

Version bytes Link to heading

Version bytes specify network on which the key was generated and whether the key is private or public.

4 byte: version bytes (mainnet: 0x0488B21E public, 0x0488ADE4 private; testnet: 0x043587CF public, 0x04358394 private)

We also know that the values were not chosen randomly:

Because of the choice of the version bytes, the Base58 representation will start with “xprv” or “xpub” on mainnet, “tprv” or “tpub” on testnet.

Thanks to this choice, when having a Base58-encoded form of an extended key, it is easy to determine network and whether it is private or public key.

We will make our lives a bit simpler by only considering mainnet in this text. We can reuse Haskell’s Word32 type and also its Binary instance. This will be later needed for serialization of our extended keys:

-- | Version bytes.
newtype Version = Version Word32 deriving (Binary, Eq, Show)

versionXprv, versionXpub :: Version
versionXprv = Version 0x0488ADE4
versionXpub = Version 0x0488B21E

Depth Link to heading

The type depth indicates the level of derivation, with master node having depth equal to zero and each child derived from a previous one having depth increased by one. Depth is one byte long and can be represented by Word8. Default value, i. e. the depth of master node, is 0.

1 byte — depth: 0x00 for master nodes, 0x01 for level-1 derived keys, ….

To serialize depth, we directly serialize the underlying one-byte value. The only operation we need to have on depth is to increase it by one, let’s call this function deeper. This particular implementation is a bit unsafe as it may overflow when called on depth 255. Here we rely on the fact that deriving to such a depth is not common. However, production-ready library should take care of this case.

-- | Level of derivation of an extended key. Master node has depth = 0,
-- each subsequent child has depth increased by one.
newtype Depth = Depth Word8 deriving (Binary, Default, Eq, Show)

-- | Increases depth by one level.
deeper :: Depth -> Depth
deeper (Depth d) = Depth (d + 1)

Key identifiers Link to heading

Extended keys can be identified by the Hash160 (RIPEMD160 after SHA256) of the serialized ECDSA public key K, ignoring the chain code. This corresponds exactly to the data used in traditional Bitcoin addresses. It is not advised to represent this data in base58 format though, as it may be interpreted as an address that way (and wallet software is not required to accept payment to the chain key itself).

Therefore, to obtain a key identifier from public key we have to serialize it and then apply SHA256 and RIPEMD160. We already have function hash160 that does exactly that.

-- | Identifier of public key.
newtype KeyId = KeyId BS.ByteString

-- | Returns identifier of the given public key.
keyId :: Secp.PubKey -> KeyId
keyId = KeyId . BA.convert . hash160 . Secp.exportPubKey True

We do not derive any class instances at the moment. KeyId is not going to be serialized and whether it should have some other instances depends on its future usage.

The function hash160 returns value of type Digest RIPEMD160, type coming from cryptographic library cryptonite. Digest a holds the digest in an opaque way but gives us access to the underlying bytes using a type class ByteArrayAccess from package memory. And the function BA.convert from the same package helps us convert these bytes into ByteString.

Fingerprint Link to heading

The first 32 bits of the [key] identifier are called the key fingerprint.

Note that the fingerprint of the parent only serves as a fast way to detect parent and child nodes in software, and software must be willing to deal with collisions. Internally, the full 160-bit identifier could be used.

We have two options how to represent these 32 bits (four bytes) in memory. We can either use Word32 type or ByteString. Word32 would certainly be more efficient but without revealing spoilers, it would be harder to manipulate than ByteString. Let us choose suboptimal ByteString for reasons that will be clear later. Perhaps Data.ByteString.Short would also be usable.

-- | Fingerprint of parent's key.
newtype Fingerprint = Fingerprint BS.ByteString deriving (Eq, Show)

Knowing that fingerprints always have four bytes, we can easily write a Binary instance. We cannot automatically derive Binary in this case because the default instance for ByteString serializes first the length of the data and then the data itself. We only need to serialize the four bytes and nothing else.

4 bytes: the fingerprint of the parent’s key (0x00000000 if master key)

instance Binary Fingerprint where
  put (Fingerprint bs) = putByteString bs
  get = Fingerprint <$> getByteString 4

And while we are at it, let us also create a Default instance for Fingerprint, which will represent fingerprints of master keys, i. e. 0x00000000:

instance Default Fingerprint where
  def = Fingerprint $ BS.pack [0, 0, 0, 0]

We can generate fingerprint by providing either KeyId or public key directly. Later it will be more convenient to get fingerprint of a public key rather than key identifier, therefore:

-- | Returns fingerprint of the given public key.
fingerprint :: Secp.PubKey -> Fingerprint
fingerprint pub = let KeyId k = keyId pub in Fingerprint $ BS.take 4 k

Child number Link to heading

4 bytes: child number. This is ser₃₂(i) for i in x_i = x_par/i, with x_i the key being serialized. (0x00000000 if master key)

Each extended key has 2³¹ normal child keys, and 2³¹ hardened child keys. Each of these child keys has an index. The normal child keys use indices 0 through 2³¹-1. The hardened child keys use indices 2³¹ through 2³²-1. To ease notation for hardened key indices, a number i_H represents i+2³¹.

This description can be hard to follow at this point. Later we will write a function for deriving child extended keys from a given extended key. Each derived child will be identified by a number called child number. Those are four-byte numbers. Half of the child numbers, numbered 0 to 2³¹−1 (or 0x00000000 to 0x7FFFFFFF), are called normal while the rest, numbered 2³¹ to 2³²−1 (0x80000000 to 0xFFFFFFFF), are called hardened.

Child numbers are important, human-facing values. To increase readability when used in text, hardened child numbers are written in form i_H or i’, which both mean i+2³¹. Therefore, in order to convert a hardened child number into this compact notation, we have to subtract 2³¹ or 0x80000000.

-- | Child number, either normal or hardened.
data ChildNumber = Normal Word32 | Hardened Word32 deriving (Show, Eq)

Although the distinction between normal and hardened child numbers on the level of data type is not strictly necessary, it will make our lives a bit easier when we start deriving children.

We will also need to construct values of this new type. Again, these implementations are not perfectly safe as they would allow to construct child numbers with values greater than 2³¹−1. But they are sufficient for our purpose.

-- | Creates hardened child number.
hardened :: Word32 -> ChildNumber
hardened = Hardened

-- | Creates non-hardened child number.
normal :: Word32 -> ChildNumber
normal = Normal

-- | Creates a child number from its absolute value.
childNumber :: Word32 -> ChildNumber
childNumber n | n >= 0x80000000 = Hardened $ n - 0x80000000
childNumber n = Normal n

Child numbers are serialized in their full form:

instance Binary ChildNumber where
  put (Normal w) = put w
  put (Hardened w) = put (0x80000000 + w)
  get = childNumber <$> get

Chain code Link to heading

Chain codes are 32-byte data that make private and public keys “extended”. They are important part of children derivation, as we will later see. But on the data type level, they are not more than 32 bytes of data:

-- | Chain code of an extended key.
newtype ChainCode = ChainCode BS.ByteString deriving (Eq, Show)

instance Binary ChainCode where
  put (ChainCode bs) = putByteString bs
  get = ChainCode <$> getByteString 32

Extended key Link to heading

Generic data type Link to heading

We have defined all the components required for extended keys. For the very last piece of data, the key itself, we will use directly data types from secp256k1-haskell library: Secp.SecKey and Secp.PubKey. Since the extended private key and extended public key differ only in the key part, let us define a data type for extended keys generic in the key:

-- | An extended key.
data Extended key = Extended
  { xVersion :: Version,
    xDepth :: Depth,
    xFingerprint :: Fingerprint,
    xChildNumber :: ChildNumber,
    xChainCode :: ChainCode,
    xKey :: key
  }
  deriving (Show, Eq)

Key serialization Link to heading

The important part here is that Secp.SecKey and Secp.PubKey do not have built-in instances of Binary. If we wanted to create them, we would have to introduce two newtypes wrapping the original types. That would probably bring some inconvenience.

Alternative approach is to introduce a new type class for types that represent a cryptographic key that can be serialized and deserialized using Binary:

-- | Class to mark types that represent a cryptographic key with an ability
-- to serialize and deserialize itself using `Binary`.
class Key k where
  getKey :: Get k
  putKey :: k -> Put

Serializing and deserializing public key does not have any restrictions, we only have to remember to operate on compressed form of the key:

• ser₂₅₆(p): serializes the integer p as a 32-byte sequence, most significant byte first.
• ser_P(P): serializes the coordinate pair P = (x,y) as a byte sequence using SEC1’s compressed form: (0x02 or 0x03) || ser₂₅₆(x), where the header byte depends on the parity of the omitted y coordinate.

and

• 33 bytes: the public key or private key data (ser_P(K) for public keys, 0x00 || ser₂₅₆(k) for private keys)

The secp256k1-haskell library can do this for us, let us use its functions. Not all 32-byte strings are valid public keys, deserialization should fail in such a case:

instance Key Secp.PubKey where
  getKey = getByteString 33 >>= maybe (fail "Not a pub key") return . Secp.importPubKey
  putKey = putByteString . Secp.exportPubKey True

Private is slightly more complicated. We have to prefix the key with 0x00 (so the length of both private and public keys are the same 33 bytes) and deserialization will require a few additional validity checks. Let’s start with serialization, which is straightforward:

instance Key Secp.SecKey where
  getKey = undefined
  putKey key = putWord8 0 >> putByteString (Secp.getSecKey key)

For deserialization, we have to validate that the key starts with 0x00 and:

• In case parse₂₅₆(I_L) ≥ n or k_i = 0, the resulting key is invalid, and one should proceed with the next value for i. (Note: this has probability lower than 1 in 2¹²⁷.)

The n is order of the curve secp256k1, as stated in specification (PDF) in section 2.4.1. Every Bitcoiner knows its value by heart: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141. Therefore, the deserialized key must not be 0 and must be less than n. Now we can finalize the instance:

instance Key Secp.SecKey where
  putKey key = putWord8 0 >> putByteString (Secp.getSecKey key)
  getKey = do
    w <- getWord8
    unless (w == 0) $ fail "Private key prefix is not 0"
    getByteString 32 >>= either fail return . parsePrivateKey

-- | Attempts to parse given bytes as private key.
parsePrivateKey :: BS.ByteString -> Either String Secp.SecKey
parsePrivateKey bs =
  if
    | bs == nullkey -> Left "Private key 0 is invalid"
    | bs >= nkey -> Left "Private key >= n is invalid"
    | otherwise -> maybe (Left "Not a secret key") Right . Secp.secKey $ bs
  where
    nullkey = BS.pack $ take 32 [0, 0 ..]
    nkey = BS.pack [0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0, 0x3b, 0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41, 0x41]

Extended key serialization Link to heading

We now have available all the tools for serialization and deserialization of extended keys. During deserialization we perform checks that verify that if depth = 0 then both parent fingerprint and child number are 0x00000000:

• 1 byte: depth: 0x00 for master nodes, 0x01 for level-1 derived keys, ….
• 4 bytes: the fingerprint of the parent’s key (0x00000000 if master key)
• 4 bytes: child number. This is ser₃₂(i) for i in x_i = x_par/i, with x_i the key being serialized. (0x00000000 if master key)

instance (Key key) => Binary (Extended key) where
  put (Extended v d f n c k) = put v >> put d >> put f >> put n >> put c >> putKey k
  get = do
    v <- get
    d <- get
    f <- get
    when (d == def && f /= def) $ fail "Zero depth with non-zero parent fingerprint"
    n <- get
    when (d == def && n /= def) $ fail "Zero depth with non-zero index"
    c <- get
    Extended v d f n c <$> getKey

Serialization and deserialization of the key is delegated to the instance of Key we created before. The def function obtain default values for the relevant data type: for Depth (d), Fingerprint (f) and ChildNumber (n). Text of BIP32 uses the term index interchangeably with child number.

Concrete data types Link to heading

To make life of users easier, we also define concrete data types for extended private key and extended public key. We can reuse everything we have defined so far:

-- | Extended private key.
newtype XPrv = XPrv (Extended Secp.SecKey) deriving (Binary, Eq, Show)

-- | Extended public key.
newtype XPub = XPub (Extended Secp.PubKey) deriving (Binary, Eq, Show)

Master key Link to heading

The total number of possible extended keypairs is almost 2⁵¹², but the produced keys are only 256 bits long, and offer about half of that in terms of security. Therefore, master keys are not generated directly, but instead from a potentially short seed value.

• Generate a seed byte sequence S of a chosen length (between 128 and 512 bits; 256 bits is advised) from a (P)RNG.
• Calculate I = HMAC-SHA512(Key = “Bitcoin seed”, Data = S)
• Split I into two 32-byte sequences, I_L and I_R.
• Use parse₂₅₆(I_L) as master secret key, and I_R as master chain code.

In case parse₂₅₆(I_L) is 0 or parse₂₅₆(I_L) ≥ n, the master key is invalid.

Next, these three points from section about serialization tell us what are some default values for master keys. Since we already defined default values for their data types (using type class Default), we can summon them by calling def.

• 1 byte: depth: 0x00 for master nodes, 0x01 for level-1 derived keys, ….
• 4 bytes: the fingerprint of the parent’s key (0x00000000 if master key)
• 4 bytes: child number. This is ser₃₂(i) for i in x_i = x_par/i, with x_i the key being serialized. (0x00000000 if master key)

We will not concern ourselves with random generation. The seed will be given. And once we have it, we perform HMAC-SHA512 and split the result into two halves, which will become new private key and new chain code. These two are enough to form new extended private key. The last line is the same check as during private key deserialization. Fortunately, we can reuse everything we have defined previously:

-- | Creates new master key for version bytes using given seed.
masterKey :: BS.ByteString -> Either String XPrv
masterKey seed =
  let hmac = BA.convert $ hmacSha512 (BC.pack "Bitcoin seed") seed
      (l, r) = BS.splitAt 32 hmac
   in XPrv . Extended versionXprv def def def (ChainCode r) <$> parsePrivateKey l

Having this function gives us the ability to generate new extended private key from a seed. Master key, then, allows us to derive virtually unlimited amount of other extended private keys and extended public keys in a deterministic fashion. That is the whole purpose of BIP32 – predictably and repeatedly generate new keys from a single short value.

Deriving children Link to heading

Now we have one extended private key, the master key, and we can use it to derive other private keys and later, after we can also create an extended public key, we can add derivation of public keys, too.

We represent an extended private key as (k, c), with k the normal private key, and c the chain code. An extended public key is represented as (K, c), with K = point(k) and c the chain code.

[…]

Child key derivation (CKD) functions

Given a parent extended key and an index i, it is possible to compute the corresponding child extended key. The algorithm to do so depends on whether the child is a hardened key or not (or, equivalently, whether i ≥ 2³¹), and whether we’re talking about private or public keys.

„Index” is what we call child number. Let us then create a first child key derivation function, one for extended private key.

Private key Link to heading

Private parent key → private child key

The function CKD_priv((k_par, c_par), i) → (k_i, c_i) computes a child extended private key from the parent extended private key:

• Check whether i ≥ 2³¹ (whether the child is a hardened key).
  • If so (hardened child): let I = HMAC-SHA512(Key = c_par, Data = 0x00 || ser₂₅₆(k_par) || ser₃₂(i)). (Note: The 0x00 pads the private key to make it 33 bytes long.)
  • If not (normal child): let I = HMAC-SHA512(Key = c_par, Data = ser_P(point(k_par)) || ser₃₂(i)).
• Split I into two 32-byte sequences, I_L and I_R.
• The returned child key k_i is parse₂₅₆(I_L) + k_par (mod n).
• The returned chain code c_i is I_R.
• In case parse₂₅₆(I_L) ≥ n or k_i = 0, the resulting key is invalid, and one should proceed with the next value for i. (Note: this has probability lower than 1 in 2¹²⁷.)

Inputs to this function are private key of parent, chain code of parent (in our case, these two will be represented by an extended key, i. e. XPrv and XPub types) and the number of the derived child. Output will be new extended private key. The derivation may fail. Let us first see the complete function:

 1deriveXPrv :: XPrv -> ChildNumber -> Maybe XPrv
 2deriveXPrv (XPrv (Extended {xChainCode = ChainCode c, ..})) i =
 3  let pub = Secp.derivePubKey xKey
 4      d = case i of
 5        Hardened _ -> encodeKey xKey
 6        Normal _ -> encodeKey pub
 7      hmac = hmacSha512 c (d <> BL.toStrict (encode i))
 8      (l, r) = BS.splitAt 32 $ BA.convert hmac
 9      parsed = either (const Nothing) (Just . Secp.getSecKey) $ parsePrivateKey l
10      tweaked = parsed >>= Secp.tweak >>= Secp.tweakAddSecKey xKey
11   in fmap
12        (XPrv . Extended xVersion (deeper xDepth) (fingerprint pub) i (ChainCode r))
13        tweaked

In the first step, lines 4–6, we need to prepare data for performing HMAC. The data are encoded private or public key, depending on whether the child number is hardened or not. With the data and key being the current chain code, we perform HMAC-SHA512(key, data). First half of the resulting 64 bytes will be next private key, second half next chain code (line 8). We have to verify that the next private key is valid (line 9). Before assembling new extended private key, we need to tweak its private key with previous private key. To tweak a private key means to add a 32-byte scalar (in our case created from previous private key) modulo n (n is order of the curve).

The new extended private key will have the same version bytes, depth one level higher and fingerprint of the previous public key.

Public key Link to heading

Public parent key → public child key

The function CKD_pub((K_par, c_par), i) → (K_i, c_i) computes a child extended public key from the parent extended public key. It is only defined for non-hardened child keys.

• Check whether i ≥ 2³¹ (whether the child is a hardened key).
  • If so (hardened child): return failure
  • If not (normal child): let I = HMAC-SHA512(Key = c_par, Data = ser_P(K_par) || ser₃₂(i)).
• Split I into two 32-byte sequences, I_L and I_R.
• The returned child key K_i is point(parse₂₅₆(I_L)) + K_par.
• The returned chain code c_i is I_R.
• In case parse₂₅₆(I_L) ≥ n or K_i is the point at infinity, the resulting key is invalid, and one should proceed with the next value for i.

In principle, derivation of public child key is not too different from the private one:

deriveXPub :: XPub -> ChildNumber -> Maybe XPub
deriveXPub (XPub (Extended {xChainCode = ChainCode c, ..})) i =
  case i of
    Hardened _ -> Nothing
    Normal _ ->
      let hmac = hmacSha512 c (encodeKey xKey <> BL.toStrict (encode i))
          (l, r) = BS.splitAt 32 $ BA.convert hmac
          parsed = Secp.exportPubKey True <$> Secp.importPubKey l
          tweaked = parsed >>= Secp.tweak >>= Secp.tweakAddPubKey xKey
       in fmap
            (XPub . Extended xVersion (deeper xDepth) (fingerprint xKey) i (ChainCode r))
            tweaked

It is not defined for hardened child keys. The value called parsed is first 32 bytes of hmac parsed as public key (to verify its validity), having then its binary representation extracted and used as tweak of the original public key (this operation is described as point(parse₂₅₆(I_L)) + K_par in the specification). The new extended public key is formed analogously to extended private key.

Type class for derivation Link to heading

Although having two separate functions for derivation – one for extended private key, another for extended public key – certainly works, I found it more convenient (the reason will become clear a bit later) to abstract child derivation into a type class. The name deriveChild1 says that we derive one child with the given number:

-- | Type class for types that can derive children of the same type.
class Derive a where
  -- | Derives new child key with the given number.
  deriveChild1 :: a -> ChildNumber -> Maybe a

instance Derive XPrv where
  deriveChild1 = deriveXPrv

instance Derive XPub where
  deriveChild1 = deriveXPub

Private to public Link to heading

BIP 32 specification also contains a subsection titled Private parent key → public child key:

The function N((k, c)) → (K, c) computes the extended public key corresponding to an extended private key (the “neutered” version, as it removes the ability to sign transactions).

• The returned key K is point(k).
• The returned chain code c is just the passed chain code.

To compute the public child key of a parent private key:

• N(CKD_priv((k_par, c_par), i)) (works always).
• CKD_pub(N(k_par, c_par), i) (works only for non-hardened child keys).

This tells us that if we want to derive a child extended public key from an extended private key, we should either first get public key from private key and then derive public key or first derive new private key and then get public key from it (which way to choose depends on our situation). In order to do that, we need to be able to get extended public key from an extended private key:

-- | Returns public extended key derived from private extended key.
xprvToXPub :: XPrv -> XPub
xprvToXPub (XPrv Extended {..}) =
  XPub
    ( Extended
        versionXpub
        xDepth
        xFingerprint
        xChildNumber
        xChainCode
        (Secp.derivePubKey xKey)
    )

This is simple, we only need to derive public key from inner private key and use the same chain code. Also, since our data type holds the version bytes, we need to change them into the public key version.

Encoding and decoding extended keys Link to heading

This 78 byte structure can be encoded like other Bitcoin data in Base58, by first adding 32 checksum bits (derived from the double SHA-256 checksum), and then converting to the Base58 representation. This results in a Base58-encoded string of up to 112 characters. Because of the choice of the version bytes, the Base58 representation will start with “xprv” or “xpub” on mainnet, “tprv” or “tpub” on testnet.

To Base58 Link to heading

-- | Returns Base58 checksummed reperesentation of a binary representation
-- of the given value.
toBase58 :: (Binary b) => b -> T.Text
toBase58 b =
  let payload = BL.toStrict $ encode b
      checksum = BA.convert $ BA.takeView (doubleSha256 payload) 4
   in T.pack $ BC.unpack $ encodeBase58 bitcoinAlphabet (payload <> checksum)

A checksum of Base58 representation is formed by first 32 bits (four bytes) of the binary data with SHA256 twice applied. To encode the binary data and its checksum, we use external library base58-bytestring. Perhaps in the future, we could also examine how that works.

This new function can be applied to both XPrv and XPub, they both have Binary instances.

From Base58 Link to heading

Decoding Base58 strings is a bit more complicated. Let’s start with defining a generic function that takes a string and attempts to decode it as Base58, including checksum verification. If the Base58 is correctly decoded, we can try to decode the result as binary representation of some type b. In order to do so, we need to make sure the b has an instance of Binary. It is a reverse of toBase58 with multiple checks added:

-- | Attempts to decode Base58 string using an instance if Binary.
decodeWithChecksum :: (Binary b) => T.Text -> Either String b
decodeWithChecksum t =
  case decodeBase58 bitcoinAlphabet (BC.pack $ T.unpack t) of
    Nothing -> Left "Could not decode input as Base58"
    Just bs ->
      case decodeOrFail (BL.fromStrict payload) of
        Left (_, _, err) -> Left err
        Right (_, _, value) ->
          if checksum /= BA.convert (BA.takeView (doubleSha256 payload) 4)
            then Left "Invalid checksum"
            else Right value
      where
        (payload, checksum) = BS.splitAt (BS.length bs - 4) bs

We could use this function directly to decode extended keys however we would like to first verify that the decoded extended key has correct version bytes. There may be multiple ways how to do it, I chose to write two separate functions that verify first four characters in the Base58-encoded string:

-- | Attempts to decode given string as Base58-encoded extened private key.
decodeXPrv :: T.Text -> Either String XPrv
decodeXPrv t =
  if T.take 4 t == T.pack "xprv"
    then decodeWithChecksum t
    else Left "Does not have prefix 'xprv'"

-- | Attempts to decode given string as Base58-encoded extened public key.
decodeXPub :: T.Text -> Either String XPub
decodeXPub t =
  if T.take 4 t == T.pack "xpub"
    then decodeWithChecksum t
    else Left "Does not have prefix 'xpub'"

The disadvantage of these two functions is that we need to have prior knowledge about which type of extended key is supposed be represented by the Base58 string. We can also have a convenient function that will try all options and will give us the one that first succeeds:

-- | Attempts to decode given string as Base58-encoded extended key.
fromBase58 :: T.Text -> Either String (Either XPrv XPub)
fromBase58 t = (Left <$> decodeXPrv t) <> (Right <$> decodeXPub t)

It is a rather rudimentary function, it will not provide too nice error messages. But it may be useful anyway.

Derivation path Link to heading

We can now derive a single child key of an extended key. However, more commonly we need to recursively derive multiple children from a master key. We could use the child derivation function repeatedly. Or we could write a few helpful types and functions to help us with it.

To shorten notation, we will write CKD_priv(CKD_priv(CKD_priv(m,3_H),2),5) as m/3_H/2/5. Equivalently for public keys, we write CKD_pub(CKD_pub(CKD_pub(M,3),2),5) as M/3/2/5.

Although BIP 32 does not specify it, this notation is often called derivation path. Letter M is a master key, letter H in subscript denotes a hardened child. In other, future BIPs, an apostrophe is also used.

Ideally, we would like to have a function that would perform multiple child key derivations, according to the derivation path, and provide us with the result. Let’s start by defining a new type representing a derivation path, which is, in essence, a list of child numbers:

-- | Derivation path.
newtype DerivationPath = DerivationPath (NonEmpty ChildNumber) deriving (Show, Eq)

The type tells us that we need to have at least one child number. After all, what use has a path that brings us nowhere?

Derivation path can be represented in a multiple ways. Not only it can be provided as a string (in the form m/3/2/5) but also as a single child number (that is also a valid derivation path). Therefore, it may be useful to allow to specify the derivation path in any of these ways. In order to do so, let us introduce a type class for types that can represent a derivation path together with two trivial instances:

-- | Class for types that can represent a derivation path.
class AsDerivationPath a where
  derivationPath :: a -> Maybe DerivationPath

instance AsDerivationPath DerivationPath where
  derivationPath = Just

instance AsDerivationPath ChildNumber where
  derivationPath c = Just $ DerivationPath (c :| [])

The operator :| is a constructor of NonEmpty.

Now we have a way to represent derivation path and we can revisit our Derive type class by adding a new function that would derive child using a derivation path instead of just by one child number:

-- | Type class for types that can derive children of the same type.
class Derive a where
  -- | Derives new child key with the given number.
  deriveChild1 :: a -> ChildNumber -> Maybe a

  -- | Derives new child key determined by the given derivation path.
  deriveChild :: (AsDerivationPath p) => a -> p -> Maybe a
  deriveChild a p =
    derivationPath p >>= (\(DerivationPath cs) -> foldM deriveChild1 a cs)

Using foldM we recursively apply deriveChild1 to previously derived child along the derivation path. How fortunate are we that we do not have to change implementation of any instance.

The very last thing we need in this section is the ability to provide derivation path as a string:

instance AsDerivationPath T.Text where
  derivationPath t =
    case T.split (== '/') t of
      (x : rs)
        | T.unpack (T.toLower x) == "m" ->
            DerivationPath <$> (mapM parseChildNumber rs >>= nonEmpty)
      _ -> Nothing
    where
      parseChildNumber s = case reads $ T.unpack s of
        [(n, "")] -> Just $ normal n
        [(n, "'")] -> Just $ hardened n
        [(n, "h")] -> Just $ hardened n
        [(n, "H")] -> Just $ hardened n
        _ -> Nothing

instance AsDerivationPath String where
  derivationPath = derivationPath . T.pack

Testing Link to heading

So much text and code and we have not yet verified that anything actually works. Luckily the specification offers a few testing cases to verify our implementation. On the other hand, if there is something more boring than writing tests, it is writing about writing tests. And as tests of this code are quite trivial, I refer the readership to the code repository.

One can also use GHCi for a quick test:

$> cabal repl
ghci> :set -XOverloadedStrings
ghci> import BipByBip.Bip32
ghci> fromBase58 "xpub68NZiKmJWnxxS6aaHmn81bvJeTESw724CRDs6HbuccFQN9Ku14VQrADWgqbhhTHBaohPX4CjNLf9fq9MYo6oDaPPLPxSb7gwQN3ih19Zm4Y"