KZG Commitment (aka Kate Polynomial Commitment) is a polynomial commitment scheme that allows a prover to compute a commitment to a polynomial such that it can be opened later at any position.

A commitment is a technique that allows one party to commit to a chosen value while keeping it hidden from others, with the ability to reveal the committed value later. A commitment has two properties:

1. Binding: The value cannot be changed once it is committed

2. Hiding: The value cannot be known until it’s revealed.

Hashing is an example of a commitment scheme. Once a value is hashed (committed), it cannot be changed, and the value cannot be known from the hash (commitment).

A polynomial commitment lets a prover commit to a polynomial p(x)and later prove a point (X, Y) to a verifier such that p(X) = Y without revealing the polynomial itself.

E.g.: You can commit a polynomial p(x) = x^3 -6x^2 + 11x -6 and later prove that p(1) = 0 without revealing the polynomial.

• Constant-sized commitment and proof: The commitment to the polynomial and the proof are constant regardless of the polynomial’s size. Even a polynomial with degree 2⁵⁰ will have the same commitment and proof size as a polynomial with degree 2¹. This helps with scalability, reducing the amount of data that needs to be transmitted and verified.

• Efficient proof verification: Since the commitment and the proof are constant, the proof verification is also very efficient with only a few operations.

• Aggregate multiple proofs: KZG commitments support the aggregation of multiple proofs into a single one. eg: you can prove (X_1, Y_1), (X_2, Y_2).....(X_N, Y_N) lies on the polynomial p(x) with a single proof.

Because of these advantages, KZG commitments are employed in verkle trees (vector commitment + Merkle Tree), Ethereum’s proto-danksharding and Scroll’s proving system. I’m currently working on an article on implementing verkle trees. So stay tuned.

This implementation assumes prior knowledge of finite fields and elliptic curves. I highly recommend Rareskill’s articles on Finite Field and Elliptic Curves if you are not familiar with these concepts.

I will not dive too deep into the math behind KZG commitment. I highly recommend Dankrad Feist’s article if you are interested. It’s pretty straightforward.

You can find the Github repository here.

This implementation uses the BLS12-381 curve.

We initialize the KZGCommitment class by setting the curve order of the BLS12–381 as the field modulus of our finite field (GF).

import galois
from py_ecc.bls12_381 import G1, G2, G12, add, multiply, curve_order, pairing, eq, neg, Z1
import random
from functools import reduce

class KZGCommitment:
    def __init__(self, curve_order, trusted_setup_degree = 10):
        print("Initializing Galois Field with BLS12_318 curve order. This may take a while.")
        self.GF = galois.GF(curve_order)
        print("Galois Field Initialized")
        (self.trusted_setup_g1, self.trusted_setup_g2) = self.generate_trusted_setup(trusted_setup_degree)

A one-time trusted setup has to be performed before computing KZG commitments. We pick a random element τ ∈ Finite Field. We compute [τ⁰ * G1, τ¹ * G1, τ² * G1,….. τ^n * G1] and [τ⁰*G2, τ¹*G2, τ²*G2,……τ^n * G2] where G1 and G2 are the generator points of the BLS12–381 curve.

Note that τ here is toxic waste. It needs to be discarded. If a prover knows τ, they can generate valid proofs for invalid values.

Ideally, this needs to be computed via multi-party computation (MPC). For the sake of simplicity, we will generate the trusted setup inside our class.

# generate [tau^i * G1] and [tau^i * G2]
def generate_trusted_setup(self, degree):
  print("Generating trusted setup")
  tau = self.GF(random.randint(1, curve_order))
  return ([multiply(G1, int(tau ** i)) for i in range(degree + 1)], [multiply(G2, int(tau ** i)) for i in range(degree + 1)])

As mentioned above, KZG commitment is a polynomial commitment scheme. In that case, how can we commit to a list of values? We use a simple math trick called Lagrange interpolation.

Lagrange interpolation takes a set of points and returns a polynomial that passes through all these points. If you have a list [10, 20, 30] , you can pass the points (0, 10), (1, 20), (2, 30) . The resulting polynomial p(x) will be such that p(0) = 10, p(1) = 20 and p(2) = 30.

Note that the Lagrange interpolation is computed here in a finite field to avoid precision errors.

