Native logup implementation of Stwo backend Powdr

Table of Contents

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, inputs, Default::default(), LinkerMode::Bus);
    test_mock_backend(pipeline);

    let inputs = [3, 5, 2, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7]
        .into_iter()
        .map(Mersenne31Field::from)
        .collect::<Vec<_>>();

    let pipeline = make_prepared_pipeline(f, inputs, Default::default(), LinkerMode::Bus);
    test_stwo_pipeline(pipeline);
}

the witness_lookup.pil file:

let N: int = 16;

namespace std::convert(N);
    let fe = [];

namespace std::prover(N);
    enum Query {
        Input(int, int),
    }

namespace Quad(N);
    col fixed id(i) { i };
    col fixed double(i) { i * 2 };

    col witness input(i) query std::prelude::Query::Input(0, i + 1);
    col witness wdouble;
    col witness quadruple;

    [input, wdouble] in [id, double];
    [wdouble, quadruple] in [id, double];

    public out = quadruple(N-1);

the first lookup identity looks like

left expression:

right expression:

These are the polynomials should be built into logup.

Stwo side, some basics

Lookup elements in constraint_framework, logup.rs:

The core function to understand is this

\(\alpha\) is for linear combination, so it can check several tables at the same time, \(z\) is the challenge for the logup. (needs a concrete example to confirm this)

attention: it takes a generic parameter N, which defines the degree of alpha_powers.

and when create a new lookupement, using relation macro like this: