【安全技术】KZG 多项式承诺

语言 Chinese, Simplified

SEO Title

Overview of Polynomial Commitments #

Polynomial commitment schemes allow one party to prove to another the correct evaluation of a polynomial at some set of points, without revealing any other information about the polynomial. A generalization of scalar commitment schemes such as Pedersen commitments, polynomial commitments are an important building block in zero-knowledge protocols; once the prover has committed to a polynomial, the verifier can query the value of the polynomial at one or many points and be assured that the responses are consistent with some predetermined polynomial which was selected without knowledge of the challenge queries.

Kate et. al.’s polynomial commitment scheme [KZG2010] consists, similarly to Pedersen commitments, of two phases.

During the commit phase, Prover $Prover$
During the open phase, $Prover$ $Prover$

The commitment satisfies certain security properties:

Hiding: Given a commitment to an unknown degree- $t$ $t$
Binding: It is computationally infeasible to construct a commitment $C$ $C$

Applications of Polynomial Commitments #

Polynomial commitments serve as an important component of several modern noninteractive proof systems.

Vector Commitments #

Given a vector $\vec{v} = [v_1, v_2, \dots, v_n]$ we can create a succinct commitment to the whole vector v $v$

by interpolating a degree- $(n-1)$ $(n - 1)$

polynomial f such that $\varf(i) = v_i$ $f (i) = v_{i}$

. This enables provers to commit to a vector of field elements such that openings prove the value at a specific index. Vector commitments can in turn be used as a building block for Verkle Trees, a variant of Merkle trees with extremely small proof sizes.

zkSNARKs #

Polynomial commitment schemes are a core primitive in zkSNARKs such as [PLONK] and [Groth16] . These general-purpose zero knowledge proofs encode computations as polynomial identity constraints and then use openings of polynomial commitments at random points to verify polynomial equality. The power of polynomial commitments here comes from the fact that two distinct degree- $t$ $t$

polynomials over a field of order $q > t$ $q > t$ $q > t$ $q > t$

may intersect in at most $t$ $t$

points, and thus agree at a random point with probability at most $\frac{t}{q}$ $\frac{t}{q}$ $\frac{t}{q}$

The KZG Construction #

Bilinear Pairings #

KZG is a pairing-based protocol, meaning it works over a group with an efficiently computable bilinear pairing.

Let $G_{1}$ $G_{1}$ $G_{1}$

, $G_{2}$ $G_{2}$ $G_{2}$

and $G_{T}$ $G_{T}$ $G_{T}$

be abelian groups of prime order $q$ $q$

. $G_{1}$ $G_{1}$ $G_{1}$

and $G_{2}$ $G_{2}$ $G_{2}$

will be written additively while $G_{T}$ $G_{T}$ $G_{T}$

will be multiplicative. A bilinear pairing is an efficiently computable function $e : G_{1} \times G_{2} \to G_{T}$ $e : G_{1} \times G_{2} \to G_{T}$ $e : G_{1} \times G_{2} \to G_{T}$ $e : G_{1} \times G_{2} \to G_{T}$ $e : G_{1} \times G_{2} \to G_{T}$ $e : G_{1} \times G_{2} \to G_{T}$ $e : G_{1} \times G_{2} \to G_{T}$ $e : G_{1} \times G_{2} \to G_{T}$ $e : G_{1} \times G_{2} \to G_{T}$ $e : G_{1} \times G_{2} \to G_{T}$ $e : G_{1} \times G_{2} \to G_{T}$

such that

$$ e(a\cdot x, b \cdot y) = e(x, y)^{ab} $$

$e (a \cdot x, b \cdot y) = e (x, y)^{a b}$

for all $x \in \cgroup_1, y \in \cgroup_2 $ $x \in G_{1}, y \in G_{2}$

. We generally assume that $e$ $e$

is non-degenerate, meaning that $e$ $e$

is not the trivial function mapping all pairs to $1_{G_{T}}$ $1_{G_{T}}$ $1_{G_{T}}$ $1_{G_{T}}$

The KZG commitment scheme was originally presented in the “type-1” setting, where $G_{1} = G_{2}$ $G_{1} = G_{2}$ $G_{1} = G_{2}$ $G_{1} = G_{2}$ $G_{1} = G_{2}$ $G_{1} = G_{2}$

. In practice, and in our presentation here, the scheme is generally implemented in the “type-3” setting, where $G_{1} \neq G_{2}$ $G_{1} \neq G_{2}$ $G_{1} \neq G_{2}$ $G_{1} \neq G_{2}$ $G_{1} \neq G_{2}$ $G_{1} \neq G_{2}$

in the sense that there is no efficiently computable isomorphism between the two groups.

