Variants of KZG: Part I, Univariate

This is Part I of a five-part series on different variations of the KZG protocol. The original appeared on the ZK Security blog.

A polynomial commitment scheme (PCS) allows a prover to commit to a polynomial and later prove its evaluations at points chosen by the verifier. The verifier can then check that the evaluations are consistent with the committed polynomial. Most practical SNARKs (Succinct Non-interactive Arguments of Knowledge) are constructed using a PCS. It consists of the following three algorithms:

• $setup(d) \rightarrow pp$: Given an upper bound $d$ on the degree, it outputs public parameters $pp$ used to commit to polynomials of degree less than $d$.

• $commit(pp, f) \rightarrow com_f$: Takes public parameters $pp$ and a polynomial $f$ of degree $< d$, and outputs a commitment $com_f$ to the polynomial.

• $open(\mathcal{P}, \mathcal{V}) \rightarrow 0/1$: An interactive protocol where the prover $\mathcal{P}$ convinces the verifier $\mathcal{V}$ that $f(u) = v$. The verifier outputs 1 (accept) or 0 (reject).

Informally, two key properties of a PCS are:

• Binding: The prover $\mathcal{P}$ cannot lie about the evaluations of the polynomial they committed to.

• Hiding: A computationally bounded adversary should learn nothing about the polynomial from the commitment.

One of the most widely used PCS is KZG10, due to its constant proof size and verification time. It is used to construct various SNARKs such as Sonic and Plonk. In this post, we explore KZG variants for univariate polynomials. But first, let’s introduce some notation and preliminaries.

Notation and Preliminaries#

We denote $\mathbb{F}_p^{(< d)}[X]$ as the set of univariate polynomials in the variable $X$ of degree less than $d$, with coefficients in the prime field $\mathbb{F}_p$. For brevity, we sometimes omit the variable and write $f$ instead of $f(X)$. We use $[k]$ to denote the set of integers $\{1, \dots, k\}$.

We assume the existence of groups $(\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T)$ of appropriate security parameter $\lambda$, along with their generators $(G_1, G_2, G_T)$. We use additive notation for $\mathbb{G}_1$ and $\mathbb{G}_2$, and multiplicative notation for $\mathbb{G}_T$. For scalar multiplication, we define $[x]_1 := x \cdot G_1$ and $[x]_2 := x \cdot G_2$. These groups support a bilinear pairing operation:

An essential property of pairings is bilinearity, meaning that for scalars $a, b$ we have:

This is important because it allows us to multiply scalars in the exponent. This property is used in many constructions to enable the verifier $\mathcal{V}$ to perform consistency checks on the messages sent by the prover $\mathcal{P}$.

Polynomial Identities#

In this section, we introduce some foundational facts about polynomials that will be helpful in understanding the various constructions covered later.

For a polynomial $f \in \mathbb{F}_p^{(< d)}[X]$, the condition that $f$ evaluates to $v$ at point $u$ (i.e. $f(u)=v$) is equivalent to the statement that the polynomial $f(X)-v$ has a root at $u$ (i.e. $f(u)-v=0$). Thus, by factor theorem, $(X-u)$ is a factor of $f(X)-v$ i.e. the polynomial $f(X)-v$ is divisible by $(X-u)$. In other words, there exists a quotient polynomial $q(X)$ such that:

More generally, evaluating $f$ on a set $S$ (i.e., evaluating $f(u)$ for all $u \in S$) is equivalent to $f(X) - r(X)$ being divisible by $Z_S(X)$. That is, there exists a quotient polynomial $q(X)$ such that:

where $r \in \mathbb{F}_p^{(< |S|)}[X]$ such that $r(u) = f(u)$ for all $u \in S$, and $Z_S(X) = \prod_{u \in S}(X-u)$.

With the notation and preliminaries in place, we can now look at the first construction.

Plain KZG#

This is the most basic construction, as described in Section 3.2 of KZG10. The key idea is that after receiving a commitment $com_f$ to polynomial $f$, $\mathcal{V}$ needs to check whether $f(u)\stackrel{?}{=}v$. As discussed earlier, checking $f(u)\stackrel{?}{=}v$ is equivalent to checking that equation $(1)$ is valid.

