The DenseAppendOnlyFixedSizeTree — Dense Fixed-Capacity Merkle Storage

The DenseAppendOnlyFixedSizeTree is a complete binary tree of a fixed height where every node — both internal and leaf — stores a data value. Positions are filled sequentially in level-order (BFS): root first (position 0), then left-to-right at each level. How the root is derived is selected by the grove version (dense_tree_versions.root_maintenance): under GROVE_V1..V3 no intermediate hashes are persisted and the root is recomputed on the fly by recursively hashing from leaves to root; from GROVE_V4 a per-position hash record is kept beside each value and an insert updates only its ancestor path. The root value is identical under both.

This design is ideal for small, bounded data structures where the maximum capacity is known in advance and you need O(1) append, O(1) retrieval by position, and a compact 32-byte root hash commitment that changes after every insert.

Tree Structure

A tree of height h has capacity 2^h - 1 positions. Positions use 0-based level-order indexing:

Height 3 tree (capacity = 7):

              pos 0          ← root (level 0)
             /     \
          pos 1    pos 2     ← level 1
         /   \    /   \
       pos 3 pos 4 pos 5 pos 6  ← level 2 (leaves)

Navigation:
  left_child(i)  = 2i + 1
  right_child(i) = 2i + 2
  parent(i)      = (i - 1) / 2
  is_leaf(i)     = 2i + 1 >= capacity

Values are appended sequentially: the first value goes to position 0 (root), then position 1, 2, 3, and so on. This means the root always has data, and the tree fills in level-order — the most natural traversal order for a complete binary tree.

Hash Computation

Every node hashes with one uniform scheme. Under GROVE_V1..V3 the root hash is not stored separately — it is recomputed from scratch whenever needed by this recursive algorithm, which visits only filled positions:

hash(position, store):
  value = store.get(position)

  if position is unfilled (>= count):
    return [0; 32]                                    ← empty sentinel

  value_hash = blake3(value)
  left_hash  = hash(2 * position + 1, store)
  right_hash = hash(2 * position + 2, store)
  return blake3(value_hash || left_hash || right_hash)

Key properties:

• All nodes (leaf and internal): blake3(blake3(value) || H(left) || H(right))
• Leaf nodes: left_hash and right_hash are both [0; 32] (unfilled children)
• Unfilled positions: [0u8; 32] (zero hash)
• Empty tree (count = 0): [0u8; 32]

No leaf/internal domain separation tags are used. The tree structure (height and count) is externally authenticated in the parent Element::DenseAppendOnlyFixedSizeTree, which flows through the Merk hierarchy. The verifier always knows exactly which positions are leaves vs internal nodes from the height and count, so an attacker cannot substitute one for the other without breaking the parent authentication chain.

This means the root hash encodes a commitment to every stored value and its exact position in the tree. Changing any value (if it were mutable) would cascade through all ancestor hashes up to the root.

Hash cost (GROVE_V1..V3): Computing the root hash visits all filled positions plus any unfilled children. For a tree with n values, worst case is O(n) blake3 calls — and every insert recomputes it, so a run of n inserts is O(n²). Acceptable for small capacities, but as the buffer of the append-only family (Chapter 14, 15) the tree reaches 2,047 positions in the shielded pool, where the last insert of every epoch cost ≈ 2k reads and ≈ 4k blake3 calls.

Path Records (GROVE_V4+)

From GROVE_V4 (dense_tree_versions.root_maintenance = 1) every insert writes one path record under its own position's key b'h' || position:

PathRecord = generation (u64 BE) || present (u16 BE) || value_hash (32)
             || entry[0..height] (32 each)          // 42 + 32·height bytes, fixed per tree

• value_hash = blake3(value) of the inserting position — so when it is later an ancestor, re-hashing it never reads its value back;
• entry[depth] is the node hash of the path position at that depth, as of this insert (present marks the depths that hold one: 0..=depth(position));
• generation is the epoch tag: the bulk-append tree reuses the same position keys every epoch (its chunk count is the tag, advanced by reset), and a record carrying another generation is never trusted.

Because positions fill in BFS order, the record of the last insert into a subtree holds that subtree's current hash (no later insert touched it), and every position's own record holds its value hash for good — both are located arithmetically from count (last_filled_in_subtree), so within an epoch no record is ever rewritten (the bulk-append tree's next epoch reuses the same keys; its records then carry a newer generation, which marks the previous epoch's as stale). An insert at position p (depth d) hashes the new leaf (blake3(value), then blake3(value_hash || 0 || 0) — both children are beyond count) and walks up: for each ancestor the on-path child's hash was just computed, the off-path sibling's hash is read from the record of the last insert into its subtree (or [0; 32] beyond count), and the ancestor's own record supplies its value_hash; one blake3 per level. That is 2 + d blake3 calls, at most 2d record reads and one record write — O(height), whatever the fill. The root is entry[0] of the last insert's record (one read).

