Bitcoin is all about signing stuff and verifying signed stuff. Well, there may be a bit more to it but signing
and verifying are quite important. At the beginning of signing and verifying, there is a very large number that
no one is supposed to know. The *private key*. This private key is a key to everything, mainly one’s funds. Human brains,
however, are not designed to deal with large numbers, they do better with words and phrases. That is why we were given
BIP 39.

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/Bip39.hs
cabal run bip39-test
```

The BIP 39 describes a method of deriving a seed from a short list of words, called *mnemonic code*, and a method
to generate this mnemonic code. This seed can be then used to create actual private key via BIP 32 or other means.

A mnemonic code or sentence is superior for human interaction compared to the handling of raw binary or hexadecimal representations of a wallet seed. The sentence could be written on paper or spoken over the telephone.

## Entropy Link to heading

*Entropy* is what gives the mnemonic code its randomness. In simple terms, it is a bunch of random bytes.

First, an initial entropy of ENT bits is generated.

We are not concerned with generating the random bytes, let us assume we already have them.

The mnemonic must encode entropy in a multiple of 32 bits. With more entropy security is improved but the sentence length increases. We refer to the initial entropy length as ENT. The allowed size of ENT is 128-256 bits.

A checksum is generated by taking the first ENT / 32 bits of its SHA256 hash.

To generate a mnemonic code, only entropy of 128, 160, 192, 224 or 256 bits is accepted. We also need to calculate checksum by taking a few bits of entropy’s SHA256 hash:

```
-- | Initial entropy.
newtype Entropy = Entropy BV.BitVector deriving (Show, Eq)
-- | Attempts to create Entropy from a given byte string. Returns Nothing
-- if byte string was not of a valid length (only 128, 160, 192, 224, 256 bits
-- are valid).
entropy :: BS.ByteString -> Maybe Entropy
entropy bs =
if BS.length bs `elem` [16, 20, 24, 28, 32]
then Just $ Entropy $ BV.concat (BV.bitVecs 8 $ BS.unpack bs) <> checksum bs
else Nothing
-- | Get checksum of entropy.
checksum :: BS.ByteString -> BV.BitVector
checksum bs = BV.most cslen $ BV.bitVec 8 $ BA.index (sha256 bs) 0
where
cslen = BS.length bs `div` 4
```

The `Entropy`

data type holds data and its checksum that is appended to it.

`BitVector`

contains a collection of bits but `ByteString`

gives us only list of `Word8`

. We can, however, convert them to
`BitVector`

s using the function `bitVecs`

aligned to 8 bits.

How many bits of the entropy’s SHA256 to take for the checksum? Length of entropy in bits divided by 32. Or, since we use bytes,
the length in bytes divided by 4. For 128 bits (16 bytes) it will be 4 bits. For 256 bits (32 bytes), the checksum
will be 8 bits long. Since we will never need more than 8 bits for the checksum, we can start by taking the first byte
from the SHA256 digest (`BA.index (sha256 bs) 0`

) and then take the needed number of bits out of it (`BV.most`

).

Coincidentally, in each case the resulting length in bits, that is entropy data plus its checksum, is divisible by 11, for example 128 + 4 = 132 and 256 + 8 = 264.

## Wordlist and mnemonic Link to heading

[…] concatenated bits are split into groups of 11 bits, each encoding a number from 0-2047, serving as an index into a wordlist. Finally, we convert these numbers into words and use the joined words as a mnemonic sentence.

So it is not a coincidence. We can now divide the entropy, including its checksum, into groups of 11 bits. Each group will then represent a number between 0 and 2047 that can be used as an index into a list of words. By translating these groups of 11 bits into words, we get the mnemonic. That is what you have to remember if you want to have access to your Bitcoins.

The list of words for English can be found at https://raw.githubusercontent.com/bitcoin/bips/master/bip-0039/english.txt. While similar lists for other languages are possible, they are discouraged.

```
-- | Converts entropy into mnemonic.
mnemonic :: Entropy -> Mnemonic
mnemonic (Entropy ent) = Mnemonic $ fmap (Wordlist.en !) indices
where
indices :: [Int]
indices = fromIntegral . BV.nat <$> BV.group (11 :: Int) ent
```

The wordlist is held in a separate module in a `Vector`

for faster indexing:

```
module BipByBip.Bip39.Wordlist where
import Data.Vector
en :: Vector String
en =
fromList
[ "abandon",
"ability",
"able",
…
]
```

## Seed Link to heading

So far we have got only a bunch of words, used by nothing in the Bitcoin protocol. To make them more useful for machines,
we need to have a way of converting these words into a binary form, the *seed*.

To create a binary seed from the mnemonic, we use the PBKDF2 function with a mnemonic sentence (in UTF-8 NFKD) used as the password and the string “mnemonic” + passphrase (again in UTF-8 NFKD) used as the salt. The iteration count is set to 2048 and HMAC-SHA512 is used as the pseudo-random function. The length of the derived key is 512 bits (= 64 bytes).

That does not sound too difficult, just apply a PBKDF2 function on the list of words we just generated.

For the cryptography part, we can use the library cryptonite again. It provides all the building blocks we need:

```
import Crypto.Hash.Algorithms qualified as Alg
import Crypto.KDF.PBKDF2 (Parameters (..), generate, prfHMAC)
-- | Returns 512-bit long key generated by PBKDF2 with HMAC-SHA512 and 2048 iterations
-- using given password and salt. This setting is used by BIP 39.
pbkdf2Hmac512 :: BS.ByteString -> BS.ByteString -> BS.ByteString
pbkdf2Hmac512 password salt =
generate (prfHMAC Alg.SHA512) (Parameters 2048 64) password salt
```

Also, we have not yet encountered the notion of *passphrase*. This is an additional, optional element to
mnemonic’s security. It represents one more word beyond the mnemonic code that user has to remember
and provide when needed. Only the right combination of mnemonic code and passphrase will give the user
access to the Bitcoins.

```
-- | Generates seed from mnemonic and an optional passphrase.
seed :: Maybe String -> Mnemonic -> BS.ByteString
seed passphrase (Mnemonic ws) = pbkdf2Hmac512 sentence password
where
password = BC.pack $ "mnemonic" ++ fromMaybe "" passphrase
sentence = BC.pack $ unwords ws
```

Now, having the seed, we can start generating private keys with the help of BIP 32.

## Parsing Link to heading

Although parsing of mnemonic codes is not explicitly described in the BIP document, it would certainly be a useful function. Using it, we could verify that a given list of words is a valid mnemonic code, i. e. all the words are part of the wordlist and the checksum is correct.

When given a list of words, we fist try to find their indices in the wordlist. Each index is 11 bits wide.
We can then concatenate these 11-bit numbers into one bit vector, split into entropy data and its checksum
and verify by calling `checksum`

function on the entropy data (held in a `ByteString`

) and comparing to the
extracted checksum. Let us start with verifying the checksum from a list if indices:

```
-- | Verifies validity of word indices by recalculating checksum.
checksumValid :: [Int] -> Bool
checksumValid idx = cs == checksum bs
where
bs = BS.pack $ fromIntegral <$> BV.group (8 :: Int) ent
ent = BV.most (len - cslen) bits
cs = BV.least cslen bits
cslen = len `mod` 32
len = BV.size bits
```

Finally, we can take user input, split it into words, try to find index of each of them and verify validity of these indices:

```
-- | Attempts to parse given string as a mnenomic,
-- fails if the string is not a valid mnemonic.
parseMnemonic :: String -> Either String Mnemonic
parseMnemonic str = case bimap reverse reverse $ foldl f (Right []) mn of
Right idx | checksumValid idx -> Right (Mnemonic mn)
Right _ -> Left "Invalid checksum"
Left err -> Left ("Unknown words: " ++ unwords err)
where
mn = words str
f :: Either [String] [Int] -> String -> Either [String] [Int]
f acc word = case word `elemIndex` Wordlist.en of
Just idx -> fmap (idx :) acc
Nothing -> either (Left . (word :)) (const $ Left [word]) acc
```

Most of this function takes care of producing a reasonable message in case of errors. The inner function
`f`

accumulates unknown words (in `Left`

) or successfully found indices (in `Right`

). If, after processing
every word, we get `Left`

, it means we have encountered some unknown words. Otherwise `Right`

gives us list
of indices that we first verify before returning final result, the verified mnemonic.

## Testing Link to heading

We can find link to test vector inside the BIP 39 and use it to verify correctness of this implementation (see source code). Or we can try some parsing in GHCi:

```
$> cabal repl
ghci> import BipByBip.Bip39
ghci> parseMnemonic "zoo zoo zoo zoo zoo zoo zoo zoo zoo zoo zoo wrong"
# Right (Mnemonic {mnemonicWords = ["zoo","zoo",…]})
ghci> parseMnemonic "zoo zoo zoo zoo zoo zoo zoo zoo zoo zoo zoo zoo"
# Left "Invalid checksum"
ghci> parseMnemonic "zoo zoo zoo zoo zoo zoo zoo zoo zoo zoo zoo zoom"
# Left "Unknown words: zoom"
```