DataCommitmentTree: generic commitment tree for data (configurable hash domain, entry format, payload size)

[QuantumExplorer]

Motivation

Platform is designing anonymous DashPay contact requests, generalizing into a platform capability: private document types that any data contract can declare — no public index structure, entries stored as hiding commitments plus ciphertexts, funded from the shielded pool, with contract-declared constraints enforced by a Halo 2 circuit. This needs a new kind of tree in GroveDB, with two consumer shapes on the Platform side:

1. Hecate — the key membership tree (a single global instance): an append-only Sinsemilla Merkle tree over identity keys, leaf = CRH(key_type || key_bytes). Recipient-existence constraints need only membership (no knowledge of the key's secret), so they work for every existing key type; sender-authorization constraints prove knowledge of the leaf key's secret, which is only affordable in-circuit for a Pallas-curve key type. The tree's anchor is a public input to the circuit.
2. Modifiable private document stores (later phase): updating hidden state means appending the new version and nullifying the old — which requires membership proofs against the store, i.e. an anchored tree, composed with a sibling nullifier set in the same pattern the shielded pool uses. Non-modifiable private document stores (phase one) never have their anchor consumed by anything and are therefore not built on this type — they get the simpler frontier-less PrivateDocumentStore element (PrivateDocumentStore: append-only element type for fixed-size opaque entries with committed config and provable range reads #784). An anchor consumer is the dividing line: entries that someone later proves membership of need this type; write-once data does not.

The conceptual split from the existing type 11 is value vs. data. Type 11's entries are Orchard notes — money — with rho/cv_net/binding-signature semantics baked into the format because notes carry value that must balance. The new type's entries are pure existence assertions with an opaque fixed-size payload; nothing is ever spent from them. To GroveDB both are just leaf + payload, which is why one generic type covers all of it — the value semantics were never GroveDB's business, and type 11 leaking them (rho, cv_net, memo-derived payload sizes) is the layering smell this issue also fixes.

Naming: the new GroveDB type is DataCommitmentTree (pairs with the existing note commitment tree as data-vs-value). Platform-side instance codenames (Hecate, and the shielded pool tree "medusa") stay out of GroveDB — this library stays application-agnostic.

Current state (updated 2026-08-25)

The type-11 coupling that motivates this issue is unchanged:

• CommitmentFrontier is Frontier<MerkleHashOrchard, 32> (grovedb-commitment-tree/src/commitment_frontier/mod.rs) — the Merkle hash is fixed to Zcash Orchard's MerkleCRH personalization, and the depth to NOTE_COMMITMENT_TREE_DEPTH.
• The entry format is fixed to CommitmentEntry { cmx, rho, cv_net, payload } (grovedb-commitment-tree/src/commitment_tree/mod.rs).
• The payload size is derived from the note-encryption layout: ciphertext_payload_size::<M>() = 32 + enc_ciphertext + 80 (216 bytes for DashMemo), tied to the MemoSize type parameter.
• The GroveDB operations inherit those types: commitment_tree_insert<M: MemoSize>, commitment_tree_anchor, commitment_tree_get_value, commitment_tree_count (grovedb/src/operations/commitment_tree.rs).
• ElementType::CommitmentTree = 11 / TreeType::CommitmentTree(chunk_power) carry no configuration beyond the chunk power.
• The client-side witness/scanning stores (ClientMemoryCommitmentTree, ClientPersistentCommitmentTree + SQLite shard store) are Orchard-note-typed.

Landed since filing (all gated to GROVE_V4) — C2 and D2 are done (their deliverables landed under their own PRs, as the plan anticipated); the DataCommitmentTree-specific items (A, B, C1/C3/C4, D1, D2b, D3, E, F) are not started:

• PrivateDocumentStore: append-only element type for fixed-size opaque entries with committed config and provable range reads #784 is done — PrivateDocumentStore, the frontier-less phase-one sibling, merged in feat: add PrivateDocumentStore element type, gated to GROVE_V4 #787: new grovedb-private-document-store crate, ElementType::PrivateDocumentStore = 24 / NonCounted twin 152, TreeType::PrivateDocumentStore = 16, GroveOp tag 19. Indexed-tree reference rows (Replace indexed-tree placeholder rows with canonical references to primary entries before release #814) followed in feat: replace indexed-tree placeholder rows with canonical references (#814) #817.
• C2's shared layer is done — feat: paginated position-range reads with proofs at the BulkAppendTree layer #786 landed paginated position-range reads with proofs at the BulkAppendTree layer; DataCommitmentTree inherits them through its embedded bulk store. V1 proofs currently reject subqueries into PrivateDocumentStore with NotSupported, with a code comment pointing at exactly this inheritance (operations/proof/generate.rs).
• D2's heavy lifting is done — the state-sync gap was split out as State sync cannot transfer the append-only tree family — a single populated CommitmentTree makes snapshots from that node unusable #785 and fixed by feat(replication): state sync support for the append-only tree family (fixes #785) #788: replication/non_merk_sync.rs now does chunked entry replay for the whole append-only family (CommitmentTree, MmrTree, BulkAppendTree, DenseAppendOnlyFixedSizeTree). The new type only needs to be added to that machinery. (Populated PrivateDocumentStore transfer is still NotSupported.)
• The append-family cost model was rebuilt — Append-only tree family charges write churn as new storage: compaction blob, epoch≥2 buffer writes and frontier rewrites are all reported as added_bytes #822/fix(costs): report append-only write churn as replacement, not new storage (#822) #825/fix(bulk): bill the committed-slot read, bound BulkAppend estimates, validate chunk header (#822 follow-up) #826 (append storage accounting: churn billed as replacement, entry bytes prepaid as added), feat(dense): O(height) dense-buffer root maintenance via per-position hash records (GROVE_V4) #828 (O(height) dense root maintenance via per-position hash records), feat(append-only): fixed per-append cost for the commitment tree — churn buffer, fixed dense model, amortized compaction, constant-price frontier (GROVE_V4) #829 (fixed per-append cost: churn buffer, fixed dense model, amortized compaction, constant-price frontier), feat(append-only): amortize the compaction's commit-time seeks — prepaid puts carry no seek (GROVE_V4) #830 (amortized commit-time seek share with prepaid puts). F1 must follow this model — the new frontier save must be constant-price like type 11's now is, and its compaction puts must use the prepaid-marker pattern.

Guiding constraints

1. The existing pool tree is untouched — isolation, not refactor. The new type is a parallel implementation in a new crate; grovedb-commitment-tree and type 11 are not modified at all, so their semantics stay frozen by construction rather than by equivalence testing. This is deliberate: the generic Merkle machinery already exists upstream (incrementalmerkletree::Frontier<H, 32> is generic over the hash), so the only duplication is the thin wrapper (cost tracking, entry serialization, storage adapter) — a small, stable price for eliminating regression risk and review burden on a live consensus tree.
2. Fail closed. New discriminants are rejected outright by older versions; everything is gated under the next GROVE_V* flag.
3. Config is consensus data. A DataCommitmentTree's configuration (hash domain, payload size, chunk power) is committed into its state root so a proof can never be reinterpreted under a different config.

Work plan

A — New grovedb-data-commitment-tree crate (generic from birth)

• A1. New crate, no modification to the existing one. Wrap incrementalmerkletree's already-generic Frontier<H, 32> with the same cost-tracking pattern as the existing CommitmentFrontier, generic over the Hashable Merkle hash. Depth 32 (const-generic default).
• A2. Configurable Sinsemilla hash. A Hashable impl over Sinsemilla MerkleCRH with a caller-supplied personalization string. Sinsemilla domains precompute generator constants per personalization — needs a lazy per-domain cache (e.g. keyed by domain string); benchmark first-use cost.
• A3. Entry + storage adapter. { leaf: [u8; 32], payload: fixed N bytes }, payload size fixed per tree, persisted via a BulkAppendTree storage adapter mirroring the pattern in grovedb-commitment-tree/src/commitment_tree/mod.rs.
• A4. Tests. Frontier root vectors cross-checked against a reference computation, serialization round-trips, per-config empty-root handling. (No type-11 equivalence machinery — nothing there changes.)

B — Merk + element plumbing

• B1. New discriminants. ElementType::DataCommitmentTree = 25 + NonCounted twin at 153 in grovedb-element/src/element_type.rs; TreeType::DataCommitmentTree at discriminant 17 in merk/src/tree_type/mod.rs; next free GroveOp sort tag is 20. (Updated 2026-08-25 — the original 16/144 plan is stale: element indices 15/16/17 are now the NonCounted/NotSummed/NotCountedOrSummed wrapper discriminants, 18–23 went to ReferenceWithSumItem and the Provable*/indexed family, and PrivateDocumentStore landed at 24/152 rather than the 15/143 this issue assumed. Note the wrapper-twin nibble layout in element_type.rs: NonCounted twins must satisfy 0x80 <= disc < 0xB0, so 153 = 0x99 is fine.)
• B2. Element config carrier. The element value encodes {domain personalization, payload size, chunk power}; constructor/helpers/visualize updates in grovedb-element/src/element/.
• B3. Config-bound state root. New composite binding for the generic type, e.g. blake3("dct_state" || config_hash || sinsemilla_root || bulk_state_root). The type-11 formula stays untouched.
• B4. Match-site sweep. is_tree(), TryFrom<u8>, display names, merk/src/element/{costs,delete,get,reconstruct}.rs, replace_subtree_root, is_empty_tree, delete semantics. Mechanical but consensus-critical.

C — Operations

• C1. Generic insert (leaf canonicality + exact payload-size validation), anchor, get_value, count — sharing implementation with the typed Orchard ops in grovedb/src/operations/commitment_tree.rs.
• C2. Position-range reads. Paginated range fetch of entries by global position, chunk-aligned to the BulkAppendTree layout. (Landed 2026-08 in feat: paginated position-range reads with proofs at the BulkAppendTree layer #786 — paginated position-range reads with proofs at the BulkAppendTree layer, exactly as scoped here. The DataCommitmentTree-specific wiring on top of it is folded into C3.)
• C3. Proof support in operations/proof/{generate,verify}.rs: inclusion proofs for entries, ranges, and count; absence falls out of the provable count (position ≥ count). (Includes wiring feat: paginated position-range reads with proofs at the BulkAppendTree layer #786's BulkAppendTree-layer range-read proofs to the new type — the V1 prover's NotSupported placeholder for PrivateDocumentStore subqueries marks the spot.)
• C4. Batch behavior. Extend the existing batch policy for commitment trees (batch/mod.rs, batch_structure.rs) to the new type; direct ops remain the mutation path.

D — Integrity, sync, tooling

• D1. verify_grovedb integrity walk for the new type (frontier ↔ bulk-tree ↔ config consistency), mirroring type 11's checks.
• D2. State sync. (Landed 2026-08: this did get its own issue — State sync cannot transfer the append-only tree family — a single populated CommitmentTree makes snapshots from that node unusable #785 — and was implemented in feat(replication): state sync support for the append-only tree family (fixes #785) #788: replication/non_merk_sync.rs now does chunked entry replay for CommitmentTree, MmrTree, BulkAppendTree, and DenseAppendOnlyFixedSizeTree, including frontier/config transfer for type 11.)
• D2b. Register DataCommitmentTree with the feat(replication): state sync support for the append-only tree family (fixes #785) #788 sync machinery (supports_entry_replay, entry replay, frontier + config transfer in replication/non_merk_sync.rs) once B lands — expected to be small.
• D3. grovedbg/debugger rendering of the new element type (non-consensus, lower priority).

E — Client-side witness store

• E1. A new, lean witness-tracking client store for DataCommitmentTree in the new crate: a prover tracks its own leaf's incremental witness across appends (with rollback handling), SQLite-backed persistence mirroring the existing client-store patterns. The existing Orchard client stores are untouched — this consumer needs no note trial-decryption machinery, so a fresh minimal store is cleaner than generalizing the note-shaped one. (Cursor-only payload scanning belongs to PrivateDocumentStore: append-only element type for fixed-size opaque entries with committed config and provable range reads #784's consumers and needs no witness store.)

F — Costs and versioning

• F1. Payload-size-parametrized storage costs; sinsemilla_hash_calls accounting unchanged; update batch/estimated_costs/{average_case,worst_case}_costs.rs and merk/src/tree_type/costs.rs.
• F2. GROVE_V* gating on all new discriminants and ops. (Updated 2026-08-25: concretely GROVE_V4 or later — GROVE_V3 is live in production, and all the landed work above is V4-gated.)
• F3. Extend the seeding/verification benches to the generic instantiation, including A2's domain-precompute cost.

Design decisions

Decision	Choice
New discriminant vs. config on type 11	New discriminant (25/153 — see B1; originally 16/144, superseded by the wrapper-discriminant reservation and #784 landing at 24/152) — type 11 stays frozen; unknown discriminants fail closed on old versions; no config branching in a consensus-critical parser
Refactor existing crate vs. new crate	New crate — Frontier<H, 32> is already generic upstream; only the thin wrapper is duplicated; type 11 regression risk eliminated by not touching it
Config carrier	In the element value, committed into the state root (B3)
Personalization	Caller-supplied string, lazily cached generators; no application registry inside GroveDB
Payload size	Fixed per tree; variable sizes punted (callers pad to uniform size, which is the right privacy posture anyway)
Depth	Fixed at 32

Sequencing and rough size

A → B serial; C and D parallelize after B; E independent; F throughout. Roughly 6–9 engineer-weeks for A–F excluding D2 (state sync is the wildcard — scope first), plus release and downstream pin bump. (Updated 2026-08-25: D2 is no longer the wildcard — #788 built the machinery, so the remaining D2 work is a small registration. C2's proof layer also pre-landed in #786. The remaining estimate is dominated by A + B + C1/C3 + E.)

Non-goals

• The Halo 2 circuit itself (Platform-side; it only consumes the anchor).
• The uniqueness tag set (existing ProvableCountTree suffices, same pattern as the nullifier set).
• Any semantic change to the existing Orchard note pool tree.

[QuantumExplorer]

This is Claude. Updated the issue body to reflect where things stand as of 2026-08-25.

Summary of the update:

Two of the plan's checkboxes are done — C2 and D2 landed under their own PRs, exactly as the plan anticipated they might:

1. C2 ✅ (feat: paginated position-range reads with proofs at the BulkAppendTree layer #786): paginated position-range reads with proofs at the BulkAppendTree layer. The DataCommitmentTree-specific wiring on top is folded into C3; the V1 prover already has a NotSupported placeholder pointing at this inheritance.
2. D2 ✅ (State sync cannot transfer the append-only tree family — a single populated CommitmentTree makes snapshots from that node unusable #785/feat(replication): state sync support for the append-only tree family (fixes #785) #788): state-sync entry replay for the whole append-only family, including type 11's frontier + config. Registering the new type with that machinery is split out as a new small item D2b.

Two other dependencies also landed (all GROVE_V4-gated):

3. PrivateDocumentStore: append-only element type for fixed-size opaque entries with committed config and provable range reads #784 shipped (via feat: add PrivateDocumentStore element type, gated to GROVE_V4 #787): PrivateDocumentStore landed as the frontier-less phase-one sibling — ElementType 24/152, TreeType 16, GroveOp tag 19 — with indexed reference rows following in feat: replace indexed-tree placeholder rows with canonical references (#814) #817.
4. The append-family cost model was rebuilt (Append-only tree family charges write churn as new storage: compaction blob, epoch≥2 buffer writes and frontier rewrites are all reported as added_bytes #822/fix(costs): report append-only write churn as replacement, not new storage (#822) #825/fix(bulk): bill the committed-slot read, bound BulkAppend estimates, validate chunk header (#822 follow-up) #826, feat(dense): O(height) dense-buffer root maintenance via per-position hash records (GROVE_V4) #828, feat(append-only): fixed per-append cost for the commitment tree — churn buffer, fixed dense model, amortized compaction, constant-price frontier (GROVE_V4) #829, feat(append-only): amortize the compaction's commit-time seeks — prepaid puts carry no seek (GROVE_V4) #830): constant-price frontier saves, churn billed as replacement, prepaid compaction puts. F1 must follow this model.

The DataCommitmentTree-specific items (A, B, C1/C3/C4, D1, D2b, D3, E, F) are not started — there is no grovedb-data-commitment-tree crate yet.

Corrections to the plan:

• B1's discriminant allocation was stale. 16/144 is impossible now (15/16/17 are the NonCounted/NotSummed/NotCountedOrSummed wrapper discriminants; 18–24 are taken through PrivateDocumentStore). The plan is updated to ElementType = 25, NonCounted twin 153, TreeType discriminant 17, next GroveOp tag 20.
• F2's gate is now concretely GROVE_V4+ (GROVE_V3 is live in production).

Remaining critical path: A (new crate) → B (plumbing) → C1/C3 (ops + proofs), with E (client witness store) independent.