Category: Zero Knowledge Proof

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 …

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 …

About the repetition in GKR

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) )]$$…

Libra GKR Prover

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)\) …

Spartan- part 1

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 …

GKR Part 2 -example

Using the following example to go through GKR protocol

this blogs follows the example in Spartan 预备知识：GKR with ZK Argument

zero knowledge version of GKR, Hyrax approach.

…