"""Shared sweep harness for the bitGAN Act-1 puzzle.

Two ideas make this faster than the earlier runners.

1.  The twelfth word is never guessed.  Eleven fixed words supply 121 bits of a
    132-bit mnemonic, so the twelfth word carries 7 free entropy bits and 4
    checksum bits.  Exactly 128 of the 2048 words are legal for any one
    ordering, and all 128 are produced directly with 128 SHA-256 calls.

2.  Derivation paths share prefixes, so they are walked as a trie.  Deriving
    m/44'/60'/0'/0/0 and m/44'/60'/0'/0/1 costs one extra level, not two whole
    paths.  This is what makes a 33-path sweep cost about the same as a 5-path
    sweep: PBKDF2 dominates and the trie keeps the marginal path near free.
"""
import hmac, hashlib, json, os, sys
from coincurve import PublicKey
try:                                    # pycryptodome's keccak is the fastest available here
    from Crypto.Hash import keccak as _ck
    def keccak(b): return _ck.new(digest_bits=256, data=b).digest()
except ImportError:
    from eth_utils import keccak
from mnemonic import Mnemonic

WL = Mnemonic("english").wordlist
WIDX = {w: i for i, w in enumerate(WL)}
SHA = hashlib.sha256
N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
TARGET = "0x18f87ec9c527aba1db44f715456bf28b0dae478d"

# ---------------------------------------------------------------- path set
# The 33 most plausible Ethereum layouts.  Earlier runs used three or five.
PATH_STRS = (
    ["m/44'/60'/0'/0/%d" % i for i in range(10)]        # BIP-44 address index 0-9 (MetaMask)
    + ["m/44'/60'/%d'/0/0" % i for i in range(1, 10)]   # Ledger Live account 1-9
    + ["m/44'/60'/0'/0",                                # MEW / Ledger "legacy"
       "m/44'/60'/0'/1/0",                              # change chain
       "m/44'/60'/0'",                                  # truncated account node
       "m/44'/60'/0'/0/0'",                             # hardened address index
       "m/44'/60'/160720'/0/0",                         # Ledger legacy custom
       "m/44'/61'/0'/0/0",                              # Ethereum Classic
       "m/44'/1'/0'/0/0",                               # testnet coin type
       "m/49'/60'/0'/0/0",
       "m/84'/60'/0'/0/0",
       "m/0/0", "m/0/1", "m/0/2", "m/0",                # bare / old-wallet layouts
       "m/0'/0'/0'"]
)

def parse_path(p):
    out = []
    for seg in p.split("/")[1:]:
        h = seg.endswith("'") or seg.endswith("h")
        out.append(int(seg.rstrip("'h")) + (0x80000000 if h else 0))
    return out

PATHS = [tuple(parse_path(p)) for p in PATH_STRS]
NPATHS = len(PATHS)

def seed(mn, pw=""):
    return hashlib.pbkdf2_hmac("sha512", mn.encode(), ("mnemonic" + pw).encode(), 2048, 64)

class Node:
    __slots__ = ("hard", "soft", "term")
    def __init__(self):
        self.hard = []   # (index, Node)  hardened children
        self.soft = []   # (index, Node)  non-hardened children (share one parent pubkey)
        self.term = None # path name if a path ends here

def _compile(paths, names):
    root = Node()
    for name, lv in zip(names, paths):
        cur = root
        for i in lv:
            bucket = cur.hard if i >= 0x80000000 else cur.soft
            nxt = None
            for j, nd in bucket:
                if j == i:
                    nxt = nd; break
            if nxt is None:
                nxt = Node(); bucket.append((i, nxt))
            cur = nxt
        cur.term = name
    return root

TRIE = _compile(PATHS, PATH_STRS)

def _addr(k):
    pub = PublicKey.from_valid_secret(k.to_bytes(32, "big")).format(False)[1:]
    return "0x" + keccak(pub)[-20:].hex()

def walk(sd, targets, hits):
    """Derive every path in the trie from one seed and append (pathname, addr)
    for every derived address that is in `targets`.

    The compressed public key of a node is computed once and reused by all of
    that node's non-hardened children, which is where the earlier per-path
    loops wasted most of their elliptic-curve work."""
    I = hmac.new(b"Bitcoin seed", sd, hashlib.sha512).digest()
    stack = [(TRIE, int.from_bytes(I[:32], "big"), I[32:])]
    while stack:
        node, k, c = stack.pop()
        if node.term is not None:
            a = _addr(k)
            if a in targets:
                hits.append((node.term, a))
        kb = k.to_bytes(32, "big")
        if node.soft:
            pub = PublicKey.from_valid_secret(kb).format(True)
            for i, sub in node.soft:
                J = hmac.new(c, pub + i.to_bytes(4, "big"), hashlib.sha512).digest()
                stack.append((sub, (int.from_bytes(J[:32], "big") + k) % N, J[32:]))
        for i, sub in node.hard:
            J = hmac.new(c, b"\x00" + kb + i.to_bytes(4, "big"), hashlib.sha512).digest()
            stack.append((sub, (int.from_bytes(J[:32], "big") + k) % N, J[32:]))

def endings(words11):
    """Yield the 128 legal 12-word mnemonics for one ordering of eleven words."""
    base = 0
    for w in words11:
        base = (base << 11) | WIDX[w]
    pre = " ".join(words11) + " "
    for L in range(128):
        ent = (base << 7) | L
        j = (L << 4) | (SHA(ent.to_bytes(16, "big")).digest()[0] >> 4)
        yield pre + WL[j]

def plant_address(words11, layer=42, path_i=0):
    """Address of the planted seed: ordering `words11`, checksum layer `layer`,
    derived at PATHS[path_i].  Used to prove a sweep can actually detect a hit."""
    mns = list(endings(words11))
    mn = mns[layer]
    sd = seed(mn)
    hits = []
    # derive just the one path
    I = hmac.new(b"Bitcoin seed", sd, hashlib.sha512).digest()
    k, c = int.from_bytes(I[:32], "big"), I[32:]
    for i in PATHS[path_i]:
        if i >= 0x80000000:
            data = b"\x00" + k.to_bytes(32, "big") + i.to_bytes(4, "big")
        else:
            data = PublicKey.from_valid_secret(k.to_bytes(32, "big")).format(True) + i.to_bytes(4, "big")
        J = hmac.new(c, data, hashlib.sha512).digest()
        k = (int.from_bytes(J[:32], "big") + k) % N
        c = J[32:]
    return mn, _addr(k)

def record_hit(job, label, mn, pathname, addr):
    line = "%s\t%s\t%s\t%s\t%s\n" % (job, label, addr, pathname, mn)
    with open("RECOVERED_HITS.txt", "a") as f:
        f.write(line)
    return line