Fflonk

Link to the paper: https://eprint.iacr.org/2021/1167.pdf
Link to the slides: https://hecmas.github.io/talk/fflonk-for-the-polygon-zkevm/
Link to some comments and optimizations: https://hackmd.io/-2oVDtk4TJGVWFAYvUoY1g?view

Comparison to Other Protocols

Protocol CRS/SRS Size Prover Comp. Proof Length Verifier Comp.
Groth16
3m+w G1
3m+w G1,m G2
2 G1,1 G2
 G1,3 P
Plonk
3n G1,2 G2
11n G1
7 G1,7 F
16 G1,2 P
Fflonk
9n G1,2 G2
35n G1
4 G1,15 F
5 G1,2 P
PolyMath
3 G1,1 F
2 G1,1 G2,2 P,O(log) F
  • m
    denotes the number of multiplication gates.
  • w
    denotes the number of wires.
  • n
    denotes the number of gates.
  • denotes number of public inputs.
  • Gi
    denotes scalar multiplications in
    Gi
    .
  • P
    denotes pairings.

Full Description of the Protocol

Fix positive integer

A dividing
p1
(for the case of a sufficiently smooth prime field, setting
A=24
is enough). Let
T
be the set of divisors of
A
, i.e.,
T={tN0<tA,tA}
. Let also
\boldsymbolS
be the set of
A
'th powers in
F
; i.e.,
\boldsymbolS={xFzF s.t. zA=x}
.

Assume that

n is a power of two such that
24n
divides
p1
, and
HF
is a multiplicative subgroup of
F
of order
n
with generator
ω
. One can show[1] that the previous divisibility assumption implies that
ω
is a
24
-th power in
F
, which is necessary to ensure that
ω
has some particular roots.

We denote by

ω3 to a generator of order
3
, by
ω4
to a generator of order
4
and by
ω8
to a generator of order
8
. Finally, we denote by
Li(S)
the Lagrange polynomials for any set
SH
and by
Li
the Lagrange polynomials for
H
.

Common preprocessed input:

n,(x[1]1,...,x9n+17[1]1),(qLi,qRi,qOi,qMi,qCi)i=1n,σ,qL(X)=i=1nqLiLi(X),qR(X)=i=1nqRiLi(X),qO(X)=i=1nqOiLi(X),qM(X)=i=1nqMiLi(X),qC(X)=i=1nqCiLi(X),Sσ1(X)=i=1nσ(i)Li(X),Sσ2(X)=i=1nσ(n+i)Li(X),Sσ3(X)=i=1nσ(2n+i)Li(X),C0(X)= qL(X8)+XqR(X8)+X2qO(X8)+X3qM(X8)+X4qC(X8)+ X5Sσ1(X8)+X6Sσ2(X8)+X7Sσ3(X8).

Degrees:

qL,qR,qO,qM,qC,Sσ1,Sσ2,Sσ3F<n[X] and
C0F<8n[X]
.

Public input:
,(wi)i[]

Prover algorithm:

Prover input:
(wi)i[3(n2)]
.

We think the circuit as having at most

n2 "useful" gates, since the last two will be used to introduce random values to the wiring polynomials to achieve a zero-knowledge protocol.

Round 1:

Generate random blinding scalars

b1,,b9F.

Compute wire polynomials

a,b,cF<n[X]:
a(X):=i=1n2wiLi(X)+b1Ln1(X)+b2Ln(X),b(X):=i=1n2w(n2)+iLi(X)+b3Ln1(X)+b4Ln(X),c(X):=i=1n2w2(n2)+iLi(X)+b5Ln1(X)+b6Ln(X).

Compute public input polynomial

PIF<[X]:
PI(X):=i=1wiLi(X).

Compute quotient polynomial

T0F<2n2[X]:
T0(X):=(qL(X)a(X)+qR(X)b(X)+qO(X)c(X)+qM(X)a(X)b(X)+qC(X)+PI(X))1ZH(X).

Compute the FFT-style combination polynomial

C1F<8n8[X]:
C1(X):=a(X4)+Xb(X4)+X2c(X4)+X3T0(X4).

P computes and sends
[C1]1:=[C1(x)]1
.

Round 2:

Compute permutation challenges

β,γF :

β=H(transcript,0),γ=H(transcript,1)

