An arithmetic circuit sees only elements of a prime field , wired into a fixed graph of additions and multiplications. It has no strings, no objects, no variable-length arrays and no branches whose shape depends on the data. A JSON document has all of these. To prove something about a document in a SNARK, such as “the value at path b.d is the string four”, the document first has to become a fixed-size vector of field elements. That map has to be well defined, injective and cheap to parse inside the circuit.
This article describes one such map, in five layers. I give the definition of each layer, an argument that the whole map is injective and canonical, the statement the circuit proves, and what the representation costs. Every number below is computed by the Lean 4 snippets along the way. They are a complete encoder, plus the first two steps of the decoder. Read in order they form one file that compiles without errors: every example is checked by the Lean compiler, and each #eval comment shows the output it prints.
The constraints
The target is the scalar field of BN254, with
has 77 decimal digits and . Three properties of the setting shape the design.
- Fixed arity. A circuit has a fixed number of input signals. A document gets field elements (default ), padded with zeros.
- No dynamic structure. Nesting must be flattened into a linear sequence before the circuit sees it. The circuit can then scan it with a fixed, unrolled loop.
- Arithmetic, not bytes. Splitting a field element into decimal digits or bits costs constraints, but the cost is uniform. So any self-delimiting digit grammar can be parsed. The encoding is chosen so that the parser is a small state machine over decimal digits.
The commitment to a document is a hash of its field elements. For that hash to identify the document, equal documents must give equal vectors. That is the canonicality requirement.
- 03Integers
paths and values become natural numbers
- 04Digit tokens
length-prefixed, runs of single digits merged
- 05Pack
guard digit plus 75 digits per element
Paths, order and integers
Flattening. For a JSON value , is the set of pairs where is a primitive (null, boolean, number or string) and is the sequence of object keys (strings) and array indices (naturals) that leads from the root to . A primitive at the top level has the empty path, .
Order. Paths are compared component by component. Two keys compare by their code-point sequences, lexicographically. Two indices compare as integers. A key and an index never meet at the same position, because a container is either an object or an array.
The running example is the 66-character document {"a":1,"c":false,"b":{"e":null,"d":"four"},"f":3.14,"ghi":[5,6,7]}. In Lean, a JSON value is an inductive type, and numeric literals are read straight into the form used below.
/-- A number in shortest decimal form: (-1)^(1-s) · m / 10^d. -/
structure Num where
s : Bool -- true for non-negative
d : Nat -- digits after the decimal point
m : Nat -- the digit string with the point removed
deriving Repr, BEq
inductive Json where
| null
| bool (b : Bool)
| num (n : Num)
| str (s : String)
| arr (xs : List Json)
| obj (kvs : List (String × Json))
/-- Strip trailing zeros after the point: 3.140 becomes (2, 314). -/
def Num.norm (s : Bool) : Nat → Nat → Num
| m, 0 => ⟨s, 0, m⟩
| m, d + 1 => if m % 10 = 0 then norm s (m / 10) d else ⟨s, d + 1, m⟩
instance : OfNat Json n := ⟨.num ⟨true, 0, n⟩⟩
instance : OfScientific Json :=
⟨fun m neg e => .num (if neg then Num.norm true m e else ⟨true, 0, m * 10 ^ e⟩)⟩
instance : Neg Json := ⟨fun | .num ⟨s, d, m⟩ => .num ⟨m == 0 || !s, d, m⟩ | j => j⟩
instance : Coe String Json := ⟨.str⟩
instance : Coe Bool Json := ⟨.bool⟩
-- {"a":1,"c":false,"b":{"e":null,"d":"four"},"f":3.14,"ghi":[5,6,7]}
def doc : Json := .obj [("a", 1), ("c", false),
("b", .obj [("e", .null), ("d", "four")]), ("f", 3.14), ("ghi", .arr [5, 6, 7])]
It has eight leaves. In sorted order they are a, b.d, b.e, c, f, ghi[0], ghi[1], ghi[2]. The order the keys were written in is gone at this point. Flattening is a structural recursion over the tree, and sorting is a merge sort on paths.
-- continues the definitions above
inductive Key where
| name (k : String) -- object key
| idx (i : Nat) -- array index
deriving BEq
abbrev Path := List Key
mutual
/-- One row per leaf: the path to it and the primitive found there. -/
def Json.leaves : Json → List (Path × Json)
| .arr xs => leavesArr 0 xs
| .obj kvs => leavesObj kvs
| v => [([], v)]
def leavesArr (i : Nat) : List Json → List (Path × Json)
| [] => []
| x :: xs => x.leaves.map (fun (p, v) => (.idx i :: p, v)) ++ leavesArr (i + 1) xs
def leavesObj : List (String × Json) → List (Path × Json)
| [] => []
| (k, x) :: kvs => x.leaves.map (fun (p, v) => (.name k :: p, v)) ++ leavesObj kvs
end
-- continues the definitions above
/-- Keys by code points, indices as integers; the two never meet. -/
def Key.lt : Key → Key → Bool
| .name a, .name b => decide (a < b)
| .idx i, .idx j => decide (i < j)
| _, _ => false
def Path.le : Path → Path → Bool
| [], _ => true
| _ :: _, [] => false
| a :: p, b :: q => if a == b then Path.le p q else a.lt b
def Json.rows (j : Json) : List (Path × Json) :=
j.leaves.mergeSort (fun a b => Path.le a.1 b.1)
def Path.show (p : Path) : String :=
".".intercalate (p.map fun | .name k => k | .idx i => s!"[{i}]") |>.replace ".[" "["
#eval doc.rows.map (·.1.show)
-- ["a", "b.d", "b.e", "c", "f", "ghi[0]", "ghi[1]", "ghi[2]"]
A path component has to distinguish three things with nothing but natural numbers: a non-empty key, the empty key "", and an array index. The key "0" and the index 0 must not collide either. A length prefix does this, with reserved as an escape.
Path encoding.
The top-level path is .
So ghi[0] is . The document {"0":1} starts with the path , and [1] starts with .
-- continues the definitions above
def codes (s : String) : List Nat := s.toList.map Char.toNat
def Key.enc : Key → List Nat
| .name "" => [0, 1]
| .name k => k.length :: codes k
| .idx i => [0, 0, i]
def Path.enc (p : Path) : List Nat := p.length :: p.flatMap Key.enc
example : Path.enc [.name "ghi", .idx 0] = [2, 3, 103, 104, 105, 0, 0, 0] := by decide
example : Path.enc [.name "0"] = [1, 1, 48] := by decide
example : Path.enc [.idx 1] = [1, 0, 0, 1] := by decide
example : Path.enc [.name ""] = [1, 0, 1] := by decide
example : Path.enc [] = [0] := by decide
Values carry a type tag in their first integer.
Value encoding.
| type | tag | encoding | example |
|---|---|---|---|
| null | 0 | null → | |
| boolean | 1 | true → | |
| number | 2 | 3.14 → | |
| string | 3 | "abc" → | |
| array or object | 4 | followed by the encoded sub-document | used for query results |
For a number, is for non-negative and for negative, is the number of digits after the decimal point in the shortest decimal form, and is the digit string with the point removed, read as a natural number. So , , , and the value is .
-- continues the definitions above
def Json.val : Json → List Nat
| .null => [0]
| .bool b => [1, if b then 1 else 0]
| .num ⟨s, d, m⟩ => [2, if s then 1 else 0, d, m]
| .str s => 3 :: s.length :: codes s
| _ => [4] -- a container; its sub-document follows (query results)
#eval [Json.null, true, "abc", 3.14, 1, -1, -12.5].map Json.val
-- [[0], [1, 1], [3, 3, 97, 98, 99], [2, 1, 2, 314], [2, 1, 0, 1], [2, 0, 0, 1], [2, 0, 1, 125]]
example : Json.val (-0) = Json.val 0 := by decide -- -0 and 0 share a code
example : Json.val 1e21 = [2, 1, 0, 10 ^ 21] := by decide -- exponents are expanded
example : Json.val 1e-7 = [2, 1, 7, 1] := by decide
The integer layer is the concatenation of over the sorted leaves. For {"a":1} this gives . For the running example it gives 72 integers.
-- continues the definitions above
def Json.ints (j : Json) : List Nat :=
j.rows.flatMap fun (p, v) => p.enc ++ v.val
#eval Json.ints (.obj [("a", 1)]) -- [1, 1, 97, 2, 1, 0, 1]
#eval doc.ints.length -- 72
Digits and packing
Concatenating the decimal forms of the integers would lose the boundaries between them. Each integer therefore becomes one or more tokens: a single length digit followed by that many digits.
Digit tokens. Let be the decimal string of , with .
- If : emit , then .
- If : emit and the first 8 digits, then continue with the remaining digits as a string. Leading zeros are kept from this point on.
So and . A length digit is never .
Run compression. Most integers in the layer above are single digits, which cost two digits each as tokens. A maximal run of consecutive one-digit integers (each a two-digit token), with , is replaced by , and the digits. That costs digits in place of . Runs of 1 or 2 are left as they are, because compressing them would not save anything. A one-digit continuation token, such as the 19 that ends , is never merged into a run, since it is the tail of a longer integer.
The escape digit is free because no token has length . A run longer than 9 is split, since the count is a single digit.
-- continues the definitions above
/-- One integer, as a digit string, becomes one or more length-prefixed tokens. -/
def tok (ds : List Char) : List String :=
if ds.length ≤ 8 then [s!"{ds.length}{String.mk ds}"]
else s!"9{String.mk (ds.take 8)}" :: tok (ds.drop 8)
termination_by ds.length
decreasing_by simp_wf; omega
def tokens (xs : List Nat) : List String := xs.flatMap fun x => tok (toString x).toList
#eval tokens [123, 1234567890] -- ["3123", "912345678", "290"]
#eval (tokens doc.ints).length -- 72
#eval (String.join (tokens doc.ints)).length -- 182
-- continues the definitions above
inductive Item where
| tok (t : String) -- a token as it stands
| run (ds : List Char) -- 3 to 9 one-digit tokens
/-- `0`, the count, then the digits; runs shorter than 3 stay plain tokens. -/
def runStr (ds : List Char) : String :=
if ds.length ≥ 3 then s!"0{ds.length}{String.mk ds}"
else String.join (ds.map fun d => s!"1{d}")
def flush (acc : List Char) : List Item :=
if acc.length ≥ 3 then [.run acc] else acc.map fun d => .tok s!"1{d}"
/-- Merge maximal runs of one-digit integers, at most 9 per run.
A one-digit continuation token is never merged: it ends a longer integer. -/
def compress (acc : List Char) : List Nat → List Item
| [] => flush acc
| x :: xs =>
if x < 10 then
if acc.length == 9 then flush acc ++ compress [x.digitChar] xs
else compress (acc ++ [x.digitChar]) xs
else flush acc ++ (tok (toString x).toList).map .tok ++ compress [] xs
Packing. The digit stream is cut into chunks of at most 75 digits, and each chunk is prefixed with the guard digit . The guard is needed because a chunk can begin with the run marker , which would disappear when the chunk is read as an integer. The cut is made at token boundaries. When a run does not fit in the space left in a chunk, it is shortened to fit, and the rest of the run goes into the next chunk.
-- continues the definitions above
/-- Fill chunks of at most 75 digits; a run that does not fit is cut in two. -/
def fill (room : Nat) (cur : String) : List Item → List String
| [] => if cur.isEmpty then [] else [cur]
| .tok t :: rest =>
if t.length ≤ room then fill (room - t.length) (cur ++ t) rest
else cur :: fill (75 - t.length) t rest
| .run ds :: rest =>
if ds.length + 2 ≤ room then
fill (room - ds.length - 2) (cur ++ runStr ds) rest
else
let k := if room ≥ 5 then room - 2 else room / 2
let next := runStr (ds.drop k)
(cur ++ runStr (ds.take k)) :: fill (75 - next.length) next rest
/-- Guard digit 1, then the chunk, read as one natural number. -/
def Json.encode (j : Json) : List Nat :=
(fill 75 "" (compress [] j.ints)).map fun c => ("1" ++ c).toNat!
#eval Json.encode (.obj [("a", 1)]) -- [11111297042101]
Why 76 digits are safe. A packed element has at most 76 digits, so it is less than . And , so the integer is its own field representative and no reduction mod ever happens. A 77-digit chunk could be as large as , and it would wrap around. The same 76-digit value also fits in a 256-bit machine word, since . Seventy-five payload digits carry bits, about 98% of .
-- continues the definitions above
def p : Nat :=
21888242871839275222246405745257275088548364400416034343698204186575808495617
example : (toString p).length = 77 := by decide
example : 10 ^ 76 < p := by decide -- 76 digits never wrap
example : p < 10 ^ 77 - 1 := by decide -- 77 digits could
example : 10 ^ 76 < 2 ^ 256 := by decide -- fits a 256-bit word
example : doc.encode.all (· < p) := by native_decide
- value
- length / run marker
- guard
The leading 1 1 pair is a run of two, so it stays as two plain tokens. The value’s four single digits become the run 04 2101.
For the running example, the 72 integers become 72 tokens (none needs a continuation) and 182 digits without run compression: 72 length digits plus 110 value digits. With compression the stream has 157 digits, which pack into three elements:
-- continues the definitions above
#eval doc.encode.length -- 3
#eval (doc.encode.map fun x => (toString x).length - 1).sum -- 157
#eval doc.encode -- the three elements printed below
1111129706210121298113100131431023111311731141211298113101030112990410113102
1032123314121331033104310509000210523310331043105090012106233103310431051010
10522107
The second element shows the boundary rule. Its last four digits, 1010, are the first two of a seven-digit run, written as plain tokens because only four digits of room were left. The third element begins with the remaining run, 05 22107.
Injectivity and canonicality
Claim. Let be the composite map from JSON values to vectors in . Restricted to documents that fit in elements, contain no empty arrays or objects, and have no duplicate keys within any object, if and only if and are equal as JSON values, with object key order ignored.
Sketch. The “if” direction holds because every layer is a function of the unordered leaf set. Flattening depends only on that set, and sorting turns the set into a unique sequence. For “only if”, I show that each layer can be inverted.
- Packing. Every non-padding element starts with the guard digit , so it is non-zero. Trailing zero elements are therefore padding. Dropping the leading digit of each element and concatenating the rest gives back the digit stream.
- Tokens. The token grammar is prefix-free. A first digit to fixes the token length, means 8 digits plus a continuation, and means a run whose length is given by the next digit. So the stream parses in exactly one way into a sequence of integers.
- Integers. This grammar is prefix-free as well. A path starts with its component count . Each component starts with (then code points follow), or with and then (empty key), or with , and then an index. A value starts with its tag, and the tag fixes how many integers follow: , , or . So the sequence splits into rows in exactly one way.
- Rows to tree. A row gives the path and the leaf value. In a leaf set, no path is a proper prefix of another. Each internal node is an array or an object according to whether its children are reached by indices or by keys. So the leaf set determines the tree.
- Numbers. comes from the shortest decimal form, so equal numbers give equal triples, and the triple determines the value.
A composition of injective maps is injective.
The first two inversion steps are short enough to check in Lean: strip the guards, then parse the token grammar back into integers. The checks below recover the integer layer exactly for the running example, for an array holding , a 10-digit integer, and the empty string, and for a case with a one-digit continuation token.
-- continues the definitions above
/-- Drop each guard digit and concatenate: the digit stream again. -/
def unpack (xs : List Nat) : List Char :=
xs.flatMap fun x => (toString x).toList.drop 1
def digit (c : Char) : Nat := c.toNat - '0'.toNat
/-- Parse tokens back into integers; `pre` holds digits awaiting a continuation. -/
def parse : (fuel : Nat) → List Char → String → List Nat
| 0, _, _ | _, [], _ => []
| f + 1, '0' :: n :: ds, _ =>
(ds.take (digit n)).map digit ++ parse f (ds.drop (digit n)) ""
| f + 1, '9' :: ds, pre => parse f (ds.drop 8) (pre ++ String.mk (ds.take 8))
| f + 1, l :: ds, pre =>
(pre ++ String.mk (ds.take (digit l))).toNat! :: parse f (ds.drop (digit l)) ""
def decode (xs : List Nat) : List Nat :=
let ds := unpack xs; parse ds.length ds ""
example : decode doc.encode = doc.ints := by native_decide
example : decode (Json.encode (.arr [9007199254740991, 1234567890, -0.5, ""]))
= Json.ints (.arr [9007199254740991, 1234567890, -0.5, ""]) := by native_decide
example : decode (Json.encode (.arr [123456789, 1, 2])) -- continuation `19`
= Json.ints (.arr [123456789, 1, 2]) := by native_decide
Canonicality is what makes the commitment well defined. The document hash is a function of the JSON value and not of how the value was serialized. Two writers who produce the same document in a different key order commit to the same leaf.
The statement proven
With the default sizes, a document is 256 elements. The commitment hashes them in two levels: 16 Poseidon hashes of 16 elements each, then one Poseidon hash of those 16 digests. The relation is
Here and are the path and value, encoded and packed the same way as the document. By default they get up to 4 and 8 elements. The document is the private witness. The verifier learns , the path and the value, and nothing about the other leaves beyond what reveals. When the value is a container, tag 4 lets the circuit return a whole sub-document.
Inside the circuit, is never built as a tree. The circuit decomposes the elements into digits and runs the token state machine over them. It compares each decoded path with and checks the value on a match. Every step is unrolled to the full capacity, so the work does not depend on the document’s actual length.
The document hash then becomes a leaf of a sparse Merkle tree for a collection (168 levels by default). Collection roots are leaves of a second tree for the database (8 levels). Proving a value at the database level adds two membership paths to the same relation.
Costs and limitations
Capacity. The default document is digits. One digit per element goes to the guard, which leaves payload digits. A printable ASCII character in a key or string costs 3 to 4 digits (a length digit plus 2 or 3 code-point digits). Other characters cost up to 6 digits inside the Basic Multilingual Plane and up to 8 outside it. Structural integers are mostly single digits, and run compression brings them close to one digit each.
Size. In the running example, 66 characters of JSON became 157 payload digits in 3 elements. One integer per field element would have needed 72. For a query on path a, the public inputs are the path [1,1,97] and the value [2,1,0,1], packed into one short element each, plus the hash. That is all the verifier has to see.
Setup. Since the parser is unrolled to capacity, the constraint count of every circuit, and with it the size of its trusted setup, grows with and with the tree depths, and not with the documents actually stored.
Limitations and open questions.
- Empty containers. A leaf-only flattening loses
[]and{}, so the injectivity claim above excludes them. Giving them a leaf form, for example tag 4 with an empty body, extends the claim; step 4 of the sketch then has to treat such a leaf as a container with no children. - Numbers. A number written with an exponent is expanded first: and , as the
OfScientificinstance above does. Its cost therefore grows linearly with the size of the exponent, and a fourth field for the exponent would bound it. Also, and get the same code. - Decimal digits. Base 10 makes the encoding easy to read and to debug. Base would cut the cost of splitting elements into digits and would use the field slightly better. I have not measured whether that saving matters next to the hashing.
- Path redundancy. Shared prefixes such as
ghiabove are repeated in every row. A dictionary of repeated path components, referred to by index, removes most of that repetition. It changes the grammar and needs its own injectivity argument.