Building Trust with KZG Commitment: Understanding, Implementation, and Python Code Samples

Published in

cumberlandlabs

5 min readJun 4, 2023

KZG commitment, also known as the Kate-Zaverucha-Groth commitment scheme, is a cryptographic construction that allows binding a value to a commitment without revealing the value itself. It is based on polynomial commitments, which provide a way to commit to a polynomial function and later prove properties about the polynomial without revealing its coefficients.

Trust me. This is really difficult to understand, will try to keep it as simple as possible. Before progressing, ensure you understand polynomials, mod function, elliptic curves(point addition and doubling), and elliptic curve pairing. I will use some Python code snippets to explain how to achieve KZG commitment.

KZG Commitments

Per SalomonCrypto, KZG commitment can be divided into PCS Trusted Setup, Commit, Open, and Verify.

PCS Trusted Setup

PCS (Powers of Tau Ceremony Setup) Trusted Setup refers to generating the initial parameters used in the KZG commitment scheme. This setup phase is crucial for establishing the security and trustworthiness of the commitment scheme. During the PCS Trusted Setup, participants generate random values and perform a multi-party computation (MPC) protocol to combine their contributions. This process ensures that the final parameters result from a collective effort and that no single participant can influence the outcome.

Let’s consider a secret ‘S,’ generated at the start but destroyed at the end of the commitment. Once we have the ‘S,’ we must bind our curve to minimum and maximum bounds using modular arithmetic (log n). Next, we will use our (modular) elliptic curve and our secret (number) S to generate a series of values starting with S^o and ending with S^n. Now we have what we call Public Structure Reference String(SRS). Here, n equals our data points in the next step commit.

In our Python example, we can consider a random integer as a secret ‘S.’

def trusted_setup(length=default_length):
    s = rand_int(n)
    s_powers = [s**i%n for i in range(length)]
    return [j*G1 for j in s_powers], s*G2

where ‘G1’ and ‘G2' are the elliptic curve generator values.

But in actuality, we can get it using the Ethereum KZG-Ceremony repository. The contribution can be done using the following two authentication methods:-

