Skip to main content

Fast Fourier Inspired Folding for Sangria

· 4 min read

This is a crosspost with zkresear.ch/t/fast-fourier-inspired-sangria.

Introduction​

Sangria is the folding protocol for Plonk prover. In the original model, the prover works iteratively and merges a new execution trace with an execution trace accumulator.

Here we will show, how to build an optimized folding process, requiring only 2 or 1 scalar multiplications per folding on the verifier side.

Original Protocol​

Accumulated instance and witness:

Un′:=(Xn′,un′,W‾n′,E‾n′),U'_n := (\mathbf{X}'_n, u'_n, \overline{W}'_n, \overline{E}'_n), Wn′:=(Wn′,en′,rWn′,rEn′)W'_n := (\mathbf{W}'_n, \mathbf{e}'_n, r'_{Wn}, r'_{En})

Iteration instance and witness:

Un:=(Xn,un,W‾n,E‾n),U_n := (\mathbf{X}_n, u_n, \overline{W}_n, \overline{E}_n), Wn:=(Wn,e,rWn,rEn)W_n := (\mathbf{W}_n, \mathbf{e}, r_{Wn}, r_{En})

Where W‾=Com(ppW,W,rW), E‾=Com(ppW,e,rE)\overline{W}=\text{Com}(\text{pp}_W, \mathbf{W}, r_W),\ \overline{E} = \text{Com}(\text{pp}_W, \mathbf{e}, r_E).

We use a relaxed Plonk gate equation: C(a,b,c,u,e)=abqM+qCu2+(aqL+cqO+bqR)u+eC(\mathbf{a}, {\mathbf{b}}, {\mathbf{c}}, u, {\mathbf{e}})={\mathbf{a}} {\mathbf{b}} {\mathbf{q_M}} + {\mathbf{q_C}} {u}^{2} + {\left({\mathbf{a}} {\mathbf{q_L}} + {\mathbf{c}} {\mathbf{q_O}} + {\mathbf{b}} {\mathbf{q_R}}\right)} {u} + {\mathbf{e}}

  1. Prover send to Verifier T‾n=Com(ppW,tn,rTn)\overline{T}_n = \text{Com}(\text{pp}_W, \mathbf{t}_n, r_{Tn}),

Introduction​

Sangria is the folding protocol for Plonk prover. In the original model, the prover works iteratively and merges a new execution trace with an execution trace accumulator.

Here we will show, how to build an optimized folding process, requiring only 2 or 1 scalar multiplications per folding on the verifier side.

Original Protocol​

Accumulated instance and witness:

Un′:=(Xn′,un′,W‾n′,E‾n′),U'_n := (\mathbf{X}'_n, u'_n, \overline{W}'_n, \overline{E}'_n), Wn′:=(Wn′,en′,rWn′,rEn′)W'_n := (\mathbf{W}'_n, \mathbf{e}'_n, r'_{Wn}, r'_{En})

Iteration instance and witness:

Un:=(Xn,un,W‾n,E‾n),U_n := (\mathbf{X}_n, u_n, \overline{W}_n, \overline{E}_n), Wn:=(Wn,e,rWn,rEn)W_n := (\mathbf{W}_n, \mathbf{e}, r_{Wn}, r_{En})

Where W‾=Com(ppW,W,rW), E‾=Com(ppW,e,rE)\overline{W}=\text{Com}(\text{pp}_W, \mathbf{W}, r_W),\ \overline{E} = \text{Com}(\text{pp}_W, \mathbf{e}, r_E).

We use a relaxed Plonk gate equation: C(a,b,c,u,e)=abqM+qCu2+(aqL+cqO+bqR)u+eC(\mathbf{a}, {\mathbf{b}}, {\mathbf{c}}, u, {\mathbf{e}})={\mathbf{a}} {\mathbf{b}} {\mathbf{q_M}} + {\mathbf{q_C}} {u}^{2} + {\left({\mathbf{a}} {\mathbf{q_L}} + {\mathbf{c}} {\mathbf{q_O}} + {\mathbf{b}} {\mathbf{q_R}}\right)} {u} + {\mathbf{e}}

  1. Prover send to Verifier T‾n=Com(ppW,tn,rTn)\overline{T}_n = \text{Com}(\text{pp}_W, \mathbf{t}_n, r_{Tn}), where tn=2 qCun′un+(anbn′+an′bn)qM+(anqL+cnqO+bnqR)un′+(an′qL+cn′qO+bn′qR)unt_n=2 \, {\mathbf{q_C}} {u'_n} {u_n} + {\left({\mathbf{a}_n} {\mathbf{b}'_n} + {\mathbf{a}'_n} {\mathbf{b}_n}\right)} {\mathbf{q_M}} + {\left({\mathbf{a}_n} {\mathbf{q_L}} + {\mathbf{c}_n} {\mathbf{q_O}} + {\mathbf{b}_n} {\mathbf{q_R}}\right)} {u'_n} + {\left({\mathbf{a}'_n} {\mathbf{q_L}} + {\mathbf{c}'_n} {\mathbf{q_O}} + {\mathbf{b}'_n} {\mathbf{q_R}}\right)} {u_n} where tn=2 qCun′un+(anbn′+an′bn)qM+(anqL+cnqO+bnqR)un′+(an′qL+cn′qO+bn′qR)unt_n=2 \, {\mathbf{q_C}} {u'_n} {u_n} + {\left({\mathbf{a}_n} {\mathbf{b}'_n} + {\mathbf{a}'_n} {\mathbf{b}_n}\right)} {\mathbf{q_M}} + {\left({\mathbf{a}_n} {\mathbf{q_L}} + {\mathbf{c}_n} {\mathbf{q_O}} + {\mathbf{b}_n} {\mathbf{q_R}}\right)} {u'_n} +\\ {\left({\mathbf{a}'_n} {\mathbf{q_L}} + {\mathbf{c}'_n} {\mathbf{q_O}} + {\mathbf{b}'_n} {\mathbf{q_R}}\right)} {u_n}
  2. Verifier sends to prover random rr
  3. Prover and Verifier output the folded instance Un+1′=(Xn+1′,un+1′,W‾n+1′,E‾n+1′),U'_{n+1}=(\mathbf{X}'_{n+1}, u'_{n+1}, \overline{W}'_{n+1}, \overline{E}'_{n+1}), where Xn+1′=Xn′+rXn,\mathbf{X}'_{n+1} = \mathbf{X}'_n + r \mathbf{X}_n, un+1′=un′+run,u'_{n+1} = u'_n + r u_n, W‾n+1′=W‾n′+rW‾n,\overline{W}'_{n+1} = \overline{W}'_n + r \overline{W}_n, E‾n+1′=E‾n′+r2E‾n−rT‾n.\overline{E}'_{n+1} = \overline{E}'_n + r^2 \overline{E}_n - r \overline{T}_n.
  4. Prover output the folded witness Wn+1′=(Wn+1′,en+1′,rW n+1′,rE n+1′),W'_{n+1} = (\mathbf{W}'_{n+1}, \mathbf{e}'_{n+1}, r'_{W\ n+1}, r'_{E\ n+1}), where Wn+1′=Wn′+rWn,\mathbf{W}'_{n+1} = \mathbf{W}'_n + r \mathbf{W}_n, en+1′=en′+r2en−rtn,\mathbf{e}'_{n+1} = \mathbf{e}'_n + r^2 \mathbf{e}_n - r \mathbf{t}_n, rW n+1′=rW n′+rrWn,r'_{W\ n+1} = r'_{W\ n} + r r_{Wn}, rE n+1′=rE n′+r2rEn−rrTn.r'_{E\ n+1} = r'_{E\ n} + r^2 r_{En} - r r_{Tn}.

