# zk 学习笔记 By [Jeffrey Hu](https://paragraph.com/@huzhiwei) · 2022-06-28 --- > 对 zk Talk 第一期《隐私型的扩容解决方案-零知识证明(1)》的一部分记录： > > [https://twitter.com/i/spaces/1LyxBoakdROKN?s=20](https://twitter.com/i/spaces/1LyxBoakdROKN?s=20) 零知识证明和 zkSNARKs --------------- “checking without understanding“。一方（prover）向另一方（verifier）证明一个命题为真，但 verifier 除了知道该命题为真以外并没有增加任何其他的知识。 在区块链领域内的应用： * 隐私 * 扩容 zkSNARKs -------- **Z**ero-**K**nowledge **S**uccinct **N**on-Interactive **AR**gument of **K**nowledge * 零知识 * 简洁 * 非交互式 * 证明 ### 零知识 “知识”在数学上是有非常良好的定义的。但“零知识”不是“零信息”的，因为要至少传递一些 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 **S**calable **T**ransparent。其中 S 不是简洁，因为一开始做不到，因此更多宣传其 Trusted Setup 的特点。 但 STARKs 其实也需要一个 uniformly-random string。 对 STARK 其实也没有像 SNARK 的学术定义，一般指的是 StarkWare 研发的算法。 Proof 最早可能比较大，但经过了多轮的迭代，目前也可以做到简洁。 Trusted Setup ------------- 以往学术界不太重视（不认为是一个大问题），但随着业界实用需求增长，也在被研究。Trusted Setup 目前不是大问题，因为： * Setup Ceremony 参与范围广，例如任何人都可以在 github 上提交，而且是永续的方式来提交。只要一个人感觉目前的随机数不安全，都可以再不断提交 * 不过 trusted setup 的 proof size 会更小 * 也可以把生成的过程用 MPC 的方式来解决 --- *Originally published on [Jeffrey Hu](https://paragraph.com/@huzhiwei/zk)*