You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Add src/verkle.rs behind a new default-offverkle cargo feature: the CAS-side carrier for verkle / vector-commitment trees. The crate stores, addresses, and walks the tree — high-arity internal nodes, EIP-6800-shaped stem nodes, and a head object that binds the algebraic world (commitments, openings) to the CAS world (ContentIds, retrieval). The crate performs no curve arithmetic: commitments are opaque, self-describing {scheme multicodec, bytes} values, and opening verification sits behind a narrow CommitmentScheme trait implemented out-of-crate. MVP ships the node shapes, ContentAddressable derivation, a resolver-driven walk from the root CID, and one proof kind: a hash-side inclusion walk verifiable with zero curve ops.
This structure is explicitly adjacent for a hash-CAS crate (curve ops, trusted setup, not post-quantum — the reason Ethereum pivoted to binary trees in EIP-7864). It is cataloged as the proof-size benchmark (~100–150 bytes/key aggregated witnesses) and for one directly transferable idea (the memoized proof-serving cache — a follow-up for the hash-tree entries, not this issue).
Why (the telescope)
The user need is verifiable membership over huge keyed datasets with tiny witnesses: proving "key K maps to value V under this root" to a party who holds only ~32 bytes of trust anchor, without shipping log-n sibling hashes per level. Vector-commitment trees are where that need is served best today, so they are the benchmark every hash-tree entry in this catalog is measured against.
What a CAS uniquely contributes — and what this issue actually builds — is the other half of the trust story: the tree itself must be retrievable and tamper-evident. Identity splits in two:
the commitment (a curve point): what succinct proofs open against;
the CID (the node's canonical bytes): how you fetch the node and prove you got the right bytes.
A CAS must carry both, bound together, or the succinct-proof world floats free of any retrievable data. That binding — plus the rule that a verifier additionally checks each child's stored commitment matches the parent's opening at that index — is the durable, transferable design content here, and it costs no curve code to carry.
Structure & CID linkage
Every node shape implements ContentAddressable (src/trait_def.rs) with the one-line canonical_form deferring to to_canonical_dagcbor (src/canonical.rs), so each node's identity is a frozen-parameter ContentId (src/content_id.rs: CIDv1, dag-cbor 0x71, BLAKE3 0x1e, 32-byte digest) and every child link serializes as a dag-cbor tag-42 IPLD link via ContentId's frozen serde.
Why MerkleNode does not fit (sibling node shapes required).MerkleNode<T> (src/merkle.rs) carries parents: BTreeSet<ContentId> — deduplicated, content-ordered causal-set semantics. Verkle children are the opposite on every axis: they are positional (index-addressed, sparse, arity ≤ 256), they point down (children, not parents), and two distinct indexes may legitimately reference the same child CID (identical subtrees) — a BTreeSet would silently collapse them. So this module ships sibling node shapes with sparse index→CID maps, reusing only the shared ContentAddressable derivation path:
VerkleInternal { commitment, children: map index → ContentId } — sparse, ≤ 256 entries. Indexes serialize as fixed-width two-hex-digit lowercase strings ("00"–"ff") so dag-cbor's string-key rule holds and lexicographic key order equals numeric index order.
VerkleRoot { scheme, params: Option<ContentId> (SRS/setup artifact by CID), commitment, data_root: ContentId } — the head object binding the algebraic world to the CAS world.
Discoverability from the root CID. Given VerkleRoot's CID, a resolver walks: root → data_root → VerkleInternal.children[key[depth]] → … → VerkleStem.slots[suffix] → value CID. The children map makes the tree walkable from the root CID exactly like a hash trie; because each node's id covers its child links, the root CID transitively binds every reachable byte.
Dual-identity verifier rule. A full verifier checks two chains in lockstep: (1) CID chain — each fetched node's bytes re-derive its claimed ContentId; (2) commitment chain — each child's stored commitment matches what the parent's commitment opens to at that index (via the CommitmentScheme seam). The MVP verifies (1) in-crate and exposes (2) as a seam.
API sketch (Rust)
// src/verkle.rs — feature "verkle" (default-OFF; bytes NON-FROZEN)// Sibling of the "merkle" feature; both exercised in CI via --all-features./// Self-describing commitment: laws name PROPERTIES (binding); profiles pin/// schemes via the multicodec `scheme` code. No curve math in this crate.#[derive(Debug,Clone,PartialEq,Eq,Serialize,Deserialize)]pubstructCommitment{pubscheme:u64,// multicodec code for the commitment scheme/// Scheme-defined encoding (e.g. compressed point). Encoding detail to/// settle before vectors: a plain serde derive emits `Vec<u8>` / `[u8; N]`/// as CBOR *integer arrays*; these fields (and `stem`) should land as CBOR/// *byte strings* (dag-cbor-idiomatic, ~4x smaller). Non-frozen either/// way, but it must be an explicit, tested decision.pubbytes:Vec<u8>,}/// Child index 0..=255; serializes as a two-hex-digit lowercase string so/// dag-cbor string-key ordering == numeric index ordering.#[derive(Debug,Clone,Copy,PartialEq,Eq,PartialOrd,Ord)]pubstructChildIndex(pubu8);#[derive(Debug,Clone,PartialEq,Eq,Serialize,Deserialize)]pubstructVerkleInternal{pubcommitment:Commitment,/// Sparse, POSITIONAL child links — a sibling shape to MerkleNode's/// causal-set parents; duplicates at distinct indexes must survive.pubchildren:BTreeMap<ChildIndex,ContentId>,}#[derive(Debug,Clone,PartialEq,Eq,Serialize,Deserialize)]pubstructVerkleStem{pubstem:[u8;31],pubcommitment:Commitment,pubsuffix_commitments:Vec<Commitment>,pubslots:BTreeMap<ChildIndex,ContentId>,// suffix -> value CID}/// Head object binding the algebraic world to the CAS world.#[derive(Debug,Clone,PartialEq,Eq,Serialize,Deserialize)]pubstructVerkleRoot{pubscheme:u64,pubparams:Option<ContentId>,// SRS / setup artifact, by CIDpubcommitment:Commitment,// what proofs open againstpubdata_root:ContentId,// what retrieval walks from}implContentAddressableforVerkleInternal{/* defer to to_canonical_dagcbor */}implContentAddressableforVerkleStem{/* ditto */}implContentAddressableforVerkleRoot{/* ditto */}/// Module-local CAS seam for traversal. A shared CID-resolving store trait is/// a planned follow-up issue (to be filed); this trait migrates to it when it/// lands.pubtraitNodeResolver{fnget(&self,id:&ContentId) -> Result<Option<Vec<u8>>,ContentError>;}/// Hash-side inclusion witness: the node CIDs along `key`'s path, root→stem.#[derive(Debug,Clone,PartialEq,Eq,Serialize,Deserialize)]pubstructVerkleWalk{pubkey:[u8;32],pubpath:Vec<ContentId>,}/// Verify inclusion by CID walk alone (zero curve ops). Mirrors the frozen/// verify() contract shape (#8): "not present / walk mismatch" is a value,/// not an Err. Ok(Some(value_cid)) on proven inclusion; Ok(None) otherwise.pubfnverify_walk<R:NodeResolver>(root:&VerkleRoot,walk:&VerkleWalk,store:&R,) -> Result<Option<ContentId>,ContentError>;/// Narrow seam for the commitment chain. Implemented OUT-of-crate (curve/// crates never enter this crate's dependency tree); in-crate only a test/// double.pubtraitCommitmentScheme{fnscheme(&self) -> u64;fnverify_opening(&self,parent:&Commitment,index:u8,child:&Commitment,proof:&[u8],) -> Result<bool,ContentError>;}
One module, one file, soft cap ≤ 2,500 lines.
Proof obligations
Law minimalism: four laws, each with a stated obligation; all are Lean-shaped because the MVP is purely functional (no temporal behavior — updates and the maintained proof cache are follow-ups, and that is where TLA+ would enter).
PO-VK-1 Deterministic encoding [Lean] — canonical_form is a function of the node value: equal child/slot maps produce equal canonical bytes and equal ContentIds regardless of insertion order, and the two-hex-digit index encoding is injective and order-preserving (distinct indexes never collide, lexicographic == numeric order).
PO-VK-2 Root-binding (tamper-evidence) [Lean] — assuming the collision-resistance property of the pinned multihash profile (BLAKE3-256), the root ContentId binds the transitive closure of child links: any change to a reachable node's bytes changes the root CID.
PO-VK-3 Walk soundness [Lean] — if verify_walk accepts (root, walk) against a resolver, then every path step's CID is the child at key[depth] in its decoded, id-verified parent, and the returned value CID is the slot at key's suffix — acceptance implies reachability at exactly that key.
PO-VK-4 Dual-identity coherence [Lean, conditional] — assuming the scheme's binding property, if every edge's opening verifies through CommitmentSchemeand the CID walk verifies, then the commitment chain and the CID chain name the same tree: proofs opened against root.commitment speak about the bytes retrievable from root.data_root.
MVP obligation: state PO-VK-1..4 in module docs with executable test mirrors; the Lean formalization itself is a follow-up issue (to be filed).
Python exposure
Follow-up issue (to be filed) after the Rust surface settles, through the existing content-addressable-py PyO3 workspace member and the tag-driven Trusted Publishing pipeline (#14): wrappers for VerkleInternal / VerkleStem / VerkleRoot, verify_walk accepting a Python-callable resolver, and commitments surfaced as opaque (scheme, bytes) pairs. Cross-language byte-parity tests mirror the #12 pattern but stay out of tests/vectors.json until Verkle conformance vectors land — that file is the frozen gate and deliberately excludes non-frozen surfaces.
Acceptance criteria
src/verkle.rs lands behind a default-offverkle cargo feature; plain cargo build / cargo test compiles no new symbols; CI and the pre-push hook exercise it via --all-features (same pattern as merkle).
Byte-vs-array encoding of Commitment.bytes / stem (CBOR byte string vs integer array) is decided explicitly and pinned by a determinism test — an explicit choice, not a serde-derive accident (non-frozen either way until vectors).
Tests: determinism and insertion-order independence of child/slot maps; duplicate child CIDs at distinct indexes survive and produce distinct bytes; changing any reachable child changes the root id; canonical round-trip; walk accept + reject cases; property-style tests over randomized sparse child maps; test-double CommitmentScheme wired through the dual-identity check.
Module docs carry the "BYTES ARE NON-FROZEN (experimental, default-off feature)" banner mirroring src/merkle.rs, state that changing bytes is not a breaking change until Verkle conformance vectors land (standalone follow-up; not an 0.1.0-rc1 blocker), and explicitly forbid adding verkle vectors to tests/vectors.json.
Module docs state the dual-identity rule (commitment for proofs, CID for retrieval) and the verifier obligation that each child's stored commitment must match the parent's opening at that index.
PO-VK-1..4 stated in module docs, each with a named test mirror.
New file stays under the 2,500-line soft cap.
Non-goals / follow-ups
No curve arithmetic, no trusted-setup handling, no Pedersen/IPA or KZG implementation in-crate — adjacent by design; these schemes are not post-quantum (the reason for Ethereum's EIP-7864 binary-tree pivot), and the CAS's value is orthogonal to the scheme choice.
No homomorphic delta updates (recompute-one-child-cheaply). Requires scheme-side algebra; out of scope until a scheme crate exists on the other side of the seam.
Hyperproofs / BalanceProofs / Pointproofs maintainable proof trees — pairing-based and out-of-band from the CAS; folded here as references only.
The one transferable idea — the memoized sibling-path cache (a maintained proof-serving layer updated O(log n) per write, serving any inclusion proof in O(1)) — belongs to the RFC 6962 / SMT hash-tree entries, not this module (follow-up issue, to be filed).
Python bindings — follow-up issue (to be filed) after the Rust surface settles.
Summary
Add
src/verkle.rsbehind a new default-offverklecargo feature: the CAS-side carrier for verkle / vector-commitment trees. The crate stores, addresses, and walks the tree — high-arity internal nodes, EIP-6800-shaped stem nodes, and a head object that binds the algebraic world (commitments, openings) to the CAS world (ContentIds, retrieval). The crate performs no curve arithmetic: commitments are opaque, self-describing{scheme multicodec, bytes}values, and opening verification sits behind a narrowCommitmentSchemetrait implemented out-of-crate. MVP ships the node shapes,ContentAddressablederivation, a resolver-driven walk from the root CID, and one proof kind: a hash-side inclusion walk verifiable with zero curve ops.This structure is explicitly adjacent for a hash-CAS crate (curve ops, trusted setup, not post-quantum — the reason Ethereum pivoted to binary trees in EIP-7864). It is cataloged as the proof-size benchmark (~100–150 bytes/key aggregated witnesses) and for one directly transferable idea (the memoized proof-serving cache — a follow-up for the hash-tree entries, not this issue).
Why (the telescope)
The user need is verifiable membership over huge keyed datasets with tiny witnesses: proving "key K maps to value V under this root" to a party who holds only ~32 bytes of trust anchor, without shipping log-n sibling hashes per level. Vector-commitment trees are where that need is served best today, so they are the benchmark every hash-tree entry in this catalog is measured against.
What a CAS uniquely contributes — and what this issue actually builds — is the other half of the trust story: the tree itself must be retrievable and tamper-evident. Identity splits in two:
A CAS must carry both, bound together, or the succinct-proof world floats free of any retrievable data. That binding — plus the rule that a verifier additionally checks each child's stored commitment matches the parent's opening at that index — is the durable, transferable design content here, and it costs no curve code to carry.
Structure & CID linkage
Every node shape implements
ContentAddressable(src/trait_def.rs) with the one-linecanonical_formdeferring toto_canonical_dagcbor(src/canonical.rs), so each node's identity is a frozen-parameterContentId(src/content_id.rs: CIDv1, dag-cbor 0x71, BLAKE3 0x1e, 32-byte digest) and every child link serializes as a dag-cbor tag-42 IPLD link viaContentId's frozen serde.Why
MerkleNodedoes not fit (sibling node shapes required).MerkleNode<T>(src/merkle.rs) carriesparents: BTreeSet<ContentId>— deduplicated, content-ordered causal-set semantics. Verkle children are the opposite on every axis: they are positional (index-addressed, sparse, arity ≤ 256), they point down (children, not parents), and two distinct indexes may legitimately reference the same child CID (identical subtrees) — aBTreeSetwould silently collapse them. So this module ships sibling node shapes with sparse index→CID maps, reusing only the sharedContentAddressablederivation path:VerkleInternal { commitment, children: map index → ContentId }— sparse, ≤ 256 entries. Indexes serialize as fixed-width two-hex-digit lowercase strings ("00"–"ff") so dag-cbor's string-key rule holds and lexicographic key order equals numeric index order.VerkleStem { stem: [u8; 31], commitment, suffix_commitments, slots: map suffix → value ContentId }— the EIP-6800 stem shape; commitments opaque.VerkleRoot { scheme, params: Option<ContentId> (SRS/setup artifact by CID), commitment, data_root: ContentId }— the head object binding the algebraic world to the CAS world.Discoverability from the root CID. Given
VerkleRoot's CID, a resolver walks: root →data_root→VerkleInternal.children[key[depth]]→ … →VerkleStem.slots[suffix]→ value CID. The children map makes the tree walkable from the root CID exactly like a hash trie; because each node's id covers its child links, the root CID transitively binds every reachable byte.Dual-identity verifier rule. A full verifier checks two chains in lockstep: (1) CID chain — each fetched node's bytes re-derive its claimed
ContentId; (2) commitment chain — each child's stored commitment matches what the parent's commitment opens to at that index (via theCommitmentSchemeseam). The MVP verifies (1) in-crate and exposes (2) as a seam.API sketch (Rust)
One module, one file, soft cap ≤ 2,500 lines.
Proof obligations
Law minimalism: four laws, each with a stated obligation; all are Lean-shaped because the MVP is purely functional (no temporal behavior — updates and the maintained proof cache are follow-ups, and that is where TLA+ would enter).
canonical_formis a function of the node value: equal child/slot maps produce equal canonical bytes and equalContentIds regardless of insertion order, and the two-hex-digit index encoding is injective and order-preserving (distinct indexes never collide, lexicographic == numeric order).ContentIdbinds the transitive closure of child links: any change to a reachable node's bytes changes the root CID.verify_walkaccepts(root, walk)against a resolver, then every path step's CID is the child atkey[depth]in its decoded, id-verified parent, and the returned value CID is the slot atkey's suffix — acceptance implies reachability at exactly that key.CommitmentSchemeand the CID walk verifies, then the commitment chain and the CID chain name the same tree: proofs opened againstroot.commitmentspeak about the bytes retrievable fromroot.data_root.MVP obligation: state PO-VK-1..4 in module docs with executable test mirrors; the Lean formalization itself is a follow-up issue (to be filed).
Python exposure
Follow-up issue (to be filed) after the Rust surface settles, through the existing content-addressable-py PyO3 workspace member and the tag-driven Trusted Publishing pipeline (#14): wrappers for
VerkleInternal/VerkleStem/VerkleRoot,verify_walkaccepting a Python-callable resolver, and commitments surfaced as opaque(scheme, bytes)pairs. Cross-language byte-parity tests mirror the #12 pattern but stay out of tests/vectors.json until Verkle conformance vectors land — that file is the frozen gate and deliberately excludes non-frozen surfaces.Acceptance criteria
src/verkle.rslands behind a default-offverklecargo feature; plaincargo build/cargo testcompiles no new symbols; CI and the pre-push hook exercise it via--all-features(same pattern asmerkle).CommitmentSchemeships with only an in-crate test double.VerkleInternal,VerkleStem,VerkleRootimplementContentAddressableviato_canonical_dagcbor; allContentIdlinks serialize as dag-cbor tag-42 (test asserts tag counts, mirroring src/merkle.rs'sparents_encode_as_tag42_links).verify_walkfollows the frozen verify contract shape (decide: freeze verify() mismatch contract; add ensure_content_id strict helper #8): mismatch/absence isOk(None), never anErr; resolver/decode failures areErr.Commitment.bytes/stem(CBOR byte string vs integer array) is decided explicitly and pinned by a determinism test — an explicit choice, not a serde-derive accident (non-frozen either way until vectors).CommitmentSchemewired through the dual-identity check.Non-goals / follow-ups
NodeResolverhere is module-local and migrates when the shared seam lands (follow-up issue, to be filed).References
merklemodule (MerkleNode DAG-node helper) #11MerkleNode; test: golden conformance vectors + Rust↔Python byte-parity gate #12 golden vectors + Rust↔Python parity; ci: guard the published core as a true leaf (zero path/git deps) #13 leaf-dependency guard; decide: freeze verify() mismatch contract; add ensure_content_id strict helper #8 verify contract; ci: tag-driven multi-platform wheels + crates.io via Trusted Publishing; retire manualmaturin upload#14 tag-driven release.Part of #30 (Merkle structure catalog epic).