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.
GKR Part 2 -example
…
Author: shuangcrypto.com
Nova
Table of Contents
A Folding Scheme for Committed Relaxed R1CS
…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 …
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 \( g \) over \(\mathbb{F}\) is said to be an …
FFT Part 1: 8 Points NTT Butterfly
Table of Contents
These will be a series post about FFT and the math structure behind it. My goal are:
- Going back fundamentally to the polynomial ring and isomorphism.
- Analyse the fft implementations in Plonky3, Gnark-crypto, arkworks
However, …
Rust Basics
Table of Contents
Traits
- Definition: Traits are a way to define shared behavior in Rust. They define a set of methods that a type must implement in order to fulfill the
GKR –Part1: Arithmetization
Take example circuit in figure 1, following the Arithmetization described in post, a step by step description of GKR arithmetication of a concrete example.
Notations representing index of gates
\(q’\in \{0,1\}^{b_N}\): The index of one of the \(N\) identical copies of the base circuit \(C_0\) within \(C\).…
Upon understanding the attack on Nova — Part 1
To understand the attack on Nova, I figure out I need to understand the role of the hash function and the validation check of hash function in Nova, from the first paper where the “cycle of curves” is not introduced, the circuit is illustrated as
to …
Nova from scratch
After understanding of the folding scheme of relaxed R1CS, of which the key idea is you can “fold” two proofs to be one, with this ability of relaxed R1CS in mind, how can one build a recursive proof from scratch? in this note I will describe several attempts to build …
About Halo2 multipoints openning
explain the multipoints opening of Halo 2, I don’t think Halo2 book explain this part clearly, and perhaps, neither my note.
the key, is the homomorphism of the commitment scheme. and combine the evaluation at different points, and combine the different polynomial evaluated at the same points. Later if I …