# KZG Polynomial Commitments
### Introduction
The **KZG** (Kate - *pronounced [kah-tay](https://www.cs.purdue.edu/homes/akate/howtopronounce.html)*, Zaverucha, and Goldwasser) polynomial commitment scheme allows a prover to compute a commitment for a polynomial, commit it, and later on prove to a verifier the value of the polynomial at a given point, with the properties that this commitment can later be opened at any position: The prover shows that the value of the polynomial at a certain position is equal to a claimed value.
It is called a *commitment* since having sent the commitment value (an *elliptic curve point*) to someone (the *verifier*), the prover cannot change the polynomial they are working with. They will only be able to provide valid proofs for one polynomial, and if they are trying to cheat, they will either fail to produce a proof or the proof will be rejected by the verifier.
The reason that it is so useful is that for anything that can be encoded into a polynomial, can now be *selectively* disclosed. For example, we can encode a membership set as points on the polynomial, and using KZG, we can easily generate *proof of membership* or *proof of non-membership*. Another example is that we can encode circuit constraints in zero knowledge proofs as a polynomial, and verifier could ask for random points to ensure that the constraints are met.
>An example comparison between how we could use merkle tree and polynomial to generate proof of membership. In merkle tree, the prover needs to provide the sibling paths of the leaf in order to prove that it belongs to the committed root. Using polynomial, we can set the members as roots of the polynomials. To prove that a point is part of a membership set, the prover needs to prove that the point evaluate to zero in the committed polynomial.
### Context
***Elliptic Curve Cryptography***
A pivotal moment in cryptography occurred with the introduction of the RSA and Diffie-Hellman key exchange algorithms, which enabled secure communication without a shared secret. Modern cryptography relies on public key systems, where the encryption key is public, and the decryption key is private. These systems depend on algorithms called Trapdoor Functions, which are easy to compute in one direction but difficult to reverse. The greater the disparity in difficulty between the two directions, the more secure the cryptographic system.
RSA and Diffie-Hellman are not ideal for future cryptography because their security relies on the difficulty of factoring large numbers, a problem that is becoming easier to solve with advanced algorithms like the *Quadratic Sieve* and *General Number Field Sieve*. As the size of keys increases to maintain security, the computational resources required become unsustainable, especially for mobile and low-powered devices. A better public key system is needed, one where the difficulty of both encryption and decryption increases at the same rate as the size of the numbers involved.
In 1985, cryptographic algorithms were proposed based on a branch of mathematics called elliptic curves.
An **elliptic curve** is the *set of points* that satisfy a specific mathematical equation. The equation for an elliptic curve looks something like this:
$$
y2 = x3 + ax + b
$$
> Technically, an elliptic curve is the set points satisfying an equation in two variables with degree two in one of the variables and three in the other.
Elliptic curve cryptography (ECC) relies on the elliptic curve discrete logarithm problem, which involves computing the private key from the public key. This problem is much harder to solve than factoring, which underpins RSA and Diffie-Hellman. Breaking a 228-bit RSA key requires less energy to than it takes to boil a teaspoon of water. Comparatively, breaking a 228-bit elliptic curve key requires enough energy to boil all the water on earth. For this level of security with RSA, you'd need a key with 2,380-bits. ECC offers a convenient tradeoff: high security with short, fast keys.
***Elliptic Curve Pairings***
Pairings go a step further in that they allow you to check certain kinds of more complicated equations on elliptic curve points. Where traditional elliptic curve math lets us check linear constraints on numbers, pairings let us check quadratic constraints.
Pairings, or bilinear maps, satisfy the following constraints.
$$
𝑒(𝑃,𝑄+𝑅)=𝑒(𝑃,𝑄)⋅𝑒(𝑃,𝑅)
$$
$$
𝑒(𝑃+𝑆,𝑄)=𝑒(𝑃,𝑄)⋅𝑒(𝑆,𝑄)
$$
An elliptic curve pairing is a map $𝐺2×𝐺1→𝐺𝑡$, where:
- $𝐺1$ is an elliptic curve, where points satisfy an equation of the form $𝑦2=𝑥3+𝑏$, and where both coordinates are elements of $𝐹𝑝$ (ie. they are simple numbers, except arithmetic is all done modulo some prime number).
- $𝐺2$ is an elliptic curve, where points satisfy the same equation as $𝐺1$, except where the coordinates are elements of $\mathbb{F}_p^{12}$(ie. they are complex numbers denoted as 𝑤, which is defined by a 12th degree polynomial).
- $𝐺𝑡$ is the type of object that the result of the elliptic curve goes into. In the curves that we look at, $𝐺𝑡$ is $\mathbb{F}_p^{12}$ (the same supercharged complex number as used in $𝐺2$$)$.
The main property that they satisfy is bilinearity, as detailed above.
***Trusted Setups***
A trusted setup ceremony is a procedure that is done once to generate a piece of data that must then be used every time some cryptographic protocol is run. Generating this data requires some secret information; the "trust" comes from the fact that some person or some group of people has to generate these secrets, use them to generate the data, and then publish the data and forget the secrets.
A secure multiparty computation allows creating these group elements by a group of computers in a way such that no single computer will know the secret $s$, and all of them would have to collude (or be compromised) in order to reveal it.
### Commitment Process [Technical Walkthrough]
1. The first step of KZG is to perform a trusted setup to generate a common reference string. It is a multi party computation (MPC) to generate a secret such that as long as one party is honest, we can guarantee the randomness of the secret. For KZG, the common reference string is an array where each element is group element $G1$ multiplied by the secret to the power of $i$, and $i$ is from 0 up to the degree of the polynomial.
```rust=
/// KZG setup structure containing group elements and CRS.
pub struct KZGSetup<E: PairingEngine> {
g1: E::G1, // Group element G1
g2: E::G2, // Group element G2
g2_tau: E::G2, // Group element G2 multiplied by the secret
degree: usize, // Degree of the polynomial
crs_g1: Vec<E::G1>, // Common Reference String (CRS) for G1
crs_g2: Vec<E::G2>, // Common Reference String (CRS) for G2
}
impl<E: PairingEngine> KZGSetup<E> {
/// Creates a new KZG setup with provided G1, G2, and polynomial degree.
pub fn new(g1: E::G1, g2: E::G2, degree: usize) -> Self {
Self {
g1,
g2,
g2_tau: g2.mul(E::ScalarField::ZERO), // Initialize g2_tau as G2 * 0
degree,
crs_g1: vec![], // Initialize CRS for G1 as an empty vector
crs_g2: vec![], // Initialize CRS for G2 as an empty vector
}
}
/// Performs the trusted setup to generate the CRS.
/// The CRS is generated by multiplying G1 and G2 with the secret raised to the power of i,
/// where i ranges from 0 to the degree of the polynomial.
pub fn setup(&mut self, secret: E::ScalarField) {
for i in 0..self.degree + 1 {
self.crs_g1.push(self.g1.mul(secret.pow(&[i as u64]))); // Add G1 * secret^i to CRS for G1
self.crs_g2.push(self.g2.mul(secret.pow(&[i as u64]))); // Add G2 * secret^i to CRS for G2
}
self.g2_tau = self.g2.mul(secret); // Calculate g2_tau as G2 * secret
}
}
```
2. We commit the polynomial by multiplying the coefficients of the polynomial with the common reference string. The size of the commitment is just a group element of an elliptic curve group. For example, for the BLS12_381 curve (a pairing friendly elliptic curve), this is merely 48 bytes.
```rust=
impl<E: PairingEngine> KZGSetup<E> {
/// Commits to a polynomial by multiplying its coefficients with the CRS.
/// Returns the commitment as a single group element of G1.
///
/// # Arguments
/// * `poly` - A slice of the polynomial coefficients.
///
/// # Returns
/// * `E::G1` - The commitment to the polynomial.
pub fn commit(&self, poly: &[E::ScalarField]) -> E::G1 {
// Initialize the commitment to G1 * 0
let mut commitment = self.g1.mul(E::ScalarField::ZERO);
// Iterate over the polynomial coefficients up to the degree
for i in 0..self.degree + 1 {
// Add the product of CRS element and polynomial coefficient to the commitment
commitment += self.crs_g1[i] * poly[i];
}
// Return the computed commitment
commitment
}
}
```
3. When the prover would like to provide a proof that a particular point on the polynomial evaluate to a value, say point $f(a) = y$, the prover will provide the proof in the form of a quotient.
$$
π = [q(x)]₁ = [ (f(x) - y) / (x - a) ]₁
$$
> We use the square bracket as the notation to represent the commitment, meaning that the quotient has to be multiplied by the common reference string generated in the trusted setup. The number one indicates that we use the common reference string generated using the $G1$ group element.
```rust=
pub fn open(&self, poly: &[E::ScalarField], point: E::ScalarField) -> E::G1 {
// evaluate the polynomial at point
let value = evaluate(poly, point);
// initialize denominator
let denominator = [-point, E::ScalarField::ONE];
// initialize numerator
let first = poly[0] - value;
let rest = &poly[1..];
let temp: Vec<E::ScalarField> = std::iter::once(first).chain(rest.iter().cloned()).collect();
let numerator: &[E::ScalarField] = &temp;
// get quotient by dividing numerator by denominator
let quotient = div(numerator, &denominator).unwrap();
// calculate pi as proof (quotient multiplied by CRS)
let mut pi = self.g1.mul(E::ScalarField::ZERO);
for i in 0..quotient.len() {
pi += self.crs_g1[i] * quotient[i];
}
// return pi
pi
}
```
4. To verify the proof, the verifier computes the bilinear pairing (as detailed above). Looking at the equation below, we can see that the left hand side is a pairing between the proof (which is in group element $G1$), and the difference between the secret and point to be evaluated (in group element $G2$). The right hand side is the difference between the polynomial and the evaluated point (in group element $G1$), paired with the group element $G2$. Essentially, it is to verify that $q(s) * (s-a)$ is equal to$ f(s) — y$, which is the same equation that we used to generate the proof, except we substitute the unknown variable x with the secret generated through the trusted setup, s.
$$
e(π,[s−a]2)=e([f(x)]1−[y]1,G2)
$$
```rust=
impl<E: PairingEngine> KZGSetup<E> {
/// Verifies a proof for a polynomial commitment.
///
/// # Arguments
/// * `point` - The point at which the polynomial is evaluated (a in the context).
/// * `value` - The claimed value of the polynomial at the given point (f(a)).
/// * `commitment` - The commitment to the polynomial.
/// * `pi` - The proof of the evaluation.
///
/// # Returns
/// * `bool` - Returns true if the proof is valid, false otherwise.
///
pub fn verify(
&self,
point: E::ScalarField,
value: E::ScalarField,
commitment: E::G1,
pi: E::G1
) -> bool {
// Compute the left-hand side pairing: pairing(proof, g2_tau - g2 * point)
let lhs = E::pairing(pi, self.g2_tau - self.g2.mul(point));
// Compute the right-hand side pairing: pairing(commitment - g1 * value, g2)
let rhs = E::pairing(commitment - self.g1.mul(value), self.g2);
// Check if both pairings are equal
lhs == rhs
}
}
```
---
*this was my submission article for the [EPF4](https://github.com/eth-protocol-fellows/protocol-studies), it was earlier published on my personal notion, but I'm moving all my study / educational notes to here now!*
Sign in with Wallet
Connect another wallet