The KZG/Kate Polynomial Commitment Scheme

Commitment schemes are fundamental components of many cryptographic protocols. A secure commitment scheme allows a committer to publish a value, called the commitment, which binds her to a message (binding) without revealing it (hiding). Later, she may open the commitment and reveal the committed message to a verifier, who can check that the message is consistent with the commitment.

Consider the following scenario.

• Peggy wants to commit to a message $m$. To do so, she writes down $m$ on a piece of paper, puts it in a box, and locks it using a padlock.

• Peggy gives the box to Victor.

• If Peggy wants to, she can later open the commitment by giving Victor the key to the padlock.

There are two basic properties here, which are essential to any commitment scheme:

• Having given away the box, Peggy cannot anymore change what is inside. Hence, when the box is opened, we know that what is revealed really was the choice that Peggy committed to originally. This is called the Binding property.

• When Victor receives the box, he cannot tell what is inside before Peggy decides to give him the key. This is called the Hiding property.

Polynomials are frequently used in cryptography because they can be used to encode a lot of information. A Polynomial Commitment Scheme (PCS) allows the committer to commit to a polynomial with a commitment string that can be used by a verifier to confirm claimed evaluations of the committed polynomial. We will look at one such PCS called KZG (Kate, Zaverucha, Goldberg). It’s also referred to as the Kate Commitment Scheme.

Pre-requisite topic before we discuss the KZG PCS

Elliptic Curve Pairings

If you are not familiar with pairings, I have given a small introduction to Pairings as part of this post - Weil Pairing and the MOV attack on Elliptic Curve Cryptography.

KZG Commmitment Scheme

Let $F(x)\in \mathbb F_p$ be the polynomial which needs to be committed. $F(x)$ is a polynomial of degree $d$ or less.

$\mathbb G$ is an Elliptic Curve group of order $p$ with a generator $G$. The Discrete Logarithm assumption & d-Strong Diffie Hellman assumption hold in the group $\mathbb G$.

Trusted Setup

The first stage of the commitment scheme is a trusted setup. During the trusted setup, a random value $a \in \mathbb F_p$ is sampled. Then the following tuple of size $d+1$ known as the Reference String is generated - $\lbrace G, aG,a^2G, a^3G, …, a^dG \rbrace$. After generating the tuple, the random value $a$ is deleted such that it’s not known to anyone.

Commitment

Let’s denote the commitment of the polynomial $F(x)$ at $x=a$ as $C_{F_a}$ where

$C_{F_a} = F(a)\cdot G$ where $F(a)$ is the polynomial evaluated at $x=a$.

Though $a$ has been deleted, the committer can stil compute the commitment using the Reference String.

Let $F(x) = f_0 + f_1x + f_2x^2 + … + f_dx^d$

$F(a) = f_0 + f_1a + f_2a^2 + … + f_da^d$

So $C_{F_a} = F(a)\cdot G = (f_0 + f_1a + f_2a^2 + … + f_da^d)\cdot G$

$C_{F_a} = f_0\cdot G + f_1a\cdot G + f_2a^2\cdot G + … + f_da^d\cdot G$

Though the committer doesn’t know $a$, she knows $\lbrace G, aG,a^2G, a^3G, …, a^dG \rbrace$ from the reference string & can evaluate $C_{F_a}$ & evaluate the commitment. The committer sends the commitment to the verifier.

Since $G$ is a generator of the Elliptic Curve group $\mathbb G$, the commitment is a point on the Elliptic Curve.

The Hiding property of the commitment is based on the Discrete Logarithm problem being hard in $\mathbb G$

Full Open & Verify

In a full open, the committer sends the polynomial to the verifier & the verifier can use the reference string & compute the commitment himself & verify if it matches with the commitment sent originally by the committer. The Binding property of the commitment is based on the d-Strong DH assumption in $\mathbb G$. It can be shown that if a committer can output two polynomials that have the same commitment, then he can also use that to solve the d-Strong DH problem.

Partial Open or Evaluation Proof

In KZG, committer can also do a partial open (i.e. evaluation at a single value) which is called as the Evaluation Proof.

The verifier sends a value $b \in \mathbb F_p$ to the committer. The committer evaluates the polynomial $F(x)$ at $x=b$ as $F(b) = c$ & sends $c$ to the verifier. The committer also has to provide a proof to the verifier that $F(b) = c$.

The proof which the committer provides to the verifier is the commitment of the Quotient Polynomial $Q(x)$ at $a$ i.e. $C_{Q_a}$

$Q(x)$ is defined as

$Q(x) = \frac {F(x) - F(b)} {x-b} = \frac {F(x) - c} {x-b}$

As per Little Bezout’s Theorem, if $F(x)$ is a polynomial, then $F(x) - F(b)$ is perfectly divisible by $(x-b)$ i.e. the remainder is $0$. So $Q(x)$ above is a polynomial i.e. it won’t have any variable in the denominator or any negative exponents. Since $Q(x)$ is a polynomial, then the committer can calculate the commitment of $Q(x)$ using the Reference String as

