The bus_id in Bus

I am using a simplified circuit for case demonstration purpose:

The bus statement to be proved is:

\([x_0,x_1]\) in [0] with \(bus_{id}\)=a,

this case has only one valid witness [0,0], with multiplicity to be 2

Original protocol:

The above statement essentially proves:

\(\frac{1}{\alpha -x_0}+\frac{1}{\alpha -x_1}=\frac{2}{\alpha}\)

where \(\alpha\) is a random …

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 stwo> result.txt

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

    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, inputs,
    …

    Spartan 4

    previous posts: 1,2, and 3

    Overview of spartan paper

    summarize again what spartan paper offer:

    • transparent zksnark for arbitrarily NP statement
    • sub-linear verification
    • time optimal prover

    sub-linear verification,computation commitment for sparse multilinear polynomials

    recall in post 3, the remaining problems:

    1. use extractable polynomial commitment for multiliear polynomial
    …

    Spartan 3

    following the previous posts about spartan: 1 and 2

    Chapter 5, A family of NIZKs with succinct interactive argument of knowledge

    from post 1 we get a goal to check

    \(\mathcal{Q}_{io}(\tau)=\sum\limits_{x\in \{0,1\}^s}\mathcal{G}_{io,\tau}(x)=\sum\limits_{x\in \{0,1\}^s}\widetilde{F}_{io}(x)\cdot \widetilde{eq}(\tau,x)=0\)

    where \(\tau\) is a random checking point.

    recall we have:

    \(\widetilde{F}_{io}(x)=\left(\sum\limits_{y\in\{0,1\}^s}\widetilde{A}(x,y)\cdot Z(y)\right)\cdot \left(\sum\limits_{y\in\{0,1\}^s}\widetilde{B}(x,y)\cdot Z(y)\right)\)

    let’s start …

    Spartan 2 some basic terminologies

    Follow my first post for Spartan

    Closed-form expression for evaluating a polynomial

    The closed-form expression for evaluating a polynomial \(\mathcal{G}(\cdot)\) at \((r_1,…,r_m)\in \mathbb{F}^m\) is

    $$\mathcal{G}(r_1,…,r_m)=\sum\limits_{x\in\{0,1\}^m}\mathcal{G}(x)\prod\limits^{m}_{i=1}\underbrace{(r_i\cdot …