多项式承诺

多项式承诺方案对比

几种常见的poly-commitment方案比较

多项式承诺的概念

假设你有一个 $n$ 次多项式 $f(x)$:

$$f(x)=a_0+a_{1}x+a_2{x}^2+...+a_n{x}^n$$

我们对多项式可以做出一个承诺 $C=commit(f)$ ，这个承诺满足以下两个性质：

• 隐藏性（Hiding）: 承诺 $C$ 不泄露关于多项式 $f(x)$ 的任何信息。也就是说，给定承诺 $C$，无法推断出多项式的系数 $a_0,a_1,...,a_n$。
• 绑定性（Binding）: 难以再找到一个 不同的多项式 $f^{\prime }(x)$ 使得 $commit(f^{\prime })=C$。也就是说，一旦你对一个多项式做出了承诺，就不能再改变它而不被发现。

很自然地，对于一个多项式的承诺，我们可以想到对多项式的每一个系数做一个哈希承诺或者 Pederson承诺，但是接下来我们描述的方案有一个更优良的性质。

承诺

$Alice$ 选择一个多项式 $f(x)$，并计算承诺 $C=commit(f)$，然后将 $C$ 发送给 $Bob$。

查询Oracle

$Bob$ 发送一个查询点 $\zeta$ 给 $Alice$，$Alice$ 计算多项式在该点的值 $y=f(\zeta )$，并生成一个证明 $\pi$，这个证明能够保证运算的正确性。

验证

$Bob$ 接收到 $y$ 和 $\pi$ 后，使用承诺 $C$ 和 $\varphi$ 来验证 $y$ 是否确实是多项式 $f(x)$ 在点 $\zeta$ 处的值。

这个 $\varphi$ 的特性非常有用，可以用来构造 可验证计算（Verifiable Computation，既对于一个 $V$ 来说，我可以把一个复杂的运算 $f$ 代理给一个不可信的 $P$ 来计算，$P$ 计算完之后给出结果和证明，$V$ 可以高效地验证结果的正确性，而不需要重新计算 $f$。

此外，我们还能用来构造 零知识证明，既 $P$ 有一个满足某个约束的值，但是不想泄露这个值本身，只想证明自己知道这个值满足约束，那么 $P$ 可以把这个值嵌入到一个多项式中，然后使用多项式承诺来生成证明。