TurboPlonk

Introduction
Findora's "triple masking" payment uses an optimized variant of TurboPlonk. The following equations summarize the structure.
We now describe the indexer, the prover, and the verifier.
Indexer
The indexer in TurboPlonk computes the commitments and openings for indexer polynomials, which consist of the following:
The fourteen selector polynomials:
q1(X),q2(X),q3(X),q4(X),qo(X),qm1(X),qm2(X),qc(X),qecc(X),qb(X),qprk1(X),qprk2(X),qprk3(X),qprk4(X)\begin{array}{c} q_1(X), q_2(X), q_3(X), q_4(X), q_o(X), q_{m1}(X), q_{m2}(X), q_c(X), q_{ecc}(X), q_{b}(X),\\ q_{prk1}(X), q_{prk2}(X), q_{prk3}(X), q_{prk4}(X) \end{array}q1​(X),q2​(X),q3​(X),q4​(X),qo​(X),qm1​(X),qm2​(X),qc​(X),qecc​(X),qb​(X),qprk1​(X),qprk2​(X),qprk3​(X),qprk4​(X)​
The five permutation polynomials:
Sσ1(X),Sσ2(X),Sσ3(X),Sσ4(X),Sσo(X)S_{\sigma1}(X), S_{\sigma2}(X), S_{\sigma3}(X), S_{\sigma4}(X), S_{\sigma o}(X)Sσ1​(X),Sσ2​(X),Sσ3​(X),Sσ4​(X),Sσo​(X)
First of all, let the number of gates be nnn
, the constraint system should have indicated a permutation σ:[5n]→[5n]\sigma: [5n]\rightarrow [5n]σ:[5n]→[5n]
, which fulfills the following requirements.
Let w(X)w(X)w(X)
 be the concatenated witness polynomial of w1(X),w2(X),w3(X),w4(X),wo(X)w_1(X), w_2(X), w_3(X), w_4(X), w_o(X)w1​(X),w2​(X),w3​(X),w4​(X),wo​(X)
. The concatenation is over the evaluation representation, not the coefficient representation.
The evaluation of w(X)w(X)w(X)
 remains unchanged after applying σ\sigmaσ
 as a permutation over the evaluation of w(X)w(X)w(X)
 itself.
Now, given four different quadratic non-residues (k1,k2,k3,k4)(k_1, k_2, k_3, k_4)(k1​,k2​,k3​,k4​)
 and a generator ω\omegaω
 with order nnn
