Plonk vs Groth16
In this post, we’ll give a quick rundown of two ZK-SNARK protocols, Groth16 and Plonk. We’ll pinpoint their key fetures and then put them side by side for a usability, performance, and security comparison.
Background on ZK-SNARK
Zero Knowledge Proof (ZKP) protocol consists of two parties, prover (P) who wants to convince another party, and verifier (V), that a statement x is true, using a secret witness w, without revealing w to the verifier or anyone else.
As an example, suppose I wish to assure someone that my bank account contains ample funds, but I’m unwilling to disclose the exact balance. In this scenario, the “my account balance exceeds 10 million dollars” serves as the public statement, while my actual balance functions as the private witness or secret input.
The following basic requirements are required for every ZKP protocol:
Completeness: honest P always will convince the honest V.
Soundness: dishonest P will not convince honest V
Zero-knowledge: dishonest V learns nothing more than the truth of the statement.
For integration into the blockchain, the ZKP protocol must satisfy the demands of having a short proof size and maintaining a reasonable time complexity for both the prover and verifier. Furthermore, given the scalability and performance challenges in blockchain technology, minimizing the interaction between the prover and verifier, especially avoiding multiple rounds, is highly preferable. Ideally, we are interested in a protocol where the prover generates a proof and transmits it to the verifier in a single round. Addressing the mentioned issues, resulted in a novel category of ZKP protocol, namely Knowledge Succinct Non-Interactive Argument of Knowledge (ZK-SNARK).
Eliminating multiple rounds of communication not only improves the protocol’s performance but also removes the requirement for both parties to be simultaneously available. To achieve this reduction in rounds, two approaches are commonly used: the Random Oracle Model and the Common Reference String (CRS). We will focus on the Common Reference String (CRS) approach, which has been employed by both the Groth16 and Plonk protocols. In theory, a trusted and honest third party is responsible for generating a random value “r” and using it to create CRS parameters, including the proving key “pk” and the verification key “vk.” It’s important to note that anyone with access to the randomness “r” can potentially generate fraudulent proof. To enhance the security of the ZK-SNARK protocol, it often leverages Multi-Party Computation, where all parties collaboratively compute a function without the need for a trusted third authority.
According to this paper, as long as there is at least one honest party the final parameters are secure.
Note: All secure parameters generated by the MPC ceremony should be removed by a secure process.
Let’s define the properties of SNARK as we did for the ZK protocol:
Succinct: the size of the proof is very small compared to the size of the statement or the witness.
Non-Interactive: no need for several interactions between P and V
The argument of Knowledge: dishonest P cannot convince honest V unless he knows some secret ‘witness’
Zero-knowledge: disclose no more than public.
To wrap up, ZK-SNARK consists of three phases: Conducting trusted setup by MPC protocol to generate proving and verification keys, generating proof by prover using prover key, public input, and secret input (witness), and verifying the proof by verifier.
CRS( randomness r , statement x) → (pk,vk)
Prover (pk, statement x, witness w)→ proof pi
Verifier( vk, pi, statement x) → accept or reject proof pi
Groth16
In 2016, Groth introduced a ZK-SNARK protocol, constructed based on a set of polynomial equations and asymmetric pairing cryptography.
Pairing-based SNARKs follow a simple paradigm where the prover computes a number of group elements using generic group operations
and the verifier checks the proof using a number of pairing product equations.
In the Groth16 scheme, any program F(x,w) = y with public input x and private witness w is converted into an arithmetic circuit C.
To prove the correctness of circuit C, we must verify the correctness of each gate. To do this, groth16 uses Quadratic Arithmetic Languages (QAP) to encode the circuit. The intuition behind encoding circuit C into QAP is that we define polynomial P(z)=Ui(z).Vi(z)-Wi(z) that encodes all multiplication gate equations where polynomials Ui, Vi, and Wi represent the left, right, and output of gate ith over (a1,…, am) which represent the circuit wire values.
Now we define a target polynomial T(z)=(z-r1)(z-r2)…(z-rn) where r1, …, rn are random variables, and n denotes the number of multiplication gates in our circuit. The basic idea is that the polynomial P(z) has been defined such that is divisible by T(z). It means there is a polynomial H(z) that P(z)=H(z)T(z). Therefore if there is a trusted party who evaluates these polynomials (U(z), V(z), W(z)) at a random point such s, putting them into CRS, then the prover can make a proof and the verifier is able to verify it.
Plonk
PlonK protocol addresses the one-time and non-unpalatable trusted setup issues by introducing universal and updatable SRS. In other words, several programs can share CRS, so long as their circuit size does not exceed the CRS threshold limit.
Likewise Groth16, in Plonk every program is converted into an arithmetic circuit of multiplicative and additive gates. However, the way that Plonk proves the correctness and consistency of the circuit is different. To prove the correctness of Plonk’s circuit, we need to prove the validity of each gate constraint, as well as the gate relationship. In addition to the verification of the polynomial equation, a mathematical method of permutation argument is adopted to verify the constraint relationship between the gates, that is, the copy constraint.
Efficiency Comparison
PlonK provides two variants, one with 9(n+a) combined degree of polynomials, and one with 11(n+a). The former has a larger proof size but reduced prover computation by about 10% compared to the latter one. Here, n stands for multiplication gates, and ‘a’ stands for addition gates in the circuit.
The performance and security comparison of Groth16 and two variants of Plonk are shown below.
Proof complexity Analysis
In common circuits, the ratio between additive gates and multiplicative gates is 2:1. Under this circuit assumption, this means PlonK is 2.25 times worse than Groth16 on proof time. With the capability for proof generation to be executed offline and off-chain, there is no necessity to be concerned about the time complexity of proof generation. However, proof size should be taken into consideration, affecting transaction size and consequently blockchain network throughput. Recall that each group element is a pair of x and y points in F.
Groth16 proof size: 2G1.(2 F) + 1 G2 ( counts 4F elements) = 6F
Plonk proof size: 9G1+ 7F = 16F
Assuming that each element takes 256 bits. According to Vitalik's post, Groth16 proof size would be around 200 bytes at an estimated level of 128 bits of security, whereas PLonk requires around 500–1000 bytes for the same security level.
Verification Complexity Analysis
Groth16’s verification algorithm is linear in its public input size, while Plonk requires a fixed number of exponential and pairing computations.
Note: needs benchmark implementation to estimate the gas cost
Conclusion
Theoretically, both Groth16 and Plonk rely on the assumption of mathematical problems and aren’t quantum-resistant. Nevertheless, Plonk requires weaker security assumptions rather than Groth16.
Regarding proof size, Plonk has a proof size of around 2x-5x that of Groth16, however, Plonk has a major advantage of universal and undatable SRS over Groth16. Consequently, the probability that the setup was compromised by collision is reduced, and no need to re-run the MPC ceremony for any changes in the program.