cover_image

fflonk: a FFT inspired verifier efficient version of PlonK

Kurt Pan XPTY
2021年09月15日 19:16
  • -a Fast-Fourier inspired verifier efficient version of
  • by Ariel Gabizon and Zachary J. Williamson
  • https://eprint.iacr.org/2021/1167.pdf

The New Polynomial Commitment Scheme

Define operators and to group together and decompose polynomials "FFT style":

  • - given return
  • - given return the unique such that

Define the vector

[BDFG20] Commitment Scheme

The commitment procedure is identical to [KZG10]. Its crucial advantage is that the verifier group operations do not grow with the number of evaluation points.

Choose a positive constant dividing . Let Let be the set of 'th powers in . We present the following -polynomial commitment scheme.

  1. - choose uniform Output .
  2. for and Let Output
  3. :
    1. For computes Let
    2. and compute where , and where
    3. and engage in and outputs if and only if she does so in the execution of .

Polynomial Protocols

To apply the new commitment scheme to the proving system[GWC19].

Fix positive integers , a subset of positive integers, a vector , and a subset A -polynomial protocol over is an round protocol between a prover a verifier and ideal party that proceeds as follows.

  1. The protocol definition includes a set of preprocessed polynomials
  2. Each of the rounds of interaction has the following form:
    • At round sends to a message .
    • The verifier responds with public random coins.
  3. Let consist of the set of preprocessed polynomials together with the polynomials sent by . At the end of the protocol, may ask if certain polynomial identities holds between the polynomials in . More specifically, each identity is of the form where
    1. are elements of
    2. are polynomials with the property that whenever , we also have .
    3. for every choice of made by when following the protocol correctly.
  4. After receiving the answers from regarding the identities, outputs if all identities hold, and outputs otherwise.

Polynomial protocol for constraint system satisfiability

  1. Let be 's assignment consistent with the public input  . computes the three polynomials , where for
  1. and compute the "Public input polynomial"
  1. computes the quotient polynomial showing satisfy the arithmetic constraint; i.e.

sends 

  1.  and run an extended permutation check protocol as in [GWC19], using the permutation between and itself, this exactly checks whether copy-satisfies . More precisely,

    (a) chooses random and sends them to .

    (b) Let , and . That is, for

(c) Define by

(d) computes , such that and for

(e) computes the quotients showing that "starts from one" and that accumulates the values of . Namely,

(f) sends to .

(g) checks the following three identities

i.

ii.

iii.

and outputs iff all checks hold.

Reference

  • [KZG10]:  A. Kate, G. M. Zaverucha, and I. Goldberg. Constant-size commitments to polynomials and their applications.
  • [GWC19]:  A. Gabizon, Z. J. Williamson, and O. Ciobotaru. PLONK: permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge.
  • [BDFG20]: D. Boneh, J. Drake, B. Fisch, and A. Gabizon. Efficient polynomial commitment schemes for multiple points and polynomials.