Research / 2024

Authenticated state with sparse Merkle trees

Draft · the definitions and theorems on this page are machine-checked in Lean; independent review is in progress.

A document store committed to by one hash: fixed-depth sparse Merkle trees, an injective map from string ids to leaf indices, batched state-transition proofs and value or predicate queries checked against a single stored root.

Sparse Merkle treesValidity proofsArithmetic circuits
1 root
all the verifier stores; every batch and every query is checked against it
14 / 19
id length that always fits a depth-100 tree, with a 64-symbol and a 31-symbol alphabet
17
hash calls to commit a 256-element document leaf: 16 chunks of 16, then one over the 16 digests

Suppose a database lives off-chain, and a smart contract that can afford to store about one 32-byte word wants to rely on its contents. The contract should accept “document Bob in collection 0 has age = 10” only if that is true of the current state. It should also accept “the database moved from state rr to state r′r'” only if some valid sequence of writes takes rr to r′r'. The standard construction is a Merkle root plus succinct proofs about paths. This article covers fixed-depth sparse trees, how string ids become leaf indices, how a document becomes one leaf, and what a query proof hides.

Sparse Merkle trees

Sparse Merkle tree (SMT). Fix a depth dd and a two-to-one hash H:F2→FH : \mathbb{F}^2 \to \mathbb{F}. The tree has 2d2^d leaf slots indexed by i∈[0,2d)i \in [0, 2^d). Each slot holds a value ℓi\ell_i, which is either the empty value 00 or the hash of a record. Internal nodes are H(left,right)H(\text{left}, \text{right}), and the root commits to the whole vector (ℓ0,…,ℓ2d−1)(\ell_0, \dots, \ell_{2^d-1}).

Almost every slot is empty, so the tree is never materialised. Every empty subtree of height kk has the same hash, the default hash:

z0=0,zk+1=H(zk,zk).z_0 = 0, \qquad z_{k+1} = H(z_k, z_k).

Storing z0,…,zdz_0, \dots, z_d plus the nodes on paths to non-empty leaves costs O(n⋅d)O(n \cdot d) nodes for nn occupied leaves, independent of 2d2^d.

A membership proof for index ii is the list of dd sibling hashes on the path from leaf ii to the root. Write iki_k for bit kk of ii, with k=0k = 0 the lowest. Field elements are modelled as natural numbers and HH is a parameter:

/-- Hash `leaf` up the tree; bit `k` of `i` says whether the node at level `k`
  is a left (0) or right (1) child. One sibling per level. -/
def rootFrom (H : Nat → Nat → Nat) (leaf i : Nat) : List Nat → Nat
  | [] => leaf
  | s :: sib => rootFrom H (if i % 2 == 0 then H leaf s else H s leaf) (i / 2) sib

def verify (H : Nat → Nat → Nat) (root i leaf : Nat) (sib : List Nat) : Bool :=
  rootFrom H leaf i sib == root

/-- Default hashes: `z 0 = 0`, `z (k+1) = H (z k) (z k)`. -/
def z (H : Nat → Nat → Nat) : Nat → Nat
  | 0 => 0
  | k + 1 => H (z H k) (z H k)

/-- Hash of the height-`k` subtree starting at slot `lo`, given the occupied
  slots as `(index, leaf)` pairs. Empty subtrees short-cut to `z k`. -/
def subtree (H : Nat → Nat → Nat) (occ : List (Nat × Nat)) : Nat → Nat → Nat
  | 0, lo => (occ.lookup lo).getD 0
  | k + 1, lo =>
    if occ.any (fun (j, _) => lo ≤ j && j < lo + 2 ^ (k + 1))
    then H (subtree H occ k lo) (subtree H occ k (lo + 2 ^ k))
    else z H (k + 1)

/-- The `d` siblings on the path from slot `i`. -/
def siblings (H : Nat → Nat → Nat) (occ : List (Nat × Nat)) (d i : Nat) : List Nat :=
  (List.range d).map fun k => subtree H occ k (((i / 2 ^ k) ^^^ 1) * 2 ^ k)

To run the definitions, a toy stand-in for HH is enough (it is not collision-resistant; it only exercises the paths). Here is a depth-4 tree with two occupied slots:

