WO-03 — Merkle and event roots

Historical report. WO-03b supersedes the unbound root and proof API below. See WO-03b-REPORT.md for the approved count seal and new evidence.

7 October 2026 · Local checks passed; stopped after step 7. Awaiting Claude’s independent review.

Branch: wo-03-merkle, from wo-04-bech32m at 307167a. Python reference and vectors frozen in e375e7b before C++ implementation. Scope: CHAIN-DESIGN §2b/§2f and the owner’s approved opaque event interface. Section 2g is used for synthetic fixtures; event validation remains WO-08/09.

Delivered

  • E46::merkle: tagged SHAKE256 leaf/node hashing, tree construction, transaction roots, inclusion proof creation/verification, event sorting and event roots.

  • Transaction IDs retain block order. Odd nodes carry unchanged. Empty roots are 32 zero bytes; singleton roots are tagged leaf hashes.

  • Events sort ascending by type byte, then lexicographic unsigned ID bytes. Duplicate (type, ID) pairs are rejected even if bodies differ. Types other than 0x02 and 0x03 are rejected.

  • Independent recursive Python reference; C++ builds levels iteratively. Frozen vectors, batch CLI, unit/differential tests, parser fuzzer and benchmark.

  • UNC formatting; warnings are errors. Standard hashing uses the existing WO-02 wrapper. No SHA-2, floating-point consensus arithmetic or difficulty constants.

Results

Evidence: summary, source fingerprints, and command logs in the same directory. Results are local implementation checks, not an independent security audit.

Gate

Result

Python/C++ differential

37,339 comparisons, zero mismatches, including 1,000 seeded random trees

Required golden sizes

0, 1, 2, 3, 5, 1,000 leaves for both transaction and event trees

Inclusion paths

8,385 paths over every position at sizes 1–129, with root/body/index/sibling mutations and missing/extra siblings

Edge cases

Odd carry, empty/singleton, leaf/node separation, raw byte ordering, prefix IDs, same ID across different types, duplicate rejection, maximum size_t verification arguments

Release suite

11/11 passed

ASan/UBSan suite

11/11 passed, sanitizer recovery disabled

Golden regeneration

Byte-for-byte identical; prior WOs’ golden files unchanged

Formatting

New C++ files pass clang-format --dry-run --Werror

Parser fuzzing

168,383 executions in 31 seconds, one worker, no crashes or sanitizer errors

Benchmark

Median 1,173.87 roots/second for 1,000 transaction IDs, one worker, five approximately 0.25-second samples

Golden/fuzzer seed: 2026100703. Benchmark includes tree allocation and hashing; it is host/load-specific. Release: Apple Clang 21, macOS arm64. Fuzzer: the already-installed Homebrew LLVM 22. At most four compiler jobs, one test/fuzz worker.

API boundary and proof semantics

Header: e46/include/e46/merkle.hpp.

Event{type, id, body} accepts a serialized body without its type byte. event_leaf() produces exactly type || body; the supplied ID is a sort key and is not inserted into the leaf. event_tree() proofs index the sorted order; sorted_events() exposes that order without mutating the caller’s input.

The library does not derive IDs, check their lengths/binding, parse event bodies, verify Rad collisions or evaluate commitment work. Opaque or empty bodies/IDs are representable by this primitive; that does not make them valid chain events. WO-08/09 must validate these before accepting a block. Synthetic §2g fixtures use actual serialized layouts and derived IDs, but do not claim mined validity.

Proofs contain 32-byte siblings, bottom up, omitting carried levels. verify() requires the expected root, leaf bytes, index and expected leaf count. It rejects impossible positions and missing/extra siblings before hashing. Bad proof contents return false; invalid construction indices and event envelopes throw std::invalid_argument. SHAKE provider failures propagate.

The expected count needs authenticated context. A sibling digest hides the size of its subtree. For example, the first leaf’s path in a three-leaf tree can also verify with a claimed count of four, because the last sibling is opaque. A regression test demonstrates this limitation. This API proves inclusion for the supplied context; it does not independently authenticate that count or the semantic validity of an event. No new consensus serialization was introduced.

Paradox A carried forward

WO-03 contains no mining difficulty constants. The owner’s provisional Z_base = 43 and Z_commit = 18 are not used here. WO-08/09 must measure the exact §2g inputs and nonce-bound puzzle shape: 48-byte Rad candidate hashes and 55-byte commitment stamp hashes. Prior 12-byte, single-search collision costs must not be substituted for those measurements. This WO supplies tree mechanics only and makes no mining-rate claim.

Re-run and review

cmake --preset release && cmake --build --preset release && ctest --preset release
cmake --preset sanitize && cmake --build --preset sanitize && ctest --preset sanitize
python3 -B e46/golden/generate_wo03.py --check

build/release/merkle_cli reads one command per line:

root <leaf-hex> ...
txroot <32-byte-txid-hex> ...
proof <index> <leaf-hex> ...
verify <root-hex> <leaf-hex> <index> <expected-count> <sibling-hex> ...
event_root <decimal-type>:<id-hex>:<body-hex> ...
event_proof <sorted-index> <decimal-type>:<id-hex>:<body-hex> ...
events <decimal-type>:<id-hex>:<body-hex> ...

Use - for an empty byte field. Responses: OK plus output, OK 1/OK 0 for verification, or ERR for malformed requests. This is a test-tool protocol; its line/token limits do not define block limits or consensus wire encoding.

For fresh-input review, import e46/golden/merkle_reference.py, or use e46/tests/verify_wo03.py --cli build/release/merkle_cli --golden e46/golden/wo03-golden.json --seed <reviewer-seed> (one command). The optional seed adds 1,000 new trees and is not printed by the verifier. Builder tests do not replace Claude’s surprise exam.

No installations, pushes, merges or later WOs. Owner edits to the maps and the separate PR/AnIdea.md proposal are preserved outside WO-03’s commits.