## 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)

#### <a id="a_i">Introduction</a>

If you’re considering using MMGen Wallet 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 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, the MMGen Wallet project page has disappeared
from all of [Github][04], [Gitlab][05], [Gitflic][06] and [mmgen.org][07] (or
been hacked), and no other verifiable 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 very 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.

#### <a id="a_rs">Obtaining the binary seed</a>

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 in default wallet format, 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.

#### <a id="a_ss">Convert the seed to binary (legacy uncompressed addresses)</a>

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
```

#### <a id="a_cs">Scramble the seed and save to binary (non-legacy and altcoin addresses and passwords)</a>

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
```

#### <a id="a_gk">Generating the keys</a>

MMGen Wallet’s 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
```

#### <a id="a_cr">Checking the result (optional, address example)</a>

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.

#### <a id="a_hpw">Converting the hex value to a password (password example)</a>

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
```

#### <a id="a_hw">Hex to WIF by hand (address example)</a>

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)
```

#### <a id="a_bcu">Base-conversion utility</a>

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
```

#### <a id="a_mh">Converting an MMGen mnemonic to hexadecimal format</a>

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 Wallet seed phrase 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-wallet
[05]: https://gitlab.com/mmgen/mmgen-wallet
[06]: https://gitflic.ru/project/mmgen/mmgen-wallet
[07]: https://mmgen.org/project/mmgen/mmgen-wallet
