Batch-Opening KZG Commitments at One Point: A Lemma and Its Proof

A polynomial commitment lets a prover commit to a polynomial $f$ and later open its value at any point convincingly. In the KZG scheme¹ both the commitment and an opening proof are a single group element, which makes it a building block of proof systems such as PLONK. In practice a verifier often needs $t$ polynomials opened at the same point $z$ : checking them one by one costs $2t$ pairings, and a single random linear combination brings that down to $2$ .² This note takes the lemma behind that step on its own and proves it in full.

Notation

Let $\G_1, \G_2, \G_T$ be cyclic groups of prime order $p$ with generators $g_1, g_2, g_T$ , let $e\colon \G_1 \times \G_2 \to \G_T$ be a non-degenerate bilinear map, and let $\F = \F_p$ . For $a \in \F$ write $\gi{a} = a \cdot g_1$ and $\gii{a} = a \cdot g_2$ .

Definition (KZG polynomial commitment)

Let $d$ be a degree bound. The trusted setup picks a random $\tau \gets \F$ , outputs

\srs = \bigl(\gi{1},\, \gi{\tau},\, \gi{\tau^2},\, \dots,\, \gi{\tau^d};\;\; \gii{1},\, \gii{\tau}\bigr)

and destroys $\tau$ . For any $f \in \F[X]$ with $\deg f \le d$ :

Commit: $\com(f) = \gi{f(\tau)}$ , which can be computed linearly from $\srs$ ;
Open: to prove $f(z) = v$ , let $q(X) = \dfrac{f(X) - v}{X - z}$ ; the proof is $\pi = \gi{q(\tau)}$ ;
Verify: accept if and only if $e\bigl(C - \gi{v},\, \gii{1}\bigr) = e\bigl(\pi,\, \gii{\tau} - \gii{z}\bigr)$ .

The verification equation holds because $q$ is a polynomial if and only if $(X - z) \mid f(X) - v$ , that is, if and only if $f(z) = v$ .

Batch opening at one point

Suppose the prover has committed to $f_1, \dots, f_t$ with commitments $C_i = \com(f_i)$ , and claims $f_i(z) = v_i$ for every $i$ . The protocol:

The verifier sends a random challenge $\gamma \gets \F$ (non-interactively, $\gamma$ comes from the Fiat–Shamir transform);
The prover computes the batched quotient $h(X) = \sum_{i=1}^{t} \gamma^{i-1} \cdot \dfrac{f_i(X) - v_i}{X - z}$ and sends $\pi = \gi{h(\tau)}$ ;
The verifier computes $C_\gamma = \sum_{i=1}^{t} \gamma^{i-1} C_i$ and $v_\gamma = \sum_{i=1}^{t} \gamma^{i-1} v_i$ , and accepts if and only if

e\bigl(C_\gamma - \gi{v_\gamma},\, \gii{1}\bigr) = e\bigl(\pi,\, \gii{\tau} - \gii{z}\bigr).

Write $F_\gamma(X) = \sum_{i=1}^{t} \gamma^{i-1}\bigl(f_i(X) - v_i\bigr)$ . An honest prover has $C_\gamma - \gi{v_\gamma} = \gi{F_\gamma(\tau)}$ and $F_\gamma(X) = h(X)\,(X - z)$ , so completeness follows directly from bilinearity:

\begin{aligned} e\bigl(C_\gamma - \gi{v_\gamma},\, \gii{1}\bigr) &= e\bigl(\gi{F_\gamma(\tau)},\, \gii{1}\bigr) \\ &= e\bigl(\gi{h(\tau)\,(\tau - z)},\, \gii{1}\bigr) \\ &= e\bigl(\gi{h(\tau)},\, \gii{\tau - z}\bigr) = e\bigl(\pi,\, \gii{\tau} - \gii{z}\bigr). \end{aligned}

Expanding $h$ in full gives the long expression below (it also tests horizontal scrolling on narrow screens):

