This article is the fourth part of the “Introduction to Zero-Knowledge Proofs” series. In the previous parts, we introduced the background and concepts of zero-knowledge proofs, as well as some core mathematical tools. In this article, we will introduce the Pinocchio protocol and Groth16.
Pinocchio Protocol
After introducing the core mathematical tools above, a nearly practical non-interactive zero-knowledge proof protocol is emerging. This complete process is the basis for the current series of zkSnark algorithms, called the Pinocchio protocol [7], or formally known as [PGHR13].
The theoretical foundation of this Pinocchio protocol paper is based on [GGPR13][8], which is mainly focused on engineering practice and is the first implementation of a nearly usable zero-knowledge proof library in C language.
Introduction of Random Offset
In practical implementation, the difference from the above process is that in order to prevent the possibility of brute force cracking (for example, when the number and value range of coefficients are limited in special cases), the prover adds a random offset δ during the construction of p(x): Let the original polynomial be:
After adding the δ offset, it becomes:
Therefore,
Let
So, for the new verification pairing:
It can still be verified, but it does not reveal more knowledge about the coefficients, making it resistant to brute force cracking.
Protocol Workflow
Setup
- Choose a generator G and encryption pairing e.
- Take a function f(u) = y with a total of n variables, where m variables are inputs/outputs. Flatten it into a digital circuit and rewrite each gate as a Rank-1 Constraint System (R1CS) form. Then, transform it into a polynomial form of degree d (related to the number of gates) and size n+1, called a Quadratic Arithmetic Program (QAP).
- Choose random numbers
- Set up
- And generate pairing operands.
- Set up proving key:
- Set up verification key:
- Discard random numbers.
Proving
- Substitute input values u and calculate all intermediate variable values using f(u).
- Assign all unencrypted variable polynomials to:
- Perform the same calculation on R(x) and O(x).
- Choose random numbers δ_l, δ_r, and δ_o.
- Calculate h(x) = (L(x)R(x) – O(x)) / t(x) + δ_r L(x) + δ_l R(x) + δ_l δ_r t(x) – δ_o.
- Assign the prover’s variable values to the encrypted mutable polynomial L_p(s) and perform the zero-knowledge δ-transformation:
- Then, calculate
and
Assign α pairs of transformations to them.
- Calculate in the same way for
and
- Assign values to variable consistency polynomial.
- Calculate and submit the proof.
Verification
- Parse the provided proof into:
- Assign input/output values to the verifier’s encrypted polynomial:
using
and
perform the same calculation.
- Check the mutable polynomial constraints:
- Perform the same check on
and
- Check variable consistency:
- Check validity calculation.
Groth16
The Pinocchio protocol described above forms the foundation for “zkSNARK” (Non-Interactive Zero-Knowledge Succinct Argument of Knowledge), and all subsequent zkSNARK algorithms are improvements based on the Pinocchio protocol under different conditions and environments. The most widely used algorithms currently include Groth16 (Filecoin, Tornado.cash, Old Zcash), Plonk (zkSync, Mina), and Halo (New Zcash). Among them, the most widely used algorithm is Groth16.
The Groth16 algorithm is an improvement of the Pinocchio protocol proposed by Jens Groth in his paper [9]. Not only does it improve existing algorithms, but it also discusses the problem of proof size for pairing-based non-interactive zero-knowledge proofs. With its compact proof size and efficient verification efficiency, Groth16 has fully met the conditions for engineering applications and has been widely used in early anonymous coin projects such as ZCash. It is the most classic zero-knowledge proof algorithm and the earliest algorithm applied in the field of blockchain.
The basic framework of the algorithm is still the Pinocchio protocol, divided into setup, proving, and verification. The biggest upgrade to the Pinocchio protocol is in the setup and verification parts. By enhancing some security assumptions of bilinear mapping pairs, the size of the Proving Key is reduced. The number of elements in K1 is reduced from seven to two, thereby reducing the amount of data and computation required for verification from 12 bilinear pairs to three.
This article introduces the two most basic practical protocols in the zkSnark family of zero-knowledge proof protocols – Pinocchio and Groth16. Recently, the Plonk and Sonic algorithms, which are quite popular in the blockchain world, are based on improvements and optimizations made to Groth16 in trusted setups. It is hoped that readers can combine the mathematical tools introduced in previous articles to understand the basic principles of these two algorithms and lay the foundation for understanding the improved algorithms and some typical non-Snark algorithms in the next article.
References
[7] Parno B, Howell J, Gentry C, et al. Pinocchio: Nearly practical verifiable computation[C]//2013 IEEE Symposium on Security and Privacy. IEEE, 2013: 238-252.
[8] R. Gennaro, C. Gentry, B. Parno, and M. Raykova, “Quadratic span programs and succinct NIZKs without PCPs,” in EUROCRYPT, 2013. Originally published as Cryptology ePrint Archive, Report 2012/215.
[9] Groth J. On the size of pairing-based non-interactive arguments[C]//Annual international conference on the theory and applications of cryptographic techniques. Springer, Berlin, Heidelberg, 2016: 305-326.
