Part I Survey about Practical Proof System
Part II How to construct a Marlin-lite SNARGs
Some useful gagets
-
(zero-test): prove that polynomial is identically zero on H
- (sumcheck): prover that $\sum_{a\in H}f(a)=b$
- (prod-check) : prove that $\prod_{a\in H}f(a)=c$
High-level Idea
Polynomial IOPs + Polynomial = SNARGs SNARKs 需要 Polynomial 是 extractable
Polynomial and Arithmetic
Definition
- Polynomial Commitment
- Arithmetic Circuit
R1CS-SAT is NPC
- R1CS constraints: three vector $a,b,c$ , exists a vector $z=(x,y,w,1)$ such that $<a,z>\times <b,z>=<c,z>$
- R1CS system: three matrix $A,B,C\in GF^{n\times n}$ , exists a vector $z\in GF^n$ such that $AZ \bigcirc BZ = CZ$
- $A =\begin{bmatrix}a_1 \ a_2 \ \dots \ a_n \end{bmatrix}^T$
Why R1CS
- good structure for IOP
- good compilation target, maybe?
IOPs: generalize IPs and PCPs
- Informall: in each round P gives V oracle access to its message
- focus on public-coin IOPs where P is limited to sending polynomials of bounded degree which V queries
使用polynomial commitment进行实例化
- P发送多项式承诺，并对V的挑战点进行open
- V检查证明
- 通过 Fiat-Shamir 进行non-interactive
polynomial-related sub-protocol
PP#1 Polynomial Equality IOP
Fact#1
two distinct polynomial of degree $\le$ d agree on $\le$ d points
- univarite case:
- For Q,R each of degree at most d, S= Q-R is a polynomial of degree $\le$ d By fundamental theorem of algebra, S has $\le$ d roots
- then Q and R agree on at most d points
- multivariate: Schwarz-Zippel lemma
Protocol#1
- P sends Q,R oracle to V
- V selects random number $\gamma \in GF$ and queries $Q(\gamma),R(\gamma)$
- if $Q(\gamma)=R(\gamma)$ then Accept, otherwise Reject
- Completeness
Soundness: error $\le \frac{d}{ GF }$ by Fact#1`
PP#2 Polynomial vanishing on a multiplicative subgroup H
let $H\subseteq GF, |H|=n,h$ a generator.
Define a vanishing polynomial on H
$Z_H(X) = \prod_{i=1}^n(X-h^i)$
Fact#2
A degree $\le$ d polynomial $g(x)$ vanishes on a set H iff there exists a polynomial R of degree $\le$ d- H such that $g(X) = Z_H(X)R(X)$
Protocol#2
- P sends g, R oracle to V
- V select $gamma$ , queries $g(\gamma), R(\gamma)$, evaluate $Z_H(\gamma)$
- $g(\gamma)=Z_H(\gamma)R(\gamma)$ then Accept
- Completeness by Fact#2
- Soundness: as PP#1 $g$ and $Z_HR$ degree at most d ,so soundness error as the same PP#1
PP#3 univarate sumcheck
Goal: For $H\subseteq GF$ a multiplication subgroup and polynomial Q of degree d, P convince V that $\sum_{\alpha \in H}Q(\alpha)=0$ (for simple, we call this equation as Eqn1)
Fact#3
Eqn1 holds iff there exists polynomial R of degree $\le$ d-n, and S of degree < n-1 such that $Q(X)=Z_H(X)R(X)+XS(X)$
Protocol#3
- P sends Q, R, S oracle to V
- V seleces $\gamma$, queries $Q(\gamma), R(\gamma), S(\gamma)$ and evaluate $Z_H(\gamma)$ 3.$Q(\gamma)=Z_H(\gamma)R(\gamma)+\gamma S(\gamma)$
- Completeness by Fact#3
- Soundness as PP#1
Marlin-Lite : An IOP for R1CS-SAT
Fix A,B,C $\in GF^{n\times n}$ for simplification Goal: prove $\exists Z\in GF^n$ such that $AZ \bigcirc BZ=CZ$
Idea#1
encode Z, AZ, BZ, CZ $\in GF^n$ as polynomial of degree n-1
As before, H $\subseteq GF$ is a multiplicative subgroup of $GF$ with |H|=n , fix generator h Defind $\hat{Z}(X)$ to be the (unique) polynomial degree $<$ n such that $\hat{Z}(h^i)=Z[i], i\in{1,\dots,n}$ likewist, $\hat{Z}_A(h^i)=(AZ)[i]$, $\hat{Z}_B(h^i)=(BZ)[i]$, $\hat{Z}_C(h^i)=(CZ)[i]$
Protocol
P sends V $\hat{Z}, \hat{Z}_A, \hat{Z_B}, \hat{Z_C}$ oracle Then $AZ \circ BZ = CZ \Longleftrightarrow \hat{Z_A}(h^i)\cdot \hat{Z_B}(h^i)=\hat{Z_C}(h^i)$ Then $AZ \circ BZ = CZ$ iff $\hat{Z_A}(X)\cdot \hat{Z_B}(X)-\hat{Z_C}(X)$ is a polynomial that vanish on H
Use PP#2
Protocol
- P sends V R oracle such that $\hat{Z_A}(X)\cdot \hat{Z_B}(X)-\hat{Z_C}(X)= R(X)Z_H(X)$
- V picks $\gamma$ checks that $\hat{Z_A}(\gamma)\cdot \hat{Z_B}(\gamma)-\hat{Z_C}(\gamma)= R(\gamma)Z_H(\gamma)$
Soundness error $\le \frac{2n}{ GF }$
But
How do we know that $\hat{Z_A}$ is consistent with the vector AZ?
Idea#2
Encode $A\in GF^{n\times n}$ as a bi-variate polynomial as before Unique $\hat A$ such that $\hat{A}(h^i,h^j)=A_{i,j}$ Then $\hat{Z_A}(X)=\sum_{i=1}^n \hat A(X,h^i)\hat Z(h^i)$ Eqn 2 and likewise for $\hat{Z_B},\hat B,\hat{Z_C}, \hat C$
How do we check this?
- To start, apply PP#1
-
V pick $\beta_A$ , sends to P, Now if Eqn3 $\hat{Z_A}(\beta_A)=\sum_{i=1}^n \hat A(\beta_A,h^i)\hat Z(h^i)$ hold then Eqn2 holds except with probability $\frac{n}{ F }$
-
-
To check Eqn3, first define $Q_A(X)=\hat{A}(\beta_A,X)\hat Z(X) - \frac{\hat{Z_A}(\beta_A)}{ H }$ - Now, Eqn3 holds iff $\sum_{i=1}^n Q_A(h^i)=0$ Use PP#3
Protocol
- P sends $R_A,S_A$ oracle
- V selects $\gamma_A$ evaluate $\hat A(\beta_A,\gamma_A), Z_H(\gamma_A)$, queries $\hat Z(\beta_A), \hat Z(\gamma_A), R_A(\gamma_A) , S_A(\gamma_A)$ and check that $\hat A(\beta_A,\gamma_A)\hat Z(\gamma_A) - \frac{Z_A(\beta_A)}{n}=R_A(\gamma_A)Z_H(\gamma_A) + \gamma_A S(\gamma_A)$
- repeat for $\hat Z_B, B, \hat Z_C ,C$
putting it all together
- P knows witness w s.t. $Z=(x,y,w,1)\in GF^{n}, AZ\circ BZ=CZ$ for R1CS matries A,B,C
- V knows A,B,C,x,y
- checking for R1CS-SAT
Protocol
Checking for R1CS-SAT with $\hat Z_A, \hat Z_B, \hat Z_C$
- P sends $\hat Z,\hat Z_A, \hat Z_B, \hat Z_C, R$ oracle
- V sample $\gamma$ checks Checking $\hat Z_A, \hat Z_B, \hat Z_C$ vs A,B,C,$\hat Z$
- V samples $\beta_A,\beta_B,\beta_C$
- P sends $R_A,S_A,R_B,S_B,R_C,S_C$
- V evaluate & checks
Some details we ignored
- P sends $\hat Z$ not $\hat W$ how can V ensure that $Z=(x,y,w,1)$
- Use PolyCommit Homomorphisim Tricks
- Does an H exist?
- pick GF carefully, pad n to a good size
- Evaluating $\hat A$ is exensive for V
- could be Outsource
- OR: structured computation makes evaluating $\hat A$ cheap
- OR: outsource evalutaion
- Idea: V commits to $\hat A$ then P evaluate, convinces V that claimed eval is correct
- another place use polynomial commitment