Research / 2024

Arithmetizing JSON

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

A canonical, injective encoding of arbitrary JSON into a short vector of field elements, so that an arithmetic circuit can prove the value at one path of a committed document without revealing the rest.

Canonical encodingArithmetic circuitsZero-knowledge proofs
66 → 3
characters of JSON to field elements in the running example
76
decimal digits per field element, one fewer than the 77-digit BN254 scalar modulus
256 × 76
digit capacity of one document in the default circuit

An arithmetic circuit sees only elements of a prime field Fp\mathbb{F}_p, 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

p=21888242871839275222246405745257275088548364400416034343698204186575808495617.p = 21888242871839275222246405745257275088548364400416034343698204186575808495617 .

pp has 77 decimal digits and log⁡2p≈253.6\log_2 p \approx 253.6. Three properties of the setting shape the design.

  1. Fixed arity. A circuit has a fixed number of input signals. A document gets NN field elements (default N=256N = 256), padded with zeros.
  2. 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.
  3. 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 NN field elements. For that hash to identify the document, equal documents must give equal vectors. That is the canonicality requirement.

  1. 01
    Flatten

    one row per leaf: path and primitive value

  2. 02
    Sort

    rows ordered by path, key by key

  3. 03
    Integers

    paths and values become natural numbers

  4. 04
    Digit tokens

    length-prefixed, runs of single digits merged

  5. 05
    Pack

    guard digit plus 75 digits per element

Fig. 1The five layers of the encoding, from a JSON value to a fixed number of field elements.

Paths, order and integers

Flattening. For a JSON value JJ, leaves(J)\mathrm{leaves}(J) is the set of pairs (π,v)(\pi, v) where vv is a primitive (null, boolean, number or string) and π=(k1,…,kn)\pi = (k_1, \dots, k_n) is the sequence of object keys (strings) and array indices (naturals) that leads from the root to vv. A primitive at the top level has the empty path, n=0n = 0.

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 (s,d,m)(s, d, m) 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 00 reserved as an escape.

Path encoding.