If equation $(1)$ is valid at a random point then with high probability it is valid at all points (by the Schwartz-Zippel Lemma). In this setting, the random point is the secret value $\alpha$. Although $\mathcal{V}$ does not know $\alpha$, it can still verify the validity of equation $(1)$ at $\alpha$ using the commitments sent by $\mathcal{P}$ and the pairing operation.

The algorithms for the construction are defined as follows:

• $setup(d) \rightarrow pp$

  • Sample a random $\alpha \in \mathbb{F}_p$
  • $pp = \left( [1]_1, [\alpha]_1, \dots, [\alpha^{d-1}]_1, [1]_2, [\alpha]_2 \right)$
  • Discard $\alpha$

• $commit(pp, f) \rightarrow com_f$

  • $com_f = [f(\alpha)]_1 = f_0 \cdot [1]_1 + f_1 \cdot [\alpha]_1 + f_2 \cdot [\alpha^2]_1 + \dots + f_{d-1} \cdot [\alpha^{d-1}]_1$
    where, $f_0, f_1, f_2, \dots, f_{d-1}$ are coefficients of $f$.

• $open(\mathcal{P}, \mathcal{V}) \rightarrow 0/1$

  • $\mathcal{P}$ computes $com_f$ and sends it to $\mathcal{V}$
  • $\mathcal{V}$ samples an element $u \in \mathbb{F}_p$ and requests an opening of $f$ at $u$
  • $\mathcal{P}$ computes the quotient polynomial $q$ using equation $(1)$ and sends its commitment $com_q$ to $\mathcal{V}$ along with the evaluation $v = f(u)$

  Note

  Now, checking equation $(1)$ is same as checking the validity of the following equation:

  $$q(X) \cdot (X-u) = f(X) - v$$

  The verifier $\mathcal{V}$ will check this equation at the secret value $\alpha$ using pairings.

  • $\mathcal{V}$ verifies the opening proof $com_q$ and outputs 1 if the following equation holds; otherwise, it outputs 0. $$e(com_q, [\alpha]_2 - u \cdot [1]_2) \stackrel{?}{=} e(com_f - v \cdot [1]_1, [1]_2)$$

This scheme is homomorphic i.e. given commitments $com_f$ and $com_g$ to polynomials $f(X)$ and $g(X)$ respectively, we can compute a commitment to the polynomial $h(X) = f(X) + g(X)$ as $com_h = com_f + com_g$. We will use this property to batch multiple openings and to make the commitment unconditionally hiding using some randomness.

We have seen how to open a single polynomial at a single point. Now, let’s extend this to opening multiple polynomials at multiple points.

One straightforward approach is to open each polynomial individually and verify each opening proof. However, this would make the number of opening proofs sent by the prover and the number of pairing checks performed by the verifier proportional to the number of polynomials.

Can we open multiple polynomials at multiple points more efficiently? We can use batching.

Batched Variants#

In this section we will look at schemes that enable efficient opening of multiple evaluation points across multiple polynomials. Instead of opening each evaluation separately, we batch all required openings together. This approach leverages the homomorphic property of KZG commitments.

A batch opening protocol for a single polynomial at multiple evaluation points is described in Section 3.4 of KZG10. A variant for opening multiple polynomials at two evaluation points is presented in Section 3 of Plonk. In this section, we focus on more general variants that allow opening multiple polynomials at multiple points, as described in BDFG20.

In this setting, the prover $\mathcal{P}$ is given polynomials $f_1, \dots, f_k \in \mathbb{F}_p^{(< d)}[X]$ and must convince the verifier $\mathcal{V}$ of the correct evaluations of each $f_i$ over a corresponding set $S_i$, where $S_i \subset T = \{u_1, u_2, \dots, u_t\}$ for all $i \in [k]$.

The prover $\mathcal{P}$ could individually prove the validity of the following equation for all $i \in [k]$, this is same as equation $(2)$.

However, as noted earlier, it would not be efficient. The key idea is that if the above equation is valid for all $i \in [k]$, then a random linear combination of these $k$ equations will also be valid with a high probability. The prover $\mathcal{P}$ receives a random value $\gamma$ from the verifier $\mathcal{V}$ and computes the random linear combination as follows:

Thus, the verifier $\mathcal{V}$ only needs to verify the validity of this single random linear combination, rather than verifying equation $(3)$ individually for each $i \in [k]$.

We focus on the $open$ protocol, as the $setup$ and $commit$ algorithms remain similar.

$open(\mathcal{P}, \mathcal{V}) \rightarrow 0/1$

• $\mathcal{P}$ sends $com_1, com_2, \dots, com_k$ to $\mathcal{V}$, as commitments to polynomials $f_1, f_2, \dots f_k$, respectively
• $\mathcal{V}$ samples sets $S_1, S_2, \dots, S_k$ and asks $\mathcal{P}$ to open $f_i$ at $S_i$ for all $i \in [k]$
• $\mathcal{V}$ sends random $\gamma$ (used to combine all the openings)
• $\mathcal{P}$ does the following:
  • Compute $q(X)$ using equation $(4)$
  • Send commitment to $q(X)$ i.e. $com_q$ to $\mathcal{V}$ along with the claimed evaluations of $f_i$ over $S_i$ for all $i \in [k]$

Note that verifying the validity of equation $(4)$ is equivalent to verifying the following equation:

where $T \setminus S_i$ denotes the set difference between $T$ and $S_i$. This can be done using two different methods.

Method I#

The verifier $\mathcal{V}$ can directly check the validity of equation $(5)$ at $\alpha$ (the secret value) using pairings. $\mathcal{V}$ outputs 1 if the following equation holds; otherwise, it outputs 0.

Note that in the above check, the verifier $\mathcal{V}$ can compute $[Z_T(\alpha)]_2$, $[Z_{T \setminus S_i}(\alpha)]_2$, and $[r_i(\alpha)]_1$ for each $i \in [k]$ on its own. Since $\mathcal{V}$ needs to compute the commitments $[Z_T(\alpha)]_2$ and $[Z_{T \setminus S_i}(\alpha)]_2$ in the group $\mathbb{G}_2$, the public parameters $pp$ must include additional powers of the secret $\alpha$ in $\mathbb{G}_2$, i.e., $\left( [1]_2, [\alpha]_2, \dots, [\alpha^t]_2 \right)$, where $t$ is the degree of $Z_T(X)$.

The opening proof in this method consists of a single group element, namely $com_q$. However, it requires $\mathcal{V}$ to compute multiple pairings and perform product operations in the target group $\mathbb{G}_T$. In the next method, we reduce the verifier’s workload.

Method II#

In this approach, an additional random point is sampled, and the validity of equation $(5)$ is checked at that point. By the Schwartz-Zippel Lemma, if equation $(5)$ holds at a randomly chosen point, then with high probability, it holds for all points.

• $\mathcal{V}$ samples a random challenge $z$ and sends it to $\mathcal{P}$

  Note

  $\mathcal{P}$ will have to prove that equation $(5)$ is valid at $z$ i.e.

  $$q(z) \cdot Z_{T}(z) \stackrel{?}{=} \sum_{i \in [k]} \gamma^{i-1} \cdot Z_{T \setminus S_i}(z) \cdot (f_i(z) - r_i(z)) \tag{6}$$

  $\mathcal{P}$ computes the polynomial $l(X)$ such that

  $$l(X) = \sum_{i \in [k]} \gamma^{i-1} \cdot Z_{T \setminus S_i}(z) \cdot (f_i(X) - r_i(z)) - q(X) \cdot Z_{T}(z)$$

  Then, $\mathcal{P}$ shows that $l(z) = 0$. Note that the values $Z_T(z)$, $Z_{T \setminus S_i}(z)$, and $r_i(z)$ can all be computed by the verifier $\mathcal{V}$.