$C_{Q_a} = Q(a)\cdot G$ (Note that this is the commitment of $Q(x)$ at $x=a$ & not at $x=b$)

If $F(x)$ weren’t perfectly divisible by $(x-b)$, then $Q(x)$ would have a denominator & negative exponents & the commiter wouldn’t be able to evaluate it using just the Reference String & without knowing $a$.

The committer sends $C_{Q_a}$ to the verifier as the Evaluation Proof.

Verifying

A commitment scheme is said to be complete if anything which is true is provable. It is said to be sound if everything which is provable is true - i.e. anything which is false cannot be proven by the scheme.

The verifier has $C_{F_a}$, $C_{Q_a}$ & $c$. He needs to verify that $F(b) = c$

$Q(x) = \frac {F(x) - c} {x-b}$

So,

$(x-b)\cdot Q(x) = F(x) - c$

If you evaluate this at $x = a$, it becomes

$(a-b)\cdot Q(a) = F(a) - c$

Multiplying both sides by the generator $G$, we get

$(a-b)\cdot Q(a)\cdot G = F(a)\cdot G - c\cdot G$

Now, $C_{F_a} = Q(a)\cdot G$ & $C_{Q_a} = F(a)\cdot G$. So substituting, we get

$(a-b)\cdot C_{Q_a} = C_{F_a} - c\cdot G$

If the verifier is able to verify that the above equality holds good, then he has verified the commitment. But since the verifier doesn’t know the value of $a$, he cannot directly verify if this equality holds good.

However, the verifier can use Elliptic Curve Pairings to verify even without knowing $a$. The pairing is denoted by the map

$e:\space \mathbb G$ X $\mathbb G \mapsto \mathbb G_T$

This is the equality to check

$(a-b)\cdot C_{Q_a} \stackrel {?}{=} C_{F_a} - c\cdot G$

Each input to the pairing map needs to be an element of the Group. Any commitment is a scalar multiple of the generator of the group, so both $C_{F_a}$ & $C_{Q_a}$ are elements of $\mathbb G$. Since $C_{Q_a}$ is an element of the group, multiplying it with the scalar $a-b$ also will result in an element of the group. So $(a-b)\cdot C_{Q_a}$ is also an element of $\mathbb G$. $C_{F_a}$ & $c\cdot G$ are both elements of the group, so $C_{F_a} - c\cdot G$ is also an element of the group. So all the terms in the equality are group elements. So they can be inputs to the pairing map.

By passing the sides of the equality as the first parameter to the map & pass $G$ as the 2nd param for each side, we can turn the equality to be verified into

$e((a-b)\cdot C_{Q_a}, G) \stackrel {?}{=} e(C_{F_a} - c\cdot G, G)$

This still doesn’t help us because we don’t know $a$.

However, bilinearity property of the pairing map means that

$e(\alpha A,B) = e(A, \alpha B)$ if $\alpha$ is a scalar.

So we can rewrite it as

$e(C_{Q_a}, (a-b)\cdot G) \stackrel {?}{=} e(C_{F_a} - c\cdot G, G)$

Further simplifying

$e(C_{Q_a}, aG - bG) \stackrel {?}{=} e(C_{F_a} - c\cdot G, G)$

Though we don’t know $a$, we do know $aG$ from our Reference String. So now the verifier can check whether the above equality is true or not. Thus the Evaluation Proof is Complete i.e. if the commitment is true, then $F(a)=b$ is provable.

Since the group $\mathbb G$ is a group where the d-Strong Diffie Hellman assumption holds, it can be shown that the probability of the committer finding two tuples $<b, c, C_{Q_a}>$ & $<b’, c’, C_{Q’_a}>$ such that

$e(C_{Q_a}, aG - bG) = e(C_{Q’_a}, aG - b’G)$ is negligible. Thus the commitment scheme is Sound .i.e if the commitment is not true, then $F(a)=b$ is not provable.

Batch Mode

KZG commitments can also be opened & verified at multiple points using a single proof.

In the stand-alone opening, the committer evaluated $F(x)$ at $b \in \mathbb F_p$ as $F(b) = c$ & provided $c$ along with the proof to the verifier.

In batch mode, the verifier sends to the committer a set of values $B = \lbrace b_1, b_2, b_3, …, b_t \rbrace$ such that $t \lt d$, the committer evaluates $f(b_1) = c_1, f(b_2) = c_2, …, f(b_t) = c_t$ and constructs the set $C = \lbrace c_1, c_2, c_3, …, c_t \rbrace$.

Let $P(x) = (x-b_1)(x-b_2)…(x-b_t)$