Compute permutation polynomial

zF<n+3[X] :
z(X):=(b7X2+b8X+b9)ZH(X)+L1(X)+i=1n1(Li+1(X)j=1i(wj+βωj+γ)(wn+j+βk1ωj+γ)(w2n+j+βk2ωj+γ)(wj+βσ(j)+γ)(wn+j+βσ(n+j)+γ)(w2n+j+βσ(2n+j)+γ))

Compute quotient polynomials

T1F<n+2[X] and
T2F<3n[X]
:
T1(X):= [L1(X)(z(X)1)]1ZH(X),T2(X):= [(a(X)+βX+γ)(b(X)+βk1X+γ)(c(X)+βk2X+γ)z(X)(a(X)+βSσ1(X)+γ)(b(X)+βSσ2(X)+γ)(c(X)+βSσ3(X)+γ)z(Xω)]1ZH(X).

Compute the FFT-style combination polynomial

C2F<9n[X]:
C2(X):=z(X3)+XT1(X3)+X2T2(X3).

P computes and send
[C2]1:=[C2(x)]1
.

Now,

P must prove to
V
the following identities:
T0(X)ZH(X)= qL(X)a(X)+qR(X)b(X)+qO(X)c(X)+qM(X)a(X)b(X)+qC(X)+PI(X),T1(X)ZH(X)= L1(X)(z(X)1),T2(X)ZH(X)= (a(X)+βX+γ)(b(X)+βk1X+γ)(c(X)+βk2X+γ)z(X)(a(X)+βSσ1(X)+γ)(b(X)+βSσ2(X)+γ)(c(X)+βSσ3(X)+γ)z(Xω).

Round 3:

Compute the random

rF :
r=H(transcript)

Compute evaluation challenge

z=r24. Notice that
z\boldsymbolS
.

Compute opening evaluations:

qL¯=qL(z),qR¯=qR(z),qO¯=qO(z),qM¯=qM(z),qC¯=qC(z)S¯σ1=Sσ1(z),S¯σ2=Sσ2(z),S¯σ3=Sσ3(z),a¯=a(z),b¯=b(z),c¯=c(z),z¯=z(z),z¯ω=z(zω),T1¯ω=T1(zω),T2¯ω=T2(zω).
Notice that these points are enough for opening
a,b,c,T0
at
z
and
z,T1,T2
at
z
and
zω
.

P sends
(qL¯,qR¯,qO¯,qM¯,qC¯,S¯σ1,S¯σ2,S¯σ3,a¯,b¯,c¯,z¯,z¯ω,T1¯ω,T2¯ω)
to
V
.

Due to Lemma 5.1, P will equivalently:

  1. Open
    C0
    at
    S0=roots8(z)={h0,h0ω8,h0ω82,h0ω83,h0ω84,h0ω85,h0ω86,h0ω87}
    .
  2. Open
    C1
    at
    S1=roots4(z)={h1,h1ω4,h1ω42,h1ω43}
    .
  3. Open
    C2
    at
    S2=roots3(z)roots3(zω)={[h2,h2ω3,h2ω32],[h3,h3ω3,h3ω32]}
    .

Here,

h08=z,
h14=z
,
h23=z
and
h33=zω
, which are computed from
r
as follows:

  • h0=r3
    , since
    h08=r24=z
    .
  • h1=r6
    , since
    h14=r24=z
    .
  • h2=r8
    , since
    h23=r24=z
    .
  • h3=r8ω1/3
    , since
    h33=r24ω=zω
    .

To this end, P computes the sets

S0,S1,S2. He also computes the sets
Z0,Z1,Z2
using
Z0,Z1,Z2
defined as follows:
Z0={qL(z),qR(z),qO(z),qM(z),qC(z),Sσ1(z),Sσ2(z),Sσ3(z)},Z1={a(z),b(z),c(z),T0(z)},Z2={[z(z),T1(z),T2(z)],[z(zω),T1(zω),T2(zω)]},Z0={C0(h0),C0(h0ω8),C0(h0ω82),C0(h0ω83),C0(h0ω84),C0(h0ω85),C0(h0ω86),C0(h0ω87)},Z1={C1(h1),C1(h1ω4),C1(h1ω42),C1(h1ω43)},Z2={[C2(h2),C2(h2ω3),C2(h2ω32)],[C2(h3),C2(h3ω3),C2(h3ω32)]}.

