Module subtree 

Gossip-triggered contiguous-subtree storage proof (ADR-0002).

Pure, network-free core of the audit redesign. Given a peer’s signed StorageCommitment and an auditor-chosen random nonce, both sides deterministically select one contiguous subtree of the committed Merkle tree; the responder expands that subtree to its leaves plus the sibling cut-hashes on the path to the root; the auditor rebuilds the root and spot-checks a few leaves against real chunk bytes.

Three independent checks (ADR-0002 “Verification, three independent checks”); this module owns the first two — the third (response deadline) is enforced by the caller:

1. Structure — verify_subtree_proof re-derives the selected branch from (nonce, key_count), rebuilds the root from the returned leaves and cut-hashes, and requires it to equal the pinned root.
2. Real bytes — select_spotcheck_indices picks a few leaves within the subtree; the caller fetches their bytes and checks both the plain content hash and the nonce freshness hash. Faking a fraction x of leaves survives only (1 - x)^k.

Tree geometry (must match super::commitment::MerkleTree)

Leaves are sorted by key and fill positions 0..N. The tree is left-packed: when a level has an odd number of nodes the last node is paired with itself (node_hash(x, x)). There are no explicit padding leaves; “padding” is the empty right side of a subtree slot that extends past N. Depth D = ceil(log2(N)). A node identified by (depth, slot) (depth measured from the root, slot in 0..2^depth) covers the contiguous leaf range [slot * span, (slot + 1) * span) where span = 2^(D - depth), intersected with 0..N.

Structs

SubtreeLeaf

One leaf of the selected subtree, as returned by the responder.

SubtreePath

The deterministically-selected contiguous subtree, derived from (nonce, key_count) and agreed by both sides.

SubtreePlan

The pure (no-bytes) geometry of a subtree proof.

SubtreeProof

A responder’s single-contiguous-subtree proof (ADR-0002 “The proof”).

Enums

BuildProofError

Why a responder could not build a subtree proof for a challenge.

StructureVerdict

Verdict from verify_subtree_proof’s structural check.

Constants

SMALL_TREE_FULL_AUDIT_FLOOR

Below this key count the whole tree is challenged; sqrt rounding is meaningless for tiny trees and a full proof is cheap.

Functions

build_subtree_proof

Build the single-contiguous-subtree proof for (nonce, tree) (responder).

nonced_leaf_hash

Build the per-leaf nonced freshness hash for a subtree leaf (responder side), reusing the existing audit digest.

select_spotcheck_indices

Pick k distinct nonce-derived leaf positions within the selected subtree.

select_subtree_path

Deterministically select one contiguous subtree from (nonce, key_count).

subtree_leaf

Build one subtree leaf from its key and the chunk bytes the responder holds.

subtree_plan

Compute the SubtreePlan for (nonce, tree) — selection geometry only, no chunk bytes touched.

verify_subtree_proof

Structural verification (ADR-0002 check 1): the returned subtree genuinely belongs to the committed tree.