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.

How it works

OFF-CHAIN (your service)
  RocksDB MPF/JMT, millions of entries
    │  read one native proof path for key K
    ▼
  strict verification + normalization  ──►  bounded, canonical witness
    │
    ▼
  operation-specific circuit  ──►  Groth16 prover  ──►  192-byte proof
                                                           │
ON-CHAIN (Cardano)                                         ▼
  state UTxO datum: old root  ──►  validator: verify proof over (old root, new root)
                                   and check the continuing state UTxO carries new root

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

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?

	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,627,770,348 CPU steps and 177,749 memory units in the JuLC VM. 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

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)

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 circuit

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

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

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

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-pre12'   // or zeroj-jmt-poseidon
}

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.