Packet: P0.8.1 η Merkle Tree Construction

Task: P0.8.1 Branch: feature/p0-8-1-merkle-tree Date: 2026-04-17 Gate: Contract approved (Step 2 committed). Proceeding to Step 4.

1. Execution plan

Phase A — dependency install

cd .worktrees/claude/p0-8-1-merkle-tree
npm install merkletreejs --save

After install, verify:

package.json now lists "merkletreejs" in dependencies
node_modules/merkletreejs/index.d.ts exists (own types shipped)
If types absent: npm install --save-dev @types/merkletreejs

Commit package.json + package-lock.json together with the implementation commit.

Phase B — implementation files

B.1 `src/domains/proof/merkle.ts`

New file. Approximately 80 lines. Structure:

file-level JSDoc block (purpose, references, purity guarantees)
import { createHash } from 'node:crypto';
import { MerkleTree } from 'merkletreejs';

// ── Constants ──────────────────────────────────────────────────────────────
export const EMPTY_TREE_ROOT: string = createHash('sha256').update('').digest('hex');

// ── Types ──────────────────────────────────────────────────────────────────
export type MerkleProofNode = { position: 'left' | 'right'; data: Buffer };
export type MerkleProof = MerkleProofNode[];
export interface MerkleTreeResult { root: string; tree: MerkleTree; }

// ── Internal hash fn ───────────────────────────────────────────────────────
const sha256 = (data: Buffer): Buffer => createHash('sha256').update(data).digest();

// ── Exports ────────────────────────────────────────────────────────────────
export function buildMerkleTree(recordHashes: string[]): MerkleTreeResult
export function generateProof(tree: MerkleTree, leafHash: string): MerkleProof
export function verifyProof(root: string, proof: MerkleProof, leafHash: string): boolean

Full bodies per contract §2.2–§2.4.

B.2 `src/tests/domains/proof/merkle.test.ts`

New file. Target: ≥12 tests.

Test plan:

#	Test	Method
1	`EMPTY_TREE_ROOT` equals `sha256('')`	Assert constant value == `e3b0c44...`
2	`buildMerkleTree([])` returns `EMPTY_TREE_ROOT`	edge case
3	`buildMerkleTree([h1])` root is 64-char hex	single leaf
4	`buildMerkleTree(10 hashes)` root is 64-char hex	happy path
5	Determinism: same 10 hashes → same root	insert twice, assertEqual
6	Determinism: shuffled order → same root	shuffle, assertEqual
7	`generateProof(tree, h1)` returns non-empty array for leaf in tree	membership
8	`generateProof(tree, nonLeaf)` returns `[]`	not-a-member
9	Valid proof verifies: `verifyProof(root, proof, leafHash)` is `true`	round-trip
10	Invalid proof rejected: tampered node data → `false`	security
11	Wrong root rejected: `verifyProof(wrongRoot, proof, leafHash)` is `false`	security
12	Wrong leaf rejected: `verifyProof(root, proof, wrongLeaf)` is `false`	security
13	Proof for every leaf in 5-leaf tree verifies (loop)	exhaustive
14	`buildMerkleTree([h1])` proof round-trip (tree size 1 edge case)	edge case

Phase C — gates

npm test -- --testPathPattern="proof/merkle"   # unit tests first
npm test                                        # full suite
npm run lint
npm run build

All four must pass before Step 5.

2. File delta summary

File	Action
`package.json`	Add `"merkletreejs": "<version>"` to `dependencies`
`package-lock.json`	Updated lock
`src/domains/proof/merkle.ts`	Create (~80 lines)
`src/__tests__/domains/proof/merkle.test.ts`	Create (~120 lines)

3. Commit plan

Step	Files	Message
4 (impl)	`src/domains/proof/merkle.ts` + `src/__tests__/...` + `package.json` + `package-lock.json`	`feat(p0-8-1-merkle-tree): build/proof/verify with merkletreejs SHA-256`
5 (verify)	`docs/verification/p0-8-1-merkle-tree-verification.md`	`verify(p0-8-1-merkle-tree): tests + gate evidence`

4. Risk mitigations

Risk	Mitigation
`merkletreejs` CJS + ESM import	Use named import `{ MerkleTree }` (not `import MerkleTree from ...`). TS `esModuleInterop` handles interop.
Types absent post-install	Check `node_modules/merkletreejs/index.d.ts`; add `@types/merkletreejs` dev-dep if missing.
Empty Buffer root from merkletreejs	Special-case in `buildMerkleTree`: if `recordHashes.length === 0` return `EMPTY_TREE_ROOT` before calling `tree.getRoot()`.
`sortPairs` omitted	Hard-code `{ sortPairs: true }` in both construction AND `MerkleTree.verify` call.
Tampered-proof test flakiness	Use a deterministic set of hashes (not `Math.random()`); mutate a specific byte index.