The goal of this blog is to explain circle group without complex mathematical definitions. However, this approach is not rigorous, it serves more like a intuition of understanding the geometry of a circle group. Before diving into the blog, may you need some pre-readings like Exploring circle STARKs or Yet …
Coset
Using multiplicative group of size 16 to demonstrate the concept of coset.
Start with STARK context:
suppose we have a trace \([1,2,3,4]\) , and we want to prove \(f(x)+1=f(gx)\)
\(g\) is the group generator for cyclic group of size 4, the same size of the trace.
generate group of size
…Stwo Coset Establishment
Canonical coset:
odd coset setup
CirclePointIndex is just a wrapper of usize, which represent actually the order of the coset generator.
when creating a new coset, we need a generator and shiftoffset, the shiftoffset mostly be the generator of the subgroup of one log size bigger
so here, CirclePointIndex::subgroup_gen is …
The files in Powdr
Files structure:
std:
prelude.asm
In the context of programming, a prelude is generally a set of common imports or definitions that a module or program can use directly without needing to specify them every time. It acts like a convenience layer, making certain functions, traits, or types available by default.…
Stwo til now –21.Oct
Table of Contents
plonk in stwo
Trace table looks like this:
| a_wire | a_val | b_wire | b_val | c_wire | c_val | multiplicity |
| 0 | 1 | 1 | 1 | 2 | 2 | 2 |
| 1 | 1 | 2 | 2 | 3 | 3 | 2 |
| 2 | 2 | 3 | 3 | 4 | 5 | 1 |
| 3 |
Constraint system in STWO
Table of Contents
How Powdr translates PIL to Plonky3 and what about to stwo —2
following the first post
got two tasks:
- generate trace from pil to stwo
- implement FrameworkEval trait, which is used by stwo to define constraint, to PowdrCircuit
let’s talk about generate trace first.
in stwo, the trace is in this format as showed in last post
ColumnVec<CircleEvaluation<SimdBackend, BaseField, BitReversedOrder>>how powdr …
How Powdr translates PIL to Plonky3 STARK—1
in Powdr, the proving function of Plonky3 is in function prove_with_key, in stark.rs
you can see the inputs for prove_with_key function has “air”, this is what used to define constraints, powdr gives “&circuit” to it, and it is a powdrcircuit, probably powdrcircuit applies the trait of AIR
so at this …
stwo fibonacci
it is about this example in stwo
two parameters:
FIB_SEQUENCE_LENGTH specifies the rounds of fibo sequence
LOG_N_INSTANCES as stwo use SIMD, data parallel data struct, this number specify how many instances of fibo sequences are proved at the same time. The data are packed in LOG_N_LANES chunks, which is 16 …
Stwo backend note2
following note1
packed31 is a vector of length 16
try to understand how the trace is generated
the bottom lines actually transfer the M31 values into circleDomain
from start:
N is log N instances
this code is to initialise the witness columns, later use to store the witness.
this code …