The Commitment Log

This page is the specification. Everything toda claims rests on the byte formats defined here, and any implementation that disagrees with them by a single byte produces proofs that do not verify.

Two domain separators bound the whole scheme:

DOMAIN_SEP_LEAF = "toda:leaf:v1"
DOMAIN_SEP_NODE = "toda:node:v1"

They exist to make leaf preimages and internal-node preimages structurally impossible to confuse, which is what closes the second-preimage attack that plagues naive Merkle trees. Their v1 suffix is the version of this entire specification. Changing either constant, or any rule below, requires bumping it.

Leaf encoding

A memory's leaf is the SHA-256 of a canonical preimage:

canonicalJson = JSON.stringify({
  content:  <the memory's content string>,
  metadata: sortKeys(<the memory's metadata> ?? null),
})

preimage = utf8("toda:leaf:v1") ‖ 0x00 ‖ utf8(canonicalJson)
leaf     = sha256(preimage)

Three rules make this deterministic across runtimes:

1. Field order is fixed. content first, metadata second. This is the literal key order of the serialized object, not an alphabetical sort.
2. Metadata keys are sorted recursively. Every object at every depth has its keys ordered by code-point comparison. Arrays keep their order; array elements are recursed into.
3. Absent metadata is null, not {} or omitted. metadata: undefined and metadata: null produce the identical preimage. metadata: {} does not.

The 0x00 separator byte sits between the domain separator and the JSON so that no leaf preimage can ever be a prefix of another with a different separator.

Worked example

{ "content": "deploys on Fridays", "metadata": { "b": 2, "a": 1 } }

canonicalizes to exactly:

{"content":"deploys on Fridays","metadata":{"a":1,"b":2}}

and the leaf is sha256("toda:leaf:v1" ‖ 0x00 ‖ that).

Do not change this without versioning

The leaf preimage is the contract between what is stored and what is proven. Every proof ever issued, and every root ever anchored on-chain, is invalidated by an unversioned change to this encoding.

Node encoding

An internal node hashes its two children under the node separator:

H(left, right) = sha256( utf8("toda:node:v1") ‖ left ‖ right )

Both children are always exactly 32 bytes, so the preimage is always exactly 12 + 32 + 32 = 76 bytes and needs no length prefixing.

The odd-node rule

When a level has an odd number of nodes, the lone rightmost node is promoted by pairing with itself:

parent = H(x, x)

It is not carried up unchanged, and it is not paired with a zero node. This choice is arbitrary but must be universal - the incremental tree, the batch tree, the proof builder, and any independent verifier all apply it identically.

Root computation

computeRoot(leaves):
  if leaves is empty: return 32 zero bytes
  level = leaves
  while level.length > 1:
    next = []
    for i in 0, 2, 4, … < level.length:
      left  = level[i]
      right = level[i+1] if it exists else left     ← the odd-node rule
      next.push(H(left, right))
    level = next
  return level[0]

Two edge cases worth stating explicitly:

Log size	Root
0 leaves	32 zero bytes (0x0000…00)
1 leaf	the leaf itself - no hashing occurs
n leaves	the fold above

Inclusion proofs

A proof for leaf index i records, at each level, the sibling that i's node is paired with, and which side that sibling is on.

getProof(leaves, i):
  siblings, directions = [], []
  idx = i
  level = leaves
  while level.length > 1:
    isRight = (idx % 2 == 1)                  ← are we the right child?
    pairIdx = isRight ? idx - 1 : idx + 1
    sibling = level[pairIdx] if it exists else level[idx]   ← odd-node: self
    siblings.push(sibling)
    directions.push(not isRight)              ← true ⇒ sibling is on the right
    level = fold(level)
    idx = floor(idx / 2)

Note the odd-node case: when idx is the last node at an even index, its sibling is itself, and the direction bit is true. This is the promote rule, expressed in proof form.

Verification

verifyProof(proof, root):
  acc = proof.leaf
  for i in 0 … proof.siblings.length - 1:
    s = proof.siblings[i]
    acc = proof.directions[i] ? H(acc, s) : H(s, acc)
  return acc == root

Pure, allocation-light, no network. A proof for a log of 1,000,000 memories has 20 siblings and verifies in 20 SHA-256 invocations.

A single-leaf log produces a proof with zero siblings, and verification reduces to leaf == root. That is correct, not a degenerate case to special-case away.

The incremental tree

Rebuilding a root from n leaves on every anchor is O(n) hashing and O(n) database reads. toda instead persists the tree's node levels and appends into them.

The stored form is levels, an array of levels, leaves-first, each node hex-encoded:

levels[0]                    = the leaves
levels[levels.length - 1]    = [root]

Appending a leaf touches only the rightmost path:

1. Push the leaf onto levels[0].
2. At each level, recompute only the parent that the new rightmost child feeds into - parentIdx = (level.length - 1) >> 1 - pairing with left twice if the right child does not exist.
3. Truncate any stale parents past parentIdx (the right spine can narrow as levels shrink).
4. Collapse levels above a now-single-node level.

That is O(log n) hashes per leaf. The persisted leafCount doubles as an optimistic concurrency guard: a save must advance it, so a lost update is detected and the sweep is retried rather than silently writing a stale tree.

The correctness invariant

For every leaf set, the incremental tree's root() is byte-identical to computeRoot(leaves). Same node separator, same odd-node rule, same ordering. This is asserted by a property test at every tree size, because it is the invariant that keeps every on-chain root and every issued proof valid simultaneously.

If the persisted tree is ever missing or has drifted from the leaf count in the database, the anchor service falls back to a full rebuild from all leaves. The O(n) path exists exactly once, and it self-heals corruption.

What the chain stores

The commitment program stores the root as [u8; 32] and never recomputes it. This is deliberate: recomputing a Merkle tree on-chain would cost compute units proportional to the log size, for a check that any client can perform for free.

The program's guarantees are authorization and ordering, not arithmetic:

Check	Enforced by
Only the owner or the named authority may commit	signer == owner ‖ signer == authority
Commits are strictly ordered	expected_nonce == nonce, then nonce += 1
The log never shrinks	new_count >= memory_count

The monotonicity rule

memory_count may never decrease. A commit that claims to cover fewer leaves than the account already acknowledges is rejected on-chain with CountRegressed.

This is the rule that makes deletion detectable. An operator who drops a memory from the database and recomputes a shorter log cannot anchor it - the chain refuses the shorter count. Their choice is to stop anchoring (visible: the tip goes stale) or to anchor a root that no longer matches the leaves they hold (visible: every proof breaks). There is no quiet third option.

The Rust ↔ TypeScript contract

The Rust program does not hash anything. Its merkle_root field is opaque bytes whose meaning is defined entirely by @toda/crypto. Concretely, the two sides agree on:

1. The leaf preimage, byte for byte, including the 0x00 separator.
2. H(l, r) = sha256("toda:node:v1" ‖ l ‖ r).
3. The odd-node promote rule.
4. Little-endian u64 encoding of memory_count and nonce (Anchor's Borsh default).
5. That merkle_root is the rolling root over leaves 0..memory_count-1, not a per-batch root.

Point 5 is the one that surprises people. The root on-chain is not the root of the batch that was just anchored - it is the root of everything.

Next: Operations - the client-side steps for writing, reading, and proving.