Repository navigation
Description
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:
- 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. - 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
PrivateDocumentStoreelement (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:
CommitmentFrontierisFrontier<MerkleHashOrchard, 32>(grovedb-commitment-tree/src/commitment_frontier/mod.rs) — the Merkle hash is fixed to Zcash Orchard's MerkleCRH personalization, and the depth toNOTE_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 forDashMemo), tied to theMemoSizetype 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: newgrovedb-private-document-storecrate,ElementType::PrivateDocumentStore = 24/ NonCounted twin 152,TreeType::PrivateDocumentStore = 16,GroveOptag 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
BulkAppendTreelayer;DataCommitmentTreeinherits them through its embedded bulk store. V1 proofs currently reject subqueries intoPrivateDocumentStorewithNotSupported, 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.rsnow 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. (PopulatedPrivateDocumentStoretransfer is stillNotSupported.) - 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
- The existing pool tree is untouched — isolation, not refactor. The new type is a parallel implementation in a new crate;
grovedb-commitment-treeand 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. - Fail closed. New discriminants are rejected outright by older versions; everything is gated under the next
GROVE_V*flag. - 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-genericFrontier<H, 32>with the same cost-tracking pattern as the existingCommitmentFrontier, generic over theHashableMerkle hash. Depth 32 (const-generic default). - A2. Configurable Sinsemilla hash. A
Hashableimpl 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 aBulkAppendTreestorage adapter mirroring the pattern ingrovedb-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 ingrovedb-element/src/element_type.rs;TreeType::DataCommitmentTreeat discriminant 17 inmerk/src/tree_type/mod.rs; next freeGroveOpsort tag is 20. (Updated 2026-08-25 — the original 16/144 plan is stale: element indices 15/16/17 are now theNonCounted/NotSummed/NotCountedOrSummedwrapper discriminants, 18–23 went toReferenceWithSumItemand the Provable*/indexed family, andPrivateDocumentStorelanded at 24/152 rather than the 15/143 this issue assumed. Note the wrapper-twin nibble layout inelement_type.rs: NonCounted twins must satisfy0x80 <= disc < 0xB0, so 153 =0x99is fine.) - B2. Element config carrier. The element value encodes
{domain personalization, payload size, chunk power}; constructor/helpers/visualize updates ingrovedb-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 ingrovedb/src/operations/commitment_tree.rs. - C2. Position-range reads. Paginated range fetch of entries by global position, chunk-aligned to the
BulkAppendTreelayout. (Landed 2026-08 in feat: paginated position-range reads with proofs at the BulkAppendTree layer #786 — paginated position-range reads with proofs at theBulkAppendTreelayer, exactly as scoped here. TheDataCommitmentTree-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'sBulkAppendTree-layer range-read proofs to the new type — the V1 prover'sNotSupportedplaceholder forPrivateDocumentStoresubqueries 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_grovedbintegrity 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.rsnow does chunked entry replay forCommitmentTree,MmrTree,BulkAppendTree, andDenseAppendOnlyFixedSizeTree, including frontier/config transfer for type 11.) - D2b. Register
DataCommitmentTreewith 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 inreplication/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
DataCommitmentTreein 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_callsaccounting unchanged; updatebatch/estimated_costs/{average_case,worst_case}_costs.rsandmerk/src/tree_type/costs.rs. - F2.
GROVE_V*gating on all new discriminants and ops. (Updated 2026-08-25: concretelyGROVE_V4or later —GROVE_V3is 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
ProvableCountTreesuffices, same pattern as the nullifier set). - Any semantic change to the existing Orchard note pool tree.
Activity
[-]Generalize commitment trees beyond Orchard notes (configurable hash domain, entry format, payload size)[/-][+]DataCommitmentTree: generic commitment tree for data (configurable hash domain, entry format, payload size)[/+]feat: add PrivateDocumentStore element type, gated to GROVE_V4 (#787)
feat: paginated position-range reads with proofs at the BulkAppendTre…
QuantumExplorer commentedon Aug 25, 2026
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:
BulkAppendTreelayer. TheDataCommitmentTree-specific wiring on top is folded into C3; the V1 prover already has aNotSupportedplaceholder pointing at this inheritance.Two other dependencies also landed (all
GROVE_V4-gated):PrivateDocumentStorelanded as the frontier-less phase-one sibling —ElementType24/152,TreeType16,GroveOptag 19 — with indexed reference rows following in feat: replace indexed-tree placeholder rows with canonical references (#814) #817.The
DataCommitmentTree-specific items (A, B, C1/C3/C4, D1, D2b, D3, E, F) are not started — there is nogrovedb-data-commitment-treecrate yet.Corrections to the plan:
NonCounted/NotSummed/NotCountedOrSummedwrapper discriminants; 18–24 are taken throughPrivateDocumentStore). The plan is updated toElementType = 25, NonCounted twin 153,TreeTypediscriminant 17, nextGroveOptag 20.GROVE_V4+ (GROVE_V3is live in production).Remaining critical path: A (new crate) → B (plumbing) → C1/C3 (ops + proofs), with E (client witness store) independent.
feat(replication)!: complete V1 state sync and bounded-memory restore (…