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, 

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 …

Circle STARK: Understanding Circle Group’s Operation as Rotation

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