# Large authenticated state (Poseidon MPF/JMT)

> Keep millions of entries off-chain, publish one Poseidon root, and prove single-key reads and updates with small Groth16 circuits. Experimental.

Canonical URL: https://zeroj.dev/guides/credentials/authenticated-state/

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.

> **Caution: Experimental**
>
> Both modules are **experimental**: opt-in, outside the stable BOM, and not externally reviewed.
> The 5-million-entry runs described below used deliberately insecure local setups, and the
> production gates listed at the end are still open. Don't protect value with them.

## How it works

```text
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.

```java title="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)`.

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

```groovy title="build.gradle"
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:

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.

## Further reading

- 5M benchmark reports: [MPF](https://github.com/bloxbean/zeroj/blob/main/docs/benchmarks/poseidon-mpf-5m-2026-08-02.md),
  [JMT](https://github.com/bloxbean/zeroj/blob/main/docs/benchmarks/poseidon-jmt-5m-2026-08-03.md)
- [Practical large-state guide](https://github.com/bloxbean/zeroj/blob/main/docs/merkle/practical-large-state-guide.md)
  and the [authenticated-state v1 specification](https://github.com/bloxbean/zeroj/blob/main/docs/merkle/poseidon-authenticated-state-v1.md)
- Design notes: [ADR-0042](https://github.com/bloxbean/zeroj/blob/main/docs/adr/0042-operation-specific-poseidon-mpf-and-jmt-circuits.md)

## Next steps

- [Private allowlist with a Merkle tree](https://zeroj.dev/tutorials/private-allowlist/)
- [Verify proofs on Cardano](https://zeroj.dev/guides/verifying/on-chain/)
- [Proving performance](https://zeroj.dev/guides/proving/performance/)