对 zk Talk 第一期《隐私型的扩容解决方案-零知识证明(1)》的一部分记录：

https://twitter.com/i/spaces/1LyxBoakdROKN?s=20

零知识证明和 zkSNARKs

“checking without understanding“。一方（prover）向另一方（verifier）证明一个命题为真，但 verifier 除了知道该命题为真以外并没有增加任何其他的知识。

在区块链领域内的应用：

• 隐私
• 扩容

zkSNARKs

Zero-Knowledge Succinct Non-Interactive ARgument of Knowledge

• 零知识
• 简洁
• 非交互式
• 证明

零知识

“知识”在数学上是有非常良好的定义的。但“零知识”不是“零信息”的，因为要至少传递一些 01 串的信息给对方。零知识本质上在于熵很大，都是很随机的信息，无法从中提取出有用的知识。

简洁

“简洁”的证明尺寸是 sublinear 的。简洁对于验证非常重要，对于区块链尤为重要，因为链上成本和考虑到其他节点容易接收等。

非交互式

• 交互式证明：
  • 最早是需要反复“问答”来确认证明者拥有某项知识
  • 最早 Goldwasser、Micali、Rackoff 在 1985 年提出“The Knowledge of Complexity of Interactive Proof Systems”
• 非交互式证明
  • 1987 年，NIZK（非交互式零知识证明），避免反复问答来确认。实现方式包括：
    • 可以引入一个第三方采用“随机预言机”
    • 也可以用 CRS（Common Reference String，公共参考串）
  • CRS 相当于是给完全没有信任基础的双方一点点信任基础（Trusted Setup）

证明

零知识证明里的证明（proof），其实一般多指的是“argument”。因为 argument 和 proof 的区别是

• proof 没有任何限制条件；而 argument 在多项式时间内可以完成的计算，而且体积比较小
• 另一个区别是在安全性上
  • 安全性上有两个对抗性的属性：可靠性、零知识
  • argument 倾向于零知识（所以也不用担心未来超级计算机去破解）

zkSNARKs vs SNARKs

也可以单独说 “SNARKs”。zkSNARKs 和 SNARKs 的算法几乎差不多，可能 80% - 90% 都是一样的，只是一些关键步骤可能不一样，两者之间不是竞争关系。主要区别是：

• zkSNARKs 加上了隐私
• SNARKs 更多只是关注于压缩，而不关心计算的数据是否是隐私的

一些重要的里程碑

• 1985 提出交互式零知识证明
• 85 年 - 92 年
  • 计算理论发展很快，很多重要理论都是在这个阶段，例如 argument 等。因为零知识证明其实和计算复杂度理论的关系比密码学的关系更大
  • 这段时间也提出了非交互式零知识证明（NIZK）
  • 最早的 SNARK 的定义也在 92 年提出
• 92 年 - 02 年
  • 基于 CRS 的非交互式零知识证明：多方共同约定一串数，给完全没有信任的基础一点点信任基础。其他的的实现方式还包括 Random Oracle、PCP 等
  • Schnorr 协议，很多零知识证明最早的起点
  • Cramer 和 Damgard（CD98）引入算术电路，用算术电路做零知识证明。即把常见的运算转换为零知识证明，之后就可以和写程序绑定在一起
• 02 年 - 10 年
  • 02、03 年左右， Dan Boneh 提出基于椭圆曲线的双线性配对（ECC pairing）椭圆曲线上和乘法相关的一些构造
  • Groth10，可以用 很短的 proof size 来构造零知识证明（之前要一个证明要大概几个G）
• 10 年之后
  • GGPR13，论证了很多零知识证明可用，并且提供了一个 libsnark 的库（两年前直接业界基本都会用的一个库；现在不太维护，业界主要都切换为 rust）
  • ZCash 第一个区块链领域内的零知识应用，基于2014 的论文和 libsnark，2015年就实现上线
  • 接下来，零知识证明社区和区块链世界开始结合，一直延续到2017-2018年
  • 从2018年到现在，很多算法开始合流

当前常见算法

当前主要的两类算法：

• PLONK
• zkSTARK

其他还包括 Marlin（Aleo）等，但和 Plonk 区别不是太大

Halo

Halo 比较受关注，不需要 trusted setup。Halo 主要基于5个前置的工作：

• 和 bulletproof 关系很大
• 一种递归分摊的工作，解决递归零知识证明的工作
• 多项式承诺（KZG 10），零知识证明的操作抽象成同一个接口，有非常简洁的接口
• STARK，StarkWare 的创始人最早对虚拟机做零知识证明的（可以看作是非常早期的 zkEVM），两个曲线可以互相嵌入
• Plonk，Aztec 团队发明的

zkSTARK

Scalable Transparent。其中 S 不是简洁，因为一开始做不到，因此更多宣传其 Trusted Setup 的特点。

但 STARKs 其实也需要一个 uniformly-random string。

对 STARK 其实也没有像 SNARK 的学术定义，一般指的是 StarkWare 研发的算法。

Proof 最早可能比较大，但经过了多轮的迭代，目前也可以做到简洁。

Trusted Setup

以往学术界不太重视（不认为是一个大问题），但随着业界实用需求增长，也在被研究。Trusted Setup 目前不是大问题，因为：

• Setup Ceremony 参与范围广，例如任何人都可以在 github 上提交，而且是永续的方式来提交。只要一个人感觉目前的随机数不安全，都可以再不断提交
• 不过 trusted setup 的 proof size 会更小
• 也可以把生成的过程用 MPC 的方式来解决