Since the degree of $F(x)$ is $d$ & $t \lt d$, we can divide $F(x)$ by $P(x)$. Let the quotient of the division be $Q(x)$ & the remainder be $R(x)$ (Note that we aren’t saying here that $F(x)$ is divisible by $Q(x)$, so we have remainder here).

i.e. $F(x) = P(x) Q(x) + R(x)$

The committer computes $Q(x)$ & also the commitment for $Q(x)$ i.e. $C_{Q_a}$ & sends those also to the verifier along with the set $C$

The committer can also send $R(x)$ to the verifier. Alternately, the verifier can also find the polynomial $R(x)$ himself as shown below.

$F(x) = P(x) Q(x) + R(x)$ with $P(x) = (x-b_1)(x-b_2)…(x-b_t)$

For any $b_i \in B = \lbrace b_1, b_2, b_3, …, b_t \rbrace$, it’s pretty apparent that $P(x)$ is zero. & hence the middle term vanishes at all $b_i \in B$.

So for all $b_i \in B$, $F(x) = R(x)$

Since $F(b_i) = c_i$ for all $\lbrace b_i \in B, c_i \in C \rbrace$, likewise

$R(b_i) = c_i$ for all $\lbrace b_i \in B, c_i \in C \rbrace$

Since the degree of $Q(x)$ is $t$ & $R(x)$ is the remainder of dividing $F(x)$ by $Q(x)$, the degree of $R(x)$ is less than $t$. Since the verifier knows evaluation of $R(x)$ at $t$ points, he can find $R(x)$ using Lagrange’s Interpolation. So now $R(x)$ is known to the verifier.

The Verifier can also find the polynomial $P(x)$ which is

$P(x) = (x-b_1)(x-b_2)…(x-b_t)$

The Verifier also computes the commitments of $P(x)$ & $R(x)$

$C_{P_a} = P(a)\cdot G$

$C_{R_a} = R(a)\cdot G$

Now the verifier can verify the Batch Evaluation by doing the following steps.

1) Verifier checks if $F(b_i) \stackrel {?}{=} R(b_i)$ for all $b_i \in B$. The committer has provided the set $C$ which are the evaluations of $F(x)$ at all $b_i \in B$. And the verifier knows $R(x)$, so he can also evaluate $R(x)$ at all the $b_i \in B$. So he can verify if $F(b_i) \stackrel {?}{=} R(b_i)$ for all $b_i \in B$

2) The verifier has to verify that the following equality holds

$F(x) \stackrel {?}{=} P(x) Q(x) + R(x)$

$F(x) - R(x) \stackrel {?}{=} P(x) Q(x)$

Multiply both sides by the generator $G$

$F(x)\cdot G - R(x)\cdot G \stackrel {?}{=} P(x) Q(x)\cdot G$

Evaluate the above at $a$

$F(a)\cdot G - R(a)\cdot G \stackrel {?}{=} P(a) Q(a)\cdot G$.

$F(a)\cdot G$ is the committment of $F$ i.e. $C_{F_a}$. Likewise, 2 other terms above are also committments. So,

$C_{F_a} - C_{R_a} \stackrel {?}{=} P(a)\cdot C_{Q_a}$

The verifier needs to evaluate the above to verify the proof. However, since $a$ is unknown, he cannot evaluate $P(a)$. But like before, he can use pairings.

$C_{F_a}$ & $C_{R_a}$ are both elements of $\mathbb G$, so $C_{F_a} - C_{R_a}$ is also an element of $\mathbb G$

$C_{Q_a}$ is an element of $\mathbb G$ & $P(a)$ is a scalar. So $P(a)\cdot C_{Q_a}$ is also an element of $\mathbb G$.

So we can apply the pairing map to both sides

$e(C_{F_a} - C_{R_a}, G) \stackrel {?}{=} e(P(a)\cdot C_{Q_a}, G)$

Note that $P(a)$ is a scalar here.And the bilinearity property of the pairing map means that

$e(\alpha A,B) = e(A, \alpha B)$ where $\alpha$ is a scalar.

So, we can rewrite the Right Hand Side as

$e(C_{F_a} - C_{R_a}, G) \stackrel {?}{=} e(C_{Q_a}, P(a)\cdot G)$

$C_{P_a}= P(a).G$, so

$e(C_{F_a} - C_{R_a}, G) \stackrel {?}{=} e(C_{Q_a}, C_{P_a})$

The verifier knows all the terms of this pairing & can evaluate to the check if the equality holds or not. Which proves the completeness of the Batch Evaluation Proof. The soundness can also be proven based on the Bilinear version of the d-Strong Diffie-Hellman assumption.

One of the advantages of the KZG PCS is that the commitment size is constant. Irrespective of how long the polynomial is (i.e. degree of the polynomial), the commitment is always just one element of the group $\mathbb G$. Likewise, the evaluation proof is also a commitment, so there again, the size is constant for the evaluation proof both at a single value and also in batch mode.

Written on January 24, 2023