Common choices of pairing-friendly groups are the Barreto-Naehrig [BN05] and Barreto-Lynn-Scott curves [BLS12-381] .

Trusted Setup #

KZG requires a setup procedure to be carried out by a trusted third party. In practice this setup is often performed as a distributed multiparty computation, such that as long as one participant is honest the setup is secure.

The public parameters are $G_{1}$ $G_{1}$ $G_{1}$

, $G_{2}$ $G_{2}$ $G_{2}$

and $G_{T}$ $G_{T}$ $G_{T}$

, with generators $g_{1} \in G_{1}, g_{2} \in G_{2}$ $g_{1} \in G_{1}, g_{2} \in G_{2}$ $g_{1} \in G_{1}, g_{2} \in G_{2}$ $g_{1} \in G_{1}, g_{2} \in G_{2}$ $g_{1} \in G_{1}, g_{2} \in G_{2}$ $g_{1} \in G_{1}, g_{2} \in G_{2}$ $g_{1} \in G_{1}, g_{2} \in G_{2}$ $g_{1} \in G_{1}, g_{2} \in G_{2}$ $g_{1} \in G_{1}, g_{2} \in G_{2}$ $g_{1} \in G_{1}, g_{2} \in G_{2}$ $g_{1} \in G_{1}, g_{2} \in G_{2}$ $g_{1} \in G_{1}, g_{2} \in G_{2}$

and $e : G_{1} \times G_{2} \to G_{T}$ $e : G_{1} \times G_{2} \to G_{T}$ $e : G_{1} \times G_{2} \to G_{T}$ $e : G_{1} \times G_{2} \to G_{T}$ $e : G_{1} \times G_{2} \to G_{T}$ $e : G_{1} \times G_{2} \to G_{T}$ $e : G_{1} \times G_{2} \to G_{T}$ $e : G_{1} \times G_{2} \to G_{T}$ $e : G_{1} \times G_{2} \to G_{T}$ $e : G_{1} \times G_{2} \to G_{T}$ $e : G_{1} \times G_{2} \to G_{T}$

a nondegenerate bilinear pairing. Let $t \in N$ $t \in N$ $t \in N$ $t \in N$

also be publicly chosen; $t$ $t$

will be the maximum degree of committed polynomials.

The setup procedure then computes

$$ \begin{align*}
\mathbf{SK} &= \sample{\alpha}\\
\mathbf{PK} &= \langle g_1, \alpha\cdot g_1, \alpha^2 \cdot g_1, \dots, \alpha^t \cdot g_1, g_2, \alpha \cdot g_2\rangle
\end{align*} $$

$\begin{aligned} S K & = α \overset{$}{\leftarrow} Z_{q} \\ P K & = ⟨ g_{1}, α \cdot g_{1}, α^{2} \cdot g_{1}, \dots, α^{t} \cdot g_{1}, g_{2}, α \cdot g_{2} ⟩ \end{aligned}$

and publishes $P K$ $P K$ $P K$

This pre-generated $P K$ $P K$ $P K$
is sometimes known as a “Structured Reference String”

$S K$ $S K$ $S K$
must be kept secret and destroyed.

If a party knows the value $α$ $α$
then they can forge openings of a commitment to $f$ $f$
at $x_{0}$ $x_{0}$ $x_{0}$
with putative value $y$ $y$
by computing

$w = (f (α) / (α - x_{0}) - y) \cdot g_{1}$ $w = (f (α) / (α - x_{0}) - y) \cdot g_{1}$ $w = (f (α) / (α - x_{0}) - y) \cdot g_{1}$ $w = (f (α) / (α - x_{0}) - y) \cdot g_{1}$ $w = (f (α) / (α - x_{0}) - y) \cdot g_{1}$ $w = (f (α) / (α - x_{0}) - y) \cdot g_{1}$ $w = (f (α) / (α - x_{0}) - y) \cdot g_{1}$ $w = (f (α) / (α - x_{0}) - y) \cdot g_{1}$ $w = (f (α) / (α - x_{0}) - y) \cdot g_{1}$ $w = (f (α) / (α - x_{0}) - y) \cdot g_{1}$ $w = (f (α) / (α - x_{0}) - y) \cdot g_{1}$ $w = (f (α) / (α - x_{0}) - y) \cdot g_{1}$ $w = (f (α) / (α - x_{0}) - y) \cdot g_{1}$ $w = (f (α) / (α - x_{0}) - y) \cdot g_{1}$ $w = (f (α) / (α - x_{0}) - y) \cdot g_{1}$ $w = (f (α) / (α - x_{0}) - y) \cdot g_{1}$ $w = (f (α) / (α - x_{0}) - y) \cdot g_{1}$ $w = (f (α) / (α - x_{0}) - y) \cdot g_{1}$ $w = (f (α) / (α - x_{0}) - y) \cdot g_{1}$ $w = (f (α) / (α - x_{0}) - y) \cdot g_{1}$ $w = (f (α) / (α - x_{0}) - y) \cdot g_{1}$

