Written by Pete Corey on Feb 19, 2018.

I’m still working my way through Andreas Antonopoulos’ amazing Mastering Bitcoin book. In the chapter on Bitcoin wallets, he describes how deterministic wallet seeds can be represented as mnemonic groups of words.

Mnemonics are generated by hashing, appending, and chunking up a random series of bytes into a list of numbers that can be evenly mapped onto a given word list.

Creating these mnemonic word sequences seems like the perfect opportunity to flex our Elixir muscles.

Deterministic wallets, mnemonics, and seeds?

This terminology may sound like gibberish, but the underlying ideas are simple.

At its core, a Bitcoin wallet is just a collection of private keys. In the most basic type of wallet, the collected keys are just randomly generated numbers. They’re not related to each other in any way. In more sophisticated wallets, each private key is generated by securely transforming the key that came before it. The initial source of entropy for these “deterministic wallets” is known as the wallet’s “seed”.

The primary benefit of using a deterministic wallet is that you only need to keep track of the wallet’s seed, not every private key contained within it. All of the primary keys used by the wallet can be regenerated from the seed.

BIP-39 attempts to make it easier for humans to remember these initial seeds. It does this by mapping the original source of entropy used to create the wallet’s seed into a sequence of short, easily memorizable words, called a mnemonic.

For example, the following BIP-39 style mnemonic maps to an initial random seed value of 0xEAF9C684F84EACA7C6B0CE08F77A6784:


turtle soda patrol vacuum turn fault
bracket border angry rookie okay anger

Isn’t the mnemonic much easier to remember?

How to Generate a Mnemonic

A a high level, the algorithm for generating a BIP-39 mnemonic looks like this:

  1. Generate sixteen to thirty two random bytes.
  2. Append a partial SHA-256 checksum.
  3. Map the resulting bits onto your word list.

Let’s build a new Elixir module, Bip39.Mnemonic to encapsulate this algorithm:


defmodule Bip39.Mnemonic do
end

Inside our module, we’ll create a generate/0 function that walks through each step of our high-level algorithm:


def generate do
  entropy
  |> attach_checksum
  |> map_onto_wordlist
end

Our generate/0 function will call an entropy/0 function, which will generate our initial random bytes for us. We’ll pass the result into attach_checksum/1, which will (as you’ve probably guessed) compute and append our partial checksum. Finally, we’ll map the resulting bits onto our wordlist with map_onto_wordlist/1.

Now all we have to do is flesh out these three functions!

Generating Entropy

Erlang, and Elixir by proxy, ships with all of the tools we need to generate our cryptographically secure source of entropy.

The BIP-39 algorithm works with an initial source of sixteen to thirty two bytes of random data. We’ll use Erlang’s :crypto.rand_uniform/2 to determine exactly how many bytes we’ll generate, and :crypto.strong_rand_bytes/1 to actually generate the bytes:


defp entropy do
  :crypto.rand_uniform(16, 32 + 1)
  |> :crypto.strong_rand_bytes()
end

You’ll notice that we’re setting the upper range in our call to :crypto.rand_uniform/2 to 32 + 1. This is because the upper limit is non-inclusive, and we want to utilize the full range of sixteen to thirty two bytes.

Attaching our Checksum

Once we’ve generated our source of entropy, we’ll need to calculate its checksum and append a piece of the resulting checksum to the end of our binary. Once again, Elixir ships with all of the tools we need.

Let’s start by sketching out our attach_checksum/1 function:


defp attach_checksum(entropy) do
end

We’ll use Erlang’s :crypto.hash/2 function to create a SHA-256 hash of our newly generated entropy binary:


hash = :crypto.hash(:sha256, entropy)

Mastering Bitcoin explains that we’ll only need to append a portion of this hash to our entropy binary. The exact number of bits we need to append depends on the number of bits of entropy we’re working with.


size =
  entropy
  |> bit_size
  |> div(32)

The size in bits of our partial checksum is the length of entropy, in bits, divided by 32. Now we can pattern match on the first size bits in our hash binary, and assign them to a new checksum variable:


<<checksum::bits-size(size), _::bits>> = hash

Finally, we’ll append the resulting checksum bits onto the end of our entropy binary:


<<entropy::bits, checksum::bits>>

That’s it!

Mapping onto a Wordlist

The real magic of the BIP-39 algorithm happens when we map the bits of our resulting binary sequence onto the two thousand forty eight words specified in the English wordlist described in the BIP-39 document.

Before we actually do the mapping, we’ll need to get this wordlist into our Elixir application. The simplest way of doing this is through a config value.

In our config/config.exs file, we’ll add the entire set of words within a word list sigil:


config :bip39, wordlist: ~w[
  abandon
  ability
  able
  about
  ...
]

Now that the wordlist is available to us, let’s start by defining our map_onto_wordlist/1 function:


defp map_onto_wordlist(entropy) do
end

Within our function, we can grab a reference to the wordlist we just placed in our application’s configuration:


wordlist =
  Application.fetch_env!(
    :bip39,
    :wordlist
  )

The actual mapping process is straight forward. We iterate over the provided entropy binary in chunks of eleven bits. Each chunk of eleven bits represents a number that we use as an index into our wordlist array:


for <<chunk::11 <- entropy>> do
  Enum.at(wordlist, chunk)
end

After iterating over our entropy binary and replacing each chunk of eleven bits with a word in our wordlist array, we’re left with our final mnemonic!

Tying it All Together

Now that our Bip39.Mnemonic is complete, we can take it for a test drive. Let’s call generate/0 in our new module to generate out first mnemonic sequence:


iex(1)> Bip39.Mnemonic.generate
["budget", "album", "fresh", "security", "pear", "water", "weird", "success",
 "ahead", "enrich", "brush", "impact", "ribbon", "board", "spider", "dismiss"]

Perfect!

Be sure to check out the full Bip39.Mnemonic module on Github, and if this kind of thing interests you and you want to dive deeper into the world of Bitcoin development, be sure to check out Mastering Bitcoin.