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 to state ” only if some valid sequence of writes takes to . 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 and a two-to-one hash . The tree has leaf slots indexed by . Each slot holds a value , which is either the empty value or the hash of a record. Internal nodes are , and the root commits to the whole vector .
Almost every slot is empty, so the tree is never materialised. Every empty subtree of height has the same hash, the default hash:
Storing plus the nodes on paths to non-empty leaves costs nodes for occupied leaves, independent of .
A membership proof for index is the list of sibling hashes on the path from leaf to the root. Write for bit of , with the lowest. Field elements are modelled as natural numbers and 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 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 hashes. Compressed variants shorten proofs on average, but a circuit is fixed at compile time and pays for all levels anyway.
Binding. If verify H root i ℓ s and verify H root i ℓ′ s′ both accept with and , then a collision of can be read off the two paths.
Proof sketch. Let and be the intermediate values, with and . Take the largest with . Then , and the two inputs to at level differ in the slot selected by , so they form a collision. Both proofs use the same , so left and right cannot be swapped, and requiring exactly 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 . 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 in that order. For an id , write a leading digit 1 and then each code as two decimal digits:
For example , , and .
The leading 1 is required. Without it, A, AA and the empty string would all map to .
Injectivity. is injective on all strings over the alphabet.
Proof. Since , we have . So has exactly decimal digits, and the digit count determines . With known, the digits after the leading 1 split into pairs, and each pair determines its symbol. ∎
Capacity. The largest index of length is . Every id of length at most fits a depth- tree iff this value is below , which is approximately
The rough rule leaves out the term, and that matters at the boundary. I checked every case below exactly with big integers:
| depth | , 64 symbols | 31 symbols, 3 digits per 2 | binary, 6 bits per symbol |
|---|---|---|---|
| 32 | 4 | 6 | 5 |
| 68 | 10 | 13 | 11 |
| 100 | 14 | 19 | 16 |
| 168 | 25 | 33 | 27 |
At , , so the rough rule says 15. In fact exceeds . 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 values and fits in three decimal digits. An odd final symbol takes two digits. The digit count is then for and for . This sequence is strictly increasing in , so the injectivity argument carries over. It spends index bits per symbol for bits of information; the 64-symbol packing spends for 6, about 90% efficiency.
Binary baseline. The circuit decomposes the index into 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:
| value | encoding |
|---|---|
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 , so every 76-digit number is below 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 digits. A Poseidon instance with 16 inputs hashes them as a two-level tree:
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 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 over document leaves, and its root becomes a leaf of a database SMT of depth . Collection slots are plain counters, not packed strings, so a small tree suffices and keeps the circuit small. With there are 256 collections. With a collection admits every id of up to 25 symbols.
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 hash evaluations, plus 17 to hash the leaf.
State transitions in batches
The verifier stores one value, the current database root . 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 writes chains . Siblings for write are taken against , so later writes see earlier ones. Only and are public. The contract checks the proof and that equals its stored root, then stores .
- off-chainOrder writes
m writes, each a doc slot and new content
- contractSwap root
if R₀ == R then R := Rₘ - laterQuery
proofs checked against the new R
Transition soundness. If 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 to that of .
Sketch. The extracted witness contains, for each step, an old leaf and siblings, exactly and of them, that open . By binding these are the true current contents of that slot. Because the same siblings are reused, the only change from to is at that slot. ∎
Cost. Each write costs path hashes and two leaf hashes. With , that is 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 and, for fixed , in and in the document size. Verification does not depend on , 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 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: and 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 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, , hides it only against an observer who cannot guess likely ids, and brings collisions after about ids.
Costs, limits and open questions
The three size parameters pull against each other. A larger depth allows longer ids, about one symbol per 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.