h(X) = \frac{f_1(X) - v_1}{X - z} + \gamma \cdot \frac{f_2(X) - v_2}{X - z} + \gamma^{2} \cdot \frac{f_3(X) - v_3}{X - z} + \gamma^{3} \cdot \frac{f_4(X) - v_4}{X - z} + \cdots + \gamma^{t-1} \cdot \frac{f_t(X) - v_t}{X - z} = \frac{1}{X - z} \sum_{i=1}^{t} \gamma^{i-1} \bigl(f_i(X) - v_i\bigr).

The lemma and its proof

The heart of soundness: if even one claimed value is wrong, then after the random linear combination it is, with overwhelming probability, still wrong.

Lemma (Random linear combination)

Let $f_1, \dots, f_t \in \F[X]$ and $z, v_1, \dots, v_t \in \F$ , with $F_\gamma$ as above. If $f_j(z) \neq v_j$ for some $j$ , then

\Pr_{\gamma \gets \F}\Bigl[\, (X - z) \mid F_\gamma(X) \,\Bigr] \;\le\; \frac{t-1}{|\F|}.

Proof

By the remainder theorem, $(X - z) \mid F_\gamma(X)$ if and only if $F_\gamma(z) = 0$ . Read $F_\gamma(z)$ as a polynomial in $\gamma$ :

P(\gamma) = \sum_{i=1}^{t} \bigl(f_i(z) - v_i\bigr)\, \gamma^{i-1} \;\in\; \F[\gamma].

Its degree is at most $t - 1$ , and the coefficient of $\gamma^{j-1}$ is $f_j(z) - v_j \neq 0$ , so $P$ is not the zero polynomial. A nonzero polynomial over a field has no more roots than its degree, so at most $t - 1$ values of $\gamma$ give $P(\gamma) = 0$ ; since $\gamma$ is uniform over $\F$ , the probability is at most $(t-1)/|\F|$ .

Theorem (Soundness of batch opening, informally)

Assume the single-polynomial KZG scheme is evaluation binding, and that the polynomial $f_i$ behind every commitment $C_i$ the adversary outputs can be extracted (for instance in the algebraic group model³). Then for any polynomial-time adversary, the probability that batch verification passes while $f_j(z) \neq v_j$ for some $j$ is at most $(t-1)/|\F| + \negl(\lambda)$ .

Proof

(Sketch.) Suppose verification passes and $f_j(z) \neq v_j$ for some $j$ . By Lemma 1, except with probability at most $(t-1)/|\F|$ , we have $F_\gamma(z) \neq 0$ . Then $C_\gamma - \gi{v_\gamma}$ is a commitment to the polynomial $F_\gamma$ , and the adversary’s $\pi$ opens it to $0$ at $z$ ; the reduction, knowing every $f_i$ , can honestly compute a proof that opens the same commitment at $z$ to $F_\gamma(z) \neq 0$ . Two valid openings of one commitment at one point, with different values, contradict evaluation binding.

Cost

	One at a time	Batched
Proof size	$t$ elements of $\G_1$	$1$ element of $\G_1$
Pairings	$2t$	$2$
Scalar multiplications in $\G_1$	about $2t$	about $t + 1$
Extra soundness loss	none	$(t-1)/\lvert\F\rvert$

For $|\F| \approx 2^{255}$ and the $t \le 2^{10}$ that occur in practice, this loss is entirely negligible.

Aniket Kate, Gregory M. Zaverucha, Ian Goldberg, “Constant-Size Commitments to Polynomials and Their Applications”, ASIACRYPT 2010. ↩︎
Ariel Gabizon, Zachary J. Williamson, Oana Ciobotaru, “PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge”, IACR ePrint 2019/953. ↩︎
Georg Fuchsbauer, Eike Kiltz, Julian Loss, “The Algebraic Group Model and its Applications”, CRYPTO 2018. ↩︎

Notation

Batch opening at one point

The lemma and its proof

Cost

Footnotes

评论