BIP 39: Mnemonic code for generating deterministic keys

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"