feat(merkle): annotated Merkle trees (sum/aggregate/range/spatial)

[hartsock]

Summary

Add one implementation seam that yields a whole family of authenticated structures: Merkle trees whose nodes carry annotations (sums, counts, min/max, interval bounds, MBRs) inside the hashed bytes, so a verifier recombines child annotations at every link and aggregate answers become provable. This folds Merkle-sum / proof-of-liabilities trees (Maxwell, DAPOL+), the MS-SMT (Taproot Assets), authenticated segment/interval trees (IntegriDB), and Merkle R-trees/quadtrees into a single Annotation monoid seam with per-profile instantiations.

MVP for this issue (one-issue-one-PR ratchet): the annotation seam + AnnotatedNode shape + one profile (checked u64 sum) + one proof kind (inclusion proof with annotation recombination), behind a default-off cargo feature with explicitly NON-FROZEN bytes. Everything else is a named follow-up. Lands under epic #17's merkle-layer track.

Why (the telescope)

Users don't need "a tree with numbers in it" — they need aggregate claims that carry their own proof:

• Proof of liabilities: "the total owed is X, and my balance is included in it" — verifiable by each user with an O(log n) path, without the operator revealing (or being able to hide) other balances.
• Verifiable aggregation: COUNT/SUM/MIN/MAX answers over data held by an untrusted store, checkable without fetching the whole dataset.
• Tamper-evident indexes: the aggregate index (sums, bounds) is part of the content address itself, so a store cannot serve a stale or doctored index for fresh data.

This is the crate's thesis — data that carries its own proof of integrity, intrinsically — extended from "these bytes are what they claim" to "this total / bound / count is what it claims." The sum-splitting attack against naive sum trees (hashing only the aggregate, not the children's aggregates) is exactly the kind of failure this crate exists to make structurally impossible.

Structure & CID linkage

Why MerkleNode cannot be reused as-is. src/merkle.rs's MerkleNode<T> holds parents in a BTreeSet<ContentId>: deduplicated, content-ordered, causal-set semantics. Annotated trees need the opposite on every axis: links point downward to children, order is positional and significant (an interval tree's canonical covering of [a,b] depends on left/right structure; swapping children must change the id), duplicates are legal in principle, and — critically — each link must carry its child's annotation alongside the ContentId. Per the documented design seam, this issue introduces a sibling node shape with Vec-shaped, annotation-bearing child links and the same ContentAddressable derivation through src/canonical.rs.

The node shape and the core rule. Every node is:

• payload: Option<T> — leaf content (Some at leaves),
• ann: A — this node's own annotation,
• children: Vec<AnnotatedLink<A>> — positional child links, where AnnotatedLink { link: ContentId, ann: A }.

