Verification: P0.8.1 η Merkle Tree Construction

Task: P0.8.1 — first η (Proof Store) surface Branch: feature/p0-8-1-merkle-tree Date: 2026-04-17 Commit: bcb36a2d Verifier: T3 Executor (Claude Sonnet 4.6)

1. Gate results

Gate	Command	Result
Unit tests (targeted)	`node --experimental-vm-modules ... jest --testPathPattern="proof/merkle" --coverage`	PASS — 22/22
Full suite	`npm test`	PASS — 724/724
Lint	`npm run lint`	PASS — 0 errors
Build	`npm run build`	PASS — 0 errors

2. Test evidence (targeted run)

PASS src/__tests__/domains/proof/merkle.test.ts
  EMPTY_TREE_ROOT
    ✓ equals sha256 of empty string
    ✓ is the canonical value e3b0c44...
    ✓ is a 64-char lowercase hex string
  buildMerkleTree
    ✓ returns EMPTY_TREE_ROOT when given an empty array
    ✓ returns a tree object for an empty array
    ✓ returns a 64-char lowercase hex root for a single leaf
    ✓ returns a 64-char lowercase hex root for 10 leaves
    ✓ is deterministic: same 10 hashes → same root across two calls
    ✓ is deterministic: shuffled input order → same root (sortPairs)
    ✓ root for 10 leaves differs from EMPTY_TREE_ROOT
    ✓ creates a new tree instance on each call (no caching)
  generateProof
    ✓ returns non-empty proof for a leaf in the tree
    ✓ returns an array of {position, data} nodes
    ✓ returns [] for a hash not in the tree
  verifyProof
    ✓ returns true for a valid proof (round-trip from generateProof)
    ✓ returns false for an empty proof with a non-trivial tree
    ✓ returns false for a tampered proof node (data mutated)
    ✓ returns false when the root does not match the proof
    ✓ returns false when the leaf hash does not match the proof
  proof round-trip for every leaf in a 5-leaf tree
    ✓ verifies all 5 leaves
  single-leaf tree edge case
    ✓ buildMerkleTree([h]) produces a non-empty, non-EMPTY_TREE_ROOT root
    ✓ proof round-trip works for single-leaf tree

Tests: 22 passed, 22 total

3. Coverage report (merkle.ts)

src/domains/proof | 100 | 100 | 100 | 100 |
  merkle.ts       | 100 | 100 | 100 | 100 |

Full 100% statement, branch, function, and line coverage.

4. Full suite summary

Test Suites: 15 passed, 15 total
Tests:       724 passed, 724 total  (+22 new from this task)

No regressions in any existing test suite.

5. Acceptance criteria sign-off

#	Criterion	Evidence
AC1	Uses `merkletreejs` with SHA-256 leaves	`package.json` dep; `merkle.ts` imports `MerkleTree` from `merkletreejs`
AC2	`buildMerkleTree(hashes)` → `{ root, tree }`, root is hex	Tests: 64-char hex root for single leaf + 10 leaves
AC3	`generateProof(tree, leafHash)` → `{position,data}[]`	Tests: shape check + not-a-member empty array
AC4	`verifyProof(root, proof, leafHash)` → boolean	Tests: round-trip true + 4 false cases
AC5	Empty tree: `root === EMPTY_TREE_ROOT === sha256('')`	Tests: pinned value `e3b0c44...`; AC5 buildMerkleTree([]) returns EMPTY_TREE_ROOT
AC6	10-leaf determinism; valid proof; invalid rejected; empty-tree	Tests: determinism (same order + shuffled); round-trip true; tamper/wrong-root/wrong-leaf false; empty-tree

All 6 acceptance criteria met.

6. Dependency note

merkletreejs@0.6.0 ships its own TypeScript declarations at dist/index.d.ts. No @types/merkletreejs required.

7. Implementation note: `sortPairs` vs `sortLeaves`

The contract initially stated sortPairs: true alone was sufficient for order- independence. During Step 4 implementation, testing revealed that sortPairs only affects sibling pairs during internal-node hashing; it does NOT sort the initial leaf array. sortLeaves: true is required to make the tree invariant to input order. Both options are now used (see TREE_OPTIONS constant in merkle.ts). The contract was updated to reflect this in §2.2. The packet is a planning doc and was not retroactively modified.

8. 5-step commit chain

Step	Commit SHA	Message
1. Audit	`6339c726`	`audit(p0-8-1-merkle-tree): first η surface — inventory deps + crypto primitives`
2. Contract	`5e3b5530`	`contract(p0-8-1-merkle-tree): build/proof/verify API + empty-tree convention`
3. Packet	`5e10a52f`	`packet(p0-8-1-merkle-tree): execution plan + dep install`
4. Implement	`bcb36a2d`	`feat(p0-8-1-merkle-tree): build/proof/verify with merkletreejs SHA-256`
5. Verify	(this commit)	`verify(p0-8-1-merkle-tree): tests + gate evidence`

9. Residual risks

Risk	Likelihood	Notes
`merkletreejs` CJS/ESM boundary in future Node versions	Low	Current Node 20 + esModuleInterop handles well; lib is actively maintained
Proof serialization for DB storage	N/A	Deferred to P0.8.2/P0.8.3 — `Buffer` objects in proof are not yet serialized
`sortLeaves` interaction with duplicate leaves	Low	Not tested; callers should deduplicate if needed