KZG Polynomial Commitment

在 KZG10 多项式承诺提出之前，已经有了其它的承诺方案，比如哈希承诺，Pedersen 承诺等等。为什么还需要多项式承诺呢？论文作者以 Verifiable Secret Sharing 为例介绍了引入多项式承诺的动机。

下面简单地回顾一下 Feldman's Verifiable Secret Sharing (VSS)：Dealer 随机选择一个 $t$ 次多项式 $p(x)=s+a_{1}x+a_2{x}^2+\cdots +a_t{x}^t$ 后，向所有人公开下面信息（Commitment）： $$\begin{array}{rl}{c}_0& =g^s\\ c_1& =g^{a_1}\\ \cdots \\ c_t& =g^{a_t}\end{array}$$ 然后把 $p(i),1\le i\le n$ 通过加密通道分别发送给第 $i$ 个参与者 $P_i$ 。第 $i$ 个参与者验证 $g^{p(i)}=c_0{c}_1^i{c}_2^{i^2}\cdots c_t^{i^t}$ 是否成立，成立就通过协议。

上面的 VSS 有个缺点：Commitment 有 $t+1$ 个值（ $c_0,c_1,\cdots ,c_t$ ）， Commitment 数据量太大。 有办法让这个 Commitment 数据量变小吗？比如，我们可以尝试这样改进：把多项式系数 $s,a_1,\cdots ,a_t$ 拼在一起计算一个哈希，即把 $\text{Hash}(s||a_1||\cdots ||a_t)$ 作为 Commitment，这样 Commitment 数据量是变小了。但是，在 Commitment 的 Open 阶段 Dealer 需要公开多项式的所有系数 $s,a_1,\cdots ,a_t$ 。这在 VSS 协议中是不可接受的，因为系数 $s$ 是 VSS 协议的关键秘密，不能让任何单个参与者知道。注：Feldman's Verifiable Secret Sharing 向参与者 $P_i$ 公开的数据是 $p(i),1\le i\le n$ ，也就是说 Dealer 只向 $P_i$ 公开了多项式 $p(x)$ 在点 $i$ 处的值，并没有公开整个多项式。

多项式承诺可以解决上面问题：

1. 在承诺的 Commit 阶段， 生成的 Commitment 比较小；
   
2. 在承诺的 Open 阶段， 不需要公开整个多项式，支持 Partial Open。
   

注：对于 KZG10 多项式承诺的这两个优点，Merkle Tree 都有，也就是说 Merkle Tree 的 Commitment 也比较小，也支持 Partial Open。和 Merkle Tree 相比，KZG10 多项式承诺的优点是 Proof Size 比较小，如表 1 所示。

KZG10 多项式承诺依赖于 Pairing： $$e:{\mathbb{G}}_1\times {\mathbb{G}}_2\to {\mathbb{G}}_T$$ 设 $G_1,G_2$ 分别是群 ${\mathbb{G}}_1,{\mathbb{G}}_2$ 的 Generator。设 $s$ 是一个秘密值，计算 $s^i\cdot G_1,s\cdot G_2$ （其中 $i=1,2,\cdots$ ）并把它们公开给所有人。在 Setup 结束后， $s$ 会被销毁，没人再知道 $s$ 值。 $s$ 也称为 trapdoor 值，因为它一旦销毁后，没有人能够再计算出这个值；换一种角度说，假设某人知道了 trapdoor 值，那么整个协议就不安全了。

假设 Prover 需要向别人承诺 $n$ 个值 $[x_0,x_1,\cdots ,x_{n-1}]$ （也就是说不想公开这些值，但在 Open 阶段要说服 Verifier 我知道这些值）。首先， Prover 把这些值编码为满足 $p(i)=x_i,0\le i\le n-1$ 的多项式，记这个多项式为 $p(x)$ 。 利用拉格朗日插值多项式公式可知： $$p(x)=\sum _{i=0}^{n-1}{x}_i\prod _{0\le j<n,j\ne i}\frac{x-j}{i-j}$$ 这是一个 $n-1$ 次多项式，记 $p_i$ 是这个 $n-1$ 次多项式的系数。也就是说这个 $n-1$ 次多项式还可以表示为 $p(x)=\sum _{i=0}^{n-1}{p}_i{x}^i$ 。

对这 $n$ 个值 $[x_0,x_1,\cdots ,x_{n-1}]$ 的 Commitment 为： $$\begin{array}{rl}C& \triangleq p(s)\cdot G_1\\ & =\sum _{i=0}^{n-1}{p}_i\cdot s^i\cdot G_1\end{array}$$ 其中的 $s^i\cdot G_1$ 在 Setup 阶段已经由 Dealer 公开给所有人了。由上面的公式可知， Commitment 是椭圆曲线 ${\mathbb{G}}_1$ 上的一个点，它不依赖于 $n$ 的大小，这就是 KZG10 的 Commitment 比较小的原因。 承诺 10 个值和承诺 1000 个值它们的 Commitment 大小是一样的。

