StwoStarkware

Description

Stwo is the next iteration of Starkware zkVMA special type of zk proving system that proves the correctness of state transitions of a virtual machine. Computation is represented by a program in a specific instruction language, it can have private and public inputs and public outputs. Most of zkVMs are STARKs. STARKShort for "scalable transparent argument of knowledge", a STARK is a type of zero-knowledge proof that resolves one of the primary weaknesses of ZK-SNARKs, its reliance on a "trusted setup”. STARKs also come with much simpler cryptographic assumptions, avoiding the need for elliptic curves, pairings, and the knowledge-of-exponent assumption and instead relying purely on hashes and information theory. This means that they are secure even against attackers with quantum computers. 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 AIRAlgebraic intermediate representation (AIR) is a type of arithmetization commonly used in zkVMs. It represents a trace of zkVM state transitions with low degree polynomial constraints that enforce the correct relation between previous and current states of the computation. Several variations of AIR are used in practice, with slight differences among them. to be proven. Stwo verifies STARK proofs directly onchain without any final SNARKShort for "succinct non-interactive argument of knowledge", a SNARK is a widely used type of zero-knowledge proof that is short and fast to verify. Different kinds of SNARKs are usually systematized by proof size, verification time, and type of setup. The most famous SNARKs are Groth16, PLONK/Marlin, Bulletproofs, and STARKs. wraps and thus requires no trusted setupGeneration of a piece of data that must then be used for some cryptographic protocol to run. Generating this data requires some secret information. The "trust" comes from the fact the secret must be destroyed after the ceremony, otherwise cryptographic properties of the protocol could be broken. Once the data is generated, and the secrets are forgotten, no further participation from the creators of the ceremony is required. There are two types of trusted setups for SNARKs: (i) trusted setup per circuit where it is generated from scratch for each circuit, (ii) trusted universal setup per proving system where it can be used for several circuits..

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 proverAn entity that generates the cryptographic proof to convince the verifier that the statement is true. In a ZK-Rollup, the prover generates the ZK (validity) proof to submit to the verifier contract. 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 systemThe infrastructure that allows projects to verify their state transitions. It is composed by onchain verifiers and offchain provers. The main two flavors are optimistic and ZK proof systems, but they can be combined in a hybrid model. In general though, if a system is able to accept state roots optimistically, even if it has a ZK component, it is considered an optimistic 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 arithmetizationA part of zk proving system, a process that transforms the computation to be proven into a set of polynomials with particular properties., 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 hashA fixed-length fingerprint of variable-size input, produced by a hash function. 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 FRIA proximity test method that is used to determine whether a set of points is mostly on a polynomial with a degree less than a specified value. It resembles the FFT but the arithmetic complexity of its prover is strictly linear and that of the verifier is strictly logarithmic. 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 blocksAn ordered list of transactions and chain-related metadata that gets bundled together and published to the L1/DA layer. Nodes execute the transactions contained within blocks to change the rollup chain’s state. Protocol rules dictate what constitutes a valid block, and invalid blocks are skipped over. 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.