Mnemonic seed phrases (BIP39, 2013)

Marek Palatinus, Pavol Rusnak, Aaron Voisine and Sean Bowe proposed writing a wallet’s seed as words. The entropy gets a checksum, the first ENT/32 bits of its SHA-256, and the bits are cut into 11-bit indices into a list of 2048 words,

\[\frac{ENT + ENT/32}{11} \text{ words}: \quad 128 \text{ bits} \to 12 \text{ words}.\]

A miscopied word fails the 4-bit checksum of a 12-word phrase 15 times in 16. The phrase is then stretched by PBKDF2-HMAC-SHA512 over 2048 iterations into the 64-byte BIP32 seed, with an optional passphrase that gives every guess a different, valid wallet. The word list here is generated by a rule rather than BIP39’s English list; the seed derivation is BIP39’s own, and reproduces its test vectors.

import matplotlib.pyplot as plt

import blockchainkit as bk

Entropy to words to seed

entropy = bytes.fromhex("0c1e24e5917779d297e14d45f14e1a1a")
phrase = bk.wallets.entropy_to_mnemonic(entropy)
print("phrase:", phrase)
assert bk.wallets.mnemonic_to_entropy(phrase) == entropy
seed = bk.wallets.mnemonic_to_seed(phrase, "")
print("seed:", seed.hex()[:32], "...")
master = bk.wallets.master_key(seed)
print("master:", bk.wallets.serialize_extended_key(master)[:24], "...")

english = " ".join(["abandon"] * 11 + ["about"])  # BIP39's first test vector.
assert bk.wallets.mnemonic_to_seed(english, "TREZOR").hex().startswith("c55257c360c07c72")

phrase: buda zale golo faro lita voli juta fome himo mono mira giko
seed: fa6e9176d2205fdf040f71c20bf525da ...
master: xprv9s21ZrQH143K43BHonUM ...

How often a miscopied word is caught

words = phrase.split()
rates = {}
for size in (16, 20, 24, 28, 32):
    sample = bk.wallets.entropy_to_mnemonic(bytes(range(size))).split()
    caught = sum(
        not bk.wallets.is_valid_mnemonic(" ".join([*sample[:3], w, *sample[4:]]))
        for w in bk.wallets.WORDLIST
        if w != sample[3]
    )
    rates[len(sample)] = caught / 2047
    print(
        f"{len(sample)} words: {caught} of 2047 replacements caught ({1 - 2 ** -(size // 4):.4f})"
    )
assert abs(rates[12] - 15 / 16) < 0.02

12 words: 1904 of 2047 replacements caught (0.9375)
15 words: 1978 of 2047 replacements caught (0.9688)
18 words: 2017 of 2047 replacements caught (0.9844)
21 words: 2031 of 2047 replacements caught (0.9922)
24 words: 2040 of 2047 replacements caught (0.9961)

Every passphrase is a valid, different wallet

for passphrase in ("", "correct", "Correct"):
    other = bk.wallets.master_key(bk.wallets.mnemonic_to_seed(phrase, passphrase))
    print(f"{passphrase!r:10} -> {bk.wallets.p2pkh_address(other.public)}")

fig, ax = plt.subplots(figsize=(6, 4))
ax.plot(list(rates), [1 - r for r in rates.values()], "o-", color="#dc2626", label="measured")
ax.plot(
    list(rates), [2 ** -(n // 3) for n in rates], "--", color="black", label="2^-(checksum bits)"
)
ax.set_yscale("log")
ax.set(xlabel="words in the phrase", ylabel="miscopied word accepted", xticks=list(rates))
ax.set_title("Longer phrases carry longer checksums")
ax.legend()
fig.tight_layout()
plt.show()

''         -> 1PfPeEV8N2TdomVtgD4EjTiGLXc4KD6vyt
'correct'  -> 147F2jMLoJfFDzpCNxwCSBQtKkhoRvFC14
'Correct'  -> 18tCMaoptY4QyMKg8rQAzYUb96pPRfUWXy

Exercise

How many words, and how many checksum bits, encode 256 bits of entropy? A worked solution is in Exercises: wallets.