Category: Zero Knowledge Proof

following previous posts: 1,2,3,4

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 …

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

…

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 …

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:

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

…

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 …

There are different ways to describe the GKR algorithm

from Libra paper:

$\tilde{V}_i(g) = \sum\limits_{x,y \in \{0,1\}^{s_{i+1}}} f_i(x,y)$

$= \sum\limits_{x,y \in \{0,1\}^{s_{i+1}}} \left( \widetilde{add}_{i+1}(g,x,y)(\tilde{V}_{i+1}(x) + \tilde{V}_{i+1}(y))\right.$

$\left. + \tilde{mult}_{i+1}(g,x,y)(\tilde{V}_{i+1}(x)\tilde{V}_{i+1}(y)) \right)$

from hyrax paper:

$$\widetilde{V_0}(q’,q)=\sum\limits_{h’\in \{0,1\}^{b_N}}\sum\limits_{h_L\in \{0,1\}^{b_G}}\sum\limits_{h_R\in \{0,1\}^{b_G}}P_{q’,q,1}(h’,h_L,h_R)$$

$$=\sum\limits_{h’\in \{0,1\}^{b_N}}\sum\limits_{h_L\in \{0,1\}^{b_G}}\sum\limits_{h_R\in \{0,1\}^{b_G}}\widetilde{eq_1}(q’,h’)$$

$$\cdot [\widetilde{mul_1}(q,h_L,h_R)(\widetilde{V_1}(h’,h_L)\times \widetilde{V_1}(h’,h_R) )$$

$$+\widetilde{add_1}(q,h_L,h_R)(\widetilde{V_1}(h’,h_L)+ \widetilde{V_1}(h’,h_R) )]$$ …

performance:

Prover is $\mathcal{O}(C)$

Verifier is $\mathcal{O}(d\log C)$ for d-depth log-space uniform circuit.

note: in sumcheck/GKR context, the size of the circuit usually is described as $2^l$, namely, the inputs of the circuit is $2^l$, for a linear prover in this setting, has complexity $\mathcal{O}(2^l)$, a logarithmic verifier has $\mathcal{O}(l)$ …

R1CS definitions

R1CS encoding

R1CS instance $x=(\mathbb{F},A,B,C,io,m,n)$

let $Z=(io,1,w)$, then we have for example

$\underbrace{\begin{bmatrix}0&1&1&0\\0&0&1&0\\…&…&…&..\\…&…&…&..\end{bmatrix}}_{A}\begin{pmatrix}w_1\\1\\w_2\\w_3\end{pmatrix}\circ \underbrace{\begin{bmatrix}0&1&0&0\\0&0&1&0\\…&…&…&..\\…&…&…&..\end{bmatrix}}_{B}\begin{pmatrix}w_1\\1\\w_2\\w_3\end{pmatrix}$

$=\underbrace{\begin{bmatrix}1&0&0&0\\0&0&0&1\\…&…&…&..\\…&…&…&..\end{bmatrix}}_{C}\begin{pmatrix}w_1\\1\\w_2\\w_3\end{pmatrix}$

This express the constraints:

$$(1+w_2) \cdot 1=w_1$$

$$w_2 \cdot w_2=w_3$$

(here $w_1$ is public input/output )

In order to use the sum-check protocol, we need to …

A Folding Scheme for Committed Relaxed R1CS

…