本文介绍 KZG 多项式承诺。

前置知识

  • 多项式承诺 介绍密码学中承诺的概念以及实现方案，其中重点介绍了多项式承诺及其几种实现方案的对比。
  • 椭圆曲线 介绍椭圆曲线、加法、生成元、配对公式等知识。

简介

KZG 多项式承诺（KZG Polynomial Commitment）源自于 Aniket Kate, Gregory M. Zaverucha 和 Ian Goldberg 在 2010 年发表了多项式承诺方案论文 Constant-Size Commitments to Polynomials and Their Applications，也被称为卡特多项式承诺方案，该方案在 plonk-style 的 zk-snark 协议中有很广泛的应用。主要特性：

  1. 承诺是一个支持配对的椭圆曲线的群元素。比如说对于 BLS12_381 曲线，大小应是 48 字节。
  2. 证明大小独立于多项式大小，永远是一个群元素。验证，同样独立于多项式大小，无论多项式次数为多少都只要两次群乘法和两次配对。
  3. 大多数时候该方案隐藏多项式 - 事实上，无限多的多项式将会拥有完全一样的卡特承诺。但是这并不是完美隐藏：如果你能猜多项式（比如说该多项式过于简单，或者它存在于一个很小的多项式集合中），你就可以找到这个被承诺的多项式。
  4. 在一个承诺中合并任意数量的取值证明是可行的。这些性质使得卡特方案对于零知识证明系统来说非常具有吸引力，例如 PLONK 和 SONIC。同时对于一些更日常的目的，或者简单的作为一个矢量承诺来使用也是非常有趣的场景，接下来的文章中我们就会看到。

数学原理

经典文章：Dankrad Feist：kzg 多项式承诺

可参考 Qi Zhou 博士关于 kzg 的讲解：

可信设置

  • EIP-4844 中采用了一种常见的 multi-participant trust setup，即 powers-of-tau；

  • 遵循 1-of-N 可信模型，不管多少人参与 generating setup 的过程，只要有一个人不泄漏自己的生成方式，可信初始化就是有效的；

  • 必要性

    • KZG commitment 的 trust setup 可以简单理解为：生成一个在每次执行 cryptographic protocol 时需要依赖的一个参数，类似于 zk-snark 需要可信初始化；
    • Prover 在提供证明时，KZG commitment C = f(s)g1。其中 f 是评估函数，s 就是 KZG trusted setup 最终获得的 final secret；
    • 可以看出 final secret 是生成多项式承诺的核心参数，而作为获取这个核心参数的可信流程，这次 KZG Ceremony 对于整个 sharding 的实现非常重要。

  • vitalik: How do trusted setups work?

应用

延伸阅读

参考