# Implementing KZG Commitment Scheme By [CleanPegasus](https://paragraph.com/@cleanpegasus-2) · 2024-07-23 --- 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. What is a commitment? --------------------- 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). ### Polynomial 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. ### Advantages of KZG Commitment * **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. Implementation -------------- This implementation assumes prior knowledge of finite fields and elliptic curves. I highly recommend Rareskill’s articles on [Finite Field](https://www.rareskills.io/post/finite-fields) and [Elliptic Curves](https://www.rareskills.io/post/elliptic-curve-addition) 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](https://medium.com/p/a18bf8ec057a/edit) if you are interested. It’s pretty straightforward. You can find the Github repository [here](https://github.com/CleanPegasus/kzg-commitment-python). ### **Imports and initializing the finite field** 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) ### **Generating trusted setup** 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)]) ### **Vector to Polynomial using Lagrange Interpolation** 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`. ![Lagrange interpolation of p(x)](https://storage.googleapis.com/papyrus_images/9dadb56cefd5f54aa93e3c22d4399b58547cede4eb0910f6e699c1e97b173e84.png) Lagrange interpolation of p(x) 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) ### **Committing the polynomial** 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. #### **Hiding** 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. #### **Binding:** 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. ### Generating Proof > _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. ![](https://storage.googleapis.com/papyrus_images/71f7c5416b0aa26bf37f83feb3a0959ae1d5754051bcd34bea90909994cae73c.png) 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) ### Verify Proof 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 to`y’`, 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. ### KZG Commitment Test 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) About me -------- I’m a blockchain engineer with an interest in cryptography and zero knowledge proofs. Hit me up on [Twitter](https://x.com/CleanPegasus) if you want to chat about blockchains or zero knowledge proofs. --- *Originally published on [CleanPegasus](https://paragraph.com/@cleanpegasus-2/implementing-kzg-commitment-scheme)*