doc: write down the derivation, so the words work without us (#128)

The twelve words were only as good as this binary staying alive. The
derivation path, the address version byte and the public-key encoding
existed nowhere outside src/, so anyone holding a phrase and no working
Bitflash had the keys and no way to find them.

doc/derivation.md states all of it: BIP-39 to seed, BIP-32 to children,
both layouts this wallet has used (legacy m/i' and BIP-44
m/44'/4346950'/0'/{0,1}/i), secp256k1 with UNCOMPRESSED public keys, and
Base58Check with version byte 25.

The uncompressed part is the trap worth naming. Hashing the same key in
compressed form yields a different, perfectly valid-looking address that
holds nothing, and nothing in the source says out loud which one is
used -- it falls out of OpenSSL's default in code inherited from 0.1.0.

doc/verify-derivation.py implements the document from scratch, sharing
no code with this project and importing nothing outside the standard
library, then checks it against addresses the wallet actually produced.
Both tables were generated by a binary first: the legacy one by the
published v1.2.15, which knows only that layout, and the BIP-44 one by
the current tree. The script reproduces all eight.

That is the point of shipping the checker rather than only the prose: if
the two ever drift, the script fails and says which side is wrong.

3 files changed, 290 insertions, 0 deletions

diff --git a/README.md b/README.md
index f41c866..6601384 100644
--- a/README.md
+++ b/README.md
@@ -90,6 +90,12 @@ words also cover the address the window shows you. **Both still matter** — the
 phrase and the file back up different things, and the difference is where people
 lose money.
 
+The derivation is written down in [doc/derivation.md](doc/derivation.md), with
+test vectors and a script that reproduces them from scratch. It is there so the
+twelve words keep working even if this software does not: paths, address format
+and encoding, enough to recover the keys with ordinary tools and no Bitflash
+code at all.
+
 ### The recovery phrase
 
 ```
diff --git a/doc/derivation.md b/doc/derivation.md
new file mode 100644
index 0000000..3ca8339
--- /dev/null
+++ b/doc/derivation.md
@@ -0,0 +1,125 @@
+# Key derivation and address format
+
+This document exists so that a Bitflash wallet can be rebuilt **without this
+software**. If the project stops, the binaries are lost, or you simply do not
+trust them, the twelve words plus what is written here are enough to recover
+your private keys with ordinary cryptographic tools.
+
+Everything below is verified by `doc/verify-derivation.py`, a self-contained
+script that implements this document from scratch — no Bitflash code, no
+libraries beyond Python's standard library — and checks that it reproduces the
+addresses the wallet produces. If the two ever disagree, this document is wrong
+and the script will say so.
+
+## Addresses
+
+An address is the Base58Check encoding of a version byte followed by
+`RIPEMD160(SHA256(public key))`.
+
+| | |
+|---|---|
+| curve | secp256k1 |
+| public key encoding | **uncompressed**, 65 bytes, `0x04 ‖ X ‖ Y` |
+| address version byte | **25** (`0x19`), which is why addresses begin with `B` |
+| checksum | first 4 bytes of `SHA256(SHA256(payload))`, appended before Base58 |
+
+The public key is uncompressed. This matters more than anything else here: the
+same private key hashed in compressed form gives a completely different, valid
+looking address that holds nothing. Bitflash descends from Bitcoin 0.1.0, which
+predates compressed keys.
+
+Outputs paying an address use the usual script:
+
+```
+OP_DUP OP_HASH160 <hash160> OP_EQUALVERIFY OP_CHECKSIG
+```
+
+Mined coins and payments made directly to a public key use the older form
+`<pubkey> OP_CHECKSIG`. A wallet scanning the chain must recognise both.
+
+## From twelve words to a master key
+
+Standard BIP-39 and BIP-32, with no modifications:
+
+1. **Seed.** `PBKDF2-HMAC-SHA512(password = mnemonic, salt = "mnemonic" + passphrase, iterations = 2048, length = 64 bytes)`. Bitflash always uses an empty passphrase, so the salt is the literal string `mnemonic`.
+2. **Master key.** `I = HMAC-SHA512(key = "Bitcoin seed", data = seed)`. The master private key is `I[0..32]`, the master chain code is `I[32..64]`.
+
+Child derivation is BIP-32 `CKDpriv`, hardened and non-hardened as usual.
+
+## Two layouts
+
+A wallet records which layout it uses in `wallet.dat` under the key `hdschema`.
+Wallets created before that field existed are treated as legacy.
+
+### Legacy (`hdschema` absent or 1)
+
+```
+m/i'
+```
+
+Hardened children of the master key, one flat sequence. Index 0 is the wallet's
+default receiving address; the key pool and change take the following indices.
+
+Used by every wallet created before BIP-44 support existed, and kept forever:
+those phrases must keep working.
+
+### BIP-44 (`hdschema` = 2)
+
+```
+m/44'/4346950'/0'/0/i      external chain (receiving)
+m/44'/4346950'/0'/1/i      internal chain (change)
+```
+
+Coin type **4346950** is `0x425446`, the ASCII bytes `BTF`. It is
+[registered for Bitflash under the symbol BITFLASH](https://github.com/satoshilabs/slips/blob/master/slip-0044.md).
+The account level is fixed at `0'`; Bitflash does not expose multiple accounts.
+
+A wallet restored from a phrase scans **both** layouts, because the words alone
+do not say which one produced them.
+
+## Test vectors
+
+Using the public BIP-39 test mnemonic:
+
+```
+abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon about
+```
+
+### Legacy
+
+| path | address |
+|---|---|
+| `m/0'` | `BHJNmVvkVv59fgn7gmgP78BtciQi2HY8Hy` |
+| `m/1'` | `B5qh9opG8sH8Mv9k2xzHoTeSUd9BkT6XEZ` |
+| `m/2'` | `BCNH8uGyvkiz3uXjhA9iiF27PWAaTStNin` |
+| `m/3'` | `BC1QNaXuTPGDgLZy53PghZMHEmZcp5GLgD` |
+
+### BIP-44 external chain
+
+| path | address |
+|---|---|
+| `m/44'/4346950'/0'/0/0` | `BF1ukigB1afmqxH64gJymPwUqFBrRqWbrb` |
+| `m/44'/4346950'/0'/0/1` | `BACY8pcuCapNQr897eRHroNrgN38GSsEzV` |
+| `m/44'/4346950'/0'/0/2` | `BMzkMN2k1phNBqy8RPb4Pv1i2QpwsWkKPa` |
+| `m/44'/4346950'/0'/0/3` | `BNPZ8U6FHXr9Ererk8psyM2RqEVtF6sfBQ` |
+
+Check them yourself:
+
+```
+python doc/verify-derivation.py
+```
+
+Both tables were produced by the wallet — the legacy one by the v1.2.15 binary,
+which only knows that layout — and then reproduced independently by the script.
+
+## What this document does not give you
+
+Deriving the keys is not the same as spending. To move recovered coins you still
+need a node that knows the network: the chain, the peer protocol, and the
+transaction format. This document is about **not losing the keys**, which is the
+part that cannot be reconstructed later by reading source code that no longer
+exists anywhere.
+
+Note also that `wallet.dat` stores private keys unencrypted. A recovery phrase
+protects you against losing the file; it does not protect the file. Anyone who
+can read it can spend the coins.
diff --git a/doc/verify-derivation.py b/doc/verify-derivation.py
new file mode 100644
index 0000000..ba8e883
--- /dev/null
+++ b/doc/verify-derivation.py
@@ -0,0 +1,159 @@
+#!/usr/bin/env python3
+"""Check doc/derivation.md against the addresses the wallet really produces.
+
+This implements the document and nothing else: BIP-39 to seed, BIP-32 to child
+keys, uncompressed secp256k1 public keys, and Base58Check with version byte 25.
+It shares no code with Bitflash and needs nothing outside the standard library,
+so agreement between the two is evidence that the document is enough to recover
+a wallet without this project's software.
+
+    python doc/verify-derivation.py
+
+Exits non-zero if any address disagrees.
+"""
+
+import hashlib
+import hmac
+import sys
+
+MNEMONIC = ("abandon abandon abandon abandon abandon abandon "
+            "abandon abandon abandon abandon abandon about")
+COIN_TYPE = 4346950          # 0x425446, the ASCII bytes "BTF"
+ADDRESS_VERSION = 25         # 0x19, so addresses start with "B"
+HARDENED = 0x80000000
+
+LEGACY = [
+    "BHJNmVvkVv59fgn7gmgP78BtciQi2HY8Hy",
+    "B5qh9opG8sH8Mv9k2xzHoTeSUd9BkT6XEZ",
+    "BCNH8uGyvkiz3uXjhA9iiF27PWAaTStNin",
+    "BC1QNaXuTPGDgLZy53PghZMHEmZcp5GLgD",
+]
+
+BIP44_EXTERNAL = [
+    "BF1ukigB1afmqxH64gJymPwUqFBrRqWbrb",
+    "BACY8pcuCapNQr897eRHroNrgN38GSsEzV",
+    "BMzkMN2k1phNBqy8RPb4Pv1i2QpwsWkKPa",
+    "BNPZ8U6FHXr9Ererk8psyM2RqEVtF6sfBQ",
+]
+
+# ---- secp256k1, plain and slow on purpose: it should be readable ------------
+
+P = 2**256 - 2**32 - 977
+N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
+G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
+     0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)
+
+
+def point_add(p, q):
+    if p is None:
+        return q
+    if q is None:
+        return p
+    if p[0] == q[0] and (p[1] + q[1]) % P == 0:
+        return None
+    if p == q:
+        lam = 3 * p[0] * p[0] * pow(2 * p[1], P - 2, P) % P
+    else:
+        lam = (q[1] - p[1]) * pow(q[0] - p[0], P - 2, P) % P
+    x = (lam * lam - p[0] - q[0]) % P
+    return (x, (lam * (p[0] - x) - p[1]) % P)
+
+
+def point_mul(k, p=G):
+    result = None
+    while k:
+        if k & 1:
+            result = point_add(result, p)
+        p = point_add(p, p)
+        k >>= 1
+    return result
+
+
+def pub_uncompressed(point):
+    return b"\x04" + point[0].to_bytes(32, "big") + point[1].to_bytes(32, "big")
+
+
+def pub_compressed(point):
+    return bytes([2 + (point[1] & 1)]) + point[0].to_bytes(32, "big")
+
+
+# ---- encoding --------------------------------------------------------------
+
+def base58check(payload):
+    alphabet = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"
+    checksum = hashlib.sha256(hashlib.sha256(payload).digest()).digest()[:4]
+    data = payload + checksum
+    number = int.from_bytes(data, "big")
+    out = ""
+    while number:
+        number, rem = divmod(number, 58)
+        out = alphabet[rem] + out
+    leading_zeros = len(data) - len(data.lstrip(b"\x00"))
+    return "1" * leading_zeros + out
+
+
+def address(privkey):
+    pub = pub_uncompressed(point_mul(privkey))
+    h160 = hashlib.new("ripemd160", hashlib.sha256(pub).digest()).digest()
+    return base58check(bytes([ADDRESS_VERSION]) + h160)
+
+
+# ---- BIP-39 and BIP-32 -----------------------------------------------------
+
+def master_from_mnemonic(mnemonic, passphrase=""):
+    seed = hashlib.pbkdf2_hmac("sha512", mnemonic.encode("utf-8"),
+                               ("mnemonic" + passphrase).encode("utf-8"),
+                               2048, 64)
+    i = hmac.new(b"Bitcoin seed", seed, hashlib.sha512).digest()
+    return int.from_bytes(i[:32], "big"), i[32:]
+
+
+def ckd_priv(key, chain, index):
+    if index >= HARDENED:
+        data = b"\x00" + key.to_bytes(32, "big")
+    else:
+        data = pub_compressed(point_mul(key))
+    i = hmac.new(chain, data + index.to_bytes(4, "big"), hashlib.sha512).digest()
+    return (int.from_bytes(i[:32], "big") + key) % N, i[32:]
+
+
+def derive(path):
+    key, chain = master_from_mnemonic(MNEMONIC)
+    for index in path:
+        key, chain = ckd_priv(key, chain, index)
+    return key
+
+
+# ---- the check -------------------------------------------------------------
+
+def main():
+    failures = 0
+
+    print("legacy   m/i'")
+    for i, expected in enumerate(LEGACY):
+        got = address(derive([i + HARDENED]))
+        ok = got == expected
+        failures += 0 if ok else 1
+        print("  m/%d'  %s %s" % (i, got, "ok" if ok else
+                                  "MISMATCH, wallet says " + expected))
+
+    print()
+    print("bip-44   m/44'/%d'/0'/0/i" % COIN_TYPE)
+    for i, expected in enumerate(BIP44_EXTERNAL):
+        got = address(derive([44 + HARDENED, COIN_TYPE + HARDENED,
+                              0 + HARDENED, 0, i]))
+        ok = got == expected
+        failures += 0 if ok else 1
+        print("  .../%d  %s %s" % (i, got, "ok" if ok else
+                                   "MISMATCH, wallet says " + expected))
+
+    print()
+    if failures:
+        print("%d address(es) disagree -- doc/derivation.md is wrong" % failures)
+        return 1
+    print("all addresses match: the document reproduces the wallet")
+    return 0
+
+
+if __name__ == "__main__":
+    sys.exit(main())