Sparse Merkle state

The SMT frontend proves statements about a sparse Merkle tree (SMT) of asset states. This page defines the tree, the three leaf states, how a leaf becomes a digest, and what each operation asserts. The engine does not store the tree: your state store does, and it supplies the roots and paths that each request carries.

The tree#

The tree has a fixed depth d, a configuration value chosen when a tree instance is created. The default is 24, which gives 2^24 slots. Every slot is addressed by a key, an AssetId that wraps a u64. When d is below 64 the key must be less than 2^d. The engine does not allocate keys or enforce their uniqueness; that belongs to the application that owns the tree.

A MerklePath holds exactly d sibling digests, ordered from the leaf level toward the root. The root is obtained by folding the leaf digest with each sibling in turn. Bit l of the key, counted from the least significant bit, decides the order at level l:

acc_0      = hash_leaf(encode(leaf))
acc_(l+1)  = compress(acc_l, sibling_l)   if bit l of the key is 0
acc_(l+1)  = compress(sibling_l, acc_l)   if bit l of the key is 1
root       = acc_d

MerklePath::compute_root implements this fold. It returns SmtError::PathLengthMismatch when the path does not hold exactly d siblings, and SmtError::KeyOutOfRange when the key does not fit the tree.

Digests#

Every digest is a Digest<BaseField>: eight KoalaBear field elements (DIGEST_WIDTH is 8). Roots, leaf hashes, the value_digest public input and the full circuit commitment all use this type. Two node digests are compressed by one Poseidon2 permutation of both inputs, truncated to eight elements.

Leaf states#

A slot is always in one of three states, the variants of LeafState:

Empty and Tombstone have different encodings and therefore different leaf digests, so the tree can tell a never-used slot from a deleted one. Both satisfy non-membership.

Occupied leaves#

An occupied leaf carries a LeafPayload with two fields:

• sync_state: the asset state as a vector of base-field elements. Converting application fields into field elements is the caller's responsibility.
• identity_digest: a 32-byte Keccak-256 digest computed outside the circuit, such as the asset's registry identity. The engine treats it as opaque bytes and does not prove the Keccak computation.

LeafState::encode turns an occupied leaf into the tag 1, then the sync_state elements, then the identity digest read little-endian and split into nine limbs of at most 30 bits (eight full limbs and a final 16-bit limb). The limbs are 30 bits wide because a 31-bit value can exceed the KoalaBear modulus, which would let two different digests encode to the same field elements; every 30-bit limb is below p, so the packing is injective. An occupied encoding therefore has 10 + n elements, where n is the number of sync_state fields.

Leaf hashing#

The leaf hash never absorbs a raw encoding. leaf_fold first lays the encoding into a fixed-width pre-image:

pre[0]            tag
pre[1]            encoding length
pre[2..]          the rest of the encoding, verbatim
remaining lanes   zero

The pre-image width is leaf_max_fields + 1 rounded up to a multiple of 8 (leaf_pre_width), so a rate-8 Poseidon2 sponge absorbs every lane in whole blocks. At the default leaf_max_fields of 31 the pre-image has 32 lanes, absorbed in four blocks. The length lane keeps encodings of different lengths apart, including an encoding and the same encoding followed by zeros.

An encoding longer than leaf_max_fields, or an empty one, is rejected with HashError::EncodingTooLong or HashError::EmptyEncoding and is never hashed. The default bound of 31 elements leaves room for the tag, up to 21 sync_state fields and the nine identity limbs. Configuration gives the limits of the bound.

Operations#

SmtOperation has three variants. Each one fixes what the witness leaf must be, how the two roots relate, and which leaf the value_digest public input names:

An update proves a single-leaf transition: one sibling path authenticates the old leaf under the old root and the new leaf under the new root. compiler::smt_valid_native is the native reference for the witness-leaf and root conditions of these three meanings; the value-digest condition is enforced by the verifier's public-input checks and the circuit. It checks a supplied witness directly, without building a circuit or a proof.

Slot lifecycle#

Insertion, replacement, deletion and restoration are all Update operations with different leaf states:

The engine does not enforce a lifecycle policy. Update accepts any pair of states whose paths match the two roots, including pairs your application may forbid, such as Tombstone to Empty. Check the transitions you allow before you request a proof.

Building a request#

The function below prepares an insertion. It recomputes the old root from the path your state store returned, stops if that root differs from the root you trust, and derives the new root and the value digest.

use statesync_gkr::SyncRequest;
use statesync_gkr::compiler::{
    AssetId, LeafPayload, LeafState, MerklePath, PublicInputs, SmtOperation, SmtParams,
    SmtWitness,
};
use statesync_gkr::primitives::field::BaseField;
use statesync_gkr::primitives::hash::{Digest, HashGadget, Poseidon2Gadget};

/// Build an `Update` request that moves the slot at `key` from `Empty` to
/// `Occupied(payload)`.
pub fn insert_request(
    params: &SmtParams,
    trusted_old_root: &Digest<BaseField>,
    key: AssetId,
    payload: LeafPayload,
    path: MerklePath,
) -> Result<SyncRequest, String> {
    let hasher = Poseidon2Gadget::new(params.leaf_max_fields as usize);
    let old_leaf = LeafState::Empty;
    let new_leaf = LeafState::Occupied(payload);

    let old_root = path
        .compute_root(&hasher, params, key, &old_leaf)
        .map_err(|error| format!("old path rejected: {error:?}"))?;
    if old_root != *trusted_old_root {
        return Err("the path does not reproduce the trusted root".to_owned());
    }
    let new_root = path
        .compute_root(&hasher, params, key, &new_leaf)
        .map_err(|error| format!("new path rejected: {error:?}"))?;
    let value_digest = hasher
        .hash_leaf(&new_leaf.encode())
        .map_err(|error| format!("leaf hashing failed: {error:?}"))?;

    let operation = SmtOperation::Update {
        key,
        old_leaf: old_leaf.clone(),
        new_leaf,
    };
    let op_kind_tag = PublicInputs::kind_tag(operation.kind());
    Ok(SyncRequest {
        operation,
        witness: SmtWitness {
            leaf: old_leaf,
            path,
        },
        public_inputs: PublicInputs {
            old_root,
            new_root,
            op_kind_tag,
            asset_id: key,
            value_digest,
        },
    })
}

Prove the request against prepared state for the Update kind. Proving state operations walks through all three operations end to end.

Depth and key limits#

Witness generation does not check the key range. A request with an out-of-range key still produces a proof, and verification rejects it.

Depth is part of the circuit. A different depth gives a different circuit, circuit commitment and prepared state, and therefore a separate tree instance. The measured profiles cover depths 24, 28 and 32.

What stays outside the engine#

• Storage. The engine does not store the tree, track occupancy or allocate keys.
• Root authentication. Recomputing a root from caller-supplied siblings shows only that this path and leaf produce that root. Whether the root belongs to your database, chain or registry has to be established before the request reaches the engine.
• Multi-leaf atomicity. Each request proves one leaf. Several leaves are several independent requests, each with its own proof; there is no atomic multi-leaf transition.

Next steps#

• Circuits and layers shows how these operations are compiled.
• Proof lifecycle describes what binds a proof to its request.
• Configuration lists the depth and leaf-bound limits.