Commit #

A commitment to a polynomial $f$ $f$

is simply the group element $f (α) \cdot g_{1}$ $f (α) \cdot g_{1}$ $f (α) \cdot g_{1}$ $f (α) \cdot g_{1}$ $f (α) \cdot g_{1}$ $f (α) \cdot g_{1}$ $f (α) \cdot g_{1}$ $f (α) \cdot g_{1}$

. Because the prover does not know $α$ $α$

and thus cannot compute the value $f (α)$ $f (α)$ $f (α)$ $f (α)$ $f (α)$

directly, the evaluation is carried out in the exponent as follows:

Given $P K$ $P K$ $P K$

, to form a commitment to $f \in Z_{q} [X]$ $f \in Z_{q} [X]$ $f \in Z_{q} [X]$ $f \in Z_{q} [X]$ $f \in Z_{q} [X]$ $f \in Z_{q} [X]$ $f \in Z_{q} [X]$ $f \in Z_{q} [X]$

with $f (X) = \sum_{i = 0}^{t} c_{i} X^{i}$ $f (X) = \sum_{i = 0}^{t} c_{i} X^{i}$ $f (X) = \sum_{i = 0}^{t} c_{i} X^{i}$ $f (X) = \sum_{i = 0}^{t} c_{i} X^{i}$ $f (X) = \sum_{i = 0}^{t} c_{i} X^{i}$ $f (X) = \sum_{i = 0}^{t} c_{i} X^{i}$ $f (X) = \sum_{i = 0}^{t} c_{i} X^{i}$ $f (X) = \sum_{i = 0}^{t} c_{i} X^{i}$ $f (X) = \sum_{i = 0}^{t} c_{i} X^{i}$ $f (X) = \sum_{i = 0}^{t} c_{i} X^{i}$ $f (X) = \sum_{i = 0}^{t} c_{i} X^{i}$ $f (X) = \sum_{i = 0}^{t} c_{i} X^{i}$ $f (X) = \sum_{i = 0}^{t} c_{i} X^{i}$ $f (X) = \sum_{i = 0}^{t} c_{i} X^{i}$ $f (X) = \sum_{i = 0}^{t} c_{i} X^{i}$

, compute and publish $C = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $C = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $C = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $C = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $C = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $C = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $C = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $C = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $C = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $C = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $C = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $C = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $C = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $C = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $C = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $C = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $C = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $C = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$

Open #

For any degree- $t$ $t$

polynomial $f$ $f$

, the polynomial $(f (X) - f (x_{0}))$ $(f (X) - f (x_{0}))$ $(f (X) - f (x_{0}))$ $(f (X) - f (x_{0}))$ $(f (X) - f (x_{0}))$ $(f (X) - f (x_{0}))$ $(f (X) - f (x_{0}))$ $(f (X) - f (x_{0}))$ $(f (X) - f (x_{0}))$ $(f (X) - f (x_{0}))$ $(f (X) - f (x_{0}))$ $(f (X) - f (x_{0}))$ $(f (X) - f (x_{0}))$

has a root at $x_{0}$ $x_{0}$ $x_{0}$

and thus can be factored as $f (X) - f (x_{0}) = (X - x_{0}) f_{x_{0}} (X)$ $f (X) - f (x_{0}) = (X - x_{0}) f_{x_{0}} (X)$ $f (X) - f (x_{0}) = (X - x_{0}) f_{x_{0}} (X)$ $f (X) - f (x_{0}) = (X - x_{0}) f_{x_{0}} (X)$ $f (X) - f (x_{0}) = (X - x_{0}) f_{x_{0}} (X)$ $f (X) - f (x_{0}) = (X - x_{0}) f_{x_{0}} (X)$ $f (X) - f (x_{0}) = (X - x_{0}) f_{x_{0}} (X)$ $f (X) - f (x_{0}) = (X - x_{0}) f_{x_{0}} (X)$ $f (X) - f (x_{0}) = (X - x_{0}) f_{x_{0}} (X)$ $f (X) - f (x_{0}) = (X - x_{0}) f_{x_{0}} (X)$ $f (X) - f (x_{0}) = (X - x_{0}) f_{x_{0}} (X)$ $f (X) - f (x_{0}) = (X - x_{0}) f_{x_{0}} (X)$ $f (X) - f (x_{0}) = (X - x_{0}) f_{x_{0}} (X)$ $f (X) - f (x_{0}) = (X - x_{0}) f_{x_{0}} (X)$ $f (X) - f (x_{0}) = (X - x_{0}) f_{x_{0}} (X)$ $f (X) - f (x_{0}) = (X - x_{0}) f_{x_{0}} (X)$ $f (X) - f (x_{0}) = (X - x_{0}) f_{x_{0}} (X)$ $f (X) - f (x_{0}) = (X - x_{0}) f_{x_{0}} (X)$ $f (X) - f (x_{0}) = (X - x_{0}) f_{x_{0}} (X)$ $f (X) - f (x_{0}) = (X - x_{0}) f_{x_{0}} (X)$ $f (X) - f (x_{0}) = (X - x_{0}) f_{x_{0}} (X)$ $f (X) - f (x_{0}) = (X - x_{0}) f_{x_{0}} (X)$ $f (X) - f (x_{0}) = (X - x_{0}) f_{x_{0}} (X)$ $f (X) - f (x_{0}) = (X - x_{0}) f_{x_{0}} (X)$

