This is a Typescript library which implements the KZG10 polynominal commitment scheme.
It can produce and verify proofs of one point per proof, or multiple points per proof.
genCoefficients = (values: bigint[]): Coefficient[]
Given a list of arbitrary values, use polynominal interpolation to generate the coefficients of a polynominal to commit. Each value must be lower than the BN254 scalar field order:
21888242871839275222246405745257275088548364400416034343698204186575808495617
commit = (coefficients: bigint[]): Commitment
Generate a commitment to the polynominal with the specified coefficients.
genProof = (coefficients: Coefficient[], index: number | bigint): Proof
Generate a proof (also known as a witness) that the polynominal will evaluate
to p(index) given index as the x-value.
verify = (commitment: Commitment, proof: Proof, index: number | bigint, value: bigint): boolean
Given a proof, verify that the polynominal with the specified commitment
evaluates to the y-value value at the x-value index.
genMultiProof = (coefficients: Coefficient[], indices: number[] | bigint[]): MultiProof
Generate a proof (also known as a witness) that the polynominal will evaluate
to p(indices[i]) per i.
verifyMulti = (commitment: Commitment, proof: MultiProof, indices: number[] | bigint[], values: bigint[])
Given a proof, verify that the polynominal with the specified commitment
evaluates to the each y-value in values at the corresponding x-value in
indices.
genVerifierContractParams = (commitment: Commitment, proof: Proof, index: number | bigint, value: bigint)
A helper function which generates parameters to the KZGVerifier.verify().
Example usage:
const params = genVerifierContractParams(commitment, proof, i, yVal)
const result = await verifierContract.verify(
params.commitment,
params.proof,
params.index,
params.value,
)The repository contains a Solidity contract with a verify() function which
performs on-chain proof verification for single-point proofs:
function verify(
Pairing.G1Point memory _commitment,
Pairing.G1Point memory _proof,
uint256 _index,
uint256 _value
) public view returns (bool)It consumes about 178078 gas when called by a contract.
It also provides a commit() function which can generate KZG commitments for
up to 128 coefficients. This function is intended for multi-point proof
verification.
| Coefficients | Execution cost |
|---|---|
| 1 | 34929 |
| 2 | 47496 |
| 4 | 72608 |
| 5 | 85177 |
| 8 | 122889 |
| 16 | 223476 |
| 32 | 424786 |
| 64 | 827980 |
| 128 | 1649494 |
By comparison, the Poseidon T=3 function which hashes 2 elements per call consumes 49858 gas. Additionally, the Poseidon T=6 function which hashes 5 elements per call consumes 112055 gas.
This means that KZG commitments may be competitive as the accumulator for a Verkle tree. The downside is that it is much more difficult to verify KZG proofs in zero-knowledge, while the Poseidon hash function is built for efficiency in zk-SNARK circuits.
The verifyMulti() function provides multi-point proof verification.
function 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)
It consumes the following gas per point:
| 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 |
Clone this repository, install dependencies, and build the source:
git clone git@github.com:weijiekoh/libkzg.git &&
cd libkzg &&
npm i &&
npm run buildRun the tests:
npm run testThe output should look like:
PASS ts/__tests__/libkzg.test.ts (12.513 s)
libkzg
commit, prove, and verify the polynomial [5, 0, 2 1]
✓ compute the coefficients to commit using genCoefficients() (4 ms)
✓ generate a KZG commitment (1 ms)
✓ generate the coefficients of a quotient polynomial
✓ generate a KZG proof (1 ms)
✓ verify a KZG proof (1553 ms)
✓ not verify an invalid KZG proof (2154 ms)
commit, prove, and verify a random polynomial
✓ generate a valid proof (1400 ms)
pairing checks
✓ perform a pairing check than e(xg, yg) = e(yg, xg) (696 ms)
✓ perform a pairing check than e(xyg, g) = e(xg, yg) (709 ms)
✓ perform pairing checks using ffjavascript (2154 ms)
✓ perform pairing checks using rustbn.js (1083 ms)
multiproofs
✓ should generate and verify a multiproof (713 ms)
✓ not verify an invalid multiproof (728 ms)
The repository also includes a Solidity verifier. To test it, first launch Ganache in a different terminal:
npm run ganacheNext, run:
npm run test-sol-verifierThe output should look like:
PASS ts/__tests__/solVerifier.test.ts (39.603 s)
Solidity verifier
✓ evalPolyAt() should work (21 ms)
✓ should generate a matching commitment (170 ms)
multi-point proof verification
✓ should verify valid proofs (12498 ms)
✓ should reject an invalid proof (184 ms)
✓ should reject a valid proof with invalid iCoeffs and zCoeffs (1212 ms)
✓ should pass a stress test (15296 ms)
single-point proof verification
✓ should verify a valid proof (4355 ms)
✓ should not verify an invalid proof (309 ms)
✓ should not verify an invalid commitment (468 ms)
The trusted setup for this library is the Perpetual Powers of Tau Ceremony (PPOT). It comes packaged with the first 65536 G1 and the first two G2 powers of tau from the 46th contribution to the ceremony, which means that it can commit up to 65536 values.
The Blake2b hash of this challenge file is:
939038cd 2dc5a1c0 20f368d2 bfad8686
950fdf7e c2d2e192 a7d59509 3068816b
becd914b a293dd8a cb6d18c7 b5116b66
ea54d915 d47a89cc fbe2d5a3 444dfbed
The challenge file can be retrieved at:
https://ppot.blob.core.windows.net/public/challenge_0046
The ceremony transcript can be retrieved at:
https://github.com/weijiekoh/perpetualpowersoftau
Anyone can verify the transcript to ensure that the values in the challenge file have not been tampered with. Moreover, as long as one participant in the ceremony has discarded their toxic waste, the whole ceremony is secure. Please read this blog post for more information.
Many thanks to Chih-Cheng Liang, Kobi Gurkan, and Barry WhiteHat for their guidance.