假设现在 Prover 想证明他掌握了 $[x_0,x_1,\cdots ,x_{n-1}]$ 中的某个值 $x_z,0\le z\le n-1$ ，记 $y\triangleq x_z$ ，也就是说 Prover 需要证明 $p(z)=y$ 。下面引入一个新多项式： $$q(x)\triangleq \frac{p(x)-y}{x-z}$$ KZG 证明了这个多项式存在。和记号 $p_i$ 类似，记 $q_i$ 是多项式 $q(x)$ 的各个系数。

Prover 如果要证明在索引 $z$ 处，多项式的值为 $y$ ，则他需要公开的 Witness 为： $$\begin{array}{rl}\pi & \triangleq q(s)\cdot G_1\\ & =\sum _{i=0}^{n-1}{q}_i\cdot s^i\cdot G_1\end{array}$$ 由上面的公式可知，Witness $\pi$ 也是椭圆曲线 ${\mathbb{G}}_1$ 上的一个点。

Verifier 收到 Witness $\pi$ 后，验证： $$e(\pi ,s\cdot G_2-z\cdot G_2)\stackrel{?}{=}e(C-y\cdot G_1,G_2)$$ 是否成立（式中 $s\cdot G_2$ 在 Setup 阶段就计算好了，因为 $s$ 在 Setup 阶段结束后就销毁了，所以 $s\cdot G_2$ 需要在销毁 $s$ 前计算），如果成立则说明 Prover 没有说谎，Commitment $C$ 中确实包含了对 $x_z$ 的承诺。

为什么 $e(\pi ,s\cdot G_2-z\cdot G_2)\stackrel{?}{=}e(C-y\cdot G_1,G_2)$ 会成立呢？这是因为： $$\begin{array}{rlrl}& & e(\pi ,s\cdot G_2-z\cdot G_2)& =e(C-y\cdot G_1,G_2)\\ & ⟵& e(q(s)\cdot G_1,s\cdot G_2-z\cdot G_2)& =e(p(s)\cdot G_1-y\cdot G_1,G_2)\\ & ⟵& e(G_1,G_2{)}^{q(s)(s-z)}& =e(G_1,G_2{)}^{p(s)-y}\\ & ⟵& q(s)(s-z)& =p(s)-y\end{array}$$ 显然，最后一式成立，所以第一式成立。

在节 2.3 中，只打开了多项式的一个点 $(z,y)$ 。现在，假设要打开 $t$ 个点，即 $p(z_i)=y_i\text{for}i\in \{0,\cdots ,t-1\}$ ，一个显而易见的办法是 Prover 分别为这 $t$ 个点计算相应的 Witness，而 Verifier 执行 $t$ 次 Verify 过程分别验证每个点。这种方法可行，但性能不好，下面介绍一种更快的方法。

首先，把需要打开的这 $t$ 个点编码为满足 $T(z_i)=y_i,0\le i\le t-1$ 的多项式，记这个多项式为 $T(x)$ 。利用拉格朗日插值多项式公式可知： $$T(x)=\sum _{i=0}^{t-1}{y}_i\prod _{0\le j<t,j\ne i}\frac{x-z_j}{z_i-z_j}$$

由于前面介绍的多项式 $p(x)$ 也经过了这些点，所以有 $p(x)=T(x)\text{for}x\in \{z_0,\dots ,z_{t-1}\}$ ，我们定义： $$q(x)\triangleq (p(x)-T(x))/Z(x)\text{where}Z(x)=\prod _{j=0}^{t-1}(x-z_j)$$ 多项式 $q(x)$ 一定存在，记 $q_i$ 是多项式 $q(x)$ 的各个系数。

Prover 计算 Witness 时，其定义不变，为： $$\begin{array}{rl}\pi & \triangleq q(s)\cdot G_1\\ & =\sum _{i=0}^{n-1}{q}_i\cdot s^i\cdot G_1\end{array}$$

Verifier 收到 $\pi$ 后，验证： $$e(\pi ,Z(s)\cdot G_2)\stackrel{?}{=}e(C-T(s)\cdot G_1,G_2)$$ 是否成立。

为什么 $e(\pi ,Z(s)\cdot G_2)\stackrel{?}{=}e(C-T(s)\cdot G_1,G_2)$ 会成立呢？这是因为： $$\begin{array}{rlrl}& & e(\pi ,Z(s)\cdot G_2)& =e(C-T(s)\cdot G_1,G_2)\\ & ⟵& e(q(s)\cdot G_1,Z(s)\cdot G_2)& =e(p(s)\cdot G_1-T(s)\cdot G_1,G_2)\\ & ⟵& e(G_1,G_2{)}^{q(s)Z(s)}& =e(G_1,G_2{)}^{p(s)-T(s)}\\ & ⟵& q(s)Z(s)& =p(s)-T(s)\end{array}$$ 显然，最后一式成立，所以第一式成立。

这里有个使用 BLS12-381 曲线演示 KZG10 多项式承诺的例子：https://github.com/qizhou/research/blob/main/poly_commit/bls/poly_commit.py