for some degree- $(t - 1)$ $(t - 1)$ $(t - 1)$ $(t - 1)$ $(t - 1)$ $(t - 1)$

polynomial $f_{x_{0}}$ $f_{x_{0}}$ $f_{x_{0}}$ $f_{x_{0}}$

. The witness to an opening of $f$ $f$

at $x_{0}$ $x_{0}$ $x_{0}$

is then $w = f_{x_{0}} (α) \cdot g_{1}$ $w = f_{x_{0}} (α) \cdot g_{1}$ $w = f_{x_{0}} (α) \cdot g_{1}$ $w = f_{x_{0}} (α) \cdot g_{1}$ $w = f_{x_{0}} (α) \cdot g_{1}$ $w = f_{x_{0}} (α) \cdot g_{1}$ $w = f_{x_{0}} (α) \cdot g_{1}$ $w = f_{x_{0}} (α) \cdot g_{1}$ $w = f_{x_{0}} (α) \cdot g_{1}$ $w = f_{x_{0}} (α) \cdot g_{1}$ $w = f_{x_{0}} (α) \cdot g_{1}$ $w = f_{x_{0}} (α) \cdot g_{1}$

More concretely, to open a commitment $C$ $C$

to polynomial $f$ $f$

at point $x_{0}$ $x_{0}$ $x_{0}$

, compute the quotient $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$ $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$ $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$ $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$ $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$ $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$ $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$ $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$ $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$ $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$ $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$ $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$ $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$ $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$ $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$ $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$ $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$ $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$ $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$ $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$ $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$ $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$ $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$ $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$ $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$ $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$ $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$ $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$ $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$ $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$ $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$ $f_{x_{0}} (X) = \frac{f (X) - f (x_{0})}{X - x_{0}} = \sum_{i = 0}^{t} c_{i} X^{i}$

and compute the witness as $w = f_{x_{0}} (α) \cdot g_{1} = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $w = f_{x_{0}} (α) \cdot g_{1} = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $w = f_{x_{0}} (α) \cdot g_{1} = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $w = f_{x_{0}} (α) \cdot g_{1} = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $w = f_{x_{0}} (α) \cdot g_{1} = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $w = f_{x_{0}} (α) \cdot g_{1} = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $w = f_{x_{0}} (α) \cdot g_{1} = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $w = f_{x_{0}} (α) \cdot g_{1} = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $w = f_{x_{0}} (α) \cdot g_{1} = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $w = f_{x_{0}} (α) \cdot g_{1} = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $w = f_{x_{0}} (α) \cdot g_{1} = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $w = f_{x_{0}} (α) \cdot g_{1} = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $w = f_{x_{0}} (α) \cdot g_{1} = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $w = f_{x_{0}} (α) \cdot g_{1} = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $w = f_{x_{0}} (α) \cdot g_{1} = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $w = f_{x_{0}} (α) \cdot g_{1} = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $w = f_{x_{0}} (α) \cdot g_{1} = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $w = f_{x_{0}} (α) \cdot g_{1} = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $w = f_{x_{0}} (α) \cdot g_{1} = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $w = f_{x_{0}} (α) \cdot g_{1} = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $w = f_{x_{0}} (α) \cdot g_{1} = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $w = f_{x_{0}} (α) \cdot g_{1} = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $w = f_{x_{0}} (α) \cdot g_{1} = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $w = f_{x_{0}} (α) \cdot g_{1} = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $w = f_{x_{0}} (α) \cdot g_{1} = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $w = f_{x_{0}} (α) \cdot g_{1} = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $w = f_{x_{0}} (α) \cdot g_{1} = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$ $w = f_{x_{0}} (α) \cdot g_{1} = \sum_{i = 0}^{t} c_{i} \cdot (α^{i} \cdot g_{1})$

