Implement Stwo challenger in Powdr 1

The first place the challenger is called is in stark.rs prove function:

in circuit_builder.rs in plonky3, the ConstraintSystem has a field: challenges_by_stage, can check how this field is built.

in stark.rs, the constraintSystem is initialized from a pil file

Table of Contents

circuit_builder.rs

Data struct has a challenges field, and has a get challenge function:

The input and output of this function is

the output can be phantomData:

can be numbers

How these result are updated? check next section PowdrTable eval

Prove function in circuit_builder

structs:

Table

air: PowdrTable

PowdrTable: constraintSystem

degree

MultiTable: tables:BTreeMap<String, Table<‘a, T>>

table contains constraintsystem, it includes one reference

the info print out here

The string part of the tables is Global

in the challenge identity part:

it does computation on challenges, so need to know how these challenges are generated.

Afterwards, put the commitment in the proving key to the challenger input buffer

afterwards, the next step is oberve_instance by multi_table, challenges updates should be related to these steps

this code

multi_table.observe_instances(challenger);

The observer_instance function iterator over all the tables in multi_table, call observe function of each table

The table’s observe_instance is

which calls the plonky3 original challenger function to update challenger buffer.

after fill the challenge input buffer, it create state, most probably for tracking the stages

In this prover state, it called MultiTable as program

and in the ran stage function, we see the challenge is sampled.

The output is

PowdrTable eval

PowdrTable should be the struct that implement the AIR trait, eval is the function where the circuit constraint is built. Data, which has the challenge field, is built here.

ProverConstraintFolder and VerifierConstraintFolder are equivalent to these structs in plonky3, but they have challenge field.

test case:

pil code:

let N: int = 8;     
        namespace Global(N); 
            let alpha: expr = std::prelude::challenge(0, 41);
            let beta: expr = std::prelude::challenge(0, 42);
            col witness x;
            col witness stage(1) y;
            x = y + beta * alpha;

what does this code do?

powdr doc has explanation for challenges:

so this code, the first parameter is stage, the second is challenge ID

let alpha: expr = std::prelude::challenge(0, 41);

Question:

challenger is “asking a verifier for a random number” but the protocol is non-interactive by using fait shamir, the random number is always generated from hash result. so the question is, what is the digest?

Plonky3 hash challenger implementation

the hashchallenger has 3 fields

It has two function:

new
flush

implement two traits

CanObserve: observe functions, clear output buffer, take values to input buffer

CanSample: take the last value form the output buffer

The flush function is two consume all the inputs data, hash them and pending the result to the output

Important detail about the challenger:

which field it should sample from? M31 Field or extension field.

The Traits in plonky3 to defined the challenger:

CanObserve
CanSample
CanSampleBits
FieldChallenger, which should implement the above three

The hash challenger described above implemented these traits

To be continued in the nest post