stwo backend note1

Powdr side

backend trait in powdr

• verify
• prove
• export_verification_key

how plonky3 implemented? this is in mod.rs

in mod.rs the backend trait is implemented for plonky3prover, in the prove function, it calls prove in stark.rs, where plonky3prover is implemented

so this prove function in stark.rs should be simliarly implemented in prover.rs in stwo

recall stark:

• get a trace with witness, and interpolate the witness to get a polynomial: the witness are the evaluations on the domain, in cicle stark, it is the circle domain

• committing to the polynomial and do the low degree extension, this step include fft and dfft
• define the constraints: boundry constraint and transition constraint:

for instance, first element should be 1, that is the committed polynomial has \(f(w^0)=1\), which means \( f(x)-1 \) has root at \(x=w^0\), so the poly should be dividable by \(x-w^0\)

STWO side

constraint related

there is a FrameworkComponent in stwo seems to be used for defining constraints

FrameworkEval has the following functions

maybe here, the frameworkEval can be understood as: how to map the domain element to a trace, which is a evaluation process.

EvalAtRow is a trait, which has many math operations add mul, sub ….

it is important til now to understand what is mask in stwo means, it is a core concept in the definitions related to air

start from ColumnVec, each element can be consider as an witness, each witness needs one column, or it contains all the index of the column

does this mean, each component, is a cluster of witnesses?

now comes the definition of mask, columnVec contains the index of the witness column, each witness column is a vector

next_trace_mask, from now I understand it is probably like adding a column, or referring the next element in a specific witness or something,

Trace related

but now, I need to understand this packedM31 and M31

as I checked the input for fibonacci

and this PackedBaseField is PackedM31

M31:

• M31 is a wrapper type around an integer type (likely u32 or u64) that represents an element in a finite field modulo PPP.
• It is designed to hold single elements and provides methods for operations (like addition, multiplication, etc.) within this finite field. The actual finite field modulus PPP is defined elsewhere in the code (likely as a constant).

PackedM31:

• PackedM31 is a vectorized or “packed” version of M31, utilizing SIMD (Single Instruction, Multiple Data) to perform parallel computations on multiple M31 elements simultaneously.
• This type is implemented using Rust’s SIMD capabilities (std::simd) and is designed to perform batch operations on vectors of M31 elements for optimized performance on modern hardware.

see note2