key(k)={[ ℓ,c1,…,cℓ ]k a string of ℓ≥1 code points ci[ 0,1 ]k=""[ 0,0,i ]k the array index i\mathrm{key}(k) = \begin{cases} [\,\ell, c_1, \dots, c_\ell\,] & k \text{ a string of } \ell \ge 1 \text{ code points } c_i \\ [\,0, 1\,] & k = \texttt{""} \\ [\,0, 0, i\,] & k \text{ the array index } i \end{cases}path(k1,…,kn)=[ n ]∥key(k1)∥⋯∥key(kn).\mathrm{path}(k_1, \dots, k_n) = [\,n\,] \mathbin{\|} \mathrm{key}(k_1) \mathbin{\|} \cdots \mathbin{\|} \mathrm{key}(k_n).

The top-level path is [0][0].

So ghi[0] is [2,3,103,104,105,0,0,0][2, 3, 103, 104, 105, 0, 0, 0]. The document {"0":1} starts with the path [1,1,48][1, 1, 48], and [1] starts with [1,0,0,0][1, 0, 0, 0].

-- 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.

typetagencodingexample
null0[0][0]null → [0][0]
boolean1[1,b][1, b]true → [1,1][1, 1]
number2[2,s,d,m][2, s, d, m]3.14 → [2,1,2,314][2, 1, 2, 314]
string3[3,ℓ,c1,…,cℓ][3, \ell, c_1, \dots, c_\ell]"abc" → [3,3,97,98,99][3, 3, 97, 98, 99]
array or object4[4][4] followed by the encoded sub-documentused for query results

For a number, ss is 11 for non-negative and 00 for negative, dd is the number of digits after the decimal point in the shortest decimal form, and mm is the digit string with the point removed, read as a natural number. So 1↦[2,1,0,1]1 \mapsto [2,1,0,1], −1↦[2,0,0,1]-1 \mapsto [2,0,0,1], −12.5↦[2,0,1,125]-12.5 \mapsto [2,0,1,125], and the value is (−1)1−s m/10d(-1)^{1-s}\, m / 10^{d}.

-- 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 path(π)∥val(v)\mathrm{path}(\pi) \mathbin{\|} \mathrm{val}(v) over the sorted leaves. For {"a":1} this gives [1,1,97,2,1,0,1][1, 1, 97, 2, 1, 0, 1]. 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 δ(x)\delta(x) be the decimal string of xx, with ∣δ(x)∣=L|\delta(x)| = L.

  • If L≤8L \le 8: emit LL, then δ(x)\delta(x).
  • If L>8L \gt 8: emit 99 and the first 8 digits, then continue with the remaining L−8L - 8 digits as a string. Leading zeros are kept from this point on.

So 123→3 123123 \to 3\,123 and 1234567890→9 12345678 2 901234567890 \to 9\,12345678\,2\,90. A length digit is never 00.

Run compression. Most integers in the layer above are single digits, which cost two digits each as tokens. A maximal run of rr consecutive one-digit integers (each a two-digit token), with 3≤r≤93 \le r \le 9, is replaced by 00, rr and the rr digits. That costs r+2r + 2 digits in place of 2r2r. 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 123456789→9 12345678 1 9123456789 \to 9\,12345678\,1\,9, is never merged into a run, since it is the tail of a longer integer.

The escape digit 00 is free because no token has length 00. 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 11. The guard is needed because a chunk can begin with the run marker 00, 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 107610^{76}. And 1076<p≈2.19×107610^{76} \lt p \approx 2.19 \times 10^{76}, so the integer is its own field representative and no reduction mod pp ever happens. A 77-digit chunk could be as large as 1077−1>p10^{77} - 1 \gt p, and it would wrap around. The same 76-digit value also fits in a 256-bit machine word, since 2256≈1.16×10772^{256} \approx 1.16 \times 10^{77}. Seventy-five payload digits carry 75log⁡210≈249.175 \log_2 10 \approx 249.1 bits, about 98% of log⁡2p\log_2 p.

-- 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
  • path
  • value
  • length / run marker
  • guard
Fig. 2The document a:1 at two layers. Top: the seven integers. Bottom: the single packed field element, 14 digits.

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 EE be the composite map from JSON values to vectors in FpN\mathbb{F}_p^N. Restricted to documents that fit in NN elements, contain no empty arrays or objects, and have no duplicate keys within any object, E(J1)=E(J2)E(J_1) = E(J_2) if and only if J1J_1 and J2J_2 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.

  1. Packing. Every non-padding element starts with the guard digit 11, 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.
  2. Tokens. The token grammar is prefix-free. A first digit 11 to 88 fixes the token length, 99 means 8 digits plus a continuation, and 00 means a run whose length is given by the next digit. So the stream parses in exactly one way into a sequence of integers.
  3. Integers. This grammar is prefix-free as well. A path starts with its component count nn. Each component starts with ℓ>0\ell \gt 0 (then ℓ\ell code points follow), or with 00 and then 11 (empty key), or with 00, 00 and then an index. A value starts with its tag, and the tag fixes how many integers follow: 00, 11, 33 or 1+ℓ1 + \ell. So the sequence splits into rows in exactly one way.
  4. 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.
  5. Numbers. (s,d,m)(s, d, m) 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. □\square

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 253−12^{53}-1, a 10-digit integer, −0.5-0.5 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 h=H(E(J))h = H(E(J)) 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

R={((h,πˉ,vˉ); x) : x∈Fp256, H(x)=h, E−1(x) has value vˉ at path πˉ}.\mathcal{R} = \Bigl\{ \bigl( (h, \bar\pi, \bar v);\ x \bigr) \ :\ x \in \mathbb{F}_p^{256},\ H(x) = h,\ E^{-1}(x) \text{ has value } \bar v \text{ at path } \bar\pi \Bigr\}.

Here πˉ\bar\pi and vˉ\bar v 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 xx is the private witness. The verifier learns hh, the path and the value, and nothing about the other leaves beyond what hh reveals. When the value is a container, tag 4 lets the circuit return a whole sub-document.

Inside the circuit, E−1E^{-1} 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 πˉ\bar\pi 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.

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. 3Documents are committed as hashes of their encodings, collected into sparse Merkle trees whose root a smart contract tracks.

Costs and limitations

Capacity. The default document is 256×76=19,456256 \times 76 = 19{,}456 digits. One digit per element goes to the guard, which leaves 19,20019{,}200 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 NN 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: 1021↦(1,0,1021)10^{21} \mapsto (1, 0, 10^{21}) and 10−7↦(1,7,1)10^{-7} \mapsto (1, 7, 1), as the OfScientific instance above does. Its cost therefore grows linearly with the size of the exponent, and a fourth field for the exponent would bound it. Also, −0-0 and 00 get the same code.
  • Decimal digits. Base 10 makes the encoding easy to read and to debug. Base 2k2^k 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 ghi above 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.