In a previous post, I introduced libkzg, an implementation of the KZG polynomial commitment scheme. This library now supports multi-point proof generation, as well as on-chain verification of up to 128 points of evaluation. In this post, I will describe the new functions pertaining to multi-point proof generation and verification, discuss its implementation, and describe tradeoffs made.
Implementation details
Typescript functions
genMultiProof(coefficients: Coefficient[], indices: number[] | bigint[]): MultiProof
Generates a KZG proof to the evaluations at indices for the polynomial with the given coefficients.
A MultiProof is a single G2 point.
verifyMulti(commitment: Commitment, proof: MultiProof, indices: number[] | bigint[], values: bigint[])
Verifies a MultiProof given the polynomial commitment, as well as the associated indices and evaluations.
Solidity functions
verifyMulti(Pairing.G1Point memory _commitment, Pairing.G2Point memory _proof, uint256[] memory _indices, uint256[] memory _values, uint256[] memory _iCoeffs, uint256[] memory _zCoeffs) ) public view returns (bool)
The Solidity verifyMulti function does the same as the Typescript verifyMulti function, but requires two additional parameters: _iCoeffs and _zCoeffs.
_iCoeffs should be the coefficients to a polynomial which interpolates the points denoted by _indices and _values.
_zCoeffs is a polynomial which intersects y=0 for each x-value in _indices.
These polynomials are required to verify the proof. See the appendix for a more detailed explanation.
The contract will ensure that _iCoeffs and _zCoeffs are valid by evaluating them at each point in _index and checking whether the result is a corresponding value in _values or 0 respectively. An alternative method is to perform polynomial interpolation in Solidity, but I have not explored that yet.
Next, it will compute the KZG commitments for _iCoeffs and _zCoeffs respectively. It is able to do this as the verifier contract has 129 G1 values from the trusted setup, stored during deployment.
Finally, it performs a single pairing check described in the appendix.
Limitations
The contract supports verification of up to 128 points per verifyMulti function call.
Gas costs
Deployment
The contract costs about 7.3 million gas to deploy. The bulk of this comes from storing 129 G1 points (a total of 258 uint256 values) from the trusted setup on-chain.
Proof verification
Multi-point proof verification is significantly cheaper per point than single-point proof verification as long as the number of points is greater than 1.
| Points | Cost | % Savings |
|---|---|---|
| 1 | 193084 | -8 |
| 2 | 221505 | 38 |
| 3 | 250283 | 53 |
| 4 | 280075 | 61 |
| 5 | 310152 | 65 |
| 6 | 341279 | 68 |
| 7 | 372763 | 70 |
| 8 | 405237 | 72 |
| 9 | 438008 | 73 |
| 50 | 2368081 | 73 |
| 75 | 4098829 | 69 |
| 100 | 6245670 | 65 |
| 128 | 9145327 | 60 |
Open questions
More efficient polynomial identity verification
The Solidity function verifies two polynomials by evaluating them at each index and checking the result. Is there a way to speed this up?
Practical use cases
What are some use cases that would immediately benefit from libkzg? One downside of KZG polynomial commitments is that updates are less efficient than those for Merkle trees, which prevents them from substituting Merkle trees in applications which require them.
Trusted setup
What are some ways to more efficiently establish social trust in the structured reference string (SRS) values which this library uses? These values come from the Perpetual Powers of Tau ceremony. Teams which use it should independently verify the ceremony transcript and check whether the SRS values stored in the verifier contract match those from the chosen challenge file. Yet, the transcript is extremely bulky and takes a long time to verify.
Verkle trees
Some authors have suggested using KZG commitments as the accumulator for Merkle trees. This deserves a longer post, but for this construction to be gas-competitive, it must beat the efficiency of the Keccack and SHA256 hash functions, which consume 349 and 1586 gas respectively to hash two 32-byte values each. In contract, the KZG commitment function is much more expensive on-chain: it consumes 47496 gas to commit to two coefficients.
One may wonder if KZG commitments can be competitive accumulators for zero-knowledge use cases. This is an open question, as it is difficult to generate and verify them in ZK. Nonetheless, it is useful to compare them with the zk-SNARK friendly Poseidon function, which consumes 49858 gas to hash 2 values, and 112055 gas to hash 5 values. In contrast, the KZG commitment function consumes 85177 gas to hash 5 values.
Appendix I: the math behind multi-point proof verification
The KZG10 paper describes how to evaluate a multi-point proof as such:
In summary:
- Given a polynomial \phi(x) whose KZG commitment is C, and a set of indices B to prove exist on \phi(x), i.e. (i_0, y_0) ... (i_{k-1}, y_{k-1}), compute an interpolation polynomial r(x) such that it goes through each point.
- Compute a zero polynomial \prod_{i \in B}(x - i).
- Compute a quotient polynomial \psi_B(x) = \frac{\phi(x) - r(x)}{ \prod_{i \in B}(x - i)}.
- The multi-point proof is the KZG commitment to the quotient polynomial: g^{\psi_B(\alpha)}.
- To verify the proof, perform this pairing check:
e(g^{\prod_{i \in B}(\alpha - i)}, g^{\psi_B(\alpha)}) \cdot e(g, g^{r(\alpha})) = e(C, g)
Multiply each side by e(g, g^{r(\alpha}))^{-1} and apply [a]:
e(g^{\prod_{i \in B}(\alpha - i)}, g^{\psi_B(\alpha)}) = e(C, g) \cdot e(g, -1 \cdot g^{r(\alpha}))
Recall some fundamental properties of elliptic curve pairings:
[a]: e(P, Q)^{x} = e(x \cdot P, Q) = e(P, x\cdot Q)
[b]: e(x \cdot P, y \cdot Q) = e(y \cdot P, x \cdot Q)
[c]: e(P + S, Q) = e(P, Q) \cdot e(S, Q)
[d]: e(P, Q + R) = e(P, Q) \cdot e(P, R)
Apply [a] and [c]:
e(g^{\prod_{i \in B}(\alpha - i)}, g^{\psi_B(\alpha)}) = e(C - g^{r(\alpha)}, g)
Make it EIP-197 friendly:
e(g^{\prod_{i \in B}(\alpha - i)}, g^{\psi_B(\alpha)}) \cdot e(-C - g^{r(\alpha)}, g) = 1
As such, the verifier contract function requires the following to perform a pairing check. It needs the following values:
- g^{\prod_{i \in B}(\alpha - i)} as a G1 point.
- g^{\psi_B(\alpha)} as a G2 point.
- C as a G1 point.
- g^{r(x)} as a G1 point.
- The G2 generator g.
To compute g^{\prod_{i \in B}(\alpha - i)} and g^{r(x)} on-chain requires:
- Verification of r(x) and \prod_{i \in B}(\alpha - i) if they are provided as parameters; otherwise, polynomial interpolation to produce them.
- Two elliptic curve multiplication operations per point.
- Two elliptic curve addition operations per point.
To produce -C - g^{r(\alpha)}, the verifier must also perform an elliptic curve addition operation in G1.
Credits
Many thanks to @barryWhiteHat, @kobigurk, @liangcc, @yingtong, and @lsankar4033 for their feedback, and @dankrad for his extremely helpful blog post on the topic.