-- continues the definitions above: a toy stand-in for H, depth-4 tree
def toyH (a b : Nat) : Nat := (a * 1000003 + b * 999983 + 12345) % 2147483647
def occ : List (Nat × Nat) := [(5, 42), (12, 7)]
def root : Nat := subtree toyH occ 4 0

#guard verify toyH root 5 42 (siblings toyH occ 4 5)       -- membership
#guard verify toyH root 3 0 (siblings toyH occ 4 3)        -- non-membership
#guard !verify toyH root 5 41 (siblings toyH occ 4 5)      -- wrong leaf fails
#eval (siblings toyH occ 4 5).length                       -- 4

A non-membership proof is the same check with leaf = 0, as in the second #guard. Because the slot is addressed directly, one path suffices; sorted trees need two neighbouring leaves. Proof length is exactly dd hashes. Compressed variants shorten proofs on average, but a circuit is fixed at compile time and pays for all dd levels anyway.

Binding. If verify H root i ℓ s and verify H root i ℓ′ s′ both accept with ℓ≠ℓ′\ell \ne \ell' and ∣s∣=∣s′∣=d|s| = |s'| = d, then a collision of HH can be read off the two paths.

Proof sketch. Let hkh_k and hk′h'_k be the intermediate values, with h0=ℓ≠h0′=ℓ′h_0 = \ell \ne h'_0 = \ell' and hd=hd′h_d = h'_d. Take the largest kk with hk≠hk′h_k \ne h'_k. Then hk+1=hk+1′h_{k+1} = h'_{k+1}, and the two inputs to HH at level kk differ in the slot selected by iki_k, so they form a collision. Both proofs use the same ii, so left and right cannot be swapped, and requiring exactly dd siblings means no proof can present an internal node as a leaf, the confusion variable-depth trees handle with domain separation. ∎

From string ids to leaf indices

Documents have string ids, while leaves have integer indices below 2d2^d. The map needs to be injective, so that two ids never share a slot. It also needs to be computable without a lookup table, so that anyone can derive the slot from the id.

Two-digit packing. Fix the 64-symbol alphabet A–Z, a–z, 0–9, -, _ with codes 0…630 \dots 63 in that order. For an id s=c1⋯cLs = c_1 \cdots c_L, write a leading digit 1 and then each code as two decimal digits:

φ(s)=102L+∑j=1Lcode(cj) 102(L−j).\varphi(s) = 10^{2L} + \sum_{j=1}^{L} \mathrm{code}(c_j)\, 10^{2(L-j)} .

For example φ(A)=100\varphi(\texttt{A}) = 100, φ(AA)=10000\varphi(\texttt{AA}) = 10000, φ(Bob)=1014027\varphi(\texttt{Bob}) = 1014027 and φ(__)=16363\varphi(\texttt{\_\_}) = 16363.

The leading 1 is required. Without it, A, AA and the empty string would all map to 00.

Injectivity. φ\varphi is injective on all strings over the alphabet.

Proof. Since 0≤code≤630 \le \mathrm{code} \le 63, we have 102L≤φ(s)<2⋅102L10^{2L} \le \varphi(s) \lt 2 \cdot 10^{2L}. So φ(s)\varphi(s) has exactly 2L+12L + 1 decimal digits, and the digit count determines LL. With LL known, the digits after the leading 1 split into LL pairs, and each pair determines its symbol. ∎

Capacity. The largest index of length LL is φ(_L)=102L+63⋅102L−199=18⋅102L−711\varphi(\texttt{\_}^L) = 10^{2L} + 63 \cdot \frac{10^{2L} - 1}{99} = \frac{18 \cdot 10^{2L} - 7}{11}. Every id of length at most LL fits a depth-dd tree iff this value is below 2d2^d, which is approximately

2L+log⁡101811<dlog⁡102,Lmax⁡(d)=⌊dlog⁡102−0.21392⌋.2L + \log_{10}\tfrac{18}{11} \lt d \log_{10} 2, \qquad L_{\max}(d) = \left\lfloor \frac{d \log_{10} 2 - 0.2139}{2} \right\rfloor .

The rough rule L≈dlog⁡102/2L \approx d\log_{10}2 / 2 leaves out the log⁡10(18/11)\log_{10}(18/11) term, and that matters at the boundary. I checked every case below exactly with big integers:

depth ddLmax⁡L_{\max}, 64 symbols31 symbols, 3 digits per 2binary, 6 bits per symbol
32465
68101311
100141916
168253327

At d=100d = 100, dlog⁡102=30.103d\log_{10}2 = 30.103, so the rough rule says 15. In fact φ(_15)≈1.636×1030\varphi(\texttt{\_}^{15}) \approx 1.636 \times 10^{30} exceeds 2100≈1.268×10302^{100} \approx 1.268 \times 10^{30}. A 15-symbol id fits only if its first symbol is in A–Z or is a, which is 27 of the 64 possible first symbols. In the same way, depth 67 is one level short for all 10-symbol ids, and 68 is the minimum. The checks, run on exact natural numbers:

def alphabet : String := "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_"

def code (c : Char) : Option Nat := alphabet.toList.indexOf? c

/-- Leading `1`, then each symbol code as two decimal digits. -/
def phi (s : String) : Option Nat :=
  s.toList.foldlM (fun acc c => (acc * 100 + ·) <$> code c) 1

#guard phi "A" = some 100 && phi "AA" = some 10000
#guard phi "Bob" = some 1014027 && phi "__" = some 16363

/-- Largest index of length `L` under each map. -/
def max64 (L : Nat) : Nat := (18 * 10 ^ (2 * L) - 7) / 11
def max31 (L : Nat) : Nat :=         -- pairs as 3 digits (max 960), odd symbol as 2
  let v := (List.replicate (L / 2) 960).foldl (· * 1000 + ·) 1
  if L % 2 == 1 then v * 100 + 30 else v
def maxBin (L : Nat) : Nat := ((List.range L).map fun j => 64 ^ (j + 1)).sum  -- shortlex

/-- Longest `L` such that every id of length ≤ `L` fits below `2^d`. -/
def lmax (f : Nat → Nat) (d : Nat) : Nat :=
  ((List.range 60).takeWhile (f · < 2 ^ d)).length - 1

#guard (List.range 30).all fun L => phi ⟨List.replicate L '_'⟩ = some (max64 L)
#eval [32, 68, 100, 168].map fun d => (lmax max64 d, lmax max31 d, lmax maxBin d)
  -- [(4, 6, 5), (10, 13, 11), (14, 19, 16), (25, 33, 27)]
#guard lmax max64 67 = 9
#eval (alphabet.toList.filter fun c =>          -- first symbols that let a
  (phi ⟨c :: List.replicate 14 '_'⟩).all (· < 2 ^ 100)).length   -- 15-symbol id fit: 27

The 31-symbol variant. If the alphabet is cut to 31 symbols, a pair of symbols has 312=961<100031^2 = 961 \lt 1000 values and fits in three decimal digits. An odd final symbol takes two digits. The digit count is then 1+3k1 + 3k for L=2kL = 2k and 3k+33k + 3 for L=2k+1L = 2k + 1. This sequence is strictly increasing in LL, so the injectivity argument carries over. It spends log⁡21000/2≈4.98\log_2 1000 / 2 \approx 4.98 index bits per symbol for log⁡231≈4.95\log_2 31 \approx 4.95 bits of information; the 64-symbol packing spends log⁡2100≈6.64\log_2 100 \approx 6.64 for 6, about 90% efficiency.

Binary baseline. The circuit decomposes the index into dd bits whatever the map, so decimal digits buy nothing inside the proof. A bijective base-64 numbering in shortlex order reaches 16 symbols at depth 100 and 27 at depth 168. The decimal map is only easier to read. A simpler binary map reads the id’s UTF-8 bytes as one big-endian integer; at 8 bits per byte it fits 12 bytes at depth 100 and 21 at depth 168, and it is injective only if ids never begin with a zero byte.

A whole document as one leaf

A leaf has to be a single field element. A document is first turned into a sequence of integers by a canonical integer encoding of JSON: leaves are sorted by path, so two objects that list the same keys in different orders encode identically. Paths are flattened and each value carries a type tag:

valueencoding
null[0]
true[1, 1]
1[2, 1, 0, 1] (type, sign, decimals, digits)
-1[2, 0, 0, 1]
3.14[2, 1, 2, 314]
"abc"[3, 3, 97, 98, 99]

