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

Table of Contents

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$$

In order to use the sum-check protocol, we need to encode R1CS in a different way, as sum-check is about …

arkwork ark-poly

Modules

domain

This module contains different evaluation domains used for polynomial arithmetic, especially those friendly to fast Fourier transforms (FFTs).

GeneralEvaluationDomain

Contains the GeneralEvaluationDomain for FFT-friendly fields.

mixed_radix

Contains the MixedRadixEvaluationDomain for fields that do not …

Docker

What is Docker?

Docker is an open-source platform designed to automate the deployment, scaling, and management of applications. It uses container technology to package applications and their dependencies into lightweight, portable containers. These containers ensure that your application runs consistently regardless of where it’s deployed.

Why use docker?

Docker offers …

Brainfuck VM instance

This blog is the learning note for Brainfuck VM

…

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.

…

Sum-check design philosophy, why it works?

Using an example of 3 variants multilinear polynomial to explain the design idea of sum-check protocol.

A 3 variants multilinear polynomial can be generally represented as

$$g(X,Y,Z)=a_0+a_xX+a_yY+a_zZ+a_{xy}XY+a_{xz}XZ+a_{yz}YZ+a_{xyz}XYZ$$

Understanding Sum-check in reverse order

In the final round of sumcheck protocol, assuming the verifier gets a one degree polynomial

$$h(z)=g(r_1,r_2,\ldots,z )=\alpha_n z …