Ethereum Wallet (From UI — https://ceremony.ethereum.org/#/)

Github

Check my contribution tweet here.

Commit

Hashing creates a unique, non-reversible fingerprint, but it has a problem: we can prove either true(1) or false(0). Therefore, we must use polynomial commitment to solve our problem statement, which starts with encoding our data in polynomial form.

Yes, you are thinking correctly. We can use Lagrange Interpolation to encode our data.

For example, if I want to encode my name ‘KUSH’ to points, I can use ASCII value and convert as follow.

These points can be used for a unique polynomial of degree 3, as we have learned in class 8th. If you have ’n’ non-collinear points, a polynomial of degree ‘n-1’ can be uniquely determined to pass through those points. This is known as Lagrange interpolation and is a specific case of polynomial interpolation.

def encode_as_polynomial(data, length=default_length):
    chunk_size=31
    data = __format_data(data, length*chunk_size)
    points = [(i,int(hexlify(data[i*chunk_size:(i+1)*chunk_size]).decode(), 16)) for i in range(length)]
    polynomial = lagrange_polynomial(points)
    return points, polynomial

def commit(polynomial, setup_g1):
    assert len(polynomial) == len(setup_g1), "polynomial too large"
    return sum([i1*i2 for i1, i2 in zip(polynomial, setup_g1)])

This creates a commitment as follows:-

f[s] = [a₀s⁰ + a₁s¹ + a₂s² ….. aₙsⁿ] = Σ (aᵢ sᶦ)

where aᵢ is the data point from the Lagrange theorem, and sᶦ is from the SRS and a point on the same elliptic curve we started from.

Open

Once the verifier has the commitment, they select a random point ‘z’ and send it to the prover.

Once the prover has z, they calculate the f[z] and h(s) as per the following formulae:-

h(x) = ( f(x) — f(z) ) / ( x — z )

To be on the same, h(x) is also on the same polynomial.

def proof(polynomial, point, setup_g1):
    assert len(polynomial)-1<=len(setup_g1), "polynomial too large"
    px_minus_y = [((n-1)*point[1]+polynomial[0])%n]+polynomial[1:]
    qx, remainder = polynomial_division(px_minus_y,(n-1)*point[0])
    assert remainder==0, "point not on polynomial"
    return sum([i1*i2 for i1, i2 in zip(qx, setup_g1[:len(qx)])])

Verify

Just need to verify e( [s-z], H ) = e( c — f(z), [1]); where e is the function for the elliptic pairing. The details can be checked here.


def verify(commitment,proof,point,s_g2):
    s_minus_x=(n-point[0])*G2+s_g2
    result=ate_pairing(proof, s_minus_x)
    c_minus_y=(n-point[1])*G1+commitment
    return result==ate_pairing(c_minus_y, G2)

Testing

import kzg
from polynomial import evaluate_polynomial

if __name__=='__main__':
    print("Trusted Setup!!")
    setup_g1, s_g2 = kzg.trusted_setup()
    print ("Setup_g1 ==> ", setup_g1)
    
    print("Data Commitment!!")
    data=b'\xff'*460 # Random Data!!
    points, poly = kzg.encode_as_polynomial(data)
    C = kzg.commit(poly, setup_g1)
    print ("Commitment ==> ", C)

    print("Open/Proof")
    point = (1, evaluate_polynomial(poly,1))
    assert points[1][0] == point[0], "xs should be equal"
    assert points[1][1] == point[1], "ys should be equal"
    pi = kzg.proof(poly, point, setup_g1)
    print ("Point (Z) ==> ", point)
    print ("Proof ==> ", pi)

    print("Verify")
    assert kzg.verify(C,pi,point,s_g2), "test fail: valid proof rejected"
    wrong_point=(point[1], point[0])
    assert not kzg.verify(C,pi,wrong_point,s_g2), "test fail: uncaught invalid proof"
    
    print("SUCCESS!")

Expected Output

Trusted Setup!!
Setup_g1 ==>  [JacobianPoint(x=Fq(0x17f1d..2c6bb), y=Fq(0x8b3f4..5e7e1)z=Fq(0x1), i=False)
, JacobianPoint(x=Fq(0x18690..cc9c6), y=Fq(0xdc7e7..efdb2)z=Fq(0x13953..9d637), i=False)
, JacobianPoint(x=Fq(0x53b8e..3d4a9), y=Fq(0xdbf23..897eb)z=Fq(0x16366..5ad94), i=False)
, JacobianPoint(x=Fq(0x3165b..4532f), y=Fq(0x18a7b..fe4cd)z=Fq(0x8299e..ceee8), i=False)
, JacobianPoint(x=Fq(0xc992d..67f0c), y=Fq(0x11283..2a51d)z=Fq(0x984f3..0b8fd), i=False)
, JacobianPoint(x=Fq(0xc1894..63adc), y=Fq(0x5b058..5c025)z=Fq(0x530bd..fa2ea), i=False)
, JacobianPoint(x=Fq(0x10047..5597c), y=Fq(0x5c0b4..65427)z=Fq(0xcbab6..418b5), i=False)
, JacobianPoint(x=Fq(0x13751..dbb55), y=Fq(0xe1417..a4e68)z=Fq(0x104ff..912de), i=False)
, JacobianPoint(x=Fq(0x821e5..31e46), y=Fq(0x1920b..2ce00)z=Fq(0xa5105..1a4aa), i=False)
, JacobianPoint(x=Fq(0xb1e35..464c8), y=Fq(0x1007c..18361)z=Fq(0x228b5..b5c10), i=False)
, JacobianPoint(x=Fq(0xcf456..511c8), y=Fq(0x123aa..e20c7)z=Fq(0x22703..760b2), i=False)
, JacobianPoint(x=Fq(0x13657..39cb0), y=Fq(0x19766..17e0c)z=Fq(0xa7348..4345b), i=False)
, JacobianPoint(x=Fq(0x11c30..53c52), y=Fq(0x2139d..77e4f)z=Fq(0x2529d..d3f97), i=False)
, JacobianPoint(x=Fq(0x1c9ab..d7106), y=Fq(0x17c5a..80aee)z=Fq(0x19183..29894), i=False)
, JacobianPoint(x=Fq(0x4a3c0..429cd), y=Fq(0x10745..7d00d)z=Fq(0x9e911..7f32e), i=False)
, JacobianPoint(x=Fq(0x193cc..120bd), y=Fq(0x11b8a..1d8ed)z=Fq(0x19d46..065e7), i=False)
]
Data Commitment!!
Commitment ==>  JacobianPoint(x=Fq(0xc8203..6dbf7), y=Fq(0x9930a..4fa66)z=Fq(0xf59d6..fc838), i=False)

Open/Proof
Point (Z) ==>  (1, 452312848583266388373324160190187140051835877600158453279131187530910662655)
Proof ==>  JacobianPoint(x=Fq(0x604d9..4017f), y=Fq(0x522d1..f2a98)z=Fq(0x169ac..b6036), i=False)

Verify
SUCCESS!

Let's Try Something Fishy

import kzg
from polynomial import evaluate_polynomial

if __name__=='__main__':
    print("Trusted Setup!!")
    setup_g1, s_g2 = kzg.trusted_setup()
    print ("Setup_g1 ==> ", setup_g1)
    
    print("Data Commitment!!")
    data=b'\xff'*460 # Random Data 1!!
    data111=b'\xf0'*460 # Random Data 2!!
    points, poly = kzg.encode_as_polynomial(data)
    points111, poly111 = kzg.encode_as_polynomial(data)
    C = kzg.commit(poly, setup_g1)
    print ("Commitment ==> ", C)

    print("Open/Proof")
    point = (1, evaluate_polynomial(poly,1))
    assert points[1][0] == point[0], "xs should be equal"
    assert points[1][1] == point[1], "ys should be equal"
    pi = kzg.proof(poly111, point, setup_g1)
    print ("Point (Z) ==> ", point)
    print ("Proof ==> ", pi)

    print("Verify")
    assert kzg.verify(C,pi,point,s_g2), "test fail: valid proof rejected"
    wrong_point=(point[1], point[0])
    assert not kzg.verify(C,pi,wrong_point,s_g2), "test fail: uncaught invalid proof"
    
    print("SUCCESS!")