Expand description
§pca-folding-ivc — one succinct proof of an agent’s WHOLE action history (Nova folding)
Recursive action-proof aggregation (PCA roadmap T4.4) done the modern way: a
folding scheme (Microsoft Nova) instead of naive SNARK-of-a-SNARK recursion. We fold
N per-action steps into a single RecursiveSNARK whose size and the per-step prover
work are independent of N, then compress that into a succinct
CompressedSNARK — ONE proof that attests the agent’s entire history.
§What one proof attests
The IVC running state is z = [chain_digest, budget_spent] (arity 2), starting at
z₀ = [0, 0]. Step i consumes a per-action witness (action_digestᵢ, costᵢ) and
enforces in-circuit:
- Unforgeable action history, cost-bound —
chain_digest₍ᵢ₊₁₎ = H(chain_digestᵢ, H(action_digestᵢ, costᵢ))whereHis a Poseidon 2-to-1 hash over the step circuit’s native field (the Pallas scalar field). The finalchain_digestis therefore a collision-resistant commitment to the exact ordered sequence of actions; no action can be inserted, dropped or reordered without finding a Poseidon collision. - Cumulative-risk bound —
budget_spent₍ᵢ₊₁₎ = budget_spentᵢ + costᵢandbudget_spent₍ᵢ₊₁₎ ≤ B_MAX, enforced by an in-circuit bit-decomposition range gadget. Because folding carriesbudget_spentacross every step, this enforces the whole-history invariant Σcostᵢ ≤ B_MAX. A step whose running total exceedsB_MAXmakes the step’s R1CS unsatisfiable, so the aggregate proof is unprovable.
§Honest scope (candor)
- The hash
His a production, collision-resistant Poseidon over the circuit’s native field — the vettedneptuneimplementation vendored bynova-snarkitself and exposed atnova_snark::frontend::gadgets::poseidon(the same code path Nova uses for its own folding random oracle). We instantiate it through the sponge API with arity 2 (absorb[chain_digestᵢ, action_digestᵢ], squeeze one element) atStrength::Standard, i.e. the Poseidon-paper round numbers for widtht = 3targeting 128-bit security over GF(p) with the quintic (x⁵) S-box. The in-circuit sponge (SpongeCircuit) and the native sponge (Sponge) share identical, deterministically-derived round constants and MDS matrix, so they compute the same digest (Nova’s ownprovider::poseidontests assert this native/circuit equivalence). This is no longer a didactic placeholder. - Nova folds over the Pallas/Vesta cycle with an IPA PCS and a Spartan
CompressedSNARK: transparent (no trusted setup) but not post-quantum. “PQ-friendly” in the roadmap sense is that folding reduces the whole history to a single relaxed-R1CS instance that a PQ final SNARK (e.g. a STARK) could compress instead; wiring that PQ wrap is future work. We do not overstate it here.
Structs§
- Action
Circuit - The per-step circuit
F: folds one action into the running[chain_digest, budget_spent]. - Action
Step - One action in the agent’s history, as plain data.
action_digestis a digest of the action (here reduced to au64for the demo; a real integration feeds a field element hashed from the canonical action bytes).costis the action’s metered risk/cost. - Proved
History - A folded, verified recursive proof of one history, with everything needed to compress it.
Constants§
- BUDGET_
BITS - Bit width for the running-budget / headroom range checks.
2^BUDGET_BITSmust exceedB_MAXand the largest attainable cumulative total. - B_MAX
- Cumulative risk ceiling: Σcostᵢ must never exceed this across the whole history.
- COST_
BITS - Bit width for the per-action cost range check (costs live in
[0, 2^COST_BITS)).
Functions§
- action_
leaf_ native - Native image of the in-circuit leaf commitment
H(action_digest, cost)(RT-05): binds the metered cost to the action inside the hash chain. - check_
claimed_ z0 - Compare a start state a prover or fixture claims against the pinned one. Succeeds only for exactly
[0, 0]: right arity, canonical field elements, equal commitment. - circuits_
for - Build the per-step circuits for a history.
- compress
- Compress the folded recursive proof into a single succinct
CompressedSNARK— the one proof of the whole history. - compress_
keys - Derive the compressed-SNARK prover/verifier keys.
- felt_
to_ hex - Big-endian
0x-hex of a field element (for the JSON public-IO fixtures). - hash2_
native - The native (non-circuit) image of [
hash2]: Poseidon overFwith the identical arity-2 constants and IO pattern. Lets callers precompute the expected finalchain_digestand cross-check the IVC output. The vendored sponge guarantees this equals the in-circuit result. - initial_
state - The IVC initial state
z₀ = [0, 0]: the ONE starting state this scheme’s verifiers accept (R3-15). - initial_
state_ commitment - Commitment to the pinned initial state,
H(z₀[0], z₀[1])(Poseidon, same sponge as the chain). Recorded in the public-IO fixture (z0_commitment) so an out-of-band consumer can check which start the proof was verified against;check_claimed_z0recomputes and compares it. - native_
final_ state - Natively replay a history to the expected final
(chain_digest, budget_spent). - prove_
history - Fold an entire action history into one
RecursiveSNARKand verify it. - public_
params - Derive Nova public parameters for the step circuit (shape-only; witness values in
sampleare irrelevant). - verify_
compressed - Verify the compressed proof against the PINNED initial state (
initial_state). Returns the final[chain_digest, budget_spent]. There is deliberately noz0parameter (R3-15): the start state is part of what the verifier is, not something the prover or a fixture file gets to choose. - verify_
compressed_ claimed verify_compressedfor a caller that holds a claimedz0: fails unless the claim equals the pinned start state, and never verifies under any other start.- verify_
recursive - Verify a folded recursive proof against the PINNED initial state (
initial_state). Returns the final[chain_digest, budget_spent]. There is deliberately noz0parameter (R3-15). - verify_
recursive_ claimed verify_recursivefor a caller that holds a claimedz0(e.g. read from a public-IO file): the claim is compared with the pinned start state first and the call fails if they differ. It can never verify a proof under any start other than[0, 0].- within_
budget - Does this history stay within the cumulative bound? (A native pre-check; the circuit is the authority.)
Type Aliases§
- Chain
Hash Arity - Arity (sponge rate) of the Poseidon chain hash: we absorb exactly two field elements —
[chain_digestᵢ, action_digestᵢ]— and squeeze one, a 2-to-1 compression. Width ist = arity + 1 = 3. - Circuit
- The concrete step circuit type folded at every step.
- Comp
Prover Key - Compressed-SNARK prover / verifier keys.
- Comp
Verifier Key - Compressed
- The final succinct proof of the whole history.
- E1
- Primary engine (Pallas).
- E2
- Secondary engine (Vesta) — the other half of the cycle.
- EE1
- Transparent IPA polynomial-evaluation engine on each curve (no trusted setup).
- EE2
- PP
- Nova public parameters for this step circuit.
- Recursive
- The folded recursive proof (one per history).
- S1
- Spartan relaxed-R1CS SNARK used to compress the folded instance on each curve.
- S2
- Scalar
- The step circuit’s native field (the primary engine’s scalar field).