Prerequisites:
Understanding of what QAP is and how to create one from R1CS.
Group theory understandings
Probabilistic Checkable Proofs ( PCP )
What is a PCP:
Prover generates a PCP oracle, which can be thought of as a big message of polynomial size. Verifier queries PCP oracle at random points, and using these queries verifier can verify the computation of a polynomial.
In Linear PCP, the PCP generated by the Prover is a linear function. The Oracle responds to linear queries by doing an inner product.
Recall:
\(p(x) = (\sum_{i=1}^m c_i \times l_i(x)) \times (\sum_{i=1}^m c_i \times r_i(x)) \times (\sum_{i=1}^m c_i \times o_i(x)) = V(x).q(x)\)
To show the above can be done using a linear PCP model.
The verifier can submit only linear queries to the PCP:
\( \times - = V(\gamma)\)
Some termonologies before we continue further:
Knowledge of exponentiation:
Sample random \(\alpha\), compute \(g^{\alpha .l_i(\tau)}\) for i = 1...m.
\(\pi_1 = g^{\sum_{i=1}^m c_i \times l_i (\tau)}\) and \(\pi_1^{'} = g^{\sum_{i=1}^m c_i \times l_i (\tau)}\)
\(e(\pi_1, g^\alpha) = e(\pi^{'}, g)\)
Generic Group Model
The adversary is only given an oracle to compute the group operation.
eg. given \(g^{\alpha.l_i(\tau)}\)for i= 1,...,m. The adversary can only compute their linear combinations.
Linear PCP
Preprocessing ( Key Generation ):
Proving key: \(p, G, g, G_T, e\)
Compute Public Keys: \(g^{l_i(\tau)},g^{r_i(\tau)},g^{o_i(\tau)}\) for \(i=1, \ldots,m\) --- (1)
Evaluate: \(g^\tau , g^{\tau^2}, \ldots, g^{\tau^m}\) ( Public ). --- (2)
Also: \(g ^ {\beta(l_i(\tau) + r_i(\tau) + o_i(\tau))})\) for \(i \in [m]\) --- (3)
Verification Key: \(g^V(\tau) \) - this is known to the verifier
delete \(\tau\)
Prove Generation
\(\pi _1 = g^{\sum_{i=1}^m c_i \times l_i(\tau)}\) , where the term in power is the public key calculated in (1).
Similarly, calculate \(\pi _2\) and \(\pi _3\) using (1) above.
\(\pi _4 = g^{q(\tau)}\) calculated using (2) above.
\(\pi_5 = \prod _{i=1}^m (g ^ {\beta(l_i(\tau) + r_i(\tau) + o_i(\tau))})^{c_i}\)
Verification
The idea is to check the value of p(x) equation equality in the exponent.
Verify using: \(\frac{e(\pi_1, \pi_2)}{e(\pi_3, g)} = e(g^{V(\tau)}, \pi_4)\) bilinear relation.
\(e(\pi_1\pi_2\pi_3, g^\beta) = e(\pi_5, g)\): This check makes sure that the prover isn't cheating and not using the same vector \(c\) in the generation of \(\pi_1, \pi_2, \pi_3\).
The above protocol is not the real implementation. If you notice, while input in the above circuit is considered as a witness. But in practical application, a circuit has both, public and private inputs.
So to convert the above into a real protocol, notice the proof property that is generated above:
$$\pi_1 = g^{\sum_{i \in I_{mid}}c_i \times l_i(\tau)} * g^{\sum_{i \in I_{io}}c_i \times l_i(\tau)}$$
where \(I_{mid}\) is the witness, and \(I_{io}\) is the public Input/output. So now the proof becomes:
$$\pi_1 = g^{\sum_{i \in I_{mid}}c_i \times l_i(\tau)}$$
and the verifier can simply do:
$$\pi_1^* = \pi_1 . g^{\sum_{i \in I_{io}}c_i \times l_i(\tau)}$$
$$\frac{e(\pi_1*,\pi_2*)}{e(\pi_3^*, g)} = e(g^{V(\tau), \pi_4})$$
And that's Groth 16 protocol under the hood!!
Variant of Groth16
$$p(x) = (\sum_{i=1}^m c_i \times l_i(x)) \times (\sum_{i=1}^m c_i \times r_i(x)) \times (\sum_{i=1}^m c_i \times o_i(x)) = V(x).q(x)$$
Proof:
\(\pi_1 = g^{\alpha + \sum_{i=1}^m c_i \times l_i (\tau)}\)
\(\pi_2 = g^{\beta + \sum_{i=1}^m c_i \times r_i (\tau)}\)
\(\pi_3 = \prod _{i=1}^m (g ^ {\sum c_i \times \beta(l_i(\tau) + r_i(\tau) + o_i(\tau)) + V(\tau)q(\tau)})\)
Verify:
- \(e(\pi_1, \pi_2) = e(\pi_3, g).e(g^\alpha, g^\beta)\)
To make the above systems Zero Knowlege, a randomizer is simply added to the proofs generated.
\(\pi _1 = g^{\sum_{i=1}^m c_i \times l_i(\tau) + \delta_1V(\tau)} \) and similarly for \(\pi_2\) and \(\pi_3\)
Properties of Groth16
Computation Cost: The cost to generate a proof in Groth16 is relatively high compared to the verification cost. This is because the prover must perform a series of complex mathematical operations, which include polynomial evaluations and multi-exponentiations in elliptic curve groups.
Input Length Dependence: The proving time is dependent on the length of the witness (the information that proves the statement). For more complex statements or larger datasets, the time required to generate a proof increases.
Memory Usage: Groth16 proving can be memory-intensive. The prover needs to handle large polynomials and multiple group elements, which requires substantial computational resources, especially for complex statements.
Parallelizability: The proving process in Groth16 can be parallelized to some extent. This means that with sufficient computational resources, the time taken to generate a proof can be reduced.
Efficient Verification: Groth16 stands out for its extremely efficient verification process. Verifying a proof typically involves a few pairings and elliptic curve operations, which are computationally cheaper than the operations required for proof generation.
Constant Time Verification: Regardless of the complexity of the original computation, the verification time remains constant. This is a significant advantage, especially in systems where quick verification is essential, like in blockchain transactions.
Low Resource Requirement: The verifier does not need extensive computational resources. This asymmetry between proving and verification complexity makes Groth16 particularly suitable for systems where the verifier's resources are limited, such as in smart contracts on a blockchain.
Asymmetry Advantage: The asymmetry in computational requirements between the prover and verifier in Groth16 is by design. While it demands more from the prover, it benefits systems where verification needs to be quick and inexpensive, a common scenario in decentralized systems like blockchains.
Scalability Impact: This asymmetry affects scalability. The efficiency in verification means that more transactions (or other verifiable computations) can be processed in a shorter time, which is crucial for the scalability of blockchains.
Security and Trust: The proving complexity also contributes to the security of the system, as it makes it computationally prohibitive to generate false proofs.
In Groth16 variants:
Proof size: 3 group elements - 144 bytes
Verifier time: 1 pairing equation
Follow me on social media: Twitter, and LinkedIn for new updates in the cryptography space and any discussion related to computer science.