Zero knowledge proof

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 …

arkwork ark-poly

Modules

domain

This module contains different evaluation domains used for polynomial arithmetic, especially those friendly to fast Fourier …

Rust Coding notes

…

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 …

Sum-check Protocol

Multi-linear extension

Following the definition from Justin Thaler

Let \(\mathbb{F}\) be any finite field, and let \( f : \{0,1\}^v \rightarrow \mathbb{F} \) be any function mapping the \( v \)-dimensional Boolean hypercube to \(\mathbb{F}\). A \( v \)-variate polynomial …