The integers are then written as decimal digit strings and packed into field elements of at most 76 digits, each starting with a digit 1. An integer is written behind a digit giving its length, so that boundaries survive concatenation; an integer of more than 8 digits is written as 9, its first 8 digits, and then the rest as a further token. A run of three to nine single-digit integers is written more compactly as 0, the run length, and the digits. The scalar field of BN254 has a 77-digit modulus r≈2.19×1076r \approx 2.19 \times 10^{76}, so every 76-digit number is below rr and no packed signal wraps around. The document {"a":1} encodes to [1, 1, 97, 2, 1, 0, 1] and packs into the single element 11111297042101: the leading 1, then 11, 11, 297 and the run 042101. The 66-character document in the check below encodes to 72 integers, which pack into three elements of 76, 76 and 8 digits. A run cut by an element boundary is restarted in the next element, and a piece of fewer than three digits on either side of the cut is written as plain tokens. The encoding, flattening every scalar to its path and sorting the rows by path:

inductive Json where
  | null | bool (b : Bool) | num (m : Int) (dec : Nat)   -- m / 10^dec
  | str (s : String) | arr (xs : List Json) | obj (kvs : List (String × Json))
inductive Key where | name (s : String) | index (n : Nat)

mutual  -- flatten to (path, scalar) pairs
def leaves (pre : List Key) : Json → List (List Key × Json)
  | .arr xs => items pre 0 xs
  | .obj kvs => fields pre kvs
  | v => [(pre, v)]
def items (pre : List Key) (i : Nat) : List Json → List (List Key × Json)
  | [] => []
  | x :: xs => leaves (pre ++ [.index i]) x ++ items pre (i + 1) xs
def fields (pre : List Key) : List (String × Json) → List (List Key × Json)
  | [] => []
  | (k, v) :: kvs => leaves (pre ++ [.name k]) v ++ fields pre kvs
end

def chars (s : String) : List Nat := s.length :: s.toList.map Char.toNat

def encKey : Key → List Nat
  | .name "" => [0, 1]               -- the empty key, kept apart from an index
  | .name s => chars s
  | .index n => [0, 0, n]

def encPath (p : List Key) : List Nat := p.length :: p.flatMap encKey

def encVal : Json → List Nat
  | .null => [0] | .bool b => [1, if b then 1 else 0]
  | .num m d => [2, if m < 0 then 0 else 1, d, m.natAbs]
  | .str s => 3 :: chars s
  | _ => []                        -- containers never reach a leaf

/-- Paths in key order: names by code points, indices as numbers. -/
def pathLe : List Key → List Key → Bool
  | [], _ => true
  | _ :: _, [] => false
  | .name a :: p, .name b :: q => if a == b then pathLe p q else decide (a < b)
  | .index a :: p, .index b :: q => if a == b then pathLe p q else decide (a < b)
  | _, _ => false                  -- a name and an index never meet

def encode (j : Json) : List Nat :=
  ((leaves [] j).mergeSort fun a b => pathLe a.1 b.1).flatMap fun (p, v) => encPath p ++ encVal v

The packing into digit strings:

-- packing digit strings (self-contained; used with `encode` below)
/-- A token is `digit count ++ digits` for at most 8 digits, `9 ++ 8 digits`
  followed by a further token for more, or a run of 3–9 single-digit
  integers as `0 ++ run length ++ digits`. -/
inductive Tok where | lit (s : String) | run (ds : List Nat)
def Tok.str : Tok → String
  | .lit s => s
  | .run ds => "0" ++ toString ds.length ++ String.join (ds.map toString)
def lits (ds : List Char) : List Tok :=
  if ds.length ≤ 8 then [.lit s!"{ds.length}{String.mk ds}"]
  else .lit s!"9{String.mk (ds.take 8)}" :: lits (ds.drop 8)
termination_by ds.length
decreasing_by simp_wf; omega
def flush (buf : List Nat) : List Tok :=
  if buf.length ≥ 3 then [.run buf] else buf.map fun d => .lit s!"1{d}"
def tokens (buf : List Nat) : List Nat → List Tok
  | [] => flush buf
  | x :: xs =>
    if x ≥ 10 then flush buf ++ lits (toString x).toList ++ tokens [] xs
    else if buf.length == 9 then flush buf ++ tokens [x] xs
    else tokens (buf ++ [x]) xs

