stark-pca — a transparent STARK of the PCA release gate
Install: cargo add stark-pca
A genuine, verifiable zk-STARK of the core release decision of Proof-Carrying Authority, built with the Winterfell STARK library (pure Rust).
- Transparent — no trusted setup, no toxic waste, no per-circuit ceremony.
- Post-quantum — security rests only on a collision-resistant hash (BLAKE3) and the random-oracle / FRI low-degree-test assumptions; there is no discrete-log or pairing assumption anywhere.
- No verifying key — a STARK has no circuit-specific setup artifact. The AIR in
src/lib.rsplus the public parameters infixtures/params.jsonare the complete verification artifact (this is the "vkey-equivalent").
Winterfell version: 0.13.1. Status: 0.2.0, unaudited.
What the AIR proves (exactly)
Field: Winterfell's 128-bit prime field (f128). Hash: Blake3_256. Fixed-point scale
S = 1_000_000 (parts-per-million), matching the @atlasauth/pca reference risk model and its Groth16
Policy-VM circuit.
Public inputs (bound into the Fiat–Shamir transcript, so a proof only verifies against
these values): the six risk weights (α, β, γ, δ, ε, ζ) at scale S; the tier-1
threshold θ₁ at scale S; the integer cost scale κ; the budget ceiling bMax at
scale S; the scale S; two opaque commitments policy_commitment, action_commitment;
and the COMMIT_LIMBS = 4 limbs of witness_commitment — the resource server's algebraic
commitment to the quantized action, which the AIR constrains (unlike the two opaque
commitments, which it only transcript-binds). See the binding section below.
Private witnesses: the six risk-magnitude inputs
(d, rev, bl, taint, conf, age) ∈ [0, S]; the trust budget B at scale S; a
predicate-match bit pm; and a caveats-satisfied bit co.
The prover demonstrates, with real in-AIR algebraic constraints, knowledge of a witness such that:
-
Fixed-point risk functional (the integer image of
riskScorein the reference model, scaleS²):r_raw = α·d + β·(S − rev) + γ·bl + δ·taint + ε·(S − conf) + ζ·age r = r_raw / S² (so r ∈ [0,1] is the real-valued risk)revandconfenter as(S − x)exactly as(1 − reversibility)and(1 − confidence)do in the reference model. -
Input validity: each
x ∈ {d, rev, bl, taint, conf, age}is proven to lie in[0, S](i.e. a well-formed[0,1]fixed-point magnitude), via two bit-decomposition range gadgets per input (x ≥ 0andS − x ≥ 0). The budgetBis proven to lie in[0, bMax·S]. -
The release gate:
allow = (tier == 1) ∧ (B ≥ κ·r) ∧ pm ∧ co and allow == 1tier == 1 ⟺ r ≤ θ₁— the auto-admit band ofrequiredThreshold(). Enforced in-AIR as the range gadgetθ₁·S² − r_raw ≥ 0.B ≥ κ·r— the budget-admission cost gate ofadmit()/cost(). Enforced in-AIR as the range gadgetB·S − κ·r_raw ≥ 0(exact rational comparison; no truncation).pm,coare proven boolean (b² = b).allowis derived in-trace as the producttgate · bgate · pm · coand asserted== 1. The two inequality bitstgate,bgateare proven consistent with the range gadgets above, so a deny witness —r > θ₁,B < κ·r,pm = 0, orco = 0— makes the constraint system unsatisfiable. You cannot forge anallow.
-
Witness ↔ commitment binding: a native in-AIR algebraic hash (a 10-lane cube-S-box SPN, one round per trace row) absorbs the nine quantized witness quantities and the first four squeezed state lanes are asserted equal to the public
witness_commitment. The same witness columns drive both the gate and the hash, so you cannot prove the gate for a witness that does not match the committed (quantized) action. See the honest fidelity-gap note below for exactly what this binds (the quantized struct) vs. the SHA-256 canonical JSONaction_commitment(not recomputed in-AIR).
The inequalities are enforced with genuine bit-decomposition range gadgets: a value
V is proven 0 ≤ V < 2⁶³ by exhibiting its 63 bits (each constrained boolean) summed by
a per-step running residual that must reach exactly 0. A "negative" (deny) difference
wraps to a field element ≥ 2⁶³, which has no valid 63-bit decomposition — so the residual
cannot reach 0 and no proof exists. This soundness relies on the field order lying in
(2⁶³, 2¹²⁸), which holds for f128.
Conformance tests (tests/integration.rs)
compliant_witness_proves_and_verifies— a compliant witness (r = 0.065 ≤ θ₁ = 0.25,B = 1.0 ≥ κ·r,pm = co = 1) proves and verifies OK.non_compliant_risk_cannot_prove_allow—r > θ₁andB < κ·r: no verifyingallowproof can be produced.non_compliant_predicate_cannot_prove_allow—pm = 0: no verifyingallowproof.tampered_proof_is_rejected— a bit-flipped proof fails verification.tampered_public_input_is_rejected— a proof does not verify under a differentaction_commitment(transcript binding).tampered_policy_weight_is_rejected— a proof does not verify under a different weight.committed_fixture_proof_verifies— the committedfixtures/sample_proof.binverifies.
Honest fidelity gaps vs the Groth16 Policy-VM circuit
This STARK is scoped to the release gate + the fixed-point risk functional. It is NOT at parity with the full Groth16 Policy-VM circuit. The precise gaps:
-
The witness IS now bound in-AIR — to the quantized preimage, via a native algebraic hash (not SHA-256). The AIR runs a genuine in-AIR algebraic hash and asserts the private witness hashes to a public commitment, so a proof can no longer be produced for a witness that does not match the committed action. Precisely:
- A
NUM_LANES = 10-wide cube-S-box SPN (aₖ = (Hₖ + 2^row + RCₖ)³, diffusionH'ⱼ = Σₖ aₖ + aⱼ, one round per trace row, per-row constant2^row, per-lane constantsRCₖ) absorbs the nine quantized witness quantities(d, rev, bl, taint, conf, age, B, pm, co)on row 0 (lanes 0..8) + a capacity IV (lane 9). - The first
COMMIT_LIMBS = 4state lanes at the final row are asserted equal to a new public inputwitness_commitment(the four field-element limbs the resource server publishes). The same witness columns feed both the risk gate and the hash, so the proof exists only for a witness whose quantized form hashes to the committed value. This is thecompute_witness_commitmentfunction; onf128,gcd(3, p−1)=1, so the cube S-box is a field permutation. - What it binds, honestly: this binds the quantized witness struct (the integer
risk/budget/boolean preimage, at scale
S) to the committed action — it is NOT an in-AIR recomputation of the SHA-256-of-canonical-JSONaction_commitment(full variable-length canonical-JSON SHA-256 in-field remains infeasible without a dedicated SHA-256 AIR and a large blow-up — that is what the RISC Zero zkVM guest does with the accelerated sha256 precompile). The algebraicwitness_commitmentand the opaque SHA-256action_commitmentare linked off-circuit by the resource server deriving both from one action. Collision resistance of the binding rests on the algebraic-hash (MiMC/Poseidon-family, algebraic-degree) heuristic; a SHA-256-identical binding, and a larger round count /x⁷S-box on small fields, are documented follow-ups.
- A
-
Predicates and caveats are reduced to booleans. The circuit encodes a
(verb, resource)allow-list entry with a numericwherebound, and the six conjunctive caveats. Here, predicate-match and caveats-satisfied are single boolean witness bits (pm,co) — the policy-matching logic that produces those bits is not re-derived in-AIR. -
Only the t=1 tier band is encoded.
requiredThresholdhas a three-tier ladder (t=1/t=2/t=3) and an optimistic-acceptance rule. This AIR proves exactly the machine-auto-admit gatetier == 1 ⟺ r ≤ θ₁;θ₂and the t=2/t=3 bands are not encoded. -
No attenuation / delegation chain. The circuit encodes the capability-chain narrowing (
budget_allocmonotonicity, depth bound). This AIR does not. -
κrestricted to a non-negative integer. The reference model allows a real-valuedkappa. Hereκis an integer multiplier (default1). The budget comparison is done by up-scaling (B·S ≥ κ·r_raw), so it is an exact rational comparison with no truncation error — but fractionalκis out of scope. -
The clamp-at-1 is a no-op on the allow domain.
riskScoreclampsrinto[0,1]. Because the gate requiresr ≤ θ₁ < 1, the clamp never binds on any satisfiableallowinput, so it is omitted;r_rawis compared directly (r_raw ≤ θ₁·S²). -
Witness-data-dependent constraint degrees. Winterfell's debug-only
validate_transition_degreesaid requires exact declared-vs-measured degree equality, which a data-dependent AIR (e.g. a zero-valued input collapsing a range-check to degree 0) cannot satisfy for all witnesses. Our declared degrees are correct upper bounds (never under-declared → always sound); that dev-only assertion is disabled in the test profile (seeCargo.toml). Proofs are generated and verified normally.
What this STARK does give you that Groth16 does not: a transparent, post-quantum, setup-free proof of the release decision and the fixed-point risk functional.
Build, test, and regenerate fixtures
Sample timings on a 4-vCPU machine: prove ≈ 3.5 ms, verify ≈ 0.4 ms, proof size 37,824 bytes (~37 KB).
Fixtures (committed)
fixtures/sample_proof.bin— a sampleallowSTARK proof (binary, ~37 KB).fixtures/public_inputs.json— the public inputs (policy) for that proof.fixtures/params.json— the STARK/verification parameters (the "vkey-equivalent").