Skip to content

REGENESIS_SPEC.md

Latest commit

 

History

History
186 lines (152 loc) · 13.1 KB

REGENESIS_SPEC.md

File metadata and controls

186 lines (152 loc) · 13.1 KB
Raw

zk-STARK Re-genesis Spec — the circuit, the prover, the verifier, the feasibility gate

The zk-STARK foundation of the voting system. This spec pins the fundamentals so they never need re-cutting: the unified vote circuit (scalar + ranked), the prover, the on-chain verifier (on a permissioned POA Besu chain — gas-free), and the feasibility stress-test that gives a go/no-go.

0. Where STARK verification happens (the on-chain/off-chain split)

The same circuit runs everywhere; only where the proof is verified differs:

Event Verified Why
Proposal graduates → rule / initiative / tag / role vote anchors on-chain STARK verified ON-CHAIN (Besu) a durable governance object is being created — the chain must check it itself
Pre-quorum tallying in the ballotbox DB (proposals, rules, etc.) verified off-chain (ballotbox DB), root anchored bulk tally; only the graduated root needs on-chain proof
Show applause (score-bearing) verified off-chain (ballotbox DB), settlement root anchored at close high volume, ephemeral; the close checkpoint carries the receipt
Show lighting / expressive off-chain aggregate, optional periodic anchor sub-second, inconsequential

So on-chain STARK load is bounded (graduations + settlements), not per-vote — which is what makes a self-hosted verifier comfortable (§4).

1. The unified vote circuit (the AIR)

A faithful STARK port of the current vote.circom (Semaphore-style), generalised to cover scalar AND ranked in one circuit, so a single verifier serves every vote shape forever (the additive guarantee).

1.1 Identity & nullifier (unchanged semantics, STARK-native primitives)

secret        = H(identityNullifier, identityTrapdoor)
commitment    = H(secret)                                  // Merkle leaf (eligibility)
nullifierHash = H(externalNullifier, identityNullifier, revision)   // rotating per change

H = the STARK-friendly hash (§3 — RPO). Identity material comes from VoteToken custody (governance) or the RFID fob (shows) — same shape, different source.

1.2 Public inputs (the proof reveals only these)

signal meaning
merkleRoot eligibility set root (token-holders, or in_show attendees)
externalNullifier ballot scope, field-reduced keccak(scope) mod p (e.g. rule:<jur>:<key>, applause:<show>:<perf>)
nullifierHash the nullifier being spent (one per voter per ballot per revision)
prevNullifierHash the prior revision's nullifier (chaining anchor; 0 on first cast)
voteMode 0 = scalar, 1 = ranked — selects the choice constraint
voteChoice scalar: the value; ranked: a commitment H(rank[0..N-1]) to the ranking
choiceCount (N) the ballot's choice count (ranked; 1 for scalar). Public — it's the ballot's on-chain config (config.choiceCount), not voter data; leaks only the ranking length, never the ranking. (Implemented public in vote_stark.)

1.3 Private inputs (witness)

identityNullifier, identityTrapdoor, pathElements[depth], pathIndices[depth], revision, and (ranked only) the ranking rank[0..N-1]. (N = choiceCount is public — see §1.2.)

1.4 Constraints (the AIR must enforce all)

  1. Membership: Merkle-verify commitment up pathElements/pathIndices (depth ≥ 20) equals merkleRoot. (Port of MerkleInclusion; pathIndices[i] ∈ {0,1}.)
  2. Nullifier binding: nullifierHash == H(externalNullifier, identityNullifier, revision) — so a valid nullifier requires the secret; scoping kills cross-ballot replay; revision rotation kills same-ballot replay.
  3. Choice validity (mode-switched):
    • scalar (voteMode=0): 0 ≤ voteChoice ≤ maxValue (range check; covers boolean 0/1, stars 1–5, sliders to 2^16−1). Bind it into the trace (the current voteChoiceSquared trick) so the choice can't be malleated.
    • ranked (voteMode=1): rank[i] ∈ [0, N) ∀i, all-distinct (a valid permutation), and voteChoice == H(rank[0..N-1]). (This is the ranked-choice gadget — range + distinctness.)
  4. Vote-change chaining (two parts — audit F1): the circuit binds prevNullifierHash to the voter's OWN prior nullifier in-circuit (the cross-revision identity binding added to close audit finding F1 — the earlier "contract-side only" framing was unimplementable since identityNullifier is secret, so one voter could overwrite another's). The contract then additionally confirms prevNullifierHash was the live head and enforces monotonic revisions (fork/replay + ordering guard, in AnonymousVoteVerifier). Both are load-bearing for vote integrity (external-auditor brief item).