Note that

Si and
Zi
can be also computed by
V
, for
i{0,1,2}
.

From now on, define

T=S0S1S2. We have
|T|=18
.

Round 4:

Compute a challenge

αF :
α=H(transcript)

P computes the polynomial
fF<9n+12[X]
:
f(X):= (X4z)(X3z)(X3zω)(C0(X)r0(X))+α(X8z)(X3z)(X3zω)(C1(X)r1(X)) ++α2(X8z)(X4z)(C2(X)r2(X)),

where:

  • The polynomial
    r0F<8[X]
    is such that
    r0(h0ω8i)=C0(h0ω8i)
    , for
    i[8]
    , that is:
    r0(X)=i=18C0(h0ω8i1)Li(S0)(X).
  • The polynomial
    r1F<4[X]
    is such that
    r1(h1ω4i)=C1(h1ω4i)
    , for
    i[4]
    , that is:
    r1(X)=i=14C1(h1ω4i1)Li(S1)(X).
  • The polynomial
    r2F<6[X]
    is such that
    r2(hjω3i)=C2(hjω3i)
    for
    i[3]
    ,
    j{2,3}
    , that is:
    r2(X)=i=13C2(h2ω3i1)Li(S2)(X)+i=46C2(h3ω3i1)Li(S2)(X).

P computes the polynomial
W(X):=f(X)/ZT(X)F<9n6[X]
and sends
[W]1:=[(f/ZT)(x)]1
.

Round 5:

Compute a random evaluation point

yF :
y=H(transcript)

P computes the polynomial

LF<9n[X]:
L(X):= (y4z)(y3z)(y3zω)(C0(X)r0(y))+α(y8z)(y3z)(y3zω)(C1(X)r1(y)) ++α2(y8z)(y4z)(C2(X)r2(y))ZT(y)f(X)ZT(X).

P computes the polynomial
W(X):=L(X)ZTS0(y)(Xy)F<9n1[X]
and sends
[W]1:=[W(x)]1
.

Return:

πSNARK=([C1]1,[C2]1,[W]1,[W]1,qL¯,qR¯,qO¯,qM¯,qC¯,S¯σ1,S¯σ2,S¯σ3,a¯,b¯,c¯,z¯,z¯ω,T1¯ω,T2¯ω)

Verifier algorithm:

Verifier preprocessed input:

[C0]1:=C0(x)[1]1,x[1]2

V((wi)i[],πSNARK) :

  1. Validate

    [C1]1,[C2]1,[W]1,[W]1G1.

  2. Validate

    qL¯,qR¯,qO¯,qM¯,qC¯,S¯σ1,S¯σ2,S¯σ3,a¯,b¯,c¯,z¯,z¯ω,T1¯ω,T2¯ωF.

  3. Validate

    wiF for
    i[]
    .

  4. Compute challenges

    β,γ,z,α,yF as in prover description, from the common inputs, public input, and the elements of
    πSNARK
    .

  5. Compute zero polynomial evaluation

    ZH(z)=zn1.

  6. Compute Lagrange polynomial evaluation

    L1(z)=ω(zn1)n(zω).

  7. Compute public input polynomial evaluation

    PI(z)=i=1wiLi(z).

  8. Computes

    r0(y)=i=18C0(h0ω8i1)Li(S0)(y). To this end,
    V
    needs to compute
    Z0
    , and he can do so from
    qL¯,qR¯,qO¯,qM¯,qC¯,S¯σ1,S¯σ2,S¯σ3
    .

  9. Computes

    r1(y)=i=14C1(h1ω4i1)Li(S1)(y). To this end,
    V
    needs to compute
    Z1
    , and he can do so from
    qL¯,qR¯,qO¯,qM¯,qC¯,a¯,b¯,c¯
    . In particular, to compute
    T0(z)
    , he proceeds as follows:
    T0(z)=(qL¯a¯+qR¯b¯+qO¯c¯+qM¯a¯b¯+qC¯+PI(z))1ZH(z)

  10. Computes

    r2(X)=i=13C2(h2ω3i1)Li(S2)(X)+i=46C2(h3ω3i1)Li(S2)(X). To this end,
    V
    needs to compute
    Z2
    , and he can do so from
    S¯σ1,S¯σ2,S¯σ3,a¯,b¯,c¯,z¯,z¯ω,T1¯ω,T2¯ω
    . In particular, to compute
    T1(z)
    and
    T2(z)
    , he proceeds as follows:
    T1(z)= [L1(z)(z¯1)]1ZH(z)T2(z)= [(a¯+βz+γ)(b¯+βk1z+γ)(c¯+βk2z+γ)z¯(a¯+βS¯σ1+γ)(b¯+βS¯σ2+γ)(c¯+βS¯σ3+γ)z¯ω]1ZH(z)

