Commitment Log

The commitment log is defined by two domain separators:

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

Changing either separator or an encoding rule requires a new version.

Leaf encoding

canonicalJson = JSON.stringify({
  content: <content>,
  metadata: sortKeys(<metadata> ?? null),
})

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

Rules:

1. content precedes metadata.
2. Metadata object keys are sorted recursively.
3. Array order is preserved.
4. Missing metadata is encoded as null.

Example

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

Canonical JSON:

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

Leaf encoding is versioned. An unversioned change invalidates existing proofs.

Node encoding

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

Both children are 32 bytes.

Odd-node rule

An unpaired rightmost node is hashed with itself:

parent = H(x, x)

It is not carried unchanged or paired with a zero node.

Root computation

computeRoot(leaves):
  if empty: return 32 zero bytes
  while more than one node remains:
    pair adjacent nodes
    use the left node twice when the right node is missing
    hash each pair with H(left, right)
  return the remaining node

Leaves	Root
0	32 zero bytes
1	The leaf
n	Merkle fold

Inclusion proofs

A proof contains the sibling hash and direction at each level.

verifyProof(proof, root):
  acc = proof.leaf
  for each sibling:
    acc = siblingOnRight ? H(acc, sibling) : H(sibling, acc)
  return acc == root

For an odd node, the sibling is the node itself. A one-leaf proof has no siblings.

Verification

A proof for one million leaves contains 20 sibling hashes and requires 20 SHA-256 operations.

Incremental tree

The service persists every tree level, with leaves at levels[0] and the root at the final level.

Appending a leaf updates only the rightmost path. This requires O(log n) hashes.

The stored leafCount is used as an optimistic concurrency guard. If the stored tree is missing or inconsistent, the service rebuilds it from the ordered leaf set.

The incremental root must equal computeRoot(leaves) for the same leaf set.

Onchain state

The program stores the root as [u8; 32]. It does not recompute the tree.

Check	Rule
Authorization	Signer is owner or authority
Ordering	expected_nonce == nonce
Count	new_count >= memory_count

Monotonicity

memory_count cannot decrease. Removing a stored leaf produces either a shorter count rejected by the program or a root that no longer matches the retained data.

Rust and TypeScript contract

Both implementations use:

1. the same leaf preimage
2. the same node hash
3. the same odd-node rule
4. little-endian u64 values for count and nonce
5. a rolling root over leaves 0..memory_count-1

The onchain root covers the full log, not only the latest batch.

Next: Operations.