Skip to main content

Crate pca_folding_ivc

Crate pca_folding_ivc 

Source
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:

  1. Unforgeable action history, cost-bound — chain_digest₍ᵢ₊₁₎ = H(chain_digestᵢ, H(action_digestᵢ, costᵢ)) where H is a Poseidon 2-to-1 hash over the step circuit’s native field (the Pallas scalar field). The final chain_digest is 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.
  2. Cumulative-risk bound — budget_spent₍ᵢ₊₁₎ = budget_spentᵢ + costᵢ and budget_spent₍ᵢ₊₁₎ ≤ B_MAX, enforced by an in-circuit bit-decomposition range gadget. Because folding carries budget_spent across every step, this enforces the whole-history invariant Σcostᵢ ≤ B_MAX. A step whose running total exceeds B_MAX makes the step’s R1CS unsatisfiable, so the aggregate proof is unprovable.

§Honest scope (candor)

  • The hash H is a production, collision-resistant Poseidon over the circuit’s native field — the vetted neptune implementation vendored by nova-snark itself and exposed at nova_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) at Strength::Standard, i.e. the Poseidon-paper round numbers for width t = 3 targeting 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 own provider::poseidon tests 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§

ActionCircuit
The per-step circuit F: folds one action into the running [chain_digest, budget_spent].
ActionStep
One action in the agent’s history, as plain data. action_digest is a digest of the action (here reduced to a u64 for the demo; a real integration feeds a field element hashed from the canonical action bytes). cost is the action’s metered risk/cost.
ProvedHistory
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_BITS must exceed B_MAX and 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 over F with the identical arity-2 constants and IO pattern. Lets callers precompute the expected final chain_digest and 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_z0 recomputes 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 RecursiveSNARK and verify it.
public_params
Derive Nova public parameters for the step circuit (shape-only; witness values in sample are irrelevant).
verify_compressed
Verify the compressed proof against the PINNED initial state (initial_state). Returns the final [chain_digest, budget_spent]. There is deliberately no z0 parameter (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_compressed for a caller that holds a claimed z0: 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 no z0 parameter (R3-15).
verify_recursive_claimed
verify_recursive for a caller that holds a claimed z0 (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§

ChainHashArity
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 is t = arity + 1 = 3.
Circuit
The concrete step circuit type folded at every step.
CompProverKey
Compressed-SNARK prover / verifier keys.
CompVerifierKey
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).