Introduction to Polynomial Commitment Schemes (PCS)
Polynomial commitment schemes (PCS) are at the core of proof systems.
They determine key properties such as proof size, verification time, and whether the system is post-quantum secure.
The Kate-Zaverucha-Goldberg (KZG) is a popular PCS, first appearing in 2010.
Learn more:
Polynomial commitment schemes allow us to commit to a polynomial via a short string and prove things about it, mostly evaluations of the polynomial at points of the verifier’s choice.
They have two key properties:
• Hiding: the commitment does not reveal anything about the polynomial.
• Binding: given a commitment to a polynomial p, it is infeasible to find another polynomial q such that the commitment to q is equal to the commitment to p.
A PCS consists of the following three algorithms:
Setup: produces the public parameters needed for producing commitments and verifying them.
Commit: given a polynomial and parameters, the algorithm outputs a short string to p (for example, a hash or a point over an elliptic curve).
Evaluate/Open: a protocol between a prover and a verifier, where the prover tries to convince the verifier that the committed polynomial evaluates to v at a point z.
The KZG commitment works over pairing-friendly elliptic curves, such as BN254 or BLS12-381. We need to generate a set of trusted parameters consisting of the powers of a secret number s, hidden inside a group/subgroup of the curve where the discrete log problem (DLP) is hard.
The secret numbers cannot be known, as this will allow the creation of false proofs!
We call this collection of points the structured reference string (SRS).
Given generators of the subgroups G1 and G2 of the curve, called g1 and g2, the SRS takes the form g1, s.g1, s^2.g1, s^3.g1, … , s^n.g1 and g2, s.g2 (typically, we only need these points from G2 for most cases).
Each element is a point of the elliptic curve.
For the BN254 curve, each point takes 64 bytes (32 for the x and y components), but we can compress them to just 32 bytes!
The commitment to a polynomial is its evaluation at the point s, multiplied by the generator of the subgroup. This is computed using the SRS in an operation called multiscalar multiplication (MSM).
The MSM is one of the key operations that has been the subject of optimization and hardware acceleration, as it is the bottleneck of many proof systems based on KZG.
Knowing the commitment reveals nothing, as any other party would have to break the DLP.
To prove evaluations, we use the fact that if a polynomial p(x) evaluates to v at z, then p(x) - v is divisible by (x - z). In other words, there is a polynomial q(x) such that q(x)(x - z) = p(x) - v.
The prover has to compute that quotient and commit to it. Using the elliptic curve pairing, the verifier can check the equality at the secret point s. If the check passes, then with overwhelming probability p(z) = v (thanks to the Schwartz-Zippel lemma).
This means that both commitments and evaluation proofs are short. Moreover, to check evaluations, we only need one pairing check (two Miller loops and one exponentiation).
KZG commitments are additively homomorphic, which means that if we have the commitments to p(x) and q(x), we can compute the commitment to a linear combination of p(x) and q(x).
The homomorphic property is important for batching: We can show that polynomials p1(x), p2(x), … pn(x) evaluate to values v1, v2, … vn with one short evaluation proof and one pairing check instead of n!
Many protocols use this trick to significantly reduce proof sizes.
Do you want to try your knowledge of KZG further?
Try solving the following puzzle from LambdaClass!
Stay tuned: 🐦 Twitter | 🗨️ Telegram | 👾 Discord | 🌐 Website | 🌌 Galxe | 📝 Manifesto