/-- Fill 75 digits per element; a run that straddles a boundary is cut and
  restarted, and a piece shorter than 3 is written as plain tokens.
  (`partial`: the cut puts the rest of the run back on the input.) -/
partial def fill (cur : String) : List Tok → List String
  | [] => [cur]
  | t :: ts =>
    let room := 75 - cur.length
    if t.str.length ≤ room then fill (cur ++ t.str) ts
    else match t with
      | .run ds =>
          let k := if room ≥ 5 then room - 2 else room / 2
          (cur ++ String.join ((flush (ds.take k)).map Tok.str)) ::
            fill "" (tokens [] (ds.drop k) ++ ts)
      | .lit _ => cur :: fill "" (t :: ts)

def pack (xs : List Nat) : List String := (fill "" (tokens [] xs)).map ("1" ++ ·)

And the stated sizes:

-- continues the definitions above
def a1 : Json := .obj [("a", .num 1 0)]
#guard encode a1 = [1, 1, 97, 2, 1, 0, 1]
#guard pack (encode a1) = ["11111297042101"]
#guard encVal .null = [0] && encVal (.bool true) = [1, 1]          -- the table
#guard encVal (.num (-1) 0) = [2, 0, 0, 1] && encVal (.num 314 2) = [2, 1, 2, 314]
#guard encVal (.str "abc") = [3, 3, 97, 98, 99]

def text := r#"{"a":1,"c":false,"b":{"e":null,"d":"four"},"f":3.14,"ghi":[5,6,7]}"#
#guard text.length = 66
def doc : Json := .obj [("a", .num 1 0), ("c", .bool false),
  ("b", .obj [("e", .null), ("d", .str "four")]), ("f", .num 314 2),
  ("ghi", .arr [.num 5 0, .num 6 0, .num 7 0])]

#eval (encode doc).length                  -- 72
#eval (pack (encode doc)).map String.length -- [76, 76, 8]
#guard pack (encode doc) =
  ["1111129706210121298113100131431023111311731141211298113101030112990410113102",
   "1032123314121331033104310509000210523310331043105090012106233103310431051010",
   "10522107"]

-- key order does not matter, and the empty key is kept apart from an index
#guard encode (.obj [("a", .num 1 0), ("b", .null)]) = encode (.obj [("b", .null), ("a", .num 1 0)])
#guard encode (.obj [("", .arr [.num 1 0])]) ≠ encode (.arr [.obj [("", .num 1 0)]])
-- an integer of more than 8 digits is split into a `9` token and a continuation
#guard pack [1234567890] = ["1912345678290"]

-- every 76-digit element is below the BN254 scalar field modulus r (77 digits)
def r : Nat := 21888242871839275222246405745257275088548364400416034343698204186575808495617
#guard 10 ^ 76 ≤ r && r < 10 ^ 77

The circuit fixes the document size at 256 elements, which is 256×76=19,456256 \times 76 = 19{,}456 digits. A Poseidon instance with 16 inputs hashes them as a two-level tree:

ℓ=H16(H16(s1..s16), H16(s17..s32), …, H16(s241..s256)),\ell = H_{16}\big(H_{16}(s_1..s_{16}),\ H_{16}(s_{17}..s_{32}),\ \dots,\ H_{16}(s_{241}..s_{256})\big),

which is 17 calls in all. Unused elements are zero. The packing gives every real element a leading digit 1, so a real element is never zero and zero-padding is unambiguous. As a result ℓ\ell commits to the document’s encoding and not merely to a prefix of it. The encoding keeps only scalar leaves, so empty arrays and objects leave no trace: {}, {"a":[]} and {"a":{}} all encode to the empty list and share a leaf.

Two levels: collections inside a database

A document store has collections. The same structure is used one level up. Each collection is an SMT of depth dcd_c over document leaves, and its root becomes a leaf of a database SMT of depth dbd_b. Collection slots are plain counters, not packed strings, so a small tree suffices and keeps the circuit small. With db=8d_b = 8 there are 256 collections. With dc=168d_c = 168 a collection admits every id of up to 25 symbols.

