This is based on June’s IFT ZK Call. Visit the IFT ZK Meeting Notes for additional resources, and the video can be viewed on YouTube.
What are polynomial commitments?
Commitment schemes are a crucial cryptographic primitives that can be used to hide data while providing assurances that the underlying data cannot be altered. Specifically, a commitment:
- Is a compressed representation of data.
- Binds the data: impossible to find two pieces of data that have the same commitment.
- Hides the data: given two commitments and a claimed data, an observer cannot do better than a 50-50 guess which commitment corresponds to the data.
Polynomial commitments are an extension of commitment schemes. Polynomial commitments have an additional requirement: ability to prove evaluations. Specifically, given a polynomial commitment \mathcal{C}, for some secret polynomial f, the Prover can provide a claimed evaluation y and proof for any v.
Why polynomials?
Proofs are generated based on a specific circuit assignments. These circuits can be represented as an array of numbers. Arrays are really nice structures and simple structures. Given this, why would we want to represent data as polynomials instead of arrays? Demonstrating that two arrays are distinct illustrates the use of polynomials.
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| A | B | C | D | E | G |
To identify an entry that the two arrays differ at, a user has to systematically check each entry in the arrays until the difference is located. In our example arrays, this requires exhausting the entire array.
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| A | B | C | D | E | G |
In general, this takes O(N) for arrays of length N.
We can probabilistically, try to address this problem. A user can query both arrays at a single location: if the entries match then the user accepts the arrays are the same; if the entries are different then the user declares that the arrays are distinct.
Despite these two arrays being different, a user that selects a location at random would likely (5/6) determine that the arrays are the same. This renders a single query approach for determining whether arrays are distinct unsuitable.
However, we can generate an associated polynomial (multilinear extension) for an array. By doing this, we translate the question of whether two arrays are different to whether two polynomials are different.
Suppose that the polynomials are defined over the finite field \mathbb{F}. A single query of two distinct polynomials with degree d are the same with probability at most d/|\mathbb{F}|. Moreover, the probability that the query are different (for distinct polynomials) is (|\mathbb{F}|-d)/|\mathbb{F}|.
The multilinear extension of an array with N entries has total degree d = \log(N).
Where are PCSs used?
Polynomial commitment schemes are a crucial component to universal SNARKs. A universal SNARK allows for a single setup of the SNARK’s public parameter to be used across a variety of circuits. This is facilitated by the use polynomial commitments.
Examples of PCSs
Merkle tree
A Merkle tree can be used as a PCS. To do this, each point of a given domain corresponds with a leaf in the Merkle tree.
A Merkle tree for the polynomial f, the hash of the evaluation f(v) is stored in leaf v. The root hash of this tree is the polynomial commitment.
The key aspect of a polynomial commitment is its ability to prove evaluations. This is done by the Prover providing the evaluation f(v) and the Merkle proof for leaf v. The Verifier can use this to verify that f(v) is indeed the correct evaluation at v.
Merkle trees have some key drawbacks though: lack of homomorphic support and the Prover has to evaluate the polynomial over each domain point.
KZG Polynomial Commitment
Before we provide a brief overview of KZG, we have a brief digression into Pedersen commitments. Pedersen commitments serve as a basis for KZG.
Pedersen commitments rely on a group \mathbb{G} over a finite field \mathbb{F} with prime order p. Given a fixed list of group elements G_1,\dots, G_n \in \mathbb{G}. We can commitment to a list of numbers v_1,\dots, v_n \in \mathbb{F} as a single group element \mathcal{C} = v_1 \cdot G_1 + v_2 \cdot G_2 + \cdots + v_n \cdot G_n.
To maintain the binding property for commitments, it is essential that the group elements G_1,\dots, G_n have no relationship among each other. In practice, this is done through multiparty computations that guarantees that the inclusion of a single honest user prevents the existence of any trapdoors.
If a relation is known among the elements, then another list of numbers can be generated with the same commitment. For example, suppose that G_2 = t \cdot G_1. We
\mathcal{C} = v_1 \cdot G_1 + v_2 \cdot G_2 + \cdots + v_n \cdot G_n
= (v_1-st)\cdot G_1 + (v_2+s)\cdot G_2 +\cdots + v_n \cdot G_n
Now, we provide an overview of KZG (Kate-Zaverucha-Goldberg). KZG is a polynomial commitment that uses Pedersen commitment to commit to the coefficients. Specifically, the polynomial f(X) = a_0 + a_1 X + a_2 X^2 + \cdots + a_d X^d
has a commitment \mathcal{C} = a_0 \cdot G_0 + a_1 \cdot G_1 + \cdots + a_d \cdot G_d.
KZG relies on a certain structure of the elements G_0,\dots, G_d. Specifically, G_i = \alpha^i \cdot G_0. To ensure that a relationship between elements are not known, it is essential that \alpha is not known by any party.
The key aspect of a polynomial commitment scheme requires a method for proving an evaluation. KZG uses clever use of “basic algebra” and elliptic curve pairings.
The remainder theorem, tells us f(X) - f(v) = q(X)\cdot(X-v). Moreover, X-v divides f(X) - f(v). KZG relies on the Prover to commit to q(X) and provides the evaluations of f(v) and q(v) to the Verifier. So, the Verifier knows commitments:
- \mathcal{C} = a_0 \cdot G_0 + a_1 \cdot G_1 + \cdots + a_d \cdot G_d; commitment of f(X).
- \mathcal{D} = q_0 \cdot G_0 + q_1 \cdot G_1 + \cdots + q_{d-1} \cdot G_{d-1}; commitment of q(X).
- \mathcal{E} = G_1 - v\cdot G_0; commitment of X-v.
Pedersen commitment is additive homomorphic. KZG uses these with elliptic curve pairings to gain multiplication. This enables the Verifier to use the commitments \mathcal{C}, \mathcal{D}, \mathcal{E} to validate the equation f(\alpha) = q(\alpha) \cdot (\alpha-v) + f(v). For specifics of the verification process, a curious reader is recommended encouraged to check the KZG paper.
The crucial drawbacks of KZG: pairing based computations can be slow, trusted setup and not quantum resistant.