• $\mathcal{P}$ sends an opening proof that $l(X)$ evaluates to 0 at $z$, i.e., the commitment $com_{l'}$ to the polynomial $l'(X)$, where:

  $$l'(X) = \frac{l(X)}{X-z}$$

  Note

  Now, verifying the validity of equation $(6)$ is reduced to checking whether the following equation holds.
  

  $$l'(X) \cdot (X-z) = l(X)$$

  We apply the same idea as before: if the above equation is valid at a randomly chosen point, then with high probability, it is valid at all points (by the Schwartz-Zippel Lemma). Therefore, the verifier $\mathcal{V}$ checks the validity of this equation at the secret value $\alpha$ using pairings.

• $\mathcal{V}$ computes $com_l$, the commitment to $l(X)$, using the homomorphic property of KZG:

  $$com_l := \sum_{i \in [k]} \gamma^{i-1} \cdot Z_{T \setminus S_i}(z) \cdot \left( \text{com}_i - r_i(z) \cdot [1]_1 \right) - Z_T(z) \cdot com_q$$

  Then, $\mathcal{V}$ outputs 1 if the following equation holds; otherwise, it outputs 0:

  $$e(com_l, [1]_2) \stackrel{?}{=} e(com_{l'}, [\alpha]_2 - z \cdot [1]_2)$$

In this case, the opening proof is two group elements i.e. $com_q$ and $com_{l'}$. However, the verifier $\mathcal{V}$ only needs to compute two pairings and performs no operations in the target group $\mathbb{G}_t$. Moreover, since $\mathcal{V}$ does not need to compute the commitments $[Z_T(\alpha)]_2$ and $[Z_{T \setminus S_i}(\alpha)]_2$ in the group $\mathbb{G}_2$, the public parameters $pp$ do not require additional powers of the secret $\alpha$ in group $\mathbb{G}_2$ (as is the case in Method I). Instead, they only need to include the elements $([1]_2, [\alpha]_2)$ elements from $\mathbb{G}_2$.

Unconditionally Hiding#

In all the schemes we have seen so far, the commit algorithm $commit$ is deterministic i.e. it does not sample a random value. This leaks some information, for example if two commitments are equal then the underlying polynomial must be the same. We will now look at schemes which use some randomness to achieve the unconditionally hiding property.

Informally, unconditionally hiding means that even a computationally unbounded adversary learns no information about the underlying polynomial from the commitment. This is achieved by adding randomness to the commitment so that it becomes uniformly distributed over the entire group. As a result, after seeing the commitment, the best an adversary can do is make a random guess about the polynomial.

An unconditionally hiding PCS is crucial in settings where privacy is important, as it enables the construction of zkSNARKs, that is, SNARKs with the zero-knowledge property. The methods to achieve an unconditionally hiding PCS are as follows.

Method I: Using a random polynomial#

This method is described in Section 3.3 of KZG10. It leverages the homomorphic property to achieve unconditionally hiding by combining two commitments: one to the polynomial $f$, and another to a random polynomial $\tilde{f}$. The key idea is to add the random commitment $com_{\tilde{f}}$ to the original commitment $com_f$, so that the resulting commitment is uniformly distributed across the group. The algorithms are described as follows:

• $setup(d) \rightarrow pp$

  • Sample random elements $\alpha, \beta \in \mathbb{F}_p$. The value $\beta$ will be used to combine the commitments to $f$ and $\tilde{f}$.
  • $pp = \left( [1]_1, [\alpha]_1, \dots, [\alpha^{d-1}]_1, [\beta]_1, [\beta \cdot \alpha]_1, \dots, [\beta \cdot \alpha^{d-1}]_1, [1]_2, [\alpha]_2 \right)$
  • Discard $\alpha, \beta$

• $commit(pp, f) \rightarrow com_{\hat{f}}$

  • Sample a random polynomial $\tilde{f} \in \mathbb{F}^{(< d)}_p[X]$

  • $com_{\hat{f}} = [f(\alpha)]_1 + [\beta \cdot \tilde{f}(\alpha)]_1$ $= f_0 \cdot [1]_1 + f_1 \cdot [\alpha]_1 + f_2 \cdot [\alpha^2]_1 + \dots + f_{d-1} \cdot [\alpha^{d-1}]_1 + \;$ $\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \tilde{f}_0 \cdot [\beta]_1 + \tilde{f}_1 \cdot [\beta \cdot \alpha]_1 + \tilde{f}_2 \cdot [\beta \cdot \alpha^2]_1 + \dots + \tilde{f}_{d-1} \cdot [\beta \cdot \alpha^{d-1}]_1$ where $f_0, f_1, \dots, f_{d-1}$ are coefficients of $f$ and $\tilde{f}_0, \tilde{f}_1, \dots, \tilde{f}_{d-1}$ are coefficients of $\tilde{f}$.

    Note

    The commitment $com_{\hat{f}}$ can also be viewed as a commitment to the polynomial $\hat{f}(X)$, where $\hat{f}(X) = f(X) + \beta \cdot \tilde{f}(X)$.

• $open(\mathcal{P}, \mathcal{V}) \rightarrow 0/1$

  • $\mathcal{P}$ computes $com_{\hat{f}}$ and sends it to $\mathcal{V}$

  • $\mathcal{V}$ samples an element $u \in \mathbb{F}_p$ and asks $\mathcal{P}$ to open $f$ at $u$

  • $\mathcal{P}$ computes the quotient polynomials $q$, $\tilde{q}$ and sends the commitment $com_{\hat{q}}$ to $\mathcal{V}$ along with the evaluations $f(u)$ and $\tilde{f}(u)$

    $$q(X) = \frac{f(X) - f(u)}{X-u}$$
    $$\tilde{q}(X) = \frac{\tilde{f}(X) - \tilde{f}(u)}{X-u}$$
    $$com_{\hat{q}} = [q(\alpha)]_1 + [\beta \cdot \tilde{q}(\alpha)]_1$$

    Note

    This reduces the check $f(u) \stackrel{?}{=} v$ to checking that $\hat{q} = q + \beta \cdot \tilde{q}$ i.e. checking the following equation is valid:

    $$\hat{q}(X) = \frac{f(X) - f(u)}{X-u} + \beta \cdot \frac{\tilde{f}(X) - \tilde{f}(u)}{X-u}$$

    $$f(X) + \beta \cdot \tilde{f}(X) = \hat{q}(X) \cdot (X-u) + (f(u) + \beta \cdot \tilde{f}(u))$$

    $$\hat{f}(X) = \hat{q}(X) \cdot (X-u) + (f(u) + \beta \cdot \tilde{f}(u))$$

    Using the same idea as before, $\mathcal{V}$ will check the above equation at $\alpha$ using the evaluations $f(u), \tilde{f}(u)$ and commitments $com_{\hat{f}},com_{\hat{q}}$ sent by $\mathcal{P}$.

  • $\mathcal{V}$ outputs 1 if the following holds, otherwise 0:
    

    $$e(com_{\hat{f}}, [1]_2) \stackrel{?}{=} e(com_{\hat{q}}, [\alpha]_2 - u \cdot [1]_2) \cdot e(f(u) \cdot [1]_1 + \tilde{f}(u) \cdot [\beta]_1, [1]_2)$$

In this method, we blind the polynomial using a random polynomial to achieve unconditionally hiding. However, the same property can also be achieved using just a single random group element, as shown in the following method.

Method II: Using a random group element#

This method achieves unconditionally hiding using a single random group element. It is described in Section 3.5.3 of Zeromorph. The main idea is to add a random group element to the original commitment, ensuring that the resulting commitment is uniformly distributed across the group. The algorithms are as follows:

• $setup(d) \rightarrow pp$

  • Sample random elements $\alpha, \beta \in \mathbb{F}_p$
  • $pp = \left( [1]_1, [\alpha]_1, \dots, [\alpha^{d-1}]_1, [\beta]_1, [1]_2, [\alpha]_2, [\beta]_2 \right)$
  • Discard $\alpha, \beta$

• $commit(pp, f) \rightarrow com_{\hat{f}}$

  • choose a random element $r \in \mathbb{F}_p$ (used to randomize the commitment to polynomial $f$)

  • $com_{\hat{f}} = [f(\alpha)]_1 + r \cdot [\beta]_1 = f_0 \cdot [1]_1 + f_1 \cdot [\alpha]_1 + f_2 \cdot [\alpha^2]_1 + \dots + f_{d-1} \cdot [\alpha^{d-1}]_1 + r \cdot [\beta]_1$
    where $f_0, f_1, \dots, f_{d-1}$ are coefficients of $f$.

    Note

    The commitment $com_{\hat{f}}$ can be viewed as a commitment to polynomial $\hat{f}(X) = f(X) + r \beta$.

• $open(\mathcal{P}, \mathcal{V}) \rightarrow 0/1$

  • $\mathcal{P}$ computes $com_{\hat{f}}$ and sends it to $\mathcal{V}$

  • $\mathcal{V}$ samples an element $u \in \mathbb{F}_p$ and asks $\mathcal{P}$ to open $f$ at $u$

  • $\mathcal{P}$ samples a random $s \in \mathbb{F}_p$ (used to randomize the commitment to quotient polynomial $q$) and computes the commitment $com_{\hat{q}}$, and sends it to $\mathcal{V}$ along with the evaluation $f(u)$. Additionally, $\mathcal{P}$ also sends $\delta$, which is the corrective term to account for the randomness in $com_{\hat{f}}$ and $com_{\hat{q}}$.

    $$q(X) = \frac{f(X) - f(u)}{X-u}$$
    $$com_{\hat{q}} = [q(\alpha)]_1 + s \cdot [\beta]_1$$
    $$\delta = r \cdot [1]_1 - s \cdot [\alpha]_1 + (s \cdot u) \cdot [1]_1 = [r - s(\alpha - u)]_1$$

    Note

    The commitment $com_{\hat{q}}$ can be viewed as a commitment to the polynomial $\hat{q}(X) = q(X) + s \beta$. From our previous discussion, we know that checking the evaluation $f(u)$ is equivalent to checking that the following equation is valid.

    $$q(X) = \frac{f(X) - f(u)}{X-u}$$

    However, the verifier $\mathcal{V}$ cannot check the above equation directly at $\alpha$ (the secret value), because they do not have commitments to $q(X)$ and $f(X)$. Instead, they possess the randomized commitments $com_{\hat{q}}$ and $com_{\hat{f}}$.

    Let us incorporate the corresponding randomness and rearrange the terms to derive an equation that $\mathcal{V}$ can verify using the commitments $com_{\hat{q}}$, $com_{\hat{f}}$, and a pairing check. This process will also provide insight into the corrective term $\delta$. We begin by adding the randomness of $com_{\hat{q}}$, i.e., $s \beta$, to both sides:

    $$q(X) + s \beta = \frac{f(X) - f(u)}{X-u} + s \beta$$$$(q(X) + s \beta) \cdot (X-u) = f(X) - f(u) + s \beta \cdot (X-u)$$

    Add the randomness of $com_{\hat{f}}$ i.e. $r \beta$ on both sides:

    $$(q(X) + s \beta) \cdot (X-u) + r \beta = f(X) - f(u) + s \beta \cdot (X-u) + r \beta$$$$(q(X) + s \beta) \cdot (X-u) + r \beta - s \beta \cdot (X-u) = (f(X)+ r \beta) - f(u)$$$$(q(X) + s \beta) \cdot (X-u) + (r - s \cdot (X-u)) \cdot \beta = (f(X)+ r \beta) - f(u)$$

    Note that in the above equation the term $(q(X) + s \beta)$ corresponds to $com_{\hat{q}}$, the term $(f(X)+ r \beta)$ corresponds to $com_{\hat{f}}$ and the term $(r - s \cdot (X-u))$ corresponds to $\delta$. Thus, $\mathcal{V}$ can verify the above equation at the secret value $\alpha$ using pairings.

  • $\mathcal{V}$ outputs 1 if the following holds; otherwise, it outputs 0:

    $$e(com_{\hat{f}} - v \cdot [1]_1, [1]_2) \stackrel{?}{=} e(com_{\hat{q}}, [\alpha]_2 - u \cdot [1]_2) \cdot e(\delta, [\beta]_2)$$

In this method, we achieve the unconditionally hiding property using a single random group element. However, the opening proof consists of two group elements, namely $com_{\hat{q}}$ and $\delta$, compared to a single group element in Method I.

Conclusion#

In this post, we explored various univariate variants of the KZG polynomial commitment scheme, including techniques for batching multiple openings and achieving the unconditionally hiding property. In the next part of this series, we will delve into the multivariate setting.