Sin7Y团队深入研讨——几种多项式承诺方案

希望通过本文的介绍，让大家对这几种主流的PC方案有更全面的认识，然后在实际的应用过程中，选择最合适的PC方案。

在学习各种零知识证明算法的过程中，经常会看到这样一个 Cryptographic Primitives：Polynomial Commitment（PC）。

先看一下 Commitment 的定义：一个 Committer 提供一个 Public Value，这个 Value 称为 Commitment，是与原始的 Message 绑定（即 Computation Binding），且不暴露 Message（即 Hiding）；Committer 需要“Open”这个 Commitment，并发送 Message 给 Verifier 来验证 Commitment 和 Message 的对应关系。

而 PC 可以看成对某个多项式 P 的 Commitment，Committer 可以在不暴露多项式 P 的前提下，通过一个 Proof，来证明多项式在某点 z 的值，满足 P(z) = a。

实现 PC 的方案有很多种：

本篇将从多个点比较上述多项式方案的不同之处。

注：并不详细阐述每个方案的具体原理细节，有兴趣可以查阅论文及相关解读文档。

表 1 中给出了常见 PC 的计算形式，在不同的零知识证明算法中，正是由于选择了不同的 PC 方案，才导致了算法本身的不同，下面，我们就通过一张图来表述零知识算法与以上 PC 方案的对应关系：

不同的 PC 方案，导致不同的零知识证明算法具有不同的性质，在效率和安全性上也有明显的区别。比如，以 FRI 为基础的 zk-STARKs 算法，由于其依赖很少的数学安全假设，因此是抗量子的，且不需要任何可信设置；

再者，以 DARK 为基础的 Supersonic 算法，如果 unknown order group 是 RSA Group，则是需要可信设置的，依赖大数分解困难性假设；如果是 Class Group，则是不需要可信设置的，依赖计算 Class Group 元素数量的困难性。下面，我们仍然以一个表格的形式对比下，每个 PC 的优缺点：

其中，绿色，黄色，红色分别对应优，中等，一般。

在零知识证明算法中，Succinct 一般代表：Prove Succinct、Verify Succinct、Communication Succinct。因此，在上表中第二行，根据每个算法对应的上述三个指标的不同，对其优劣进行了标识。接下来，让我们具体看一下，每个 PC 对应的性能指标：

颜色标识与上述一致。

从表格中可以看出，从 Succinct 角度评比，KZG 方案最佳；它的证明大小和验证时间都是常量级，也就是说 Circuit 的 size 增大，不会导致 Proof size 的增大；而其他的 PC 方案，Proof size的大小，都与 circuit 规模有关，且为递增关系。但是，从安全性角度分析，KZG 的方案由于需要第三方的可信设置（参见表 1），因此相对于其他的方案，安全性弱一些。

上述过程给出了几种主流 PC 方案的多角度比较分析，在实际的生产应用过程中，需要项目方对其应用场景做全面评估。到底是要更高的安全性，还是要更好的效率，这一直是一个权衡博弈的问题。希望通过上述的介绍，让大家对这几种主流的 PC 方案有更全面的认识，然后在实际的应用过程中，选择最合适的 PC 方案。

• 发表于 1天前
• 阅读 ( 64 )
• 学分 ( 0 )
• 分类：零知识证明