Scalar is the degenerate ranked case (N=1) — implement ranked, derive scalar from it, so there is provably one circuit. voteMode exists only to pick the choice constraint cheaply.

1.5 Parameters (tunable; lock at the cut)

Merkle depth (≥20 → ≥1M members), ranked N_max (e.g. 8), FRI blow-up + query count (security λ ≥ 96-bit), field & hash (§3).

2. The substrate switch (happens AT the re-genesis)

Today: BN254 field + Poseidon + Groth16. The cut switches the whole zk substrate to STARK:

  • Field: Goldilocks p = 2^64 − 2^32 + 1 (64-bit, STARK-native, fast on phone + node).
  • Hashes — TWO distinct roles (don't conflate):
    • In-AIR identity hash = RPO (Rescue-Prime Optimized) — algebraic, Goldilocks-native; used for commitment / nullifierHash inside the circuit (§1.1). Unchanged.
    • FRI/trace commitment hash = Blake3 (or keccak) — the hash the prover uses for its Merkle commitments, which the on-chain verifier re-hashes to check. This is the dominant on-chain verify cost (§4), and it's a SEPARATE choice from the in-AIR hash. Blake3 is EVM-cheap; RPO commitments are ~50× heavier in pure Solidity (fine under the precompile). Winterfell lets you pick this independently — its examples default to Blake3, which is what we want for the Solidity-FRI interim.
  • Proof system: STARK (FRI), no trusted setup, post-quantum.
  • Ballotbox DB rebuild: every commitment / Merkle tree / nullifier in the ballotbox DB is recomputed under RPO/Goldilocks at the cut — the same circuits then run against the ballotbox DB exactly as on-chain (a hard requirement). This rebuild is a re-genesis step, not a migration.

3. Prover decision (recommendation: Winterfell)

Option Field/Hash On-chain verify Phone-prove Notes
Winterfell (Rust) ✅ rec Goldilocks / RPO write our own (Solidity or Besu precompile) WASM (demo proved ~1s) direct AIR, lean proofs, no VM overhead, we own the verifier protocol
Miden (Rust VM) Goldilocks / RPO Miden verifier WASM write circuit as a program (easier authoring) but heavier proofs; bundle already references it
genSTARK (JS) 2^128−… none yes (the demo) feasibility spike only — research-grade, no production verifier
Plonky2/3, Cairo/Stone Goldilocks wraps to SNARK / StarkWare infra — reintroduces trusted-setup wrap or external infra — rejected

Why Winterfell: we write the AIR directly (matches §1 cleanly), Goldilocks+RPO, WASM-compilable for the phone-proving we already proved, and — decisively — we author the verifier ourselves, which is exactly what a chain-we-own wants. Miden is the fallback if writing the AIR by hand proves too costly (trade authoring ease for heavier proofs).

4. Verifier decision — on OUR chain, gas is not the question

On public Ethereum a Solidity FRI verifier is millions of gas = real money. On vote_besu (POA, gasPrice = 0, gasLimit ours to set) that cost is $0 — verification on-chain is not just feasible, it's the default. The only real budget is node CPU per verify (every validator re-runs it). Two forms, both on our chain:

Form What When
Solidity FRI verifier the FRI check in EVM bytecode the feasibility/stress-test interim — fast to stand up, validates the whole path on the real chain
Besu precompile the FRI check as a native Besu plugin (native-speed hashing/field math, tiny fixed gas) production — ~100× faster node execution; the clean form

Solidity-FRI → precompile is an additive swap (same protocol, faster host), so we can ship the interim and harden later without a re-cut. Either way, public Ethereum never enters — we lift and verify the STARK on our own chain.

The cost lever (measured — §5): the FRI/trace commitment hash dominates on-chain verify cost. A Blake3/keccak-commitment verify is ~2M gas / ~67 ms on our node — feasible even in Solidity. An RPO-commitment verify in pure Solidity is ~100M gas / ~3.4 s — which is precisely the case the precompile erases (native RPO ~100× faster). So: commit with Blake3 for the Solidity-FRI interim; the precompile makes RPO commitments cheap too. RPO stays the in-AIR identity hash regardless (§2).

5. The feasibility stress-test (the go/no-go — run during the dev cutover)

The instinct: stress-test with mock STARK verification, determine feasibility. The plan:

  1. Mock verifier on dev Besu: implement a representative FRI-verify in Solidity (real hashing + field-op volume for the chosen params) and deploy to a dev Besu chain.
  2. Benchmark a single verify: gas used, node wall-clock per verify, proof size.
  3. Stress the graduation load: simulate K proposals graduating in a window, each replaying M voter proofs; measure verifications/block and block-time impact at raised gasLimit.
  4. Phone-prove the real circuit: port §1 to Winterfell, prove on a phone (target ≤ ~2s).
  5. Decision: if Solidity-FRI node-time holds at expected load → ship it for v1, precompile later. If it bottlenecks block production → precompile is required. This benchmark is the feasibility verdict.

MEASURED — chain-side mock on a dev Besu chain (2026-06-24)

A MockFriVerify reproducing the verify operation volume (keccak Merkle + Goldilocks mulmod), benchmarked on the dev node:

  • EVM throughput: ~30M gas/s (4.96M-gas call executed in 160 ms).

  • Per-op: keccak ≈ 320 gas, Goldilocks field-mul ≈ 225 gas.

  • Projected single verify (λ≈96, depth-20 Merkle, ~32–48 queries):

    Commitment hash gas/verify node time/verify on-chain?
    Blake3/keccak Merkle ~2.0M ~67 ms ✅ easily — even Solidity
    RPO Merkle in pure Solidity ~101M ~3.4 s ⚠️ wants the precompile

Verdict: on-chain STARK verification on our own Besu is feasible — a Blake3-commitment verify is ~2M gas / ~67 ms (~15 verifies/s/node), comfortably within reach (current dev gasLimit 8M is a raisable config knob). The chain-side go/no-go is GO for the Solidity-FRI interim with Blake3 commitments; the precompile is an optimization, not a prerequisite. Remaining for full go/no-go: the agent's phone-prove number (step 4) to confirm the proving half.

6. Genesis checklist — what MUST be baked at the cut (everything else is additive)

  1. The STARK verifier (Solidity-FRI and/or precompile) wired where AnonymousVoteVerifier is today.
  2. The unified circuit (§1) — scalar + ranked, so no future vote shape forces a new verifier.
  3. Field + hash locked (Goldilocks + RPO) across on-chain verifier, prover, and ballotbox DB.
  4. The identity/commitment/nullifier scheme (RPO, rotating nullifier) — shared by VoteToken + fob.
  5. CheckpointRegistry, ChainClock, PTS minter — already general; reused for graduation/settlement.

Additive after (no re-genesis): ShowRegistry / check-in attestation / performance contracts; new externalNullifier scopes; the Solidity-FRI → precompile swap; new B.2 structures; wider N_max/depth only if §1.5 was cut generously (so size them with headroom now).

7. Implementation handoff (the coding-agent brief)

A STARK/Rust agent can build from this spec. Deliverables, in order:

  1. vote_stark AIR (Winterfell, Rust): §1 circuit; unit-tested against test vectors ported from the current circom (same identities → same commitment/nullifierHash under RPO/Goldilocks) so off-chain ↔ on-chain ↔ ballotbox-DB agreement is provable.
  2. WASM build for client/phone proving (parity with the genSTARK demo's latency).
  3. Reference verifier (Rust) + Solidity-FRI verifier matching the exact transcript/params.
  4. Besu precompile verifier (native) — same protocol, production host.
  5. The §5 benchmark harness. Hand this doc as the brief; the agent does NOT need the rest of the repo to start (1)–(3).

8. Open decisions (lock before/at the cut)

  • N_max for ranked (8?), Merkle depth (20? 24?), security λ (96/100-bit) → proof size vs. cost.
  • Winterfell vs. Miden (authoring effort vs. proof weight) — §3.
  • Solidity-FRI for v1 vs. precompile-from-day-one — decided by the §5 benchmark.
  • Whether the ballotbox-DB rebuild reuses the same Merkle depth as on-chain (it should, for circuit parity).