, we define a mapping as follows.
σ0(i)={ωi−1i∈{1,2,...,n}k1⋅ωi−1−ni∈{n+1,n+2,...,2n}k2⋅ωi−1−2ni∈{2n+1,2n+2,...,3n}k3⋅ωi−1−3ni∈{3n+1,3n+2,...,4n}k4⋅ωi−1−4ni∈{4n+1,4n+2,...,5n}\sigma_0 \left(i\right) = \begin{cases} \omega^{i-1} & i\in \{1,2,...,n\}\\ k_1\cdot \omega^{i -1 - n} & i \in\{n+1, n+2, ..., 2n\}\\ k_2\cdot \omega^{i -1 - 2n} & i \in\{2n+1, 2n+2, ..., 3n\}\\ k_3\cdot \omega^{i -1- 3n} & i \in\{3n+1, 3n+2, ..., 4n\}\\ k_4\cdot \omega^{i -1- 4n} & i \in\{4n+1, 4n+2, ..., 5n\} \end{cases}σ0​(i)=⎩⎨⎧​ωi−1k1​⋅ωi−1−nk2​⋅ωi−1−2nk3​⋅ωi−1−3nk4​⋅ωi−1−4n​i∈{1,2,...,n}i∈{n+1,n+2,...,2n}i∈{2n+1,2n+2,...,3n}i∈{3n+1,3n+2,...,4n}i∈{4n+1,4n+2,...,5n}​
where i=1,2,...,ni = 1, 2, ..., ni=1,2,...,n
. And we apply this mapping to each element in σ\sigmaσ
, obtaining a map σ∗(x):[5n]→F\sigma^*(x): [5n] \rightarrow\mathbb{F}σ∗(x):[5n]→F
. We split this map into five permutation polynomials, as follows.
​Sσ1(X)S_{\sigma1}(X)Sσ1​(X)
's evaluation on 1,ω,...,ωn−11,\omega, ..., \omega^{n-1}1,ω,...,ωn−1
 equals σ∗(x)\sigma^*(x)σ∗(x)
's evaluation on 1,2,...,n1, 2, ..., n1,2,...,n
.
​Sσ2(X)S_{\sigma2}(X)Sσ2​(X)
's evaluation on 1,ω,...,ωn−11, \omega, ..., \omega^{n-1}1,ω,...,ωn−1
 equals σ∗(x)\sigma^*(x)σ∗(x)
's evaluation on n+1,n+2,...,2nn+1, n+2, ..., 2nn+1,n+2,...,2n
.
​Sσ3(X)S_{\sigma3}(X)Sσ3​(X)
's evaluation on 1,ω,...,ωn−11, \omega, ..., \omega^{n-1}1,ω,...,ωn−1
 equals σ∗(x)\sigma^*(x)σ∗(x)
's evaluation on 2n+1,2n+2,...,3n2n+1, 2n+2, ..., 3n2n+1,2n+2,...,3n
.
​Sσ4(X)S_{\sigma4}(X)Sσ4​(X)
's evaluation on 1,ω,...,ωn−11, \omega, ..., \omega^{n-1}1,ω,...,ωn−1
 equals σ∗(x)\sigma^*(x)σ∗(x)
's evaluation on 3n+1,3n+2,...,4n3n+1, 3n+2, ..., 4n3n+1,3n+2,...,4n
.
​Sσo(X)S_{\sigma o}(X)Sσo​(X)
's evaluation on 1,ω,...,ωn−11, \omega, ..., \omega^{n-1}1,ω,...,ωn−1
 equals σ∗(x)\sigma^*(x)σ∗(x)
's evaluation on 4n+1,4n+2,...,5n4n+1, 4n+2, ..., 5n4n+1,4n+2,...,5n
.
Step 1: commit all polynomials
We first commit all these indexer polynomials. The commitments are included in the verifier parameters. We then perform some precomputation: we prepare a representation of these polynomials that are easy to be use later for proving, by doing a coset FFT over them. The prepared polynomials are included in the prover parameters.
Step 2: precompute the two helper polynomials
Compute the following polynomial defined on a domain HHH
 of size nnn
:
L1(X)=Xn−1X−1L_1(X) = \frac{X^n - 1}{X-1}L1​(X)=X−1Xn−1​
and store its coset FFT representation. This is done by first observing that L1(X)L_1(X)L1​(X)
 evaluates to nnn
 on X=1X = 1X=1
 and 000
 otherwise in HHH
. We can perform an inverse FFT to convert it back to the coefficient representation (which indeed looks nontrivial). Then, we perform a coset FFT, which gives us the prepared version of this polynomial.
Another polynomial we precompute is the vanishing polynomial of domain HHH
 of size nnn
:
ZH(X)=Xn−1Z_H(X) = X^n - 1ZH​(X)=Xn−1
and we want to store its coset FFT representation. This is done by a coset FFT over the coefficient representation above. The representations for the two helper polynomials are included in the prover parameters.
Step 3: compute the Lagrange interpolation constants
Recall that the Lagrange interpolation from (1,y0),(ω,y1),...,(ωn,yn)(1, y_0), (\omega, y_1), ..., (\omega^n, y_n)(1,y0​),(ω,y1​),...,(ωn,yn​)
 where ω\omegaω
 is the generator for a domain HHH
, into to a polynomial f(X)f(X)f(X)
 of degree nnn
 is as follows:
f(X)=∑j=0n   yj   (∏0≤m≤nm≠j   X−ωmωj−ωm)f(X) = \sum_{j=0}^n~~~y_j~~~\left(\prod_{{\substack{0\leq m \leq n\\ m\neq j}}}~~~\frac{X - \omega^m}{\omega^j - \omega^m}\right)f(X)=j=0∑n​   yj​   ⎝⎛​0≤m≤nm=j​∏​   ωj−ωmX−ωm​⎠⎞​
We can rewrite it as follows.
Now, precompute cjc_jcj​
 for every j∈{0,1,...,n}j\in\{0,1, ..., n\}j∈{0,1,...,n}
.
cj=∏0≤m≤nm≠j  1ωj−ωmc_j = \prod_{{\substack{0\leq m \leq n\\ m\neq j}}}~~\frac{1}{\omega^j - \omega^m}cj​=0≤m≤nm=j​∏​  ωj−ωm1​
This allows us to simplify f(X)f(X)f(X)
 as follows.
These constants cjc_jcj​
 (j∈{0,1,...,n})(j\in\{0,1, ..., n\})(j∈{0,1,...,n})
 are included in the verifier parameters. We conclude the description of the indexer.
Prover
The prover in TurboPlonk uses the prover parameters from the indexer and a complete constraint system with all the gate values and copy check information ready. It follows the following steps.
Step 1: assemble public inputs
The prover parameters have indicated which witness value indeed belongs to public inputs. The prover finds those witness values and stores them in a vector of length ninn_{in}nin​
, which is the number of field elements in public inputs. This is to enable us to calculate the state of the verifier.
Step 2: instantiate the verifier
For the purpose of the Fiat-Shamir transform, we create a cryptographic sponge, which will absorb the verifier's state as well as the messages that the verifier would receive from the prover in an interactive proof protocol.
After we create the sponge, we put the following two things into the sponge: (1) verifier parameters and (2) public inputs.
Step 3: commit witness polynomials with hiding
Given the witness polynomials w1(X),w2(X),w3(X),w4(X),wo(X)w_1(X),\allowbreak w_2(X),\allowbreak w_3(X),\allowbreak w_4(X),\allowbreak w_o(X)w1​(X),w2​(X),w3​(X),w4​(X),wo​(X)
, we add a random blinding polynomial over each of them. The prover samples b1,b2,b3,...,b13∈Fb_1,\allowbreak b_2,\allowbreak b_3,\allowbreak ...,\allowbreak b_{13}\in \mathbb{F}b1​,b2​,b3​,...,b13​∈F
 and computes blinded witness polynomials.
We commit each of the polynomial above and put the polynomial commitments cmw1,cmw2,cmw3,cmw4,cmwo∈G1\mathsf{cm}_{w1},\allowbreak \mathsf{cm}_{w2},\allowbreak \mathsf{cm}_{w3},\allowbreak \mathsf{cm}_{w4},\allowbreak \mathsf{cm}_{wo}\in\mathbb{G}_1cmw1​,cmw2​,cmw3​,cmw4​,cmwo​∈G1​
 into the sponge.
Step 4: build the sigma polynomial, for wiring
The prover squeezes out two challenges β,γ∈F\beta, \gamma\in\mathbb{F}β,γ∈F
 from the sponge. We now need to build the sigma polynomial. It helps for us to first compute:
Si:=(wi+β⋅ωi−1+γ)⋅(wn+i+β⋅k1⋅ωi−1+γ)⋅(w2n+i+β⋅k2⋅ωi−1+γ)⋅(w3n+i+β⋅k3⋅ωi−1+γ)⋅(w4n+i+β⋅k4⋅ωi−1+γ)(wi+σ∗(i)⋅β+γ)⋅(wn+i+σ∗(n+i)⋅β+γ)⋅(w2n+i+σ∗(2n+i)⋅β+γ)⋅(w3n+i+σ∗(3n+i)⋅β+γ)⋅(w4n+i+σ∗(4n+i)⋅β+γ)S_i := \frac{\begin{array}{c}(w_i+\beta\cdot\omega^{i-1} + \gamma)\cdot (w_{n+i} + \beta\cdot k_1\cdot\omega^{i-1} + \gamma)\cdot (w_{2n+i} + \beta\cdot k_2\cdot\omega^{i-1} + \gamma)\\\cdot (w_{3n+i} + \beta\cdot k_3\cdot \omega^{i-1} + \gamma)\cdot (w_{4n+i} + \beta\cdot k_4\cdot \omega^{i-1} + \gamma)\end{array}}{\begin{array}{c} (w_i + \sigma^*(i)\cdot\beta + \gamma)\cdot (w_{n+i} + \sigma^*(n+i)\cdot\beta + \gamma)\cdot (w_{2n+i} + \sigma^*(2n+i)\cdot\beta + \gamma)\\ \cdot (w_{3n+i} + \sigma^*(3n+i)\cdot \beta + \gamma)\cdot (w_{4n+i} + \sigma^*(4n+i)\cdot \beta + \gamma) \end{array}}Si​:=(wi​+σ∗(i)⋅β+γ)⋅(wn+i​+σ∗(n+i)⋅β+γ)⋅(w2n+i​+σ∗(2n+i)⋅β+γ)⋅(w3n+i​+σ∗(3n+i)⋅β+γ)⋅(w4n+i​+σ∗(4n+i)⋅β+γ)​(wi​+β⋅ωi−1+γ)⋅(wn+i​+β⋅k1​⋅ωi−1+γ)⋅(w2n+i​+β⋅k2​⋅ωi−1+γ)⋅(w3n+i​+β⋅k3​⋅ωi−1+γ)⋅(w4n+i​+β⋅k4​⋅ωi−1+γ)​​
We can then define the permutation polynomial z(X)z(X)z(X)
 with the following evaluations:
z(ωi−1)={1i=1∏j=1i−1Sii=2,3,...,nz(\omega^{i-1}) = \begin{cases} 1 & i = 1\\ \prod_{j=1}^{i-1} S_i & i = 2, 3, ..., n\\ \end{cases}z(ωi−1)={1∏j=1i−1​Si​​i=1i=2,3,...,n​
Step 5: commit the sigma polynomial, with hiding
The prover first samples b14,b15,b16∈Fb_{14},\allowbreak b_{15},\allowbreak b_{16}\in\mathbb{F}b14​,b15​,b16​∈F
 and apply them as blinding factors to the polynomial z(X)z(X)z(X)
.
z~(X)=z(X)+ZH(X)⋅(b14X2+b15X+b16)\widetilde{z}(X) = z(X) + Z_H(X)\cdot (b_{14} X^2 + b_{15} X + b_{16})z(X)=z(X)+ZH​(X)⋅(b14​X2+b15​X+b16​)
We commit this polynomial and put the polynomial commitment cmz∈G1\mathsf{cm}_{z}\in\mathbb{G}_1cmz​∈G1​
 into the sponge.
Step 6: compute the quotient polynomial
The prover squeezes out a challenge α\alphaα
 from the sponge. This is used to construct the following polynomial.
where
and
and
and
and
and
Then, in the coefficient representations, we split the polynomial into five parts: t1(X)t_1(X)t1​(X)
, t2(X)t_2(X)t2​(X)
, t3(X)t_3(X)t3​(X)
, t4(X)t_4(X)t4​(X)
, and t5(X)t_5(X)t5​(X)
, where each polynomial has degree n−2n-2n−2
. This is because t(X)t(X)t(X)
 is expected to have degree 3⋅(n+2)+2⋅(n+1)+(n+2)−n=5n+103\cdot (n+2) + 2\cdot(n+1) + (n+2) - n = 5n+103⋅(n+2)+2⋅(n+1)+(n+2)−n=5n+10
, and 5n+10=5⋅(n+2)5n+10 = 5 \cdot (n+2)5n+10=5⋅(n+2)
.
Step 7: commit the split quotient polynomials, without hiding
We commit all these polynomials and put the commitments cmt1\mathsf{cm}_{t1}cmt1​
, cmt2\mathsf{cm}_{t2}cmt2​
, cmt3\mathsf{cm}_{t3}cmt3​
, cmt4\mathsf{cm}_{t4}cmt4​
, and cmt5\mathsf{cm}_{t5}cmt5​
 into the sponge.
Step 8: open the polynomials at a random point
The prover squeezes a random challenge ζ∈F\zeta\in\mathbb{F}ζ∈F
 and compute the following opening evaluations:
w1~(ζ),w2~(ζ),w3~(ζ),w4~(ζ),wo~(ζ),Sσ1(ζ),Sσ2(ζ),Sσ3(ζ),Sσ4(ζ),qprk3(ζ),qprk4(ζ),w1~(ζω),w2~(ζω),w3~(ζω),z~(ζω)\begin{array}{c} \widetilde{w_1}(\zeta), \widetilde{w_2}(\zeta), \widetilde{w_3}(\zeta), \widetilde{w_4}(\zeta), \widetilde{w_o}(\zeta), S_{\sigma 1}(\zeta), S_{\sigma 2}(\zeta), S_{\sigma 3}(\zeta), S_{\sigma 4}(\zeta),\\[0.5em] q_{prk3}(\zeta), q_{prk4}(\zeta), \widetilde{w_1}(\zeta\omega), \widetilde{w_2}(\zeta\omega), \widetilde{w_3}(\zeta\omega), \widetilde{z}(\zeta \omega) \end{array}w1​​(ζ),w2​​(ζ),w3​​(ζ),w4​​(ζ),wo​​(ζ),Sσ1​(ζ),Sσ2​(ζ),Sσ3​(ζ),Sσ4​(ζ),qprk3​(ζ),qprk4​(ζ),w1​​(ζω),w2​​(ζω),w3​​(ζω),z(ζω)​
And we remind the readers that some evaluations are over ζω\zeta\omegaζω
 instead of ζ\zetaζ
. This is common in entry product arguments. The prover puts these, which are elements in F\mathbb{F}F
, into the sponge.
Step 9: compute the linearization polynomial
The linearization polynomial is, at a high level, to replace w1~(X)\widetilde{w_1}(X)w1​​(X)
, w2~(X)\widetilde{w_2}(X)w2​​(X)
, w3~(X)\widetilde{w_3}(X)w3​​(X)
, w1~(Xω)\widetilde{w_1}(X\omega)w1​​(Xω)
, w2~(Xω)\widetilde{w_2}(X\omega)w2​​(Xω)
, w3~(Xω)\widetilde{w_3}(X\omega)w3​​(Xω)
, w4~(X)\widetilde{w_4}(X)w4​​(X)
, wo~(X)\widetilde{w_o}(X)wo​​(X)
, Sσ1(X){S_{\sigma1}}(X)Sσ1​(X)
, Sσ2(X){S_{\sigma2}}(X)Sσ2​(X)
, Sσ3(X){S_{\sigma3}}(X)Sσ3​(X)
, Sσ4(X){S_{\sigma4}}(X)Sσ4​(X)
, qprk3(X)q_{prk3}(X)qprk3​(X)
, qprk4(X)q_{prk4}(X)qprk4​(X)
, and z~(Xω)\widetilde{z}(X\omega)z(Xω)
 with the evaluations over that random point. More specifically, r(X)r(X)r(X)
 reads as follows. Note that the locations of ZH(X)Z_H(X)ZH​(X)
 are different now. The constant terms of r(X)r(X)r(X)
 are removed here.
where
and
and
Note that Sσo(X)S_{\sigma o}(X)Sσo​(X)
 is not being replaced by its evaluation, and
r3(X)=z~(X)⋅L1(ζ)r_{3}(X) = \widetilde{z}(X) \cdot L_1(\zeta)r3​(X)=z(X)⋅L1​(ζ)
and
and
Now we have the linearization polynomial. Although this polynomial is not linear, its degree is down from ≈5n\approx 5n≈5n
 to ≈n\approx n≈n
, and one can see that the polynomial collapses to a small one.
We note that the evaluation of r(X)r(X)r(X)
 at point ζ\zetaζ
 is as follows. The prover does not need to include this number in the proof because it can be computed by the verifier.
Step 10: compute the opening proof polynomials
Now we want to prove that the previous openings are correct, as well as r(X)r(X)r(X)
 is actually vanishing in HHH
. We first squeeze out a challenge v∈Fv\in\mathbb{F}v∈F
 from the sponge. This is done by showing that one can find a polynomial Wζ(X)W_\zeta(X)Wζ​(X)
 such that:
and similarly, another polynomial Wζω(X)W_{\zeta\omega}(X)Wζω​(X)
 as follows.
We commit these two polynomials as cmζ\mathsf{cm}_{\zeta}cmζ​
 and cmζω\mathsf{cm}_{\zeta\omega}cmζω​
.
Step 11: output the full proof
After the Fiat-Shamir transform, the final proof reads as follows.
(cmw1,cmw2,cmw3,cmw4,cmwo,cmz,cmt1,cmt2,cmt3,cmt4,cmt5,w1~(ζ),w2~(ζ),w3~(ζ),w4~(ζ),wo~(ζ),Sσ1(ζ),Sσ2(ζ),Sσ3(ζ),Sσ4(ζ),qprk3(ζ),qprk4(ζ),w1~(ζω),w2~(ζω),w3~(ζω),z~(ζω),cmζ,cmζω)\left(\begin{array}{c} \mathsf{cm}_{w1}, \mathsf{cm}_{w2}, \mathsf{cm}_{w3}, \mathsf{cm}_{w4}, \mathsf{cm}_{wo},\\ \mathsf{cm}_{z}, \\ \mathsf{cm}_{t1}, \mathsf{cm}_{t2}, \mathsf{cm}_{t3}, \mathsf{cm}_{t4}, \mathsf{cm}_{t5},\\ \widetilde{w_1}(\zeta), \widetilde{w_2}(\zeta), \widetilde{w_3}(\zeta), \widetilde{w_4}(\zeta), \widetilde{w_o}(\zeta),\\S_{\sigma 1}(\zeta), S_{\sigma 2}(\zeta), S_{\sigma 3}(\zeta), S_{\sigma 4}(\zeta),\\ q_{prk3}(\zeta),q_{prk4}(\zeta), \widetilde{w_1}(\zeta\omega), \widetilde{w_2}(\zeta\omega), \widetilde{w_3}(\zeta\omega),\\ \widetilde{z}(\zeta\omega),\\ \mathsf{cm}_{\zeta}, \mathsf{cm}_{\zeta\omega} \end{array}\right)⎝⎛​cmw1​,cmw2​,cmw3​,cmw4​,cmwo​,cmz​,cmt1​,cmt2​,cmt3​,cmt4​,cmt5​,w1​​(ζ),w2​​(ζ),w3​​(ζ),w4​​(ζ),wo​​(ζ),Sσ1​(ζ),Sσ2​(ζ),Sσ3​(ζ),Sσ4​(ζ),qprk3​(ζ),qprk4​(ζ),w1​​(ζω),w2​​(ζω),w3​​(ζω),z(ζω),cmζ​,cmζω​​⎠⎞​
Verifier
The verifier reads the full proof above and proceeds as follows.
Step 1: compute all the challenges
For convenience, the verifier first computes all the random challenges in this protocol execution: β\betaβ
, γ\gammaγ
, α\alphaα
, ζ\zetaζ
, vvv
, and uuu
.
Initialize the same cryptographic sponge.
Put cmw1,cmw2,cmw3,cmw4,cmwo\mathsf{cm}_{w1}, \mathsf{cm}_{w2}, \mathsf{cm}_{w3}, \mathsf{cm}_{w4}, \mathsf{cm}_{wo}cmw1​,cmw2​,cmw3​,cmw4​,cmwo​
 into the sponge and squeeze out β,γ∈F\beta,\gamma\in\mathbb{F}β,γ∈F
 from the sponge.
Put cmz\mathsf{cm}_{z}cmz​
 into the sponge and squeeze out α∈F\alpha\in\mathbb{F}α∈F
 from the sponge.
Put cmt1,cmt2,cmt3,cmt4,cmt5\mathsf{cm}_{t1}, \mathsf{cm}_{t2}, \mathsf{cm}_{t3}, \mathsf{cm}_{t4}, \mathsf{cm}_{t5}cmt1​,cmt2​,cmt3​,cmt4​,cmt5​
 into the sponge and squeeze out ζ∈F\zeta\in\mathbb{F}ζ∈F
 from the sponge.
Put w1~(ζ),w2~(ζ),w3~(ζ),w4~(ζ),wo~(ζ),Sσ1(ζ),Sσ2(ζ),Sσ3(ζ),Sσ4(ζ),qprk3(ζ),qprk4(ζ),w1~(ζω),w2~(ζω),w3~(ζω),z~(ζω)\widetilde{w_1}(\zeta), \widetilde{w_2}(\zeta), \widetilde{w_3}(\zeta), \widetilde{w_4}(\zeta), \widetilde{w_o}(\zeta), S_{\sigma 1}(\zeta), S_{\sigma 2}(\zeta), S_{\sigma 3}(\zeta), S_{\sigma 4}(\zeta), q_{prk3}(\zeta), q_{prk4}(\zeta),\allowbreak \widetilde{w_1}(\zeta\omega),\allowbreak \widetilde{w_2}(\zeta\omega),\allowbreak \widetilde{w_3}(\zeta\omega), \widetilde{z}(\zeta \omega)w1​​(ζ),w2​​(ζ),w3​​(ζ),w4​​(ζ),wo​​(ζ),Sσ1​(ζ),Sσ2​(ζ),Sσ3​(ζ),Sσ4​(ζ),qprk3​(ζ),qprk4​(ζ),w1​​(ζω),w2​​(ζω),w3​​(ζω),z(ζω)
 into the sponge and squeeze out v∈Fv\in\mathbb{F}v∈F
 from the sponge.
Put cmζ\mathsf{cm}_{\zeta}cmζ​
 and cmζω\mathsf{cm}_{\zeta\omega}cmζω​
 into the sponge and squeeze out u∈Fu\in\mathbb{F}u∈F
 from the sponge.
Step 2: compute r(ζ)r(\zeta)r(ζ)
​
Recall from the Step 9 of the prover, r(ζ)r(\zeta)r(ζ)
 can indeed be computed by the verifier.
Step 3: assemble cmr\mathsf{cm}_rcmr​
​
The verifier can also assemble the commitment of r(X)r(X)r(X)
 from available commitments, as follows.
where
and
and
and
Step 4: compute linear combination of commitments
Let the cumulative commitment cm\mathsf{cm}cm
 be as follows. Note that the last one has a coefficient uuu
.
Step 5: compute linear combination of evaluations
Let the cumulative evaluation sss
 be as follows. Also, note the last one.
Step 6: pairing
Compute L,RL, RL,R
 as follows.
L=e((cmζ+u⋅cmζω),x⋅H)L = e((\mathsf{cm}_{\zeta} + u\cdot \mathsf{cm}_{\zeta\omega}), x\cdot H)L=e((cmζ​+u⋅cmζω​),x⋅H)
where HHH
 is the generator of G2\mathbb{G}_2G2​
 in the SRS and xxx
 is the secret in the SRS. The element x⋅Hx\cdot Hx⋅H
 here is part of the SRS.
R=e((ζ⋅cmζ+u⋅ζ⋅ω⋅cmζω+cm−s⋅G),H)R = e((\zeta\cdot\mathsf{cm}_{\zeta}+u\cdot\zeta\cdot\omega\cdot\mathsf{cm}_{\zeta\omega}+\mathsf{cm} - s\cdot G), H)R=e((ζ⋅cmζ​+u⋅ζ⋅ω⋅cmζω​+cm−s⋅G),H)
where GGG
 is the generator of G1\mathbb{G}_1G1​
 in the SRS.
Step 7: decision
The verifier accepts the proof if L=RL = RL=R
 and rejects otherwise.
Last modified 2mo ago