The core rule (the anti-sum-splitting law): each child's annotation is embedded in the parent's canonical dag-cbor bytes, i.e. in the parent's hash preimage. With CID linkage this binding is doubly structural: the parent's ContentId commits to every (link, ann) pair, and each child's ContentId independently commits to that child's own ann (because the annotation lives inside the child's canonical bytes). A prover cannot present the same tree with two different sums.

The double binding does create one obligation the verifier must discharge explicitly: a link's stored ann and the resolved child's own ann field are two separate commitments to the same value, and nothing forces them equal at construction time in an adversarial tree. Every walk therefore checks link/child annotation agreement (each resolved child's own ann equals the ann on the link that named it) — otherwise a subtree could claim one total in its parent's link and a different one in its own bytes while every node still passes its node-local conservation check. This agreement premise is load-bearing in the conservation-soundness law below.

How it relates to src/content_id.rs. The node implements ContentAddressable (src/trait_def.rs) with canonical_form deferring to to_canonical_dagcbor, so its identity is a standard ContentId (frozen v1 CID params) and each child link serializes as the frozen tag-42 IPLD link form. No bespoke hashing anywhere — proof verification is literally "reconstruct the node's canonical bytes, derive its ContentId, compare."

Discoverability & traversal by root CID. Given only the root ContentId and a CID-resolving lookup (get: &ContentId -> bytes), a verifier fetches bytes, checks them against the CID (ContentId::from_canonical_bytes / verify()), decodes the node, and recurses into children. Two node-local checks make partial audits of arbitrary subtrees meaningful without fetching the whole DAG: conservation — node.ann == fold(combine, children[..].ann) — and link/child agreement — each resolved child's own ann equals the link's ann. The annotations thereby act as a verifiable aggregate index over the DAG.

API sketch (Rust)

New module src/annotated.rs behind a new default-off feature annotated-merkle (it does not depend on the merkle feature: it shares the trait_def/canonical/content_id seams, not MerkleNode itself; CI exercises both via --all-features). New file stays under the soft 2,500-line cap.

/// The annotation seam: a monoid over annotation values.
/// Laws name PROPERTIES (associativity, identity, determinism of encoding);
/// profiles pin concrete types. `combine` is fallible so profiles can refuse
/// degenerate results (e.g. integer overflow) instead of wrapping.
pub trait Annotation: Serialize + DeserializeOwned + Clone + Eq {
    fn identity() -> Self;
    fn combine(&self, other: &Self) -> Result<Self, ContentError>;
}

/// MVP profile: conserved u64 total via checked_add (overflow => Err, never wrap).
pub struct Sum(pub u64);

/// A positional child link binding the child's ContentId AND its annotation
/// into the parent's hash preimage (the core anti-sum-splitting rule).
pub struct AnnotatedLink<A> { pub link: ContentId, pub ann: A }

pub struct AnnotatedNode<T, A> {
    pub payload: Option<T>,              // Some at leaves
    pub ann: A,                          // this node's own annotation
    pub children: Vec<AnnotatedLink<A>>, // positional, order-significant
}

impl<T: Serialize, A: Annotation> ContentAddressable for AnnotatedNode<T, A> {
    fn canonical_form(&self) -> Result<Vec<u8>, ContentError> { /* to_canonical_dagcbor */ }
}

impl<T: Serialize, A: Annotation> AnnotatedNode<T, A> {
    pub fn leaf(payload: T, ann: A) -> Self;
    /// Internal node; ann is DERIVED by folding child annotations (never caller-supplied).
    pub fn internal(children: Vec<AnnotatedLink<A>>) -> Result<Self, ContentError>;
    /// Node-local conservation: ann == fold(combine, children anns). Mismatch = Ok(false).
    pub fn check_local(&self) -> Result<bool, ContentError>;
    pub fn id(&self) -> Result<ContentId, ContentError>;
}

/// Inclusion proof: for each level, the full sibling `(link, ann)` context and
/// the position of the proven child. Verification RECONSTRUCTS each parent's
/// canonical bytes (deriving each parent's ann by folding, which enforces
/// conservation by construction at every step), re-derives its ContentId,
/// compares the final id against `root`, and compares the derived root
/// annotation against `root_ann` — the published total (e.g. total
/// liabilities) the caller is auditing against.
pub struct InclusionProof<A> { /* Vec of per-level (position, sibling AnnotatedLinks) */ }

pub fn verify_inclusion<A: Annotation>(
    root: &ContentId,
    root_ann: &A,
    leaf: &ContentId,
    leaf_ann: &A,
    proof: &InclusionProof<A>,
) -> Result<bool, ContentError>;

/// MVP builder: balanced binary sum tree from leaves; emits every node's
/// (ContentId, canonical bytes) through a caller-supplied sink and returns the
/// root id. Traversal helpers take a minimal CID-resolving lookup
/// (e.g. `impl FnMut(&ContentId) -> Result<Option<Vec<u8>>, ContentError>`),
/// verify every fetched node's bytes against its CID, and check link/child
/// annotation agreement on every edge; a real store trait is a cross-cutting
/// seam (sibling issue in this epic).

Overflow in Sum::combine surfaces as a new ContentError variant — src/error.rs keeps the enum #[non_exhaustive] precisely so a new variant is a sanctioned, non-breaking addition.

Proof obligations

Law minimalism: four laws, each load-bearing, each naming a property (the CID already self-describes codec+hash; no law names an algorithm).

1. Annotation binding (anti-sum-splitting) [Lean] — The canonical encoding of AnnotatedNode is injective on (payload, ann, children) including every child's (link, ann) pair: altering any child annotation changes the parent's canonical bytes, hence its ContentId (up to hash collision-resistance, which is assumed as a property, not proven). This is the law whose absence enables the known sum-splitting attack.
2. Profile monoid laws [Lean] — For each shipped profile (Sum in this MVP): combine is associative and identity is neutral on the defined (non-overflowing) fragment; overflow is Err, never a wrapped value.
3. Conservation soundness [Lean] — If every node in a tree passes check_local, every link resolves to bytes matching its ContentId, and every link's ann equals its resolved child's own ann (link/child agreement), then the root annotation equals the monoid fold of the leaf annotations (induction on tree structure). The agreement premise is load-bearing: the link-side and child-side commitments to an annotation are distinct, and without checking they agree the statement is false — which is why the traversal walk checks it on every edge. Corollary: a per-user (link, ann) path proof against a published root total is sound.
4. Untrusted-store walk safety [TLA+] — A verifier resolving from a root ContentId against an adversarial store never incorporates bytes that fail CID verification (or an edge that fails link/child agreement) into an accepted answer, and the walk terminates on any finite store (visited-set on CIDs). This is protocol/interaction-shaped, hence TLA+.

Obligations are recorded in this issue and the module docs; discharging them may land in a formal follow-up (sibling issue in this epic) — but law 1 and law 3 must at minimum have direct regression tests in this PR (see acceptance criteria).

Python exposure

Not MVP-blocking, tracked as a follow-up (sibling issue in this epic): content-addressable-py grows verification-side support first — verify_inclusion plus the Sum profile — so Python auditors can check proofs produced by Rust provers over the existing PyO3/pythonize surface. Cross-language byte parity for annotated nodes joins the promised Merkle conformance-vector effort (same NON-FROZEN status as MerkleNode; deliberately excluded from tests/vectors.json, per #12). Distribution is unchanged: the existing maturin + tag-driven Trusted Publishing pipeline (#14).

Acceptance criteria

• src/annotated.rs behind new default-off feature annotated-merkle; plain cargo build / cargo test compiles none of it; CI and pre-push exercise it via --all-features.
• Module docs carry the same ⚠️ BYTES ARE NON-FROZEN banner and rationale as src/merkle.rs, including the field-key-strings-are-load-bearing note; byte freeze explicitly deferred to the Merkle conformance vectors follow-up (Epic: Road to 0.1.0-rc1 — freeze the byte/wire contract + ship the Merkle layer #17). No annotated-node vectors added to tests/vectors.json.
• Module docs state the MerkleNode non-reuse rationale (causal-set parents vs. positional annotated children) and cross-link both modules.
• Annotation trait + Sum profile with checked arithmetic; overflow returns Err via a new #[non_exhaustive]-sanctioned ContentError variant — never a wrapped value, never a panic.
• Sum-splitting regression test: construct a valid tree, tamper with one child annotation in a proof/node, assert the derived ContentId changes and verify_inclusion / check_local reject (documents the attack by name in the test docstring).
• Link/child disagreement regression test: construct a tree where every node passes check_local in isolation but one link's ann differs from its resolved child's own ann; assert the traversal walk rejects it (documents in the docstring why node-local conservation alone is insufficient — the agreement premise of law 3).
• Property tests (e.g. proptest as a dev-dependency) for: id determinism; child-order significance (swapping two children changes the id — the inverse of MerkleNode's insertion-order-independence test); conservation (internal derives ann = fold of children, check_local accepts); monoid laws for Sum on non-overflowing inputs; dag-cbor round-trip of nodes.
• Inclusion proof: happy path verifies against root id and the published root annotation (root_ann); negative paths (wrong leaf, wrong position, wrong root annotation, tampered sibling link, tampered sibling annotation) all reject with Ok(false), matching the frozen verify mismatch contract (decide: freeze verify() mismatch contract; add ensure_content_id strict helper #8).
• Traversal helper walks a tree from root ContentId via a caller-supplied lookup, verifying every fetched node's bytes against its CID before decoding and checking link/child annotation agreement on every edge.
• Proof obligations 1–4 recorded in module docs with their [Lean]/[TLA+] tags; laws 1 and 3 covered by direct tests in this PR.
• Zero warnings (cargo clippy -- -D warnings), cargo fmt clean, all existing tests (including --all-features) pass; no change to any frozen surface (ContentId params, serde forms, tests/vectors.json).

Non-goals / follow-ups

• SMT × sum (MS-SMT profile) — sparse-Merkle keying so exclusion proofs double as proof-of-no-hidden-balance (sibling issue in this epic).
• Range/interval profile (IntegriDB-style) — committed [min,max] bounds annotation + canonical-covering proofs for verifiable COUNT/SUM/MIN/MAX over [a,b], and the nested d-dimensional composition via CID links (sibling issue in this epic).
• Spatial profile (MR-tree / Merkle quadtree) — MBR annotations + window/kNN completeness verification; note history-independence holds only for pinned-split-rule structures (quadtree/KD), not insertion-order-dependent R-trees (sibling issue in this epic).
• Privacy layer — Pedersen commitments, Bulletproofs range proofs, user-count padding (DAPOL+) are out of scope for this crate; they belong to a consumer layer.
• Store trait — this MVP takes a minimal lookup closure; the shared CID-resolving store seam is cross-cutting (sibling issue in this epic).
• Byte freeze / conformance vectors — annotated-node bytes freeze together with the Merkle conformance vectors toward 0.1.0-rc1 (Epic: Road to 0.1.0-rc1 — freeze the byte/wire contract + ship the Merkle layer #17).
• Python bindings — verification-side exposure per the Python exposure section (sibling issue in this epic).

References

• Ji & Chalkias, "Generalized Proof of Liabilities", CCS 2021 (DAPOL+)
• MS-SMT design, Taproot Assets: https://github.com/Roasbeef/bips/blob/bip-taro/bip-taro-ms-smt.mediawiki
• Zhang, Katz, Papamanthou, "IntegriDB: Verifiable SQL for Outsourced Databases", CCS 2015
• Yang, Papadias, Papadopoulos, Kalnis, "Authenticated Indexing for Outsourced Spatial Databases", VLDB J. 2009
• Repo: src/content_id.rs (frozen ContentId), src/trait_def.rs (ContentAddressable), src/canonical.rs (canonical dag-cbor), src/merkle.rs (MerkleNode, causal-set parents + NON-FROZEN precedent)
• Epic Epic: Road to 0.1.0-rc1 — freeze the byte/wire contract + ship the Merkle layer #17 (Road to 0.1.0-rc1); decide: freeze verify() mismatch contract; add ensure_content_id strict helper #8 (frozen verify mismatch contract); feat: add feature-gated merkle module (MerkleNode DAG-node helper) #11 (MerkleNode); test: golden conformance vectors + Rust↔Python byte-parity gate #12 (frozen golden vectors exclude merkle bytes); ci: tag-driven multi-platform wheels + crates.io via Trusted Publishing; retire manual maturin upload #14 (tag-driven release pipeline)

---

Part of #30 (Merkle structure catalog epic).