What an insert is charged is not the work of its particular position but a fixed model for the tree's height (v1_insert_model_cost): the blake3 calls (2 + avg depth) and record reads averaged over every position of a full buffer, rounded up — at chunk_power 11: 12 blake3 calls, 18 record reads of 394 bytes — plus the two puts (slot, record), each of a size that does not depend on the position. Appending to a tree of a given height therefore costs the same whatever the position, and an estimator can charge exactly it.

Records are derived state: root_hash trusts them, so integrity audits (verify_grovedb, the binding check at the end of a state-sync restore) derive the root from the values instead (root_hash_from_values, and the compute_current_state_root_from_values of the trees built on the buffer) and report a position-0 record that disagrees with the walked root as its own issue (__dense_hash_records__).

A record that is absent (a buffer filled under GROVE_V1..V3) or stale (an earlier generation) is recomputed from the values — the version-0 walk over that subtree — read-only and billed the same model; for the append-only family's rolling buffer that catch-up ends with the epoch the switch happened in. Stored values, positions, proofs and roots are identical under both versions; only the records (and the work an insert is charged) differ.

The Element Variant

#![allow(unused)]
fn main() {
Element::DenseAppendOnlyFixedSizeTree(
    u16,                   // count — number of values stored (max 65,535)
    u8,                    // height — immutable after creation (1..=16)
    Option<ElementFlags>,  // flags — storage flags
)
}

The root hash is NOT stored in the Element — it flows as the Merk child hash via insert_subtree's subtree_root_hash parameter.

Discriminant: 14 (ElementType), TreeType = 10

Cost size: DENSE_TREE_COST_SIZE = 6 bytes (2 count + 1 height + 1 discriminant

• 2 overhead)

Storage Layout

Like MmrTree and BulkAppendTree, the DenseAppendOnlyFixedSizeTree stores data in the data namespace (not a child Merk). Values are keyed by their position as a big-endian u16:

Subtree path: blake3(parent_path || key)

Storage keys:
  [0, 0] → value at position 0 (root)
  [0, 1] → value at position 1
  [0, 2] → value at position 2
  ...

From GROVE_V4 a path record sits beside each value under a 3-byte key (b'h' || position as big-endian u16); the 2-byte slot keys and 3-byte record keys cannot collide.

The Element itself (stored in the parent Merk) carries the count and height. The root hash flows as the Merk child hash. This means:

• Reading the root hash is one record read from GROVE_V4 (O(n) recomputation from storage under GROVE_V1..V3)
• Reading a value by position is O(1) — single storage lookup
• Inserting is O(height) from GROVE_V4 — one slot write, one record write, the ancestor path's record reads and 2 + depth blake3 calls, charged as the height's fixed model (O(n) hashing under GROVE_V1..V3: one storage write + full root hash recomputation)

Operations

dense_tree_insert(path, key, value, tx, grove_version)

Appends a value to the next available position. Returns (root_hash, position).

Step 1: Read element, extract (count, height)
Step 2: Check capacity: if count >= 2^height - 1 → error
Step 3: Build subtree path, open storage context
Step 4: Write value to position = count
Step 5: Reconstruct DenseFixedSizedMerkleTree from state
Step 6: Call tree.insert(value, store) → (root_hash, position, hash_calls)
Step 7: Update element with new root_hash and count + 1
Step 8: Propagate changes up through Merk hierarchy
Step 9: Commit transaction

dense_tree_get(path, key, position, tx, grove_version)

Retrieves the value at a given position. Returns None if position >= count.

dense_tree_root_hash(path, key, tx, grove_version)

Returns the root hash stored in the element. This is the hash computed during the most recent insert — no recomputation needed.

dense_tree_count(path, key, tx, grove_version)

Returns the number of values stored (the count field from the element).

Batch Operations

The GroveOp::DenseTreeInsert variant supports batch insertion through the standard GroveDB batch pipeline:

#![allow(unused)]
fn main() {
let ops = vec![
    QualifiedGroveDbOp::dense_tree_insert_op(
        vec![b"parent".to_vec()],
        b"my_dense_tree".to_vec(),
        b"value_data".to_vec(),
    ),
];
db.apply_batch(ops, None, None, grove_version)?;
}

Preprocessing: Like all non-Merk tree types, DenseTreeInsert ops are preprocessed before the main batch body executes. The preprocess_dense_tree_ops method:

1. Groups all DenseTreeInsert ops by (path, key)
2. For each group, executes the inserts sequentially (reading the element, inserting each value, updating the root hash)
3. Converts each group into a ReplaceNonMerkTreeRoot op that carries the final root_hash and count through the standard propagation machinery

