Field note
Stwo Circle-STARKs Over Mersenne-31, From Trace to Proof
A STARK begins with an execution trace: a rectangular table whose rows describe consecutive steps of a computation. An algebraic intermediate representation, or AIR, states local laws over that table. For example, a column may hold a state counter and a constraint may require the next row to equal the current row plus one.
The prover commits to a trace and demonstrates that the constraints hold throughout it without sending every row. FRI supplies the polynomial proximity argument: the committed evaluations behave like evaluations of low-degree polynomials, which is what turns many local checks into one succinct proof.
Why “circle” appears in circle-STARK
Traditional STARK constructions evaluate over multiplicative subgroups with convenient power-of-two sizes. Mersenne-31, the prime field with p = 2³¹ − 1, does not offer the same subgroup structure. Circle-STARKs use points on an algebraic circle group to recover efficient power-of-two evaluation domains. The geometry is different; the objective is familiar: interpolate, commit, sample, and verify low-degree structure efficiently.
Why M31 is attractive
An M31 element fits comfortably in a machine word, enabling fast native arithmetic and SIMD-friendly proving. That choice is not free. A 31-bit challenge is too small for the system's soundness target, so Fiat–Shamir challenges live in the quartic extension QM31, roughly 124 bits. Large foreign-field operations such as secp256k1 verification must be decomposed into range-checked limbs.
The field therefore propagates through the architecture:
- resource commitments use Poseidon2 specialized to M31;
- LogUp multiset checks use QM31 challenges;
- range checks become lookup arguments;
- the ECDSA notary signature requires non-native 256-bit arithmetic;
- recursive verification must itself fit the Stwo-oriented trace.
What the proof says in this vault
The Compliance-AIR checks consume-once identity, membership, nullifier non-membership, resource shape, fee presence, action binding, and complete partitioning. Kind-specific AIR leaves check meaning: fungible-asset conservation, account authorization, or FiatOfferV1's transition and private bank evidence.
Those leaves are recursively folded into an epoch proof. Ethereum verifies the aggregate transition and new roots instead of executing each private action or learning its private witness.
Privacy is an explicit mode
Succinctness alone does not imply zero knowledge. The target requires witness blinding and randomized FRI. It also pads every logic leaf to a global maximum shape so proof dimensions do not identify whether a leaf ran account logic, a transfer, Solve, Cancel, or Expire. That buys stronger function privacy at a real cost: every co-tenant pays for the largest leaf, including PayMoney's in-circuit ECDSA verifier.
Stwo is consequently not a magic privacy layer. It is the proving engine selected by the Architecture of Record. Correctness still depends on the AIR expressing the intended rules, zero-knowledge configuration hiding the witness, and the implementation matching the pinned field, hash, lookup, and transcript parameters.