docs: one documentation directory, not two (#137)

docs/ has held the README's images since the fair-launch release. I
added doc/ yesterday for the derivation spec without looking, and #108
then correctly used docs/ -- leaving the repository with both, one
letter apart, which is the kind of thing that quietly costs someone ten
minutes a year forever.

The mistake was mine, so the move is mine: derivation.md and
verify-derivation.py go to docs/, and the two README links follow.

No content changes. The verifier still reproduces the wallet from its
new path, which is the only thing here that can actually break.

2 files changed, 284 insertions, 0 deletions

diff --git a/docs/derivation.md b/docs/derivation.md
new file mode 100644
index 0000000..c5ee3ad
--- /dev/null
+++ b/docs/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 `docs/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 docs/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/docs/verify-derivation.py b/docs/verify-derivation.py
new file mode 100644
index 0000000..ba8e883
--- /dev/null
+++ b/docs/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())