Two-level sparse Merkle state with on-chain commitmentJSON documents are canonically encoded and hashed into collection sparse Merkle trees. Collection roots are leaves of a database sparse Merkle tree. The database root is committed on-chain with a validity proof, and values are queried by proof against that root.EVM · on-chainState verifierroot · commit(zkp)Query verifierget(path, proof) …DB rootSMT of collection rootsproof of transitionuserscollection SMT rootpostscollection SMT root…"Bob"id → SMT index"Alice"id → SMT index"post1"id → SMT indexleaf = H(enc(doc))JSON → uint signals (≤76 digits each)prove one path without revealing the doc
Fig. 1Two-level state. Documents are encoded and hashed into collection trees, collection roots are leaves of the database tree, and only the database root is kept by the verifying contract.

A proof about one document is two path checks chained together. The document leaf is checked against its collection root, and that root is checked against the database root. That costs dc+db=176d_c + d_b = 176 hash evaluations, plus 17 to hash the leaf.

State transitions in batches

The verifier stores one value, the current database root RR. A write replaces one leaf. The siblings on its path do not change, so the old and new roots come from the same sibling list:

-- continues the Merkle definitions above (rootFrom, z, subtree, siblings, toyH)
/-- One write. Leaves are already document hashes; 0 is the empty slot, so
  insert is `oldLeaf = 0` and delete is `newLeaf = 0`. -/
structure Write where
  col : Nat
  i : Nat
  oldLeaf : Nat
  newLeaf : Nat
  sibDoc : List Nat  -- d_c siblings, valid for both the old and the new leaf
  sibCol : List Nat  -- d_b siblings

def applyWrite (H : Nat → Nat → Nat) (R : Nat) (w : Write) : Option Nat :=
  let cOld := rootFrom H w.oldLeaf w.i w.sibDoc            -- d_c hashes
  if rootFrom H cOld w.col w.sibCol == R then              -- d_b hashes
    let cNew := rootFrom H w.newLeaf w.i w.sibDoc          -- d_c hashes
    some (rootFrom H cNew w.col w.sibCol)                  -- d_b hashes
  else none

/-- A batch chains R₀ → R₁ → … → Rₘ; any failed opening rejects it. -/
def applyBatch (H : Nat → Nat → Nat) (R₀ : Nat) (ws : List Write) : Option Nat :=
  ws.foldlM (applyWrite H) R₀

-- empty db (d_b = 1) of empty collections (d_c = 2): insert leaf 42 at col 1, slot 2
def R₀ : Nat := z toyH 3
def ins : Write := ⟨1, 2, 0, 42, [z toyH 0, z toyH 1], [z toyH 2]⟩
#guard applyBatch toyH R₀ [ins] = some (toyH (z toyH 2) (subtree toyH [(2, 42)] 2 0))
#guard applyBatch toyH R₀ [{ ins with oldLeaf := 5 }] = none   -- wrong old leaf
#guard 2 * (168 + 8) + 2 * 17 = 386                            -- Poseidon calls per write

Insert and delete are the cases where the old or new leaf is 0. A batch of mm writes chains R0→R1→⋯→RmR_0 \to R_1 \to \dots \to R_m. Siblings for write jj are taken against Rj−1R_{j-1}, so later writes see earlier ones. Only R0R_0 and RmR_m are public. The contract checks the proof and that R0R_0 equals its stored root, then stores RmR_m.

  1. off-chain
    Order writes

    m writes, each a doc slot and new content

  2. witness
    Chain roots
    R0 → R1 → … → Rm
  3. prove
    One SNARK

    public: R0, Rm; private: docs and siblings

  4. contract
    Swap root
    if R₀ == R then R := Rₘ
  5. later
    Query

    proofs checked against the new R

Fig. 2One batch: writes are applied in order, the circuit proves the chain of roots, and the contract swaps one stored root for another after checking the proof.

Transition soundness. If HH is collision-resistant and the proof system is knowledge-sound, an accepted batch proof yields documents and writes whose sequential application takes the committed state of R0R_0 to that of RmR_m.

Sketch. The extracted witness contains, for each step, an old leaf and siblings, exactly dcd_c and dbd_b of them, that open Rj−1R_{j-1}. By binding these are the true current contents of that slot. Because the same siblings are reused, the only change from Rj−1R_{j-1} to RjR_j is at that slot. ∎