Reveal $⟨ x_{0}, f (x_{0}), w ⟩$ $⟨ x_{0}, f (x_{0}), w ⟩$ $⟨ x_{0}, f (x_{0}), w ⟩$ $⟨ x_{0}, f (x_{0}), w ⟩$ $⟨ x_{0}, f (x_{0}), w ⟩$ $⟨ x_{0}, f (x_{0}), w ⟩$ $⟨ x_{0}, f (x_{0}), w ⟩$ $⟨ x_{0}, f (x_{0}), w ⟩$ $⟨ x_{0}, f (x_{0}), w ⟩$ $⟨ x_{0}, f (x_{0}), w ⟩$ $⟨ x_{0}, f (x_{0}), w ⟩$ $⟨ x_{0}, f (x_{0}), w ⟩$ $⟨ x_{0}, f (x_{0}), w ⟩$

Verify #

Verification of an opening of $\varf$ at $\varx_0 $ $x_{0}$

with witness $\varw = \varf_{\varx_0}(\alpha)\cdot g_1 $ $w = f_{x_{0}} (α) \cdot g_{1}$

amounts to checking in the exponent that $ \varf(\alpha) \equalQ (X- \varx_0)(\alpha) \cdot \varf_{\varx_0}(\alpha) + \varf(\varx_0) $ $f (α) \overset{?}{=} (X - x_{0}) (α) \cdot f_{x_{0}} (α) + f (x_{0})$

. Since the prover does not know the value of $ \alpha$ $α$

, we can think of the check as happening at a random point and thus with high probability succeeds only if the polynomial identity $\varf(X) \equalQ (X- \varx_0) \cdot \varf_{\varx_0}(X) + \varf(\varx_0) $ $f (X) \overset{?}{=} (X - x_{0}) \cdot f_{x_{0}} (X) + f (x_{0})$

holds at all points.

Concretely, to verify an evaluation $ \langle \varx_0, \varf(\varx_0), \varw \rangle $ $⟨ x_{0}, f (x_{0}), w ⟩$

on commitment $\varC$ , check

$$e(\varC, g_2) \equalQ e(\varw, \alpha \cdot g_2 - \varx_0 \cdot g_2) \cdot e(g_1, g_2)^{\varf(\varx_0)}$$ $e (C, g_{2}) \overset{?}{=} e (w, α \cdot g_{2} - x_{0} \cdot g_{2}) \cdot e (g_{1}, g_{2})^{f (x_{0})}$

To see that the scheme is complete in the sense that every correctly computed opening passes verification, we compute

$$ \begin{align*}
&e(\varw, \alpha \cdot g_2 - \varx_0 \cdot g_2) \cdot e(g_1, g_2)^{\varf(\varx_0)}\\
&= e(\varf_{\varx_0}(\alpha)\cdot g_1, (\alpha - \varx_0)\cdot g_2) \cdot e(g_1, g_2)^{\varf(\varx_0)}\\
&= e(g_1, g_2)^{\varf_{\varx_0}(\alpha)\cdot (\alpha - \varx_0) + \varf(\varx_0)}\\
&= e(g_1, g_2)^{\frac{\varf(\alpha) - \varf(\varx_0)}{\alpha - \varx_0} \cdot (\alpha - \varx_0) + \varf(\varx_0)}\\
&= e(g_1, g_2)^{\varf(\alpha)}\\
&= e(\varf(\alpha)\cdot g_1, g_2)\\
&= e(\varC, g_2)
\end{align*} $$ $\begin{aligned} e (w, α \cdot g_{2} - x_{0} \cdot g_{2}) \cdot e (g_{1}, g_{2})^{f (x_{0})} \\ = e (f_{x_{0}} (α) \cdot g_{1}, (α - x_{0}) \cdot g_{2}) \cdot e (g_{1}, g_{2})^{f (x_{0})} \\ = e (g_{1}, g_{2})^{f_{x_{0}} (α) \cdot (α - x_{0}) + f (x_{0})} \\ = e (g_{1}, g_{2})^{\frac{f (α) - f (x_{0})}{α - x_{0}} \cdot (α - x_{0}) + f (x_{0})} \\ = e (g_{1}, g_{2})^{f (α)} \\ = e (f (α) \cdot g_{1}, g_{2}) \\ = e (C, g_{2}) \end{aligned}$

Hardness Assumptions #

Discrete Logarithm #