Helper for the Steps 8,9,10:

C0(h0ω8i)= qL¯+(h0ω8i)qR¯+(h0ω8i)2qO¯+(h0ω8i)3qM¯+(h0ω8i)4qC¯ +(h0ω8i)5S¯σ1+(h0ω8i)6S¯σ2+(h0ω8i)7S¯σ3C1(h1ω4i)= a¯+(h1ω4i)b¯+(h1ω4i)2c¯+(h1ω4i)3T0(z)C2(h2ω3i)= z¯+(h2ω3i)T1(z)+(h2ω3i)2T2(z)C2(h3ω3i)= z¯ω+(h3ω3i)T1¯ω+(h3ω3i)2T2¯ω

  1. Compute the polynomial commitment

    [F]1:
    [F]1:= [C0]1+α(y8z)(y3z)(y3zω)(y4z)(y3z)(y3zω)[C1]1+α2(y8z)(y4z)(y4z)(y3z)(y3zω)[C2]1

  2. Compute group-encoded batch evaluation

    [E]1:
    [E]1:= (r0(y)+α(y8z)(y3z)(y3zω)(y4z)(y3z)(y3zω)r1(y)+α2(y8z)(y4z)(y4z)(y3z)(y3zω)r2(y))[1]1

  3. Compute the full difference

    [J]1:
    [J]1:=(y8z)[W]1

  4. Validate all evaluations:

e([F]1[E]1[J]1+y[W]1,[1]2)=?e([W]1,[x]2)

Some Doubts and Open Questions

  • [Solved] Election of

    A: For our use case
    12
    is a good candidate since it is the least common multiple of
    3
    and
    4
    , but in the paper they claim that
    24
    is necessary. Why? I think that they say that because
    they are considering the commitment to the preprocessed polynomials (which are
    8
    are therefore the
    lcm(3,4,8)=24
    ). However, we have seen the verifier do not need to use the commitments to the preprocessed polynomials, and therefore are not necessary.

  • [Solved] Section 7 Assumptions: At the beginning of Section 7, why do you assume that

    24n divides
    p1
    ?
    I suppose that is to guarantee the existence of the different roots that have to be computed during the protocol. YES: it is to be able to compute roots of the generator
    ω
    .

  • [Solved] Preprocessed Polynomials

    qL,qR,qO,qM,qC,Sσ1,Sσ2,Sσ3: I do not know yet why the verifier need to use the commitments to the preprocessed polynomials, I need to figure it out (it only uses
    [x]2
    from the preprocessing). Why do they need to send to the verifier in Lemma 6.4? In case we have to, the prover computes
    g:=combinet0(f0)
    and sends the commitment to
    g
    to the verifier, which I do not see how this commitment would be used by the verifier itself.

  • [Solved] Computation of

    r1,r2: In round 4 of the proving algorithm, the prover computes the polynomials
    r1F<4[X]
    and
    r1F<6[X]
    by Lagrange interpolation. How does the verifier need to obtain them? He needs so to compute
    r1(y),r2(y)
    . If they are computed via Lagrange interpolation, the verifier complexity will be dominated by this computation (rather than elliptic curve operations).

    • We are exploring the prover sending
      r1(y)
      and
      r2(y)
      to the verifier, but we must check if this would break the soundness of the protocol. Moreover, this would increase the proof size by
      2
      field elements.
    • We are exploring a sound alternative: the prover sending to the verifier the inverse needed to compute the
      10
      Lagrange polynomials needed in the definition of
      r1(y),r2(y)
      . We are using a batching protocol for computing multiple inverses, so with one is enough.
tags: PlonK

  1. Hint: Take an element of order

    24n and check the relationship between this element and
    ω
    . ↩︎