2021-05-20

Thanks to Zac Williamson and Kev for explaining ideas that helped form this document. Thanks to Han for spotting a mistake in "Approach 2" of the MiMC custom gate that could lead to breaking soundness.

Introduction

PLONK has flexible arithmetization, and can quite easily express complex polynomial gates. "Basic PLONK", as defined in the paper, defines only fan-in 2 arithmetic gates. The purpose of this document is to show what are custom gates and how they affect the performance of a PLONK proof.

At a high level, PLONK defines the gates as part of a "quotient polynomial" $t(x)$ - if this polynomial is zero at the points that represents gates, then the constraint system is satisfied.

The arithmetic gate contribution to the quotient polynomial is defined as:

$a(X)b(X)q_M(X) + a(X)q_L(X) + b(X)q_R(X) + c(X)q_O(X) + PI(X) + q_C(X)$

For example, a multiplication gate that calculates $xy = z$ is going to have:

• $a(g^i) = x$
• $b(g^i) = y$
• $c(g^i) = z$
• $q_M(g^i) = 1$
• $q_O(g^i) = -1$
• $q_L(g^i), q_R(g^i), PI(g^i), q_C(g^i) = 0$

Basic PLONK

"Basic PLONK" has the following performance characteristics:

1. Proof size of $9\mathbb{G}1$ + $7\mathbb{F}$ arising from: a. Commitments to the wires polynomials $a(x)$, $b(x)$, $c(x)$ b. Commitment to the permutation polynomial $z(x)$ c. Commitments to 3 $n-$degree polynomials, components of the $3n-$degree quotient polynomial $t(x)$ d. Commitment to the opening polynomial $W_z(x)$, ensuring sure the evaluations of $t(x), r(x), a(x), b(x), c(x), S{\sigma_1}, S{\sigma_2}$ are correct at $z$ e. Commitment to the opening polynomial $W_{zw}(x)$, ensuring the evaluation of $z(x)$ is correct at $zw$
2. Proving complexity of: a. $9n$ $\mathbb{G}_1$ exponentiations resulting from computing commitments of polynomials of degree $n$: 3 from 1a, 1 from 1b, 3 from 1c, 1 from 1d, 1 from 1e b. Roughly $54n$ field operations from FFTs:
   • 8 of degree $4n$ from:
     • The contribution of the permutation argument - 3 for $\sigma_{0,1,2}$
     • 1 for $z$
     • 3 for the $a, b, c$ wires polynomials
     • 1 inverse transform for the quotient polynomial itself at degree $4n$
   • 6 of degree $2n$ from:
     • The contribution of the arithmetic gate - $q_M, q_L, q_R, q_O$ and $q_C$
     • 1 inverse transform for the quotient polynomial itself at degree $2n$
   • 12 of degree $n$ from:
     • 12 inverse transforms on all the polynomials we need to perform FFT on
3. Verification complexity of (discounting field operations and hashes):
   • 18 exponentiations in $\mathbb{G}_1$:
     • 6 from the linearization polynomial opening:
       • 5 from the arithmetic gate polynomials $q_M, q_L, q_R, q_O$ and $q_C$
       • 1 from the $z$ polynomial
     • 9 from the quotient polynomial opening:
       • 3 from the $n-$degree parts of $t$
       • 3 from the wire polynomials $a, b$ and $c$
       • 2 from the permutation polynomials $s_{\sigma1}, s_{\sigma2}$
     • 1 from the evaluation commitment - containing all the evaluations of the opened polynomials
     • 1 from the polynomial commitment argument for evaluation at $z$ - the random opening point
     • 1 from the polynomial commitment argument for evaluation at $zw$ - the random opening point + 1