# `libkzg`: a minimum-viable KZG polynomial commitment scheme implementation [DRAFT]

Existing research highlights promising use cases for Kate-Zaverucha-Goldberg ([KZG10](https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf)) commitments in ETH2, particularly as [a better accumulator of block data than Merkle trees](https://ethresear.ch/t/using-polynomial-commitments-to-replace-state-roots/7095). Despite strong interest from the research community, however, there are few, if any, implementations of this commitment scheme which smart contract developers can use today.

In this post, I present [`libkzg`](http://github.com/weijiekoh/libkzg), an implementation written in Typescript, and which contains a Solidity verifier. I also describe in detail the choice of trusted setup, how `libkzg` uses the EIP-197 precompiled contract for pairing checks to verify a single-point KZG proof, and discuss how to perform multi-point proofs on-chain.

`libkzg` currently supports the following features:

1. The ability to convert an arbitrary list of values to the coefficients of a polynomial.
2. The ability to generate a KZG commitment function to said coefficients.
3. The ability to generate a proof (or witness) that the polynomial evaluates to a particular value at at given point (or index).
4. The ability to verify said proof in Typescript and the EVM.

It currently does not support proofs of evaluation at multiple points, but this feature may be built sometime after this post is published. Do note that multi-point proofs may not be feasible to implement in the EVM, and a follow-up post will discuss this.

[TOC]

## Implementation details

### Function interfaces

**`genCoefficients(values: BigInt[]): Coefficient[]`**

Performs polynomial interpolation on the given values and returns a new polynomial, which is represented as a list of coefficients. Note that the new polynomial, not `values`, should be fed into `commit()` in order to commit to `values`.

**`commit(coefficients: Coefficient[]): Commitment`**

Given a list of values, this function should output their KZG commitment.

**`genProof(coefficients: Coefficient[], index: number): Proof`**

Generates a proof that the polynomial evaluates to `coefficients[index]` at the x-value `index`.

**`verify(c: Commitment, proof: Proof, index: number, value: BigInt): boolean`**

Returns true if the proof (that for the polynomial committed to, the evaluation at the given index equals the given value) is valid, and false otherwise.

### The trusted setup

The KZG scheme requires a trusted setup. To abstract this away from developers, `libkzg` comes packaged with values from the 46th contribution to the [Perpetual Powers of Tau Ceremony](https://github.com/weijiekoh/perpetualpowersoftau) (PPOT). As PPOT is a multi-party trusted setup, as long as just one participant had safely discarded their toxic waste during the ceremony, nobody can generate fake proofs.

The number of so-called powers of tau from this ceremony is the maximum number of coefficients this library supports. For the sake of portability, `libkzg` only supports up to 65536 coefficients. That said, anyone can choose any existing contribution to PPOT and modify `libkzg` to support up to a maximum of $2 ^ {28}$ coefficients (although this would require an unwieldly amount disk space in the range of dozens of gigabytes for off-chain use, and be limited by gas costs for deploying te verifier contract on-chain).

### Verification in the EVM

`libkzg` provides a Solidity contract that can verify single-point proofs. The contract code is [here](https://github.com/weijiekoh/libkzg/blob/master/sol/KZGVerifier.sol). Each invocation consumes about 178k gas. Its function signature is:

function verifyKZG(
    uint256 _commitmentX,
    uint256 _commitmentY,
    uint256 _proofX,
    uint256 _proofY,
    uint256 _index,
    uint256 _value
) public view returns (bool)

The verifier uses the [EIP-197](https://github.com/ethereum/EIPs/blob/master/EIPS/eip-197.md) precompiled contract to perform a pairing check. According to the KZG10 paper, this pairing check must pass in order for the proof to be valid. It states:


It is crucial that this equation is converted into a form that can be efficiently computed on-chain. On the one hand, the EIP-197 precompiled contract accepts a list of G1 and G2 group elements $(a_1, b_1 ... a_n, b_n)$, and checks if they fulfill this equation:

$e(a_1, b_1) \cdot \ldots \cdot e(a_n, b_n) = 1$

On the other hand, all on-chain operations cost gas, so it is important to minimise the number of $a_n, b_n$ elements, as well as group operations on said elements, particularly curve point addition and multiplication. Furthermore, we want to avoid performing these operations on G2 group elements entirely. Unlike curve operations in G1, which can be done using [EIP-196](https://github.com/ethereum/EIPs/blob/master/EIPS/eip-196.md) precompiled contracts, those for G2 have to be implemented in Solidity, and this increases code complexity and steepens gas costs.

As such, to achieve gas-efficiency and simplicity, we have to perform some algebra on the above equations. To begin this process, here is a legend to its mathematical symbols:

| Symbol | Description |
|-|-|
| $e$ | The pairing function. |
| $w_i$ or $g^{\psi_i(\alpha)}$ | The proof, which is also associated with the `_index`. |
| $g$ | The generator of either G1 or G2. In the expression $e(g, P)$, $g$ is the generator of G1. In $e(P, g)$, $g$ is the generator of G2. | |
| $g^\alpha$ | The generator $g$ (either G1 or G2) raised to the first power of tau. In other words, this is the *second* value from the trusted setup's TauG1 or TauG2 outputs. (The first is simply $g^{\alpha ^ 0} = g^{1} = g$.). |
| $g^{\alpha(x)}$ or $g^\alpha$ | The KZG commitment to the polynomial with coefficients `[0, 1]` which is $(1)x^1 - (0)x^0 = x$
| $g^{i}$ or $g ^{1} \cdot i$| The KZG commitment to the polynomial with coefficients `[_index]` which is $ix^0 = i$ |
| $\phi(x)$ |The committed polynomial. |
| $\phi(i)$ | This is `_value`, which is the evaluation of the committed polynomial at the x-value `_index`. |
| $\psi_i(\alpha)$ | The polynomial $\frac{\phi(x) - \phi(i)}{x-i}$, also known as the quotient polynomial. |

Next, recall some [fundamental properties of elliptic curve pairings](https://blog.statebox.org/elliptic-curve-pairings-213131769fac):

**[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)$

**Now, simplify this equation from the original paper:**
$e(g^{\psi_i(\alpha)}, g^{\alpha - i}) \cdot e(g, g)^{\phi(i)} = e(C, g)$

**Subsitute $C$ with $g^{\phi(x)}$ and flip sides:**
$e(g^{\phi(x)}, g) = e(g^{\psi_i(\alpha)}, g^{\alpha - i}) \cdot e(g, g)^{\phi(i)}$

**Apply [a] to shift $\phi(i)$:**
$e(g^{\phi(x)}, g) = e(g^{\psi_i(\alpha)}, g^{\alpha - i}) \cdot e(\phi(i) \cdot g, g)$

**Multiply both sides by $e(\phi(i) \cdot g, g)^{-1}$:**
$e(g^{\phi(x)}, g) \cdot e(\phi(i) \cdot g, g)^{-1} = e(g^{\psi_i(\alpha)}, g^{\alpha - i})$

**Apply [a] to shift $-1$:**
$e(g^{\phi(x)}, g) \cdot e(-\phi(i) \cdot g, g) = e(g^{\psi_i(\alpha)}, g^{\alpha - i})$

**Apply [c] to reduce the number of pairings from 3 to 2:**
$e(g^{\phi(x)}-g \cdot \phi(i), g) = e(g^{\psi_i(\alpha)}, g^{\alpha - i})$

**Substitute $g^{\alpha - i}$ with $g^\alpha \cdot g^{-i}$:**

According to the original paper:

$g^{\alpha - i} = \frac{g^\alpha}{g^i}$

So, $g^{\alpha - i}$ is the generator to the power of $\alpha -i$, and can also be expressed as $g^\alpha \cdot g^{-i}$.

$e(g^{\phi(x)}-g \cdot \phi(i), g) = e(g^{\psi_i(\alpha)}, g^\alpha \cdot g^{-i})$

**Apply [a] to shift $\alpha - i$:**
$e(g^{\phi(x)}-g \cdot \phi(i), g) = e(g^{\psi_i(\alpha)}, g)^{\alpha -i}$

$e(g^{\phi(x)}-g \cdot \phi(i), g) = e(g^{\psi_i(\alpha)}, g)^{\alpha} \cdot e(g^{\psi_i(\alpha)}, g)^{-i}$

$e(g^{\phi(x)}-g \cdot \phi(i), g) = e(\alpha \cdot g^{\psi_i(\alpha)}, g) \cdot e(-i \cdot g^{\psi_i(\alpha)}, g)$

$e(g^{\phi(x)}-g \cdot \phi(i), g) \cdot e(-i \cdot g^{\psi_i(\alpha)}, g)^{-1} = e(\alpha \cdot g^{\psi_i(\alpha)}, g)$

$e(g^{\phi(x)}-g \cdot \phi(i), g) \cdot e(i \cdot g^{\psi_i(\alpha)}, g) = e(\alpha \cdot g^{\psi_i(\alpha)}, g)$

**Apply [c] to reduce the number of pairings from 3 to 2:**
$e((g^{\phi(x)}-g \cdot \phi(i)) + (i \cdot g^{\psi_i(\alpha)}), g) = e(\alpha \cdot g^{\psi_i(\alpha)}, g)$

**Divide both sides by $e(\alpha \cdot g^{\psi_i(\alpha)}, g)$ to make it EIP-197 friendly:**
$e((g^{\phi(x)}-g \cdot \phi(i)) + (i \cdot g^{\psi_i(\alpha)}), g) \cdot e(\alpha \cdot g^{\psi_i(\alpha)}, g)^{-1} = 1$

**Apply [a] to shift $-1$:**
$e((g^{\phi(x)}-g \cdot \phi(i)) + (i \cdot g^{\psi_i(\alpha)}), g) \cdot e(-\alpha \cdot g^{\psi_i(\alpha)}, g) = 1$

**Apply [a] to remove one G1 multiplication step:**
$e((g^{\phi(x)}-g \cdot \phi(i)) + (i \cdot g^{\psi_i(\alpha)}), g) \cdot e(- g^{\psi_i(\alpha)}, \alpha \cdot g) = 1$

As a result, the verifier contract only needs to:

- Perform one G1 curve point addition.
- Perform one G1 curve point scalar multiplication.
- Perform a pairing check with 2 pairings.

The only elements from the trusted setup it must store on-chain are:
- The generator of G1.
- The generator of G2.
- $\alpha \cdot g$ of G2, which is the generator of G2 raised to the first power of tau from the contribution file.

As such, with [EIP-1108](https://eips.ethereum.org/EIPS/eip-1108) already on mainnet, the `verifyKZG()` contract function only consumes 178k gas.

## Credits

Many thanks to Barry Whitehat, Kobi Gurkan, Chih-Cheng Liang, Lai Ying Tong, and Lakshman Sankar for their feedback.

## Resources

[Constant-Size Commitments to Polynomials and Their Applications](https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf) by Kate, Zaverucha, and Goldberg.

[Kate polynomial commitments](https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html) by Dankrad Feist.

[Kate-Zaverucha-Goldberg (KZG) Constant-Sized Polynomial Commitments](https://alinush.github.io/2020/05/06/kzg-polynomial-commitments.html) by Alin Tomescu.

<!--
## Problem: on-chain multi-point proof verification

It is prohibitively expensive to perform multi-point proof verification on-chain because it requires multiple operations in the G2 group. To see why this is the case, we first review the steps which the original paper lays out:


In summary:

1. 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})$, create an interpolation polynomial $r(x)$ such that it goes through each point.
2. Compute a zero polynomial $\prod_{i \in B}(x - i)$.
3. Compute a quotient polynomial $\psi_B(x) = \frac{\phi(x) - r(x)}{ \prod_{i \in B}(x - i)}$.
4. The multi-point proof is the KZG commitment to the quotient polynomial: $g^{\psi_B(\alpha)}$.
5. 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)$

**Alin Tomescu's method is to check that:**

$e(C/g^{r(\alpha)}, g) = e(g^{\psi_B(\alpha)}, g^{\prod_{i \in B}(\alpha - i)})$

Which is equivalent to:

$e(g^{\phi(\alpha)-r(\alpha)}, g) = e(g, g)^{\psi_B(\alpha) \cdot \prod_{i \in B}(\alpha - i)}$

This means that to verify a multi-point proof on-chain, we need:

- $-1 \cdot g^{\phi(\alpha)-r(\alpha)}$ in G1
- $\psi_B(\alpha) \cdot \prod_{i \in B}(\alpha - i)$ in G1

Using a zk-SNARK, we can access these values on-chain and then perform the necessary pairing check. The zk-SNARK circuit would accept the following public inputs:

- The indices of the values to prove
- The y-values

Its private inputs would be:

- The coefficients to the committed polynomial $\phi(x)$.
- The coefficients to the interpolation polynomial $r(x)$.
- The coefficients to the quotient polynomial $\psi_B(x)$.
- The coefficients to the zero polynomial $\prod_{i \in B}(\alpha - i)$.

The circuit would verify that:

- $\phi(x) - r(x) = \psi_B(x) \cdot \prod_{i \in B}(x - i)$
- The evaluation of $\prod_{i \in B}(\alpha - i)$ at each $i$ equals 0.

Its outputs would be:

- The coefficients of $g^{\phi(\alpha)-r(\alpha)}$
- $\psi_B(\alpha) \cdot \prod_{i \in B}(\alpha - i)$ in G1

It would have to perform:

- One polynomial subtraction
- One KZG commitment
- One G1 negation
- One polynomial multiplication
- One polynomial comparision

---

-->

# Multi-point KZG proof verification in the EVM

In a [previous post](https://ethresear.ch/t/a-minimum-viable-kzg-polynomial-commitment-scheme-implementation/7675), I introduced [`libkzg`](https://github.com/weijiekoh/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 |

## Appendix I: the math behind multi-point proof verification

The [KZG10 paper](https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf) describes how to evaluate a multi-point proof as such:


In summary:

1. 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.
2. Compute a zero polynomial $\prod_{i \in B}(x - i)$.
3. Compute a quotient polynomial $\psi_B(x) = \frac{\phi(x) - r(x)}{ \prod_{i \in B}(x - i)}$.
4. The multi-point proof is the KZG commitment to the quotient polynomial: $g^{\psi_B(\alpha)}$.
5. 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}))$

**Apply [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](https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html) on the topic.