Multiple inserts to the same dense tree within a single batch are supported — they are processed in order and the consistency check allows duplicate keys for this op type.

Propagation: The root hash and count flow through the NonMerkTreeMeta::DenseTree variant in ReplaceNonMerkTreeRoot, following the same pattern as MmrTree and BulkAppendTree.

Proofs

DenseAppendOnlyFixedSizeTree supports V1 subquery proofs via the ProofBytes::DenseTree variant. Individual positions can be proved against the tree's root hash using inclusion proofs that carry ancestor values and sibling subtree hashes.

Auth Path Structure

Because internal nodes hash their own value (not just child hashes), the authentication path differs from a standard Merkle tree. To verify a leaf at position p, the verifier needs:

1. The leaf value (the proved entry)
2. Ancestor value hashes for every internal node on the path from p to the root (only the 32-byte hash, not the full value)
3. Sibling subtree hashes for every child that is NOT on the path

Because all nodes use blake3(H(value) || H(left) || H(right)) (no domain tags), the proof only carries 32-byte value hashes for ancestors — not full values. This keeps proofs compact regardless of how large individual values are.

#![allow(unused)]
fn main() {
pub struct DenseTreeProof {
    pub entries: Vec<(u16, Vec<u8>)>,            // proved (position, value) pairs
    pub node_value_hashes: Vec<(u16, [u8; 32])>, // ancestor value hashes on the auth path
    pub node_hashes: Vec<(u16, [u8; 32])>,       // precomputed sibling subtree hashes
}
}

Note: height and count are not in the proof struct — the verifier gets them from the parent Element, which is authenticated by the Merk hierarchy.

Walkthrough Example

Tree with height=3, capacity=7, count=5, proving position 4:

        0
       / \
      1   2
     / \ / \
    3  4 5  6

Path from 4 to root: 4 → 1 → 0. Expanded set: {0, 1, 4}.

The proof contains:

• entries: [(4, value[4])] — the proved position
• node_value_hashes: [(0, H(value[0])), (1, H(value[1]))] — ancestor value hashes (32 bytes each, not full values)
• node_hashes: [(2, H(subtree_2)), (3, H(node_3))] — siblings not on the path

Verification recomputes the root hash bottom-up:

1. H(4) = blake3(blake3(value[4]) || [0;32] || [0;32]) — leaf (children are unfilled)
2. H(3) — from node_hashes
3. H(1) = blake3(H(value[1]) || H(3) || H(4)) — internal uses value hash from node_value_hashes
4. H(2) — from node_hashes
5. H(0) = blake3(H(value[0]) || H(1) || H(2)) — root uses value hash from node_value_hashes
6. Compare H(0) against expected root hash

Multi-Position Proofs

When proving multiple positions, the expanded set merges overlapping auth paths. Shared ancestors are included only once, making multi-position proofs more compact than independent single-position proofs.

V0 Limitation

V0 proofs cannot descend into dense trees. If a V0 query matches a DenseAppendOnlyFixedSizeTree with a subquery, the system returns Error::NotSupported directing the caller to use prove_query_v1.

Query Key Encoding

Dense tree positions are encoded as big-endian u16 (2-byte) query keys, unlike MmrTree and BulkAppendTree which use u64. All standard QueryItem range types are supported.

Comparison with Other Non-Merk Trees

When to choose DenseAppendOnlyFixedSizeTree:

• The maximum number of entries is known at creation time
• You need every position (including internal nodes) to store data
• You want the simplest possible data model with no unbounded growth
• O(n) root hash recomputation is acceptable (small tree heights)

When NOT to choose it:

• You need unlimited capacity → use MmrTree or BulkAppendTree
• You need ZK compatibility → use CommitmentTree

Usage Example

#![allow(unused)]
fn main() {
use grovedb::Element;
use grovedb_version::version::GroveVersion;

let grove_version = GroveVersion::latest();

// Create a dense tree of height 4 (capacity = 15 values)
db.insert(
    &[b"state"],
    b"validator_slots",
    Element::empty_dense_tree(4),
    None,
    None,
    grove_version,
)?;

// Append values — positions filled 0, 1, 2, ...
let (root_hash, pos) = db.dense_tree_insert(
    &[b"state"],
    b"validator_slots",
    validator_pubkey.to_vec(),
    None,
    grove_version,
)?;
// pos == 0, root_hash = blake3(validator_pubkey)

// Read back by position
let value = db.dense_tree_get(
    &[b"state"],
    b"validator_slots",
    0,     // position
    None,
    grove_version,
)?;
assert_eq!(value, Some(validator_pubkey.to_vec()));

// Query metadata
let count = db.dense_tree_count(&[b"state"], b"validator_slots", None, grove_version)?;
let hash = db.dense_tree_root_hash(&[b"state"], b"validator_slots", None, grove_version)?;
}

Implementation Files