Groth16
Presentation: https://www.youtube.com/watch?v=1upt6GOdYXk
Introduction
Groth16 is a zk-SNARK construction introduced in 2016 by Jens Groth, characterized by its compact proof size of just 3 group elements and exceptionally fast verification speed. It is widely used in frameworks like circom and RISC0.
Background
Quardratic Arithmetic Protocol (QAP)
For a system where the number of instance variables is , the number of witness variables is (thus, the total number of variables is ), and the number of constraints is , R1CS can be represented as follows:

This R1CS system can be reduced to a Quadratic Arithmetic Program (QAP):
where
: A polynomial such that where and .
: A polynomial such that where and .
: A polynomial such that where and .
: .
: A variable, where .
Here, .
Then we can define as follows:
Where .
In BKSV20 and GR22 it is shown that for Groth16 there exists potential malleability on the public input unless certain linear independence requirements are met. An easy way to meet these requirements is to add additional constraints for all public inputs. This is done implicitly by the Arkworks and SnarkJS implementations. (it's taken from https://xn--2-umb.com/22/groth16/.) See also https://geometry.xyz/notebook/groth16-malleability!
Protocol Explanation
Key Generation
Sample the toxic wastes . They are called toxic wastes which can be used to create fake proofs which will be accepted by the verifier. So they should be discarded right after key generation, or generated through MPC(or Trusted Setup).
Create a verifying key .
Create a proving key .
Computing h(X)
Create :
where are lagrange basis polynomials.
Evaluate on a coset domain:
where . The reason why we compute on a coset domain is avoiding division by zero since .
Evaluate :
Compute :
where are lagrange basis polynomials on a coset domain.
To compute , the costs are:
3 IFFT operations of length
3 FFT on a coset domain operation of length
1 evaluations of length
IFFT on a coset domain operations of length (This step can be removed by using Jordi's Trick.)
NOTE: (I)FFT operations on a coset domain implicitly include additional linear operations proportional to the domain size. The (I)FFT operations on a coset domain can be removed by using Jordi's Trick.
Proof Generation
Sample and generate the proof .
where are the coefficients of the .
To generate a proof , the costs are:
For computing :
1 MSM operation of length in
For computing :
1 MSM operation of length in
For computing :
1 MSM operation of length in
1 MSM operation of length in
1 MSM operation of length in (for )
Jordi's Trick
To compute of the proof efficiently, consider the following setup:
Where be a -th root of unity and an -th root of unity. These satisfy:
and are lagrange basis polynomials.
Properties of
can be divided into evaluations at even powers and odd powers.
Evaluation at even powers of : For , evaluates to zero at even powers of :
This implies:
Evaluation at odd powers of : For , given , we can compute the evaluations at odd powers of :
Where .
This implies:
Thus, the evaluations of at odd powers of can be efficiently computed by combining FFT results of .
Optimizing in the Proving Key
To eliminate the IFFT of , the term in the proving key (pk) is replaced with :
Then computing is performed as follows:
Create :
where are lagrange basis polynomials.
Create :
where is -th root of unity.
Evaluate :
where is -th root of unity.
Evaluate :
To compute , the costs are:
3 IFFT operations of length
3 FFT operation of length
1 evaluations of length
Proof Verification
The verifier checks the proof using the pairing equation: (Note that the right hand side will be precomputed.)
Proof. Considering only the exponent part, the equation simplifies as follows:
To verify a proof, the costs are:
1 MSM operation of length in
3 pairing operations
Batch Proof Verification
Assume there are proofs. We denote each proof for as follows:
Using the random linear combination trick with , you can verify proofs in a batch:
Proof.
From the single verification case, for , we know that the following equation holds:
Multiplying both sides by gives:
Summing over to , we obtain:
These are precisely the exponent parts in the batch verification equation.
To verify proofs, the costs are:
MSM operations of length in
scalar multiplications in
field multiplications
pairing operations
If each proof were verified individually, the process would require expensive pairing operations. However, batch verification significantly reduces this cost.
Malleability
Malleability is a property of cryptographic systems or protocols where an attacker can modify a valid message or ciphertext into another valid message or ciphertext without needing to know the original plaintext. The modified message still appears valid under the cryptographic scheme, which can lead to vulnerabilities and unintended consequences.
Attack 1
An attacker selects and modifies the proof as follows:
Even though the modified proof differs from the original, it remains valid because .
Attack 2
An attacker selects and modifies as folows:
Proof. The validity of the modified proof can be shown as:
Combining Attacks
By combining the two attacks above, a fresh proof for the same statement can be constructed, which is indistinguishable from the existing proofs. (The attacks above contains the same part of the proof.) The modified proof is computed as follows (see GM17, BKSV20 and the Tachyon implementation):
Proof. The modified proof remains valid:
Conclusion
Groth16 is a highly efficient zk-SNARK protocol that combines succinctness, fast verification, and strong zero-knowledge guarantees. Its compact proof size of just 3 group elements and (almost) constant-time verification make it a preferred choice for various privacy-preserving applications or proof compressions(STARK to SNARK).
References
Last updated