KZG Polynomial Commitments

KZG is a polynomial commitment scheme whose distinguishing features are its constant-sized commitments, proofs, and its constant-time verification.

It operates on subgroups of elliptic curves over finite fields ${\mathbb{G}}_1=⟨g_1⟩$, ${\mathbb{G}}_2=⟨g_2⟩$, and ${\mathbb{G}}_T=⟨g_T⟩$ of prime order $r$ ($r$ depends on the chosen security level $\lambda$), for which a pairing $e:{\mathbb{G}}_1\times {\mathbb{G}}_2\mapsto {\mathbb{G}}_T$ exists. From now on, we adopt the convenient notation for elliptic curve multiplication: $[n{]}_1=n{g}_1$ and $[n{]}_2=n{g}_2$.

As a commitment scheme, it is a tuple of deterministic polynomial-time algorithms commit, proveEval and verifyEval such that

1. Commit, on input a polynomial, returns a commitment:

   $\text{commit}(\text{CK},f(x)):$

   1. $\text{assert }\mathrm{deg}(f(x))<d$
   2. $\text{return }c\leftarrow {\prod }_{i=0}^{n-1}{p}_i[{\tau }^i{]}_1=[f(\tau ){]}_1$

2. ProveEval outputs a proof $\pi$ that $f$ evaluates to $f(z)$ in $z$:

   $\text{proveEval}(\text{CK},f(x),z):$

   1. $q(x)\leftarrow \frac{f(x)-f(z)}{x-z}$
   2. $\text{return }\pi \leftarrow \text{commit}(\text{CK},q)$

3. VerifyEval, on input a proof, outputs true if the given proof testifies that the committed polynomial $f$ evaluates to $y$ in $z$ (using the pairing $e$):

   $\text{verifyEval}(\text{VK},c,z,y,\pi ):$

   1. $\text{return }e(c-[y{]}_1,g_2)\stackrel{?}{=}e(\pi ,[\tau {]}_2-[z{]}_2)$

The crux of KZG is that if $f(x)$ has $z$ as root, then the quotient $q(x)$ is well-defined. This comes from the euclidean division of $f(x)$ by $x-z$: $f(x)=q(x)(x-z)+r(x)$, $\mathrm{deg}r(x)=0$ and $f(z)=r(z)\equiv r(x)$. Moreover, it is impractical to forge false proofs: this requires to find a polynomial $g(x)$ which has the same commitment as $f(x)$, i.e. $f((x)-g(x))(\tau )=0$, which either requires the knowledge of $\tau$ or to try to make the difference zero in as most places as possible in the hope to cover $\tau$. In the latter case, this is highly unlikely, as the probability to find a zero is already

$\text{P}[(f(x)-g(x))(s)=0|s{\leftarrow }_R{\mathbb{F}}_r]\le d/|{\mathbb{F}}_r|$

thanks to the Schwartz-Zippel lemma in the univariate case. In typical use cases, the largest degree can be $2^{21}$ and the cardinal of the scalar field $|{\mathbb{F}}_r|\approx 2^{255}$ so the probability to find a zero is $1/2^{234}$.

See batched KZG proofs for efficient ways to compute and verify KZG proofs.

---

Security Proofs

Correctness

By bilinearity of $e$ (we only rely on the property $\forall \lambda \in {\mathbb{F}}_p,e(a,\lambda b)=e(\lambda a,b)$):

$$\begin{array}{rl}e(\pi ,[\text{SK}-z{]}_2)& =e((q(\text{SK})(\text{SK}-z))g_1,g_2)\\ & =e(((q(\text{SK})(\text{SK}-z)+f(z))-f(z))g_1,g_2)\\ & =e(c-[f(z){]}_1,g_2)\end{array}$$

Hiding

Suppose that there exists an adversary $\mathcal{A}$ breaking the hiding property of a commitment $\mathcal{C}$: it can compute the underlying polynomial $f(x)$ of degree $t$ given the commitment to $f(x)$ and $t$ valid witnesses $(z,y,{\pi }_{f(z)=y})$. By reduction, it is possible to construct an algorithm $\mathcal{B}$ from $\mathcal{A}$ that breaks the discrete logarithm assumption. The algorithm $\mathcal{B}$ has to solve the following discrete log instance $([1{]}_1,[a{]}_1)$. It first computes a trusted setup from a random $\alpha \in ({\mathbb{F}}_r{)}^{\times }$: $\text{PK}=\{[1{]}_1,[\alpha {]}_1,[{\alpha }^2{]}_1,\dots ,[{\alpha }^t{]}_1\}$. $\mathcal{B}$ then chooses $t$ random scalars $(b_i{)}_{i\in [[0,t-1]]}$ and computes

