An $O(n)$-sized circuit for evaluating $\widetilde{M}$

talking about this circuit:

notes:

for witness: $row, col, val$ are enough to describe a multilinear extension $\widetilde{M}$

$e_{row}, e_{col}$ should be the evaluations

I need recap on Offline memory checking

let’s follow this post to continue

I think …

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,

…

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:

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: FFT on circle domain

Following the first post: Circle STARK: Understanding Circle Group’s Operation as Rotation

The goal of this post is to explain 2-adic FFT on circle domain.

why FFT?

In STARK, there are two cases where FFT is used:

transform a polynomial from its evaluation form to its coefficients form.
FRI, where

…

Notes on Risc-V ZKVMs with Uma Roy

A Rust program is compiled to ELF, using traditional compiler (as ELF is not only used for ZKVM, but also for embedded system as well, this step is pretty much standard)

instruction explanation:

ADD, value1 stored in address xD, added this value by 5 and store the value in x29…

What is Runtime?

Runtime refers to the period when a program is actively running or executing on a …

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 …

Coset

Using multiplicative group of size 16 to demonstrate the concept of coset.

Start with STARK context:

suppose we have a trace $[1,2,3,4]$ , and we want to prove $f(x)+1=f(gx)$

$g$ is the group generator for cyclic group of size 4, the same size of the trace.

generate group of size

…

Shuang's Crypto Notes

Spartan 5

An \(O(n)\)-sized circuit for evaluating \(\widetilde{M}\)