<aside> 📘 TL;DR;
证明一组消息的完整性，给定一个消息，证明它属于这组消息。本质上功能和 Merkel-tree 一致，但是验证的计算效率为常数级，在数据量较大时性能显著好于 Merkel-tree。
生成一个用后即焚的秘密数 $\tau$（很多其他文章中称其为 s）。
挑战在于如何安全地生成并销毁这个秘密数，可以参考 Ethereum KZG ceremony。
用一个 $\ell$ 维的多项式拟合这组消息（利用泰勒级数可以拟合任意维度的多项式），这个多项式有 $\ell+1$ 个参数，利用秘密数生成 $\ell+1$ 个公共参数 $(g^{\tau^i})_{i\in[0,\ell]}$。其中 $g$ 是预先选定的椭圆曲线的本原元。公共参数生成完毕后，销毁秘密数 $\tau$。
<aside> 💡 举个例子，一个 3 维的多项式形如：$\phi(X) = 3x^3 + 2x^2 + x + 5$。
</aside>
<aside> 💡 关于椭圆曲线、本原元、有限域等相关信息，可以参考我此前写的博客。
</aside>
这个 $\ell$ 维的多项式称为 $\phi(X)$，将秘密数 $\tau$ 作为自变量计算可得 $\phi(\tau)$，然后可以计算得到 Commitment = $g^{\phi(\tau)}$，简称为 $C$，这个 $C$ 会作为数据的完整性证明持久化存储。（这个计算过程实际上不需要用到 $\tau$ 的明文，仅需要公共参数 $g^{\tau}$）。
可以看出 $C$ 仅仅是椭圆曲线有限域内的一个点，它的长度很小，在 BLS12_381 曲线上仅为 48 bytes。作为对比，sha-256 的 merkel-tree root 为 32 bytes。虽然 KZG 的承诺稍微长了一点，但是验证时所需的数据量会更小。
接下来就是需要证明某一个消息真的存在于这组消息之中，也就是消息的完整性证明。
选取一个消息 $a$，在多项式上满足 $\phi(a) = y$。我们需要去构建一个新的多项式 $q(X)$，这个多项式能够满足 $q(X) = \frac{\phi(X) - y}{X - a}$。
然后利用这个新的多项式，结合秘密数，计算得到 proof $\pi = g^{q(\tau)}$。注意此时秘密数 $\tau$ 已经被销毁，该计算并不需要用到 $\tau$ 的原值，而是通过公共参数 $g^{\tau}$ 就足够了。
验证者手中有椭圆曲线 $g$，公共参数 $(g^{\tau^i})_{i\in[0,\ell]}$，承诺 $C$，消息在多项式 $\phi(X)$ 上的数据点 $(a, y)$ 和证明 $\pi$。注意验证者并不需要知道多项式 $\phi(X)$ 的参数，而是只知道待验证的 $(a, y)$ 这一个点而已。
通过验证 $e(c / g^y, g) == e(\pi, g^\tau / g^a)$，证明消息的完整性。
值得注意的是，KZG 验证所需的数据量是恒定的。而 Merkel-tree 在验证时需要提供 $\log{n}$ 的消息哈希。当消息数量非常巨大时，在提供相同隐私性的同时，KZG 可以显著提升验证效率。
</aside>
Kate, Zaverucha and Goldberg introduced a constant-sized polynomial commitment scheme in 2010. We refer to this scheme as KZG and quickly introduce it below.
Prerequisites:
<aside> 📘 KZG 在对话前，需要先经历一个 trusted setup 的流程，挑选一个安全的椭圆曲线，生成各方都愿意接受的公共参数。
</aside>
To commit to degree $\le \ell$ polynomials, need $\ell$-SDH public parameters: $(g,g^\tau,g^{\tau^2},\dots,g^{\tau^\ell}) = (g^{\tau^i})_{i\in[0,\ell]}$
Here, $\tau$ is called the trapdoor. These parameters should be generated via a distributed protocol that outputs just the $g^{\tau^i}$’s and forgets the trapdoor $\tau$.
The public parameters are updatable: given $g^{\tau^i}$’s, anyone can update them to $g^{\alpha^i}$’s where $\alpha = \tau + \Delta$ by picking a random $\Delta$ and computing: $g^{\alpha^i} = \left(g^{\tau^i}\right)^{\Delta^i}$
This is useful when you want to safely re-use a pre-generated set of public parameters, without trusting that nobody knows the trapdoor.
Commitment to $\phi(X)=\sum_{i\in[0,d]} \phi_i X^i$ is $c=g^{\phi(\tau)}$ computed as:
$$ c=\prod_{i\in[0,\deg{\phi}]} \left(g^{\tau^i}\right)^{\phi_i} $$
Since it is just one group element, the commitment is constant-sized.