The hiding property of KZG commitments relies on the hardness of the discrete logarithm in the group $G_{1}$ $G_{1}$ $G_{1}$

$t$ $t$

The binding property requires the $t$ $t$

-Strong Diffie Hellman ( $t$ $t$

-SDH) assumption: Given $g, α \cdot g, \dots, α^{t} \cdot g$ $g, α \cdot g, \dots, α^{t} \cdot g$ $g, α \cdot g, \dots, α^{t} \cdot g$ $g, α \cdot g, \dots, α^{t} \cdot g$ $g, α \cdot g, \dots, α^{t} \cdot g$ $g, α \cdot g, \dots, α^{t} \cdot g$ $g, α \cdot g, \dots, α^{t} \cdot g$ $g, α \cdot g, \dots, α^{t} \cdot g$ $g, α \cdot g, \dots, α^{t} \cdot g$ $g, α \cdot g, \dots, α^{t} \cdot g$ $g, α \cdot g, \dots, α^{t} \cdot g$ $g, α \cdot g, \dots, α^{t} \cdot g$ $g, α \cdot g, \dots, α^{t} \cdot g$

it is hard to find a pair $⟨ c, \frac{1}{α + c} \cdot g ⟩$ $⟨ c, \frac{1}{α + c} \cdot g ⟩$ $⟨ c, \frac{1}{α + c} \cdot g ⟩$ $⟨ c, \frac{1}{α + c} \cdot g ⟩$ $⟨ c, \frac{1}{α + c} \cdot g ⟩$ $⟨ c, \frac{1}{α + c} \cdot g ⟩$ $⟨ c, \frac{1}{α + c} \cdot g ⟩$ $⟨ c, \frac{1}{α + c} \cdot g ⟩$ $⟨ c, \frac{1}{α + c} \cdot g ⟩$ $⟨ c, \frac{1}{α + c} \cdot g ⟩$ $⟨ c, \frac{1}{α + c} \cdot g ⟩$

. This is a slightly stronger form of the $t$ $t$

-Polynomial Diffie Hellman assumption that, given $g, α \cdot g, \dots, α^{t} \cdot g$ $g, α \cdot g, \dots, α^{t} \cdot g$ $g, α \cdot g, \dots, α^{t} \cdot g$ $g, α \cdot g, \dots, α^{t} \cdot g$ $g, α \cdot g, \dots, α^{t} \cdot g$ $g, α \cdot g, \dots, α^{t} \cdot g$ $g, α \cdot g, \dots, α^{t} \cdot g$ $g, α \cdot g, \dots, α^{t} \cdot g$ $g, α \cdot g, \dots, α^{t} \cdot g$ $g, α \cdot g, \dots, α^{t} \cdot g$ $g, α \cdot g, \dots, α^{t} \cdot g$ $g, α \cdot g, \dots, α^{t} \cdot g$ $g, α \cdot g, \dots, α^{t} \cdot g$

, it is hard to find $α^{t + 1} \cdot g$ $α^{t + 1} \cdot g$ $α^{t + 1} \cdot g$ $α^{t + 1} \cdot g$ $α^{t + 1} \cdot g$ $α^{t + 1} \cdot g$ $α^{t + 1} \cdot g$

$t$ $t$

-SDH implies the computational Diffie Hellman assumption, as well as the hardness of the discrete logarithm problem.

KZG Variants #

Indistinguishable and Unconditionally hiding (“Pedersen”) variants #

The KZG commitment scheme as presented above can be viewed as a generalization of the Discrete Log commitment $C (x) = x \cdot g$ $C (x) = x \cdot g$ $C (x) = x \cdot g$ $C (x) = x \cdot g$ $C (x) = x \cdot g$ $C (x) = x \cdot g$ $C (x) = x \cdot g$ $C (x) = x \cdot g$ $C (x) = x \cdot g$

. This scheme is binding and is hiding against a computationally-bounded adversary when $x$ $x$

is chosen uniformly at random, but lacks indistinguishability: if $x$ $x$

is drawn from a small set known to the adversary then the adversary can distinguish which of the elements was committed. For example, if Alice wants to commit to a single bit $b \in {0, 1}$ $b \in {0, 1}$ $b \in {0, 1}$ $b \in {0, 1}$ $b \in {0, 1}$ $b \in {0, 1}$ $b \in {0, 1}$ $b \in {0, 1}$

then she will either publish $0 \cdot g = 0$ $0 \cdot g = 0$ $0 \cdot g = 0$ $0 \cdot g = 0$ $0 \cdot g = 0$ $0 \cdot g = 0$

or $1 \cdot g = g$ $1 \cdot g = g$ $1 \cdot g = g$ $1 \cdot g = g$ $1 \cdot g = g$ $1 \cdot g = g$

