Appendix C: Hash Computation Reference

Merk Node Hash

node_hash = blake3(key_len(1) || key || value_hash(32) || left_hash(32) || right_hash(32))

GroveDB Subtree Prefix

prefix = blake3(parent_prefix || key) → 32 bytes

State Root — BulkAppendTree

state_root = blake3("bulk_state" || mmr_root || dense_tree_root)

The buffer is a DenseFixedSizedMerkleTree — dense_tree_root is its root hash.

Dense Merkle Root — BulkAppendTree Chunks

leaves[i] = blake3(entry[i])
internal[parent] = blake3(left_child || right_child)
root = internal[0] (top of complete binary tree)

Dense Tree Root Hash — DenseAppendOnlyFixedSizeTree

Recursive from root (position 0):
  all nodes with data: blake3(blake3(value) || H(left) || H(right))
                       (no domain separation tags — structure externally authenticated)
  leaf nodes:          left_hash = right_hash = [0; 32]
  unfilled position:   [0; 32]
  empty tree:          [0; 32]

Dense Tree Proof Verification — DenseAppendOnlyFixedSizeTree

Given: entries, node_value_hashes, node_hashes, expected_root

Pre-checks:
  1. Validate height in [1, 16]
  2. Validate count <= capacity (= 2^height - 1)
  3. Reject if any field has > 100,000 elements (DoS prevention)
  4. Reject duplicate positions within entries, node_value_hashes, node_hashes
  5. Reject overlapping positions between the three fields
  6. Reject node_hashes at ancestors of any proved entry (prevents forgery)

recompute_hash(position):
  if position >= capacity or position >= count → [0; 32]
  if position in node_hashes → return precomputed hash
  value_hash = blake3(entries[position]) or node_value_hashes[position]
  left_hash  = recompute_hash(2*pos+1)
  right_hash = recompute_hash(2*pos+2)
  return blake3(value_hash || left_hash || right_hash)

Verify: recompute_hash(0) == expected_root

GroveDB cross-validation:
  proof.height must match element.height
  proof.count must match element.count

MMR Node Merge — MmrTree / BulkAppendTree Chunk MMR

parent.hash = blake3(left.hash || right.hash)

Sinsemilla Root — CommitmentTree

Sinsemilla hash over Pallas curve (see Zcash ZIP-244)
MerkleHashOrchard::empty_root(Level::from(32)) for empty tree

combine_hash (Parent-Child Binding)

combine_hash(value_hash, child_hash) = blake3(value_hash || child_hash)
For Merk trees: child_hash = child Merk root hash
For non-Merk trees: child_hash = type-specific root (mmr_root, state_root, dense_root, etc.)

The GroveDB Book — documenting the internals of GroveDB for developers and researchers. Based on the GroveDB source code.