Links

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}
  • 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)
First of all, let the number of gates be
nn
, the constraint system should have indicated a permutation
σ:[5n][5n]\sigma: [5n]\rightarrow [5n]
, which fulfills the following requirements.
  • Let
    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)
    . The concatenation is over the evaluation representation, not the coefficient representation.
  • The evaluation of
    w(X)w(X)
    remains unchanged after applying
    σ\sigma
    as a permutation over the evaluation of
    w(X)w(X)
    itself.
Now, given four different quadratic non-residues
(k1,k2,k3,k4)(k_1, k_2, k_3, k_4)
and a generator
ω\omega
with order
nn
, we define a mapping as follows.
σ0(i)={ωi1i{1,2,...,n}k1ωi1ni{n+1,n+2,...,2n}k2ωi12ni{2n+1,2n+2,...,3n}k3ωi13ni{3n+1,3n+2,...,4n}k4ωi14ni{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}
where
i=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}
. We split this map into five permutation polynomials, as follows.
  • Sσ1(X)S_{\sigma1}(X)
    's evaluation on
    1,ω,...,ωn11,\omega, ..., \omega^{n-1}
    equals
    σ(x)\sigma^*(x)
    's evaluation on
    1,2,...,n1, 2, ..., n
    .
  • Sσ2(X)S_{\sigma2}(X)
    's evaluation on
    1,ω,...,ωn11, \omega, ..., \omega^{n-1}
    equals
    σ(x)\sigma^*(x)
    's evaluation on
    n+1,n+2,...,2nn+1, n+2, ..., 2n
    .
  • Sσ3(X)S_{\sigma3}(X)
    's evaluation on
    1,ω,...,ωn11, \omega, ..., \omega^{n-1}
    equals
    σ(x)\sigma^*(x)
    's evaluation on
    2n+1,2n+2,...,3n2n+1, 2n+2, ..., 3n
    .
  • Sσ4(X)S_{\sigma4}(X)
    's evaluation on
    1,ω,...,ωn11, \omega, ..., \omega^{n-1}
    equals
    σ(x)\sigma^*(x)
    's evaluation on
    3n+1,3n+2,...,4n3n+1, 3n+2, ..., 4n
    .
  • Sσo(X)S_{\sigma o}(X)
    's evaluation on
    1,ω,...,ωn11, \omega, ..., \omega^{n-1}
    equals
    σ(x)\sigma^*(x)
    's evaluation on
    4n+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
