## Table of Contents * [Introduction](#a_i) * [Obtaining the binary seed](#a_rs) * [Convert the seed to binary (legacy uncompressed addresses)](#a_ss) * [Scramble the seed and save to binary (non-legacy and altcoin addresses and passwords)](#a_cs) * [Generating the keys](#a_gk) * [Checking the result (optional, address example)](#a_cr) * [Converting the hex value to a password (password example)](#a_hpw) * [Hex to WIF by hand (address example)](#a_hw) * [Base-conversion utility](#a_bcu) * [Converting an MMGen mnemonic to hexadecimal format](#a_mh) #### Introduction If you’re considering using MMGen and are a Bitcoiner with a normal, healthy degree of paranoia, then the following question will probably come to mind: “What if I have funds in an MMGen wallet and I lose the software? How do I recover my coins?” Let’s take this scenario to its logical extreme and assume you’ve lost all backup copies of the software, MMGen’s project page has disappeared from both [Github][04] and [Gitlab][05] (or been hacked) and no other repositories or copies are available on the Internet. The following tutorial will show you how to recover the private keys for your coin addresses in the event this unlikely combination of circumstances ever occurs. In addition to private keys, this tutorial can also be used to recover passwords generated with the `mmgen-passgen` command. #### Obtaining the binary seed To keep things simple, we’ll assume you have a copy of your seed in hexadecimal (mmhex) format. If your backup’s in mnemonic format, skip to the section [Converting an MMGen mnemonic to hexadecimal format](#a_mh) below and return here when you’ve finished. If your backup is an MMGen wallet, it will need to be decrypted. That case will be covered in a future tutorial. Okay, so let’s say you have a 128-bit seed with Seed ID `FE3C6545` and funds in the first three legacy uncompressed (`L`) addresses of this seed. Here are the addresses: ```text FE3C6545 { 1 1JVi3qcNcjMM7cTR7y9ihKUG1yDLpKRJfL 2 15EfKymfe3v7mqCaL174hTWSgBLFAHvtaR 3 1CUDd6nPHdP5pT7nN8k2AA5WdKRaKPjmea } ``` Since you might have your funds in Segwit (`S`) addresses, we’ll consider that case too: ```text FE3C6545 SEGWIT { 1 3LpkKqtGkcCukRrgEFWyCajSApioiEWeTw 2 3FYZQyWqBJcCjaSjCV9ZVj3gKyB9u8AYCX 3 37wM8hwt69qwH7hZHAMn6RVdc8vMuM1CwJ } ``` Keys for compressed (`C`), Bech32 (`B`) and altcoin addresses, as well as passwords, are generated in a way analogous to Segwit keys, so for them you’ll proceed as with the Segwit case. Here’s the seed itself in `mmhex` format, which you’ve stored in some safe place (on paper in a safe-deposit box, for example): ```text afc3fe 456d 7f5f 1c4b fe3b c916 b875 60ae 6a3e ``` Now your task is to generate keys for the addresses so you can spend your coins. This task is divided into two parts: 1. generating the keys and converting them to hexadecimal format; and 2. converting the hex keys to wallet interchange (WIF) format for importation into Bitcoin Core or some other wallet. We’ll solve this task using standard command-line utilities available on any Linux or other Unix-like system. #### Convert the seed to binary (legacy uncompressed addresses) For the legacy addresses, we begin by converting the seed to binary form and storing it in a file. For that we use `xxd`, a handy tool for converting binary to hex and vice versa. Don’t forget to omit the checksum from the seed and remove the spaces: ```bash $ echo 456d7f5f1c4bfe3bc916b87560ae6a3e | xxd -r -p > myseed.bin ``` #### Scramble the seed and save to binary (non-legacy and altcoin addresses and passwords) Other address types and passwords are generated by first “scrambling” the seed with a unique identifier, or “scramble string”, using the HMAC-SHA256 algorithm. The scrambled seed is then given ten rounds of SHA256 to create the base seed used to generate our keys. Our first task then is to find out the correct scramble string for our coin and address type (or password). For BTC and BTC fork coins, the string will be simply the address type, e.g. `compressed` or `segwit`. For Bitcoin-based altcoins, the string is the coin symbol and address type separated by a colon, e.g. `ltc:legacy`. The strings for non-Bitcoin-derived altcoins are irregular and are listed in the table below. For passwords, the string is the password format, e.g. `b58`; the password length, e.g. `20`; and the password ID string, e.g. `alice@fubar.io`, all separated by colons: | Coin + Address type | Scramble String | |:-----------------------------------------|:-------------------------| | BTC/BCH compressed | `compressed` | | BTC Segwit-P2SH | `segwit` | | BTC native Segwit (Bech32) | `bech32` | | LTC legacy | `ltc:legacy` | | LTC compressed | `ltc:compressed` | | LTC Segwit | `ltc:segwit` | | LTC Bech32 | `ltc:bech32` | | DASH legacy | `dash:legacy` | | DASH compressed | `dash:compressed` | | ETH | `eth` | | ETC | `etc` | | XMR | `xmr:monero` | | ZEC-T | `zec:legacy` | | ZEC-Z | `zec:zcash_z` | | Password type | Scramble String | |:-----------------------------------------|:-------------------------| | Base58 passwords for Alice’s email acct. | `b58:20:alice@fubar.io` | | Same as above, half-length passwords | `b58:10:alice@fubar.io` | | Same as above, default Base32 passwords | `b32:24:alice@fubar.io` | | 32-byte hex seed for Alice’s PGP key | `hex:64:alice@gnupg` | Once we’ve determined the correct string, we scramble our seed with it as follows using the `openssl` utility available by default on any Unix-based system: ```bash # e.g. for LTC Segwit addresses: $ scramble_str='ltc:segwit' # e.g. for default-format passwords for Alice’s email account at fubar.io: $ scramble_str='b58:20:alice@fubar.io' $ echo -n "$scramble_str" | openssl dgst -r -sha256 -mac hmac -macopt hexkey:456d7f5f1c4bfe3bc916b87560ae6a3e | xxd -r -p > scrambled-round0.bin ``` Now add the ten rounds of sha256: ```bash $ for i in 0 1 2 3 4 5 6 7 8 9; do openssl dgst -sha256 -binary scrambled-round${i}.bin > scrambled-round$((i+1)).bin done $ mv scrambled-round10.bin myseed.bin ``` #### Generating the keys The MMGen key-generating algorithm uses a chain of SHA-512 hashes with double SHA-256 branches to generate the keys from which each address is derived. To obtain the chain’s first link, we make a single SHA-512 hash of the seed and save it in binary form: ```bash $ sha512sum myseed.bin | xxd -r -p > link1.bin ``` A double SHA-256 hash of the first link gives us the key of our first address: ```bash $ sha256sum link1.bin | xxd -r -p | sha256sum 05d7219524b983290138a60ada101370007f59a625c43a46f0f8d92950955e36 ``` Or, for the Segwit example: ```text b8e58ded53e9ba5a9f4e279a956c061a7da5487bde6a95f1ede0722d287881a0 ``` Or, for the password example: ```text bd60b8ba034bbb40498667ee600bc0cc0b99eb19164e8d412a48f16da4e00d6b ``` #### Checking the result (optional, address example) With `mmgen-tool`, we can easily generate the WIF key and address from this hexadecimal key and see that it’s correct: ```bash $ mmgen-tool hex2wif 05d7219524b983290138a60ada101370007f59a625c43a46f0f8d92950955e36 5HrrmMdQbELyW7iCns5kvSbN9GCPTqEfG7iP1PZiYk49yDDivTi $ mmgen-tool wif2addr 5HrrmMdQbELyW7iCns5kvSbN9GCPTqEfG7iP1PZiYk49yDDivTi 1JVi3qcNcjMM7cTR7y9ihKUG1yDLpKRJfL # matches FE3C6545:L:1 above ``` Or, for the Segwit example: ```bash $ mmgen-tool hex2wif b8e58ded53e9ba5a9f4e279a956c061a7da5487bde6a95f1ede0722d287881a0 compressed=1 L3R8Fn21PsY3PWgT8BMggFwXswA2EZntwEGFS5mfDJpSiLq29a9F # for a compressed (`C`) address, leave out the `segwit=1` argument $ mmgen-tool wif2addr L3R8Fn21PsY3PWgT8BMggFwXswA2EZntwEGFS5mfDJpSiLq29a9F segwit=1 3LpkKqtGkcCukRrgEFWyCajSApioiEWeTw # matches FE3C6545:S:1 above ``` But since we’re trying to do this without the MMGen software, we need to find some other way to do the hex-to-WIF conversion. We could use one of many key-manipulation tools available on the Internet, such as [this one][01], or [this one][02]. Or we can do it ourselves: that will be covered in the next section. Meanwhile, let’s finish generating hex keys for the rest of our addresses (or passwords). To get the next key, we generate the next link in the chain from the first link and take its double SHA-256 hash, just as we did for the first one: ```bash $ sha512sum link1.bin | xxd -r -p > link2.bin $ sha256sum link2.bin | xxd -r -p | sha256sum 5db8fe3c8b52ccc98deab5afae780b6fbe56629e7ee1c6ed826fc2d6a81fb144 # uncompressed example 42f1b998f0f9b7b27b5d0b92ffa8c1c6b96d7202789c41b6e6a6a402e318a04d # Segwit example 9b59cec2e5d4f2a74f0d4eb2400efcf854f5a893bef0e9bf1ee83f72ca1118c3 # password example ``` And so on and so forth, until we’ve generated all the keys we need: three, in our case. If we’re generating keys for Ethereum and Monero, our work is done: the raw hexadecimal keys are all we need. Otherwise, read on. #### Converting the hex value to a password (password example) If it’s passwords we’re generating, we must now convert our hex key to the desired password format, base58 in our case. For this we can use the homemade `hex2b58.py` [Base-conversion utility](#a_bcu) described below: ```bash # bd60b8... is the double sha256 of our link1.bin from above $ ./hex2b58.py bd60b8ba034bbb40498667ee600bc0cc0b99eb19164e8d412a48f16da4e00d6b DkFbZk2fDKQ7C55ASHQjhwcCdTsCiRq4ZLMMD5WQVAvv ``` The password is just the last 20 characters of the output: ```text dTsCiRq4ZLMMD5WQVAvv ``` #### Hex to WIF by hand (address example) Since we’ve chosen to convert our hex keys to WIF format manually, we have a bit of work ahead of us. Let’s begin with our just-generated key #1 from seed `FE3C6545`: ```bash # uncompressed example 05d7219524b983290138a60ada101370007f59a625c43a46f0f8d92950955e36 # Segwit example b8e58ded53e9ba5a9f4e279a956c061a7da5487bde6a95f1ede0722d287881a0 ``` WIF format prepends hex `80` to the beginning of the key. If the key is associated with a compressed public key, it also appends `01`: ```bash # uncompressed example: 8005d7219524b983290138a60ada101370007f59a625c43a46f0f8d92950955e36 # Segwit example (Segwit uses compressed public keys): 80b8e58ded53e9ba5a9f4e279a956c061a7da5487bde6a95f1ede0722d287881a001 ``` The Base58Check format invented by Satoshi for Bitcoin addresses and keys contains a checksum, which we now generate by taking the first four bytes (eight characters) of the double SHA256 of the above result: ```bash # uncompressed example: $ echo 8005d7219524b983290138a60ada101370007f59a625c43a46f0f8d92950955e36 | xxd -r -p | sha256sum | xxd -r -p | sha256sum | cut -c 1-8 7b818629 # Segwit example: $ echo 80b8e58ded53e9ba5a9f4e279a956c061a7da5487bde6a95f1ede0722d287881a001 | xxd -r -p | sha256sum | xxd -r -p | sha256sum | cut -c 1-8 89bba812 ``` The checksum gets appended to the end, giving us the following final result: ```bash # uncompressed example 8005d7219524b983290138a60ada101370007f59a625c43a46f0f8d92950955e367b818629 # Segwit example 80b8e58ded53e9ba5a9f4e279a956c061a7da5487bde6a95f1ede0722d287881a00189bba812 ``` The last step is to convert all this into Base 58. Satoshi created Base-58 encoding for convenient and error-free writing down and dictating of Bitcoin keys and addresses. He began with a Base-62 alphabet consisting of the ten digits plus the upper and lower case Latin letters (10 + 26 + 26 = 62): ```text 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijlkmnopqrstuvwxyz ``` Since ‘0’ (zero) is easily confused with capital ‘O’ visually, and capital ‘I’ with lowercase ‘l’, he dropped those characters, leaving the following 58: ```text 123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz ``` With ‘0’ gone, ‘1’ now represents decimal zero, ‘2’ represents decimal one, and so forth all the way up to ‘z’, representing decimal fifty-seven. Now all that remains is to convert our hexadecimal key to decimal and then Base 58 using this alphabet. This can be done in just four lines of code you can try out at the Python prompt: ```python # uncompressed example: $ python3 >>> b58a = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz' >>> num = int('8005d7219524b983290138a60ada101370007f59a625c43a46f0f8d92950955e367b818629',16) >>> result = [b58a[num // 58**e % 58] for e in range(60)] >>> print(''.join(reversed(result)).lstrip('1')) 5HrrmMdQbELyW7iCns5kvSbN9GCPTqEfG7iP1PZiYk49yDDivTi # matches key for FE3C6545:L:1 above # Segwit example has the following differences: ... >>> num = int('80b8e58ded53e9ba5a9f4e279a956c061a7da5487bde6a95f1ede0722d287881a00189bba812',16) ... L3R8Fn21PsY3PWgT8BMggFwXswA2EZntwEGFS5mfDJpSiLq29a9F # matches key for FE3C6545:S:1 above ``` Explanation: the variable `b58a` holds the Base 58 alphabet; `num` holds the key in decimal, converted from hexadecimal by Python’s `int()` function; the third line does the base-58 conversion; and the last line formats the result by reversing the order of the digits, converting it to a string and stripping off the leading zeroes (‘1’s). Programmers unfamiliar with Python might find the following base conversion code clearer: ```python def numtob58(n): result = [] while n: result = result + [b58a[n % 58]] # divide n by 58 and take the remainder n = n // 58 return result result = numtob58(num) ``` #### Base-conversion utility Adapting our code a bit and putting it in a file gives us have a handy conversion utility we can use for any key: ```python $ cat hex2b58.py #!/usr/bin/env python3 import sys b58a = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz' num = int(sys.argv[1],16) result = [b58a[num // 58**e % 58] for e in range(60)] print(''.join(reversed(result)).lstrip('1')) ``` ```text $ ./hex2b58.py 8005d7219524b983290138a60ada101370007f59a625c43a46f0f8d92950955e367b818629 5HrrmMdQbELyW7iCns5kvSbN9GCPTqEfG7iP1PZiYk49yDDivTi $ ./hex2b58.py 80b8e58ded53e9ba5a9f4e279a956c061a7da5487bde6a95f1ede0722d287881a00189bba812 L3R8Fn21PsY3PWgT8BMggFwXswA2EZntwEGFS5mfDJpSiLq29a9F ``` #### Converting an MMGen mnemonic to hexadecimal format Our familiar base-10 system uses a series of ten symbols known as digits to represent numbers from zero to nine: ```text 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ``` If a number has more than one digit, its value is the sum of its digits multiplied by increasing powers of ten, beginning with the rightmost, least significant digit (the “ones column”). Thus the number 1234, for example, can be represented as follows: ```text 4 x 1 + 3 x 10 + 2 x 100 + 1 x 1000 ``` Or in exponential notation: ```text 4 x 10⁰ + 3 x 10¹ + 2 x 10² + 1 x 10³ ``` An MMGen seed mnemonic is a number too, only the “digits” it’s comprised of come from an alphabetically sorted series of 1626 words, the [Electrum wordlist][03], which begins like this: ```text able (0), about (1), above (2), abuse (3), accept (4) ... ``` and ends like this: ```text yet (1621), young (1622), yours (1623), yourself (1624), youth (1625) ``` (Type `mmgen-tool mn_printlist enum=true` to see the full enumerated list) The words of the Electrum wordlist thus make up a base-1626 numbering system, just like the ten digits of our familiar base-10 system. Here’s the mnemonic of our seed `FE3C6545`: ```text dude foot desperate tie stood themselves trip descend cease suicide apple busy ``` To decode it, we begin by listing its words, from least to most significant, along with the value of each word corresponding to its position in the wordlist: ```text busy - 200 apple - 59 suicide - 1384 cease - 221 descend - 379 trip - 1493 themselves - 1433 stood - 1348 tie - 1459 desperate - 386 foot - 562 dude - 439 ``` All that remains is to multiply the values by increasing powers of the base and sum the results, just as we did in our ‘1234’ example above: ```text 200 x 1626⁰ + 59 x 1626¹ + 1384 x 1626² + 221 x 1626³ + 379 x 1626⁴ + 1493 x 1626⁵ + 1433 x 1626⁶ + 1348 x 1626⁷ + 1459 x 1626⁸ + 386 x 1626⁹ + 562 x 1626¹⁰ + 439 x 1626¹¹ ``` While we could theoretically do the math with a calculator, a few lines of Python will make our work much easier: ```python $ python3 >>> sum = exp = 0 >>> for word in (200,59,1384,221,379,1493,1433,1348,1459,386,562,439): >>> sum += word * 1626 ** exp >>> exp += 1 >>> print(hex(sum)) 0x456d7f5f1c4bfe3bc916b87560ae6a3e # the result in hexadecimal: matches our original hex seed above ``` In case you’re wondering why 1626 was chosen as the base: 1626 is just large enough to allow a 128-bit seed to be represented by twelve words. This can also be demonstrated at the Python prompt: ```python $ python3 >>> 1626**12 >= 2**128 True >>> 1625**12 >= 2**128 False ``` [01]: https://github.com/casascius/Bitcoin-Address-Utility [02]: https://github.com/matja/bitcoin-tool [03]: https://github.com/spesmilo/electrum/blob/1.9.5/lib/mnemonic.py [04]: https://github.com/mmgen/mmgen [05]: https://gitlab.com/mmgen/mmgen