We can check, that C(an+1′,bn+1′,cn+1′,un+1′,en+1′)=C(an′,bn′,cn′,un′,en′)+r2C(an,bn,cn,un,en)C(\mathbf{a}'_{n+1}, \mathbf{b}'_{n+1}, \mathbf{c}'_{n+1}, u'_{n+1}, \mathbf{e}'_{n+1}) = C(\mathbf{a}'_n, \mathbf{b}'_n, \mathbf{c}'_n, u'_n, \mathbf{e}'_n) + r^2 C(\mathbf{a}_n, \mathbf{b}_n, \mathbf{c}_n, u_n, \mathbf{e}_n).

Fast-Fourier Inspired Approach​

We see, that most operations on the verifier side are linear. So, we can use the approach from GW21.

Let's define the following functions:

fL(X)=a(X4)+Xb(X4)+X2c(X4)+X3e(X4),f_L(X) = a(X^4) + X b(X^4) + X^2 c(X^4) + X^3 e(X^4), fR(X)=a(X4)+Xb(X4)+X2c(X4)−X3t(X4),f_R(X) = a(X^4) + X b(X^4) + X^2 c(X^4) - X^3 t(X^4), ϵR(X)=X3e(X4)\epsilon_R(X) = X^3 e(X^4)

where a,b,c,e,ta, b, c, e, t are polynomials corresponding to vectors a,b,c,e,t\mathbf{a}, \mathbf{b}, \mathbf{c}, \mathbf{e}, \mathbf{t}. It is important, that the field has a multiplicative subgroup of order 44. If we need more columns, we can use the same approach with bigger subgroups.

Then we can rewrite the witness part of the folding procedure as follows:

  1. Prover computes t\mathbf{t} and sends to verifier [fR n][f_{R\ n}], [ϵR n][\epsilon_{R\ n}]
  2. Verifier sends to prover random rr
  3. Prover and Verifier output the folded instance

[fL n+1′]=[fL n′]+r[fR n]+r2[ϵR n][f'_{L\ n+1}] = [f'_{L\ n}] + r [f_{R\ n}] + r^2 [\epsilon_{R\ n}]

  1. Prover output the folded witness

fL n+1′=fL n′+rfR n+r2ϵR n,f'_{L\ n+1} = f'_{L\ n} + r f_{R\ n} + r^2 \epsilon_{R\ n},

For final check we should make openings of fLf_L at points x,x−1,−x,−x−1x, x \sqrt{-1}, -x, -x \sqrt{-1}, where xx is random, and recover a(x4),b(x4),c(x4),e(x4)a(x^4), b(x^4), c(x^4), e(x^4).

It is important to note that the folding process complexity is still linear. We don't need an explicit representation of f(x) in the prover-side folding process:

[fL(x)]=[∑i=0n−1(ai+bixλi(x4)+cix2λi(x4)+eix3λi(x4))]=∑i=0n−1([ai]+bi[xλi(x4)]+ci[x2λi(x4)]+ei[x3λi(x4)]).[f_L(x)] = [\sum_{i=0}^{n-1} (a_i + b_i x \lambda_i(x^4) + c_i x^2 \lambda_i(x^4) + e_i x^3 \lambda_i(x^4))] =\\ \sum_{i=0}^{n-1} ([a_i] + b_i [x \lambda_i(x^4)] + c_i [x^2 \lambda_i(x^4)] + e_i [x^3 \lambda_i(x^4)]).

The proposed method provides only 2 scalar multiplications per folding instead of 5 or more. And it requires 4 times bigger CRS.

UPD: In the case of IVC, when the 2nd instance is original Plonk, ϵR(X)=0\epsilon_R(X)=0 and we need only one scalar multiplication per folding.