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
Protocol | CRS/SRS Size | Prover Comp. | Proof Length | Verifier Comp. |
---|---|---|---|---|
Groth16 | ||||
Plonk | ||||
Fflonk | ||||
PolyMath |
Fix positive integer dividing (for the case of a sufficiently smooth prime field, setting is enough). Let be the set of divisors of , i.e., . Let also be the set of 'th powers in ; i.e., .
Assume that is a power of two such that divides , and is a multiplicative subgroup of of order with generator . One can show[1] that the previous divisibility assumption implies that is a -th power in , which is necessary to ensure that has some particular roots.
We denote by to a generator of order , by to a generator of order and by to a generator of order . Finally, we denote by the Lagrange polynomials for any set and by the Lagrange polynomials for .
Degrees: and .
We think the circuit as having at most "useful" gates, since the last two will be used to introduce random values to the wiring polynomials to achieve a zero-knowledge protocol.
Generate random blinding scalars .
Compute wire polynomials :
Compute public input polynomial :
Compute quotient polynomial :
Compute the FFT-style combination polynomial :
computes and sends .
Compute permutation challenges :
Compute permutation polynomial :
Compute quotient polynomials and :
Compute the FFT-style combination polynomial :
computes and send .
Now, must prove to the following identities:
Compute the random :
Compute evaluation challenge . Notice that .
Compute opening evaluations:
Notice that these points are enough for opening at and at and .
sends to .
Due to Lemma 5.1, P will equivalently:
Here, , , and , which are computed from as follows:
To this end, P computes the sets . He also computes the sets using defined as follows:
Note that and can be also computed by , for .
From now on, define . We have .
Compute a challenge :
computes the polynomial :
where:
computes the polynomial and sends .
Compute a random evaluation point :
P computes the polynomial :
computes the polynomial and sends .
Return:
:
Validate .
Validate .
Validate for .
Compute challenges as in prover description, from the common inputs, public input, and the elements of .
Compute zero polynomial evaluation .
Compute Lagrange polynomial evaluation .
Compute public input polynomial evaluation .
Computes . To this end, needs to compute , and he can do so from .
Computes . To this end, needs to compute , and he can do so from . In particular, to compute , he proceeds as follows:
Computes . To this end, needs to compute , and he can do so from . In particular, to compute and , he proceeds as follows:
Helper for the Steps 8,9,10:
Compute the polynomial commitment :
Compute group-encoded batch evaluation :
Compute the full difference :
Validate all evaluations:
[Solved] Election of : For our use case is a good candidate since it is the least common multiple of and , but in the paper they claim that is necessary. Why? I think that they say that because they are considering the commitment to the preprocessed polynomials (which are are therefore the ). 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 divides ? 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 : 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 from the preprocessing). Why do they need to send to the verifier in Lemma 6.4? In case we have to, the prover computes and sends the commitment to to the verifier, which I do not see how this commitment would be used by the verifier itself.
[Solved] Computation of : In round 4 of the proving algorithm, the prover computes the polynomials and by Lagrange interpolation. How does the verifier need to obtain them? He needs so to compute . If they are computed via Lagrange interpolation, the verifier complexity will be dominated by this computation (rather than elliptic curve operations).
PlonK
Hint: Take an element of order and check the relationship between this element and . ↩︎