KZG Polynomial Commitment

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

下面简单地回顾一下 Feldman's Verifiable Secret Sharing (VSS)：Dealer 随机选择一个 \(t\) 次多项式 \(p(x)=s+a_1x+a_2x^2+\cdots+a_tx^t\) 后，向所有人公开下面信息（Commitment）： \[\begin{aligned} c_0 &= g^s \\ c_1 &= g^{a_1} \\ \cdots \\ c_t &= g^{a_t}\end{aligned}\] 然后把 \(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}\rightarrow \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\lt n,j\neq 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{aligned} C &\triangleq p(s) \cdot G_1 \\ &= \sum_{i=0}^{n-1}p_i \cdot s^i \cdot G_1 \end{aligned}\] 其中的 \(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{aligned} \pi &\triangleq q(s) \cdot G_1 \\ &= \sum_{i=0}^{n-1}q_i \cdot s^i \cdot G_1\end{aligned}\] 由上面的公式可知，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{aligned} && e(\pi, s \cdot G_2 - z \cdot G_2) &= e(C - y \cdot G_1, G_2) \\ & \longleftarrow & 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) \\ & \longleftarrow & e(G_1, G_2)^{q(s)(s - z)} &= e(G_1, G_2)^{p(s) - y} \\ & \longleftarrow & q(s)(s - z) &= p(s) - y \end{aligned}\] 显然，最后一式成立，所以第一式成立。

在节 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\lt t,j\neq 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{aligned} \pi &\triangleq q(s) \cdot G_1 \\ &= \sum_{i=0}^{n-1}q_i \cdot s^i \cdot G_1\end{aligned}\]

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{aligned} && e(\pi, Z(s) \cdot G_2) &= e(C-T(s) \cdot G_1,G_2) \\ & \longleftarrow & e(q(s)\cdot G_1, Z(s) \cdot G_2) &= e(p(s) \cdot G_1 - T(s) \cdot G_1, G_2) \\ & \longleftarrow & e(G_1, G_2)^{q(s) Z(s)} &= e(G_1, G_2)^{p(s) - T(s)} \\ & \longleftarrow & q(s)Z(s) &= p(s) - T(s) \end{aligned}\] 显然，最后一式成立，所以第一式成立。

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