# interpolate the given points to return a galois polynomial
def lagrange_interpolation_galois(self, xs, ys):
  assert len(xs) == len(ys), "Length mismatch"
  length = len(xs)

  def pi(j, y):
      p_result = self.GF(1)
      for k in range(length):
          if k == j:
              continue
          q, _ = divmod(galois.Poly([self.GF(1), -xs[k]], self.GF), (xs[j] - xs[k])
          p_result = p_result * q
      return y * p_result

  result = self.GF(0)
  for i in range (length):
      result = result + pi(i, ys[i])

  return result


# convert an integer to a finite field value
def convert_int_to_gf(num):
  if num < 0:
    return -GF(-num)
  else:
    return GF(num)

# lagrange interpolation to convert vector to a galois polynomial
def vector_to_polynomial(vector):
  xs = [convert_int_to_gf(i) for i in range(len(vector))]
  vector_gf = [convert_int_to_gf(x) for x in vector]
  return lagrange_interpolation_galois(xs, vector_gf)

A polynomial evaluated at the trusted setup is its commitment.

Commitment C = [p(τ)]₁

eg: Commitment to polynomial p(x) = x^3 -6x^2 + 11x -6 would be

C = [p(τ)]₁ = τ³G1– 6 * τ²G1 + 11 * τG1–6*G1

def evaluate_at_trusted_setup(self, polynomial, trusted_setup):
    trusted_setup = trusted_setup[:polynomial.degree + 1]
    return reduce(add, (multiply(point, int(coeff)) for point, coeff in zip(trusted_setup, polynomial.coeffs[::-1])), Z1)

def commit_polynomial(self, polynomial):
    return self.evaluate_at_trusted_setup(polynomial, self.trusted_setup_g1)

Let’s see if our commitment scheme has both binding and hiding properties.

If you notice closely, you can see that our commitment is a G1 elliptic curve point. It’s common knowledge that you cannot find the discrete logarithm of an elliptical curve point. So our polynomial cannot be revealed from the commitment.

Before we dive into the binding property of our commitment scheme, I want to introduce you to the Schwartz-Zippel lemma.

Schwartz–Zippel lemma

Any two polynomials can intersect each other at most d points where d is the degree of the larger polynomial. If you have polynomials p(x) with degree 10 and q(x) with degree 3, these two polynomials will intersect at most 10 different points.

For a polynomial commitment to be binding, once the prover has committed to a polynomial,p(x) he should not be able to change the polynomial to q(x). Therefore, [p(τ)]₁!= [q(τ)]₁.

Since the prover does not know τ (note that the prover only knows [τ]₁, [τ²]₁, [τ³]₁, etc.; they do not know the scalar value τ), for [q(τ)]₁ to have a high probability of being equal to [p(τ)]₁, both of these polynomials have to intersect at as many places as possible. But we know from the Schwartz-Zippel lemma that two polynomials can intersect at most d points, where d is the degree of the larger polynomial.

Suppose we have 2 polynomials with degrees 2²⁰. These polynomials will intersect at at most 2²⁰ points. The curve order of our BLS12–381 curve is ~2²⁵⁶. The probability of collision here is 2²⁰ / 2²⁵⁶= ~0.

Thus, our KZG commitment scheme is binding.

A polynomial is divisible by (x-z) if it has a root at z . The converse is also true. If a polynomial has a root at z it is divisible by (x — z) . Let’s look at an example. Take the polynomial p(x) = x³ — 6x² + 11x — 6. One of the roots of this polynomial is 3. When you simplify this polynomial, you get p(x) = (x — 1)(x — 2)(x — 3). As you can see it is divisible by (x — 3).

We need to prove a point (z, y) exists on the polynomial such that p(z) = y . We can see that p(x) — y is 0 at z. This means p(x) — y is divisible by (x — z).

$q(x) = p(x) - y / (x - z)$

The proof π of (z, y) in polynomial p(x) is the evaluation of q(x) at [τ]₁.

π = [q(τ)]₁

Let's go a little further and see how we can prove multiple points with a single proof.

Given the points (z_0, y_0), (z_1, y_1),……(z_n, y_n)such that p(z_i) = y_i we first compute a polynomial I(x) that passes through all these points using Lagrange interpolation.

The polynomial p(x) — I(x) is 0 at z_0, z_1, z_2,.... z_n. Therefore, it must be divisible by (x — z_0)(x — z_1)(x — z_2)....(x — z_n).

$z(x) = (x - z_{0})(x - z_{1})(x - z_{2})……(x - z_{n})$

$q(x) = p(x) - I(x) / z(x)$

The proof π of (z_0, y_0), (z_1, y_1),……(z_k-1, y_k-1) in polynomial p(x) is the evaluation of q(x) at [τ]₁.

π = [q(τ)]₁

# generate a proof for a given set of point
def generate_proof(self, polynomial, points):
  x_s = [self.convert_int_to_gf(x) for x, y in points]
  y_s = [self.convert_int_to_gf(y) for x, y in points]

  points_polynomial = self.lagrange_interpolation_galois(x_s, y_s)
  numerator = polynomial - points_polynomial
  denominator = self.GF(1)
  for x in x_s:
      denominator = denominator * galois.Poly([self.GF(1), -x], self.GF)

  q, r = divmod(numerator, denominator)
  assert r == 0, "This is not a valid proof."

  return self.evaluate_at_trusted_setup(q, self.trusted_setup_g1)

We have our commitment C = [p(τ)]₁ and proof π = [q(τ)]₁. The verifier needs to check the below pairing.

$$e(\pi, [Z(\tau)]{2}) = e(C - [I(\tau)]{1}, G2)$$

The proof essentially checks the below equation with pairing.

$\pi * z(\tau) = p(\tau) * I(\tau)$

$p(\tau) - I(\tau) / z(\tau) * z(\tau) = p(\tau) - I(\tau)$

# Verify proof
def verify_proof(self, commitment, points, proof):
  x_s = [self.convert_int_to_gf(x) for x, y in points]
  y_s = [self.convert_int_to_gf(y) for x, y in points]
  points_polynomial = self.lagrange_interpolation_galois(x_s, y_s)

  z = galois.Poly([1], self.GF)
  for x in x_s:
      z = z * galois.Poly([self.GF(1), -x], self.GF)
  z_s = self.evaluate_at_trusted_setup(z, self.trusted_setup_g2)
  lhs = pairing(z_s, proof)
  i_s = self.evaluate_at_trusted_setup(points_polynomial, self.trusted_setup_g1)
  rhs = pairing(G2, add(commitment, neg(i_s)))
  print("isProofValid: ", eq(lhs, rhs))
  assert eq(lhs, rhs), "The proof is invalid."

A good proof mechanism has two properties.

• Correctness: If the prover follows the defined steps, they should be able to produce a valid proof. This is evident from the above equation.

• Soundness: A prover cannot provide incorrect proof as valid proof.

If a prover wants to provide an invalid proof p(z) = y' where p(z) is not equal toy’, he needs to divide p(x) — y' by (x-z) without a remainder. But this division is clearly not possible since p(z) != y' .

Let’s try to create a fake proof from our verification equation.

$\pi * z(\tau) = p(\tau) * I(\tau)$

$\pi = p(\tau) * I(\tau) / z(\tau)$

To provide a fake proof, the prover has to know the scalar value of τ so he can change z(x) such that it will create a valid proof. Since the prover does not know τ, it is impossible to create a fake proof.

Thus, our proof is both correct and sound.

Now that we have completed all parts of our commitment scheme (commitment, proof generation, and verification), let’s test it on a list of values.

The below code commits a vector [10, 20, 36, 50, 90] as a polynomial using KZG commitment scheme. We create a proof for two points (0, 10), (1, 20) and verify if the proof is valid.

if __name__ == '__main__':
    kzg = KZGCommitment(curve_order)
    vector = [10, 20, 36, 50, 90]  # example vector
    print("Commiting Vector: ", vector)
    polynomial = kzg.vector_to_polynomial(vector)
    commitment = kzg.commit_polynomial(polynomial)
    points = [(0, 10), (1, 20)]  # element 10 at index 0 and element 20 at index 1
    proof = kzg.generate_proof(polynomial, points)
    print("Proof: ", proof)
    kzg.verify_proof(commitment, points, proof)

I’m a blockchain engineer with an interest in cryptography and zero knowledge proofs. Hit me up on Twitter if you want to chat about blockchains or zero knowledge proofs.