$$[a{]}_1+\sum _{i=0}^{t-1}{b}_i[{\alpha }^{i+1}{]}_1=[a+\sum _{i=0}^{t-1}{b}_i{\alpha }^{i+1}{]}_1,$$

which is the commitment to $f(x)=a+{\sum }_{i=0}^{t-1}{b}_i{x}^{i+1}$, namely $[f(\alpha ){]}_1$. $\mathcal{B}$ then chooses $t$ arbitrary points $(z_i{)}_{i\in [[0,t-1]]}$, and computes $t$ valid witnesses for the $t$ chosen evaluations ${\pi }_{f(z_i)=b_i}=(\alpha -z_i{)}^{-1}([f(\alpha ){]}_1-[b_i{]}_1)$. It then inputs $\text{PK}$, $[f(\alpha ){]}_1$ the commitment to $f(x)$, and the $t$ valid witness tuples $(z_i,b_i,{\pi }_{f(z_i)=b_i})$ to $\mathcal{A}$. Once $\mathcal{A}$ outputs $f(x)$, $\mathcal{B}$ outputs the constant term $a$ of $f(x)$, which is the solution to the given discrete logarithm instance.

Polynomial binding property

By reduction to the discrete logarithm problem, suppose that an adversary breaks the polynomial binding property by outputting two distinct polynomials $f(x)\in {\mathbb{F}}_p[x{]}_{\le d}$ and $g(x)\in {\mathbb{F}}_p[x{]}_{\le d}$ such that their commitments are equal, ie. $[f(\text{SK}){]}_1=[g(\text{SK}){]}_1$. This implies $[f(\text{SK})-g(\text{SK}){]}_1=0_{{\mathbb{G}}_1}$ which is slightly weaker as it requires $|{\mathbb{G}}_1||f(\text{SK})-g(\text{SK})$, but since the evaluations live in ${\mathbb{F}}_r$ for which $|{\mathbb{F}}_r|=|{\mathbb{G}}_1|$, $f(\text{SK})-g(\text{SK})=0$ necessarily. Hence, the polynomial $h(x)=f(x)-g(x)$ has $\text{SK}$ as root, which can be found with polynomial factorization algorithms over finite fields, such as Berlekamp in $O(d^3)$ (as its runtime is dominated by a Gaussian elimination).

Evaluation binding property

By reduction to the $t$-SDH assumption, suppose that an adversary $\mathcal{A}$ can break the evaluation binding property, i.e., can output a commitment $c$ to $f(x)$, and two different valid witness tuples $(z,y,{\pi }_{f(z)=y})$ and $(z,y^{\prime },{\pi }_{f(z)=y^{\prime }})$. An algorithm $\mathcal{B}$ inputs a trusted setup $\text{PK}=([1{]}_1,[\alpha {]}_1,[{\alpha }^2{]}_1,\dots ,[{\alpha }^t{]}_1)\in {\mathbb{G}}_1^{t+1}$ to $\mathcal{A}$, which returns a commitment $c$ to some polynomial $f(x)$ for which the witness tuples $(z,y,{\pi }_{f(z)=y}=[q(\alpha ){]}_1)$, $(z,y^{\prime },{\pi }_{f^{\prime }(z)=y^{\prime }}=[q^{\prime }(\alpha ){]}_1)$ are valid openings ($\text{VerifyEval}$ returns $\text{true}$ for them). By the correctness of the scheme,

$$e(c-[y{]}_1,g_2)=e({\pi }_{f(z)=y},[\alpha -z{]}_2)$$ $$e(c-[y^{\prime }{]}_1,g_2)=e({\pi }_{f(z)=y^{\prime }},[\alpha -z{]}_2).$$

From which we get: $(f(\alpha )-y)e(g_1,g_2)=q(\alpha )(\alpha -z)e(g_1,g_2).$ $(f(\alpha )-y^{\prime })e(g_1,g_2)=q^{\prime }(\alpha )(\alpha -z)e(g_1,g_2).$ Thus $f(\alpha )=q(\alpha )(\alpha -z)+y=q^{\prime }(\alpha )(\alpha -z)+y^{\prime }.$ With a bit of algebra, $\frac{q(\alpha )-q^{\prime }(\alpha )}{y^{\prime }-y}=\frac{1}{\alpha -z}.$ Thus $\mathcal{B}$ computes

$$\frac{{\pi }_{f(z)=y}-{\pi }_{f(z)=y^{\prime }}}{y^{\prime }-y}=[\frac{q(\alpha )-q^{\prime }(\alpha )}{y^{\prime }-y}{]}_1=[\frac{1}{\alpha -z}{]}_1,$$

and returns $(-z,[\frac{1}{\alpha -z}{]}_1)$ a solution to the $t$-SDH instance $\text{PK}$.