HH
of size
nn
:
L1(X)=Xn1X1L_1(X) = \frac{X^n - 1}{X-1}
and store its coset FFT representation. This is done by first observing that
L1(X)L_1(X)
evaluates to
nn
on
X=1X = 1
and
00
otherwise in
HH
. 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
HH
of size
nn
:
ZH(X)=Xn1Z_H(X) = X^n - 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)
where
ω\omega
is the generator for a domain
HH
, into to a polynomial
f(X)f(X)
of degree
nn
is as follows:
f(X)=j=0n   yj   (0mnmj   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)
We can rewrite it as follows.
Now, precompute
cjc_j
for every
j{0,1,...,n}j\in\{0,1, ..., n\}
.
cj=0mnmj  1ωjωmc_j = \prod_{{\substack{0\leq m \leq n\\ m\neq j}}}~~\frac{1}{\omega^j - \omega^m}
This allows us to simplify
f(X)f(X)
as follows.
These constants
cjc_j
(j{0,1,...,n})(j\in\{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}
, 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)
, we add a random blinding polynomial over each of them. The prover samples
b1,b2,b3,...,b13Fb_1,\allowbreak b_2,\allowbreak b_3,\allowbreak ...,\allowbreak b_{13}\in \mathbb{F}
and computes blinded witness polynomials.
We commit each of the polynomial above and put the polynomial commitments
cmw1,cmw2,cmw3,cmw4,cmwoG1\mathsf{cm}_{w1},\allowbreak \mathsf{cm}_{w2},\allowbreak \mathsf{cm}_{w3},\allowbreak \mathsf{cm}_{w4},\allowbreak \mathsf{cm}_{wo}\in\mathbb{G}_1
into the sponge.
Step 4: build the sigma polynomial, for wiring
The prover squeezes out two challenges
β,γF\beta, \gamma\in\mathbb{F}
from the sponge. We now need to build the sigma polynomial. It helps for us to first compute:
Si:=(wi+βωi1+γ)(wn+i+βk1ωi1+γ)(w2n+i+βk2ωi1+γ)(w3n+i+βk3ωi1+γ)(w4n+i+βk4ωi1+γ)(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}}
We can then define the permutation polynomial
z(X)z(X)
with the following evaluations:
z(ωi1)={1i=1j=1i1Sii=2,3,...,nz(\omega^{i-1}) = \begin{cases} 1 & i = 1\\ \prod_{j=1}^{i-1} S_i & i = 2, 3, ..., n\\ \end{cases}
Step 5: commit the sigma polynomial, with hiding
The prover first samples
b14,b15,b16Fb_{14},\allowbreak b_{15},\allowbreak b_{16}\in\mathbb{F}
and apply them as blinding factors to the polynomial
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})
We commit this polynomial and put the polynomial commitment
cmzG1\mathsf{cm}_{z}\in\mathbb{G}_1
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)
,
t2(X)t_2(X)
,
t3(X)t_3(X)
,
t4(X)t_4(X)
, and
t5(X)t_5(X)
, where each polynomial has degree
n2n-2
. This is because
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+10
, and
5n+10=5(n+2)5n+10 = 5 \cdot (n+2)
.
Step 7: commit the split quotient polynomials, without hiding
We commit all these polynomials and put the commitments
cmt1\mathsf{cm}_{t1}
,
cmt2\mathsf{cm}_{t2}
,
cmt3\mathsf{cm}_{t3}
,
cmt4\mathsf{cm}_{t4}
, and
cmt5\mathsf{cm}_{t5}
into the sponge.
Step 8: open the polynomials at a random point
The prover squeezes a random challenge
ζF\zeta\in\mathbb{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}
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}
, 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)
,
w2~(X)\widetilde{w_2}(X)
,
w3~(X)\widetilde{w_3}(X)
,
w1~(Xω)\widetilde{w_1}(X\omega)
,
w2~(Xω)\widetilde{w_2}(X\omega)
,
w3~(Xω)\widetilde{w_3}(X\omega)
,
w4~(X)\widetilde{w_4}(X)
,
wo~(X)\widetilde{w_o}(X)
,
Sσ1(X){S_{\sigma1}}(X)
,
Sσ2(X){S_{\sigma2}}(X)
,
Sσ3(X){S_{\sigma3}}(X)
,
Sσ4(X){S_{\sigma4}}(X)
,
qprk3(X)q_{prk3}(X)
,
qprk4(X)q_{prk4}(X)
, and
z~(Xω)\widetilde{z}(X\omega)
with the evaluations over that random point. More specifically,
r(X)r(X)
reads as follows. Note that the locations of
ZH(X)Z_H(X)
are different now. The constant terms of
r(X)r(X)
are removed here.
where
and
and
Note that
Sσo(X)S_{\sigma 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)
and
and
Now we have the linearization polynomial. Although this polynomial is not linear, its degree is down from
5n\approx 5n
to
n\approx n
, and one can see that the polynomial collapses to a small one.
We note that the evaluation of
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)
is actually vanishing in
HH
. We first squeeze out a challenge
vFv\in\mathbb{F}
from the sponge. This is done by showing that one can find a polynomial
Wζ(X)W_\zeta(X)
such that:
and similarly, another polynomial
Wζω(X)W_{\zeta\omega}(X)
as follows.
We commit these two polynomials as
cmζ\mathsf{cm}_{\zeta}
and
cmζω\mathsf{cm}_{\zeta\omega}
.
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)

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
,
vv
, and
uu
.
  • 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}
    into the sponge and squeeze out
    β,γF\beta,\gamma\in\mathbb{F}
    from the sponge.
  • Put
    cmz\mathsf{cm}_{z}
    into the sponge and squeeze out
    αF\alpha\in\mathbb{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}
    into the sponge and squeeze out
    ζF\zeta\in\mathbb{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)
    into the sponge and squeeze out
    vFv\in\mathbb{F}
    from the sponge.
  • Put
    cmζ\mathsf{cm}_{\zeta}
    and
    cmζω\mathsf{cm}_{\zeta\omega}
    into the sponge and squeeze out
    uFu\in\mathbb{F}
    from the sponge.
Step 2: compute
r(ζ)r(\zeta)
Recall from the Step 9 of the prover,
r(ζ)r(\zeta)
can indeed be computed by the verifier.
Step 3: assemble
cmr\mathsf{cm}_r
The verifier can also assemble the commitment of
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}
be as follows. Note that the last one has a coefficient
uu
.
Step 5: compute linear combination of evaluations
Let the cumulative evaluation
ss
be as follows. Also, note the last one.
Step 6: pairing
Compute
L,RL, R
as follows.
L=e((cmζ+ucmζω),xH)L = e((\mathsf{cm}_{\zeta} + u\cdot \mathsf{cm}_{\zeta\omega}), x\cdot H)
where
HH
is the generator of
G2\mathbb{G}_2
in the SRS and
xx
is the secret in the SRS. The element
xHx\cdot H
here is part of the SRS.
R=e((ζcmζ+uζωcmζω+cmsG),H)R = e((\zeta\cdot\mathsf{cm}_{\zeta}+u\cdot\zeta\cdot\omega\cdot\mathsf{cm}_{\zeta\omega}+\mathsf{cm} - s\cdot G), H)
where
GG
is the generator of
G1\mathbb{G}_1
in the SRS.
Step 7: decision
The verifier accepts the proof if
L=RL = R
and rejects otherwise.