and Bob can clearly learn which bit was committed. Pedersen commitments solve this problem by adding a random masking value $r$ $r$

and an extra random public generator $h$ $h$

such that $C_{r} (x) = x \cdot g + r \cdot h$ $C_{r} (x) = x \cdot g + r \cdot h$ $C_{r} (x) = x \cdot g + r \cdot h$ $C_{r} (x) = x \cdot g + r \cdot h$ $C_{r} (x) = x \cdot g + r \cdot h$ $C_{r} (x) = x \cdot g + r \cdot h$ $C_{r} (x) = x \cdot g + r \cdot h$ $C_{r} (x) = x \cdot g + r \cdot h$ $C_{r} (x) = x \cdot g + r \cdot h$ $C_{r} (x) = x \cdot g + r \cdot h$ $C_{r} (x) = x \cdot g + r \cdot h$ $C_{r} (x) = x \cdot g + r \cdot h$ $C_{r} (x) = x \cdot g + r \cdot h$ $C_{r} (x) = x \cdot g + r \cdot h$

. This commitment is now indistinguishable and unconditionally hiding: for any value $y$ $y$

there exists some unique $s$ $s$

such that $C_{r} (x) = x \cdot g + r \cdot h = y \cdot g + s \cdot h = C_{s} (y)$ $C_{r} (x) = x \cdot g + r \cdot h = y \cdot g + s \cdot h = C_{s} (y)$ $C_{r} (x) = x \cdot g + r \cdot h = y \cdot g + s \cdot h = C_{s} (y)$ $C_{r} (x) = x \cdot g + r \cdot h = y \cdot g + s \cdot h = C_{s} (y)$ $C_{r} (x) = x \cdot g + r \cdot h = y \cdot g + s \cdot h = C_{s} (y)$ $C_{r} (x) = x \cdot g + r \cdot h = y \cdot g + s \cdot h = C_{s} (y)$ $C_{r} (x) = x \cdot g + r \cdot h = y \cdot g + s \cdot h = C_{s} (y)$ $C_{r} (x) = x \cdot g + r \cdot h = y \cdot g + s \cdot h = C_{s} (y)$ $C_{r} (x) = x \cdot g + r \cdot h = y \cdot g + s \cdot h = C_{s} (y)$ $C_{r} (x) = x \cdot g + r \cdot h = y \cdot g + s \cdot h = C_{s} (y)$ $C_{r} (x) = x \cdot g + r \cdot h = y \cdot g + s \cdot h = C_{s} (y)$ $C_{r} (x) = x \cdot g + r \cdot h = y \cdot g + s \cdot h = C_{s} (y)$ $C_{r} (x) = x \cdot g + r \cdot h = y \cdot g + s \cdot h = C_{s} (y)$ $C_{r} (x) = x \cdot g + r \cdot h = y \cdot g + s \cdot h = C_{s} (y)$ $C_{r} (x) = x \cdot g + r \cdot h = y \cdot g + s \cdot h = C_{s} (y)$ $C_{r} (x) = x \cdot g + r \cdot h = y \cdot g + s \cdot h = C_{s} (y)$ $C_{r} (x) = x \cdot g + r \cdot h = y \cdot g + s \cdot h = C_{s} (y)$ $C_{r} (x) = x \cdot g + r \cdot h = y \cdot g + s \cdot h = C_{s} (y)$ $C_{r} (x) = x \cdot g + r \cdot h = y \cdot g + s \cdot h = C_{s} (y)$ $C_{r} (x) = x \cdot g + r \cdot h = y \cdot g + s \cdot h = C_{s} (y)$ $C_{r} (x) = x \cdot g + r \cdot h = y \cdot g + s \cdot h = C_{s} (y)$ $C_{r} (x) = x \cdot g + r \cdot h = y \cdot g + s \cdot h = C_{s} (y)$ $C_{r} (x) = x \cdot g + r \cdot h = y \cdot g + s \cdot h = C_{s} (y)$ $C_{r} (x) = x \cdot g + r \cdot h = y \cdot g + s \cdot h = C_{s} (y)$ $C_{r} (x) = x \cdot g + r \cdot h = y \cdot g + s \cdot h = C_{s} (y)$ $C_{r} (x) = x \cdot g + r \cdot h = y \cdot g + s \cdot h = C_{s} (y)$ $C_{r} (x) = x \cdot g + r \cdot h = y \cdot g + s \cdot h = C_{s} (y)$ $C_{r} (x) = x \cdot g + r \cdot h = y \cdot g + s \cdot h = C_{s} (y)$

, so even a computationally-unbounded adversary cannot learn $x$ $x$

