Large authenticated state (Poseidon MPF/JMT)
Many private applications revolve around a big table: a registry of members, credential status flags, account balances, or the state of a rollup-like app. You can’t put millions of entries on Cardano, and you can’t put them in a circuit. You can, however, keep them in an authenticated tree off-chain, publish only the tree’s root, and prove statements about one entry at a time.
ZeroJ’s zeroj-mpf-poseidon and zeroj-jmt-poseidon modules do exactly that. They adapt Cardano
Client Lib’s Merkle Patricia Forestry (MPF) and Jellyfish Merkle Tree (JMT) to a Poseidon hash
over BLS12-381, so the same tree the service stores can be opened inside a Groth16 circuit.
How it works
Section titled “How it works”The key is already in the tree; only its value changes.
Waiting for a change to prove.
Groth16AuthenticatedStateTransitionValidatorOne applied script per operation: this one is for value update.signed by the authorized operatorone continuing state UTxO: new root, version + 1same value and state token, nothing mintedproof verifies over (old root, new root)proof is for an older root: rejectedThe state token's minting policy is outside Groth16: it must mint exactly one token, once.
1. Keep the big table off-chain
Your service keeps millions of entries in a Poseidon MPF or JMT tree, for example in RocksDB. The tree's root is a fingerprint of the whole database: change any entry and the fingerprint changes. Cardano stores only that fingerprint, with a version number.
2. Read one path
To change one entry, the service reads its proof path: the few nodes between that entry and the root. The prover checks the path strictly and pads it to a fixed maximum length. A malformed or too-deep path is rejected before any proving work.
3. Prove the change
A narrow circuit for this one operation proves that applying the change to the old root gives the new root. It sees one path, never the database, so the cost depends on the path bound, not on how many entries there are. Only the two roots are public.
4. Move the state on Cardano
The operator spends the state UTxO and creates one continuing state UTxO with the new root and version + 1. The validator checks the signer, the value and the state token, then verifies the proof against the old root from the spent datum. Tick Proof built on an older root to see a stale proof fail.
5. What the chain learned
Only that the fingerprint moved by one valid change of this kind. The proof doesn't name the entry or tie the change to a user; add those fields in your own circuit if you need them. Both modules are experimental, and the production gates listed below are still open.
The circuit never sees the database. It sees one path, padded to a fixed maximum length, and the root(s) as public inputs. Proving cost depends on that path bound, not on how many entries the tree holds.
Operation-specific circuits
Section titled “Operation-specific circuits”Each operation has its own narrow circuit, its own R1CS hash and its own keys. That keeps the statement explicit and the constraint count small. There is no generic “do anything” circuit whose behaviour a prover could steer.
| Statement | MPF | JMT | Public inputs |
|---|---|---|---|
| Inclusion: key/value is in the tree | ✓ | ✓ | root |
| Non-inclusion: the path ends empty | ✓ | ✓ | root |
| Non-inclusion: a different key occupies the path | ✓ | ✓ | root |
| Value update | ✓ | ✓ | oldRoot, newRoot |
| Insert at an empty spot | ✓ | ✓ | oldRoot, newRoot |
| Insert beside a different leaf | ✓ | ✓ | oldRoot, newRoot |
| Tombstone update | — | ✓ | oldRoot, newRoot, tombstone hash |
| Physical delete, multiproofs, batch updates | deferred | deferred | — |
The circuits are exposed as PoseidonMpfCircuitTemplates / PoseidonJmtCircuitTemplates factory
methods (inclusion(maxSteps), valueUpdate(maxSteps), …) and as ZkMpf* / ZkJmt* gadgets.
MPF or JMT?
Section titled “MPF or JMT?”| Poseidon MPF | Poseidon JMT | |
|---|---|---|
| Structure | Radix-16 Patricia trie with compressed paths | Versioned Jellyfish Merkle Tree |
| Best for | Membership/read-heavy state, compact native proofs, existing MPF data | Update-heavy state that needs version history, rollback and pruning |
| Measured complete profile at 5M entries | S9 (≤ 9 branch steps) | S12 (≤ 12 levels) |
| Circuit size at that profile | 56,635 constraints | 14,057 constraints |
| Median Groth16 prove | 4.173 s | 2.901 s |
| Native (private) proof size | 805–939 B sampled | 2,744–3,161 B sampled |
| Deletion | No physical delete yet | Tombstones only; a tombstone is not proof of absence |
Both produce the same 192-byte compressed Groth16 proof and a 432-byte compressed VK for one public input, so on-chain cost is the same: ZeroJ measured 2,052,276,435 CPU steps and 138,837 memory units in the JuLC VM (JuLC 0.1.0-pre18). The JMT’s larger native proof is private prover input and never reaches the chain.
The two root profiles (zeroj-poseidon-mpf-v1, zeroj-poseidon-jmt-v1) are incompatible with
each other and with classic Blake2b MPF/JMT roots, including Aiken MPF roots.
Pick a path bound
Section titled “Pick a path bound”A circuit covers paths up to a fixed length (“S9” = 9 steps). Choosing it is a data question:
- Measure the depth of your real tree. In the 5M MPF run, S8 covered all but 218 entries; S9 covered all of them. In the 5M JMT run, S8 covered 99.74 % and S12 covered everything.
- Plan the overflow. Approve two or more exact profiles, route each request to the smallest one that fits, and reject (or send to an approved fallback) anything deeper. Never silently truncate or pad a path outside the canonical rules.
- Stop key grinding. Poseidon keeps honest paths roughly balanced, but a user who can choose keys freely can try to create deep paths. Derive keys in a way callers can’t grind, or use a fixed-depth design.
Prove an inclusion (MPF)
Section titled “Prove an inclusion (MPF)”Witness factories first verify the native CCL proof strictly, then normalize it into circuit inputs. They reject malformed proofs and paths deeper than the bound before any proving work.
import org.zeroj.api.CurveId;import org.zeroj.circuit.CircuitBuilder;import org.zeroj.circuit.annotation.ZkInputMap;import org.zeroj.merkle.mpf.poseidon.ccl.PoseidonMpfTrie;import org.zeroj.merkle.mpf.poseidon.circuit.PoseidonMpfCircuitTemplates;import org.zeroj.merkle.mpf.poseidon.profile.PoseidonMpfHash;import org.zeroj.merkle.mpf.poseidon.profile.PoseidonMpfValueCommitment;import org.zeroj.merkle.mpf.poseidon.witness.PoseidonMpfBranchWitness;
import java.math.BigInteger;
PoseidonMpfTrie trie = PoseidonMpfTrie.inMemory(); // or PoseidonMpfTrie.create(nodeStore, root)trie.put(keyBytes, valueBytes);
byte[] root = trie.getRootHash();byte[] proofWire = trie.getProofWire(keyBytes).orElseThrow();int maxBranches = 8;
PoseidonMpfBranchWitness witness = PoseidonMpfBranchWitness.inclusion( root, keyBytes, valueBytes, proofWire, maxBranches); // throws on an invalid/too-deep proof
ZkInputMap inputs = new ZkInputMap() .put(PoseidonMpfCircuitTemplates.ROOT, PoseidonMpfHash.fieldFromDigestBytes(root)) .put(PoseidonMpfCircuitTemplates.VALUE, PoseidonMpfValueCommitment.field(valueBytes));witness.putInto(inputs);
CircuitBuilder circuit = PoseidonMpfCircuitTemplates.inclusion(maxBranches);BigInteger[] circuitWitness = circuit.calculateWitness(inputs.toWitnessMap(), CurveId.BLS12_381);// …then compile, set up (ceremony keys in production) and prove as for any Groth16 circuitThe JMT flow has the same shape: PoseidonJmtTree, PoseidonJmtInclusionWitness.create(...),
PoseidonJmtCircuitTemplates.inclusion(maxLevels).
What the proof does and doesn’t say
Section titled “What the proof does and doesn’t say”- A root-only inclusion proof says “the prover knows some entry under this root”, and nothing public about which one. It doesn’t bind a particular key to a user. Add the key, owner, nullifier, version or transaction fields your application needs in your own circuit.
- JMT version numbers are storage coordinates, not authenticated state.
Bind
{chain point, version, root}in your application, with one logical writer. - A JMT tombstone is still an included value. Never present it as non-inclusion.
The state-transition validator
Section titled “The state-transition validator”zeroj-onchain-julc includes a representative Cardano validator,
Groth16AuthenticatedStateTransitionValidator, also experimental. It reads the old root from the
state-token UTxO being spent and the new root from the single continuing state-token UTxO. It
enforces a version increment, the authorized signer, value and token conservation and no minting,
then verifies one operation-specific Groth16 proof over the two roots.
Its release tooling (Groth16AuthenticatedStateTransitionScriptFactory) binds the exact circuit
manifest, R1CS and VK identities, validator-template digest, JuLC compiler profile, script hash,
network, state token, signer and a one-shot genesis attestation, and it refuses benchmark bundles
on mainnet. The state token’s minting policy is outside Groth16: you must independently ensure it
mints exactly one token, once.
Add the dependency
Section titled “Add the dependency”Both modules are published outside zeroj-bom-core, so pin the version. RocksDB is not a
dependency. The persistent load and benchmark tools live in the unpublished
benchmarks/ projects (-PincludeBenchmarks).
dependencies { implementation 'org.zeroj:zeroj-mpf-poseidon:0.1.0-pre13' // or zeroj-jmt-poseidon}Gates that remain open
Section titled “Gates that remain open”The local tests cover golden vectors, CCL compatibility, malicious witness mutations, cross-operation and cross-structure replay, real value transitions and JuLC VM evaluation. They show the implementation is internally consistent and scales on the measured machine. They do not show production assurance. Before protecting value, ZeroJ’s own guide requires:
- freezing every deployed operation and profile, with published manifest, R1CS hash, VK identity, Poseidon fingerprint, compiler version and validator-template hash;
- independent circuit and cryptographic review;
- a reviewed Groth16 ceremony for each exact circuit;
- full state-token transactions validated on Yaci DevKit and a public network under current protocol parameters;
- an enforced one-shot, supply-of-one state-token policy;
- operational procedures for backup, restore, compaction, retention, rollback and rebuild;
- monitoring of proof depth, prover latency and memory, and rejected over-bound requests.
Further reading
Section titled “Further reading”- 5M benchmark reports: MPF, JMT
- Practical large-state guide and the authenticated-state v1 specification
- Design notes: ADR-0042