StwoStarkware

Description

Stwo is the next iteration of Starkware zkVM STARK system. It is intended to prove the execution of programs written in Cairo language and compiled into Cairo assembly (cASM) byte code, however it also allows writing custom AIR to be proven. Stwo verifies STARK proofs directly onchain without any final SNARK wraps and thus requires no trusted setup.

Stwo targets 96 bits of cryptographic security + 30 bits of PoW grinding security (e.g. see constructor params on this contract). Here PoW grinding refers to a challenge that prover needs to compute every time they generate a proof. An honest prover performs the work only once but a malicious prover has additional computational load with every attempted forging of a proof.

Proof system

Stwo proof system is a zkVM working with AIR arithmetizations over Mersenne31 field. This stwo-cairo toolkit allows compiling Cairo program traces to the AIR arithmetization, however it is possible to create custom AIRs to be proven by Stwo, see more here.

Stwo offers several innovations to optimize proving time. Firstly, its use of small Mersenne31 field compared to previous version felt252 field is much better aligned with CPU arithmetics, also operations over M31 could be highly optimized as explained here. Secondly, Stwo implements a circle STARK as introduced in this paper. Thirdly, Stwo prover now uses Blake2 hash function instead of Poseidon, which is more efficient.

Circle STARKs

Circle STARKs replace interpolation domain without any structure with an interpolation domain with a structure of a circle domain, where points of interpolation are chosen from a complex unit circle over Mersenne31 field. It allows using Circle FFT algorithm, which speeds up the interpolation step in STARK proving, as well as Circle FRI algorithm for low-degree polynomial testing.

StarkNet Operating System (SNOS)

The base layer of Stwo proving L2s is a Cairo program called SNOS that proves the correct STF from one state to another given the list of transactions. SNOS execution includes checking transaction inputs (e.g. state), executing transactions and processing state diffs. The source code of the Starknet OS can be found here.

Recursive aggregation

Proofs of SNOS executions of several consecutive blocks are recursively aggregated. The correctness of this aggregation is checked by applicative bootloader program, which also verifies the correct relation of corresponding SNOS inputs and outputs. Applicative bootloader proofs are aggregated across several blockchains and proven by SHARP. The SHARP STARK proof is verified onchain without any SNARK wraps.

Trusted setup

Stwo is a STARK (transparent SNARK) that does not perform a wrap in a SNARK, so it does not require any trusted setup.