js-merkle-streaming-proof-pruning

Answer

Done. I implemented and verified the solution; the deliverable is ~/merkle/SOLUTION.md (self-contained: root-cause analysis, full merkle.js, test suite, how to run).

Root cause (short)

A naive streaming prover emits well-formed but wrong proofs because it doesn't treat a proof as an atomic value bound to one tree snapshot:

1. Live mutable root during proof assembly → proof mixes two trees.
2. Pruning without pinning in-flight work → missing node silently substituted.
3. No count binding in H(l||r) → tree-shape ambiguity.
4. No leaf-index binding in H(data) → payload replay after insertion.
5. Non-deterministic range decomposition → boundary drift / empty-range bypass.
6. Non-canonical encoding → multiple byte forms of one proof.

The fix

• RFC-6962-style tree with hardened, domain-separated hashing: leafHash(i,data)=SHA256(0x00‖u64(i)‖u32(len)‖data), nodeHash(l,r,count)=SHA256(0x01‖u64(count)‖l‖r), deterministic split k = largest power of two < count.
• proveRange captures (n, root) synchronously, sets a freeze, pins every fringe node/leaf, and materialises all hashes + leaf copies before any await.
• Verifier rebuilds the same skeleton from (n,start,end) and checks leaf set, fringe count, each [lo,hi) boundary, root reproduction, and expected root.
• Strict LRU cap on nodes/leaves; evicted old ranges throw RangePrunedError — never a guessed hash.
• Versioned binary encoding with strict decode (rejects trailing bytes).

Verification

node --test test.js → 14/14 pass, covering all ranges for n≤40, canonical encoding, tamper/boundary/size/index rejection, empty-range replay, append-racing-proof isolation, memory-cap enforcement, pinning, and a 300-seed fuzz proving no mutation verifies against the wrong root.

Files: merkle.js (implementation), test.js (suite), SOLUTION.md (writeup with both embedded).