Cost. Each write costs 2(dc+db)2(d_c + d_b) path hashes and two leaf hashes. With dc=168d_c = 168, db=8d_b = 8 that is 352+34=386352 + 34 = 386 Poseidon calls. A batch of 10 is 3,860, before the constraints that parse and check the encodings. The circuit is fixed-size, so a shorter batch must be padded with no-op writes. The constraint count, and with it the size of the trusted setup, grows linearly in mm and, for fixed mm, in dc+dbd_c + d_b and in the document size. Verification does not depend on mm, dcd_c or the document size. A Groth16 proof is three group elements, which is eight 32-byte words, and the work grows only with the number of public inputs.

Queries against the committed root

A query proof opens one path inside one document. The circuit’s statement, with the leaf hash and the path lookup as parameters:

-- continues the Merkle definitions above (uses rootFrom)
/-- What the query asserts about the value at `path`. -/
inductive Claim where
  | value (enc : List Nat)                          -- valueAt doc path = some enc
  | cond (pred : List Nat → Bool) (result : Bool)   -- pred value = result bit

structure QueryPublic where   -- public inputs
  R : Nat
  col : Nat
  i : Nat
  path : List Nat
  claim : Claim

structure QueryWitness where  -- private: stays in the proof
  doc : List Nat              -- 256 packed elements
  sibDoc : List Nat
  sibCol : List Nat

def queryOk (H : Nat → Nat → Nat) (leaf : List Nat → Nat)
    (valueAt : List Nat → List Nat → Option (List Nat))
    (q : QueryPublic) (w : QueryWitness) : Bool :=
  rootFrom H (rootFrom H (leaf w.doc) q.i w.sibDoc) q.col w.sibCol == q.R &&
  match valueAt w.doc q.path, q.claim with
  | some v, .value enc => v == enc
  | some v, .cond p b => p v == b
  | none, _ => false

The contract checks the proof and then checks that the public RR equals its stored root. For {"a":1} the public part is the path a and the value 1 in encoded form, and the rest of the document stays in the witness. The value is returned typed, or as a raw encoded subtree from which further paths can be read on-chain without a new proof.

A conditional query replaces the value with a predicate and a single result bit. The predicate is encoded the same way as values and passed as a public input. The predicates are order comparisons on numbers, strings and booleans ($gt, $gte, $lt, $lte), equality and set membership on any type ($eq, $ne, $in, $nin), and containment on arrays ($contains and its any/all/none forms). Comparing decimals needs care: 3.143.14 and 33 are encoded with different decimal counts, so the circuit has to scale to a common exponent before comparing digit strings.

What is hidden and what is not. If the proof system is zero-knowledge, the rest of the document, the other documents and the sibling hashes stay hidden from the proof itself. Leaves are unsalted hashes, though, so state that an observer can guess in full can be checked against the public root. The following are public:

  • the root, and with it the timing of every state change;
  • the collection slot and the document slot. Because φ\varphi is invertible, the slot reveals the id itself;
  • the queried path, and either the value or the predicate together with its truth value.

Repeated threshold queries on one field amount to a binary search, so $gt hides a number only if the verifier is limited in how many such queries it can ask. Hashing the id into a slot, i=H(id) mod 2di = H(\text{id}) \bmod 2^d, hides it only against an observer who cannot guess likely ids, and brings collisions after about 2d/22^{d/2} ids.

Costs, limits and open questions

The three size parameters pull against each other. A larger depth dcd_c allows longer ids, about one symbol per 6.646.64 levels with the decimal map. But every level adds two hashes per write and one per query. The document size fixes the leaf-hash and parsing cost of every proof, even for tiny documents. A larger batch spreads the fixed verification cost, but setup and proving time grow with it.

Other limits:

  • Data availability. The contract holds a root, not data. If the operator withholds documents, nobody else can prove anything or continue the state.
  • Single writer. One committer orders writes. Proofs stop that committer from forging state, but not from censoring writes or reordering them.

Open questions I would like to settle: whether a shortlex binary id map, or a two-tier map with short ids in a dense subtree, gives a better trade-off between depth and id length than decimal packing; how to amortise the 17-call leaf hash when a write changes one field (for example, a Merkle tree over the document’s own paths); and whether recursive proof composition can remove the fixed batch size without bringing back per-batch setup.