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 formatExtended 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
fingerprintof the parent’s key (0x00000000 if master key)- 4 bytes
child number. This is ser_{32}(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 keydata (ser_{P}(K) for public keys, 0x00 || ser_{256}(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

_{32}(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

^{31}normal child keys, and 2^{31}hardened child keys. Each of these child keys has an index. The normal child keys use indices 0 through 2^{31}-1. The hardened child keys use indices 2^{31}through 2^{32}-1. To ease notation for hardened key indices, a number i_{H}represents i+2^{31}.

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^{31}−1 (or `0x00000000`

to `0x7FFFFFFF`

), are called *normal* while the rest, numbered
2^{31} to 2^{32}−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^{31}. Therefore, in order to convert a hardened child number
into this compact notation, we have to subtract 2^{31} 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^{31}−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
_{256}(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_{256}(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_{256}(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
_{256}(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^{127}.)

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
_{32}(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

^{512}, 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
_{256}(I_{L}) as master secret key, and I_{R}as master chain code.In case parse

_{256}(I_{L}) is 0 or parse_{256}(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
_{32}(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) functionsGiven 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

^{31}), 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 keyThe 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
^{31}(whether the child is a hardened key).

- If so (hardened child): let I = HMAC-SHA512(Key = c
_{par}, Data = 0x00 || ser_{256}(k_{par}) || ser_{32}(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_{32}(i)).- Split I into two 32-byte sequences, I
_{L}and I_{R}.- The returned child key k
_{i}is parse_{256}(I_{L}) + k_{par}(mod n).- The returned chain code c
_{i}is I_{R}.- In case parse
_{256}(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^{127}.)

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 keyThe 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
^{31}(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_{32}(i)).- Split I into two 32-byte sequences, I
_{L}and I_{R}.- The returned child key K
_{i}is point(parse_{256}(I_{L})) + K_{par}.- The returned chain code c
_{i}is I_{R}.- In case parse
_{256}(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 _{256}(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"
```