from $C_{r} (x)$ $C_{r} (x)$ $C_{r} (x)$ $C_{r} (x)$ $C_{r} (x)$ $C_{r} (x)$

, if $r$ $r$

is unknown.

In a similar vein, let $f (x)$ $f (x)$ $f (x)$ $f (x)$ $f (x)$

be a degree- $t$ $t$

polynomial.

An adversary capable of solving the Discrete Log problem can find the discrete log of $C (f) = f (α) \cdot g_{1}$ $C (f) = f (α) \cdot g_{1}$ $C (f) = f (α) \cdot g_{1}$ $C (f) = f (α) \cdot g_{1}$ $C (f) = f (α) \cdot g_{1}$ $C (f) = f (α) \cdot g_{1}$ $C (f) = f (α) \cdot g_{1}$ $C (f) = f (α) \cdot g_{1}$ $C (f) = f (α) \cdot g_{1}$ $C (f) = f (α) \cdot g_{1}$ $C (f) = f (α) \cdot g_{1}$ $C (f) = f (α) \cdot g_{1}$ $C (f) = f (α) \cdot g_{1}$
If $f (x_{0})$ $f (x_{0})$ $f (x_{0})$ $f (x_{0})$ $f (x_{0})$ $f (x_{0})$

There are two common approaches to resolve these issues:

Choose one extra point on $f$ $f$
Use the “Pedersen Variant”: let $h_{1}$ $h_{1}$ $h_{1}$

Security note: $h_{1}$ $h_{1}$ $h_{1}$
must be chosen independently from $g_{1}$ $g_{1}$ $g_{1}$
, i.e., no one may know the discrete log of $h_{1}$ $h_{1}$ $h_{1}$
with respect to $g_{1}$ $g_{1}$ $g_{1}$
. If Alice knows $s$ $s$
such that $h_{1} = s \cdot g_{1}$ $h_{1} = s \cdot g_{1}$ $h_{1} = s \cdot g_{1}$ $h_{1} = s \cdot g_{1}$ $h_{1} = s \cdot g_{1}$ $h_{1} = s \cdot g_{1}$ $h_{1} = s \cdot g_{1}$ $h_{1} = s \cdot g_{1}$
then the commitment scheme fails to be binding:

If $h_{1} = s \cdot g_{1}$ $h_{1} = s \cdot g_{1}$ $h_{1} = s \cdot g_{1}$ $h_{1} = s \cdot g_{1}$ $h_{1} = s \cdot g_{1}$ $h_{1} = s \cdot g_{1}$ $h_{1} = s \cdot g_{1}$ $h_{1} = s \cdot g_{1}$
then $\begin{aligned} C_{r} (x) & = x \cdot g_{1} + r \cdot h_{1} \\ = x \cdot g_{1} + (s \cdot r) \cdot g_{1} \\ = (x + (y - x) + s (r - \frac{y - x}{s})) \cdot g_{1} \\ = y \cdot g_{1} + (r - \frac{y - x}{s}) \cdot h_{1} \\ = C_{r - \frac{(y - x)}{s}} (y) \end{aligned}$

$$ \begin{align*} \varC_r(x) &= x \cdot g_1 + r \cdot h_1\\ &= x\cdot g_1 + {(s \cdot r)}\cdot g_1\\ &= (x + (y - x) + s(r - \frac{y - x}{s}))\cdot g_1\\ &= y\cdot g_1 + (r - \frac{y - x}{s})\cdot h_1\\ &= C_{r-\frac{(y - x)}{s}}(y) \end{align*}$$

Security Pitfalls #

Small-order elements: Pairing based cryptography often involves elliptic curve groups of composite order. Any elliptic curve points accepted from untrusted parties must be verified to reside in the proper large prime-order subgroup.
Polynomial interpolation: If $t + 1$ $t + 1$ $t + 1$ $t + 1$
Trusted setup: If using a trusted setup, $S K$ $S K$ $S K$

References #

[KZG2010] Polynomial Commitments (2010).
[Verkle Trees] Verkle trees.
[PLONK] PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge (2019).
[Groth16] On the size of pairing-based non-interactive arguments (2016).
[Pairing-Friendly Curves] Pairing-Friendly Curves.
[PBC] Pairing-based cryptography.

本文地址

https://architect.pub/kzg-polynomial-commitments

登录发表评论
3 次浏览

发布日期

星期二, 一月 28, 2025 - 13:27

最后修改

星期二, 一月 28, 2025 - 14:19

热门内容

今日:

总体:

最近浏览：

热门内容

今日:

总体:

最近浏览：

【安全技术】KZG 多项式承诺

category

Overview of Polynomial Commitments #