Skip to content

Large authenticated state (Poseidon MPF/JMT)

View Markdown

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.

Authenticated state · step 1 / 5
Your serviceoff-chain database
Tree
RocksDB · Poseidon MPF+5,000,000 entries in the measured runs. One path runs from the root to your entry.
keySECRETHIDDENalice████████
valueSECRETHIDDEN40 → 55████████

The key is already in the tree; only its value changes.

root: a fingerprint of every entryPUBLIC0xc609…2149
Proveryour server

Waiting for a change to prove.

Check the path firstproof path checked against the rootfits the S9 bound: at most 9 branch stepspadded to exactly 9 stepsA malformed or deeper path is rejected before any proving work.
Circuit: value updateSees one path, never the database. Each operation has its own circuit and keys.
oldRootPUBLIC0xc609…2149
newRootPUBLIC0x04b0…c0e7
πGroth16 proof192 bytes
Cardanostate UTxO
State UTxO datum
rootPUBLIC0xc609…2149
versionPUBLIC7
Cardano stores only the fingerprint, never the entries.
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: rejected
What Cardano learnedthe fingerprint moved by one valid value updateNot revealed: which entry changed, or its value. The public inputs are only the two roots.nothing: the state is still at version 7

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

SECRET stays in your servicePUBLIC on CardanoHash values are illustrative.

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.

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.

StatementMPFJMTPublic 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 updatesdeferreddeferred—

The circuits are exposed as PoseidonMpfCircuitTemplates / PoseidonJmtCircuitTemplates factory methods (inclusion(maxSteps), valueUpdate(maxSteps), …) and as ZkMpf* / ZkJmt* gadgets.

Poseidon MPFPoseidon JMT
StructureRadix-16 Patricia trie with compressed pathsVersioned Jellyfish Merkle Tree
Best forMembership/read-heavy state, compact native proofs, existing MPF dataUpdate-heavy state that needs version history, rollback and pruning
Measured complete profile at 5M entriesS9 (≤ 9 branch steps)S12 (≤ 12 levels)
Circuit size at that profile56,635 constraints14,057 constraints
Median Groth16 prove4.173 s2.901 s
Native (private) proof size805–939 B sampled2,744–3,161 B sampled
DeletionNo physical delete yetTombstones 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.

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.

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.

MpfInclusion.java
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 circuit

The JMT flow has the same shape: PoseidonJmtTree, PoseidonJmtInclusionWitness.create(...), PoseidonJmtCircuitTemplates.inclusion(maxLevels).

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

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.

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

build.gradle
dependencies {
implementation 'org.zeroj:zeroj-mpf-poseidon:0.1.0-pre13' // or zeroj-jmt-poseidon
}

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:

  1. freezing every deployed operation and profile, with published manifest, R1CS hash, VK identity, Poseidon fingerprint, compiler version and validator-template hash;
  2. independent circuit and cryptographic review;
  3. a reviewed Groth16 ceremony for each exact circuit;
  4. full state-token transactions validated on Yaci DevKit and a public network under current protocol parameters;
  5. an enforced one-shot, supply-of-one state-token policy;
  6. operational procedures for backup, restore, compaction, retention, rollback and rebuild;
  7. monitoring of proof depth, prover latency and memory, and rejected over-bound requests.