logup GKR stwo implementation steps

Include challenge in input MLE

question 1: the challenge in logup denominators are really necessary to be in MLE?

yes, this challenge is irrelevant to the GKR protocol (don’t mess it with the challenges in sum-check and challenges for later random linear combination of MLE evaluations), \(\frac{1}{\alpha +x}\) \(\alpha\) guarantees …

Stwo logup-GKR : build test example

step 1: get the most important 2 ingredients:

when create a component like this:

there are two important thing:

  • FrameworkComponent
  • eval that implement FrameworkEval

we can see the example actually use two types of Component, one is from FrameworkComponent (MleCoeffColumnComponent), one is from MleEvalProverComponent, which is defined specifically for MLE …

High degree constraint in Plonky3 and Stwo

How to define high degree constraint in Plonky3 and Stwo as a user

Plonky3:

A user must verify the following equation when determining the degree of the constraint (further explanation is provided in the next section):

let \(d\) be the degree of the constraint:

\(d-1\leq 2^{\text{log_blow_up_factor}}\)

If this condition is …

Note for bus in stwo 2

continue from this blog

Another thought: proving everying thing together and logup by stwo as extra.

Building LogUp trace

basic steps:
  • logup trace generator, size is determined.
    let mut logup_gen = LogupTraceGenerator::new(log_size);
    • generate columns that is associated with this logup trace generator
    let mut col_gen = logup_gen.new_col();
    • write fraction, building

    Notes for bus in stwo

    related to this PR

    Test case

    cargo install --path ./cli-rs

    compile with the correct field

    powdr-rs compile riscv/tests/riscv_data/keccak -o output --field bb
    cargo run --features stwo pil  output/keccak.asm --linker-mode native  -o output --force --field m31  --prove-with stworesult.txt

    This can give keccak_opt.pil file with lookup identity, it is native lookup, …

    Native logup implementation of Stwo backend Powdr -2

    following the first post 1

    test command

    RUST_LOG=stwo=trace cargo test --package powdr-pipeline --test pil --features stwo -- witness_lookup --exact --show-outputresult.txt

    Implementation notes

    Witness to BaseColumn

    witness needs to be transformed into BaseColumns and then use the combine function to get fraction.

    in Plonk example, all the witness columns are …

    Deep dive to InfoEvaluator of Stwo

    The reason I write this is because I saw the verification sample ood points are related to InfoEvalator. InfoEvalator contains this mask or mask offset information which basically embedded the circuit information.

    This mask points of MleEvalProverComponent

    Start with component built

    when a component is buit, it takes a location_allocator, …

    Native logup implementation of Stwo backend Powdr

    Powdr side:

    run test in pipeline (I changed the test so it can include stwo):

    #[test]
    fn witness_lookup() {
        let f = "pil/witness_lookup.pil";
        let inputs = [3, 5, 2, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7]
            .into_iter()
            .map(GoldilocksField::from)
            .collect::<Vec<_();
        let pipeline = make_prepared_pipeline(f,