# 零知识前沿：关于SNARKs，STARKs和未来的应用 By [Kurt Pan](https://paragraph.com/@kurtpan) · 2022-05-07 --- 作者：Vaish Puri 译者：Kurt Pan * * * > “我只知道一件事，那就是我一无所知”——苏格拉底 在今天的文章中，我将剖析有史以来最强大但经常被误解的密码学工具之一：**零知识证明**。此外，我将重点介绍未来实现的用例和建议，并展示为什么零知识证明是crypto未来的关键。 为什么零知识证明很重要 ----------- 简单地说，零知识证明是证明者在不实际透露任何信息的情况下说服验证者某事是真实的一种方式。让我们用一个类比来说明这一点：假设我们有两个人，Alice 和 Bob。Alice有一副密封的 52 张扑克牌。Alice偷偷拿了一张红牌（♥️，♦️）想向Bob证明她有一张红牌，但不想出示该红牌本身。为了做到这一点，Alice 需要将所有的黑牌（♠️，♦️）从牌堆中拿出来，然后将它们展示给 Bob。Bob 检查所有 26 张黑牌，验证其不重复不遗漏。由是确定 Alice 拥有的牌必是红牌。因此，Alice能够向Bob证明她有红牌，而无需实际出示。这个类比是_极度_简化的而且并没有描绘出全貌，但技术背后的核心理念是一样的。 零知识证明并非这十年来甚至这个新千年来的新鲜事物。事实上，该想法是[在 1980 年代](https://www.nytimes.com/1987/02/17/science/a-new-approach-to-protecting-secrets-is-discovered.html)由抽象数学的研究者首次提出的。该方案旨在解决当时的与证明者和验证者之间的理论系统--**交互式证明**\--相关的问题。 但是如果验证者是恶意的怎么办？除了验证声明的真实性之外，证明者还泄漏了多少额外信息？让我们看看中心化服务器上口令的哈希是如何存储的。传统上，在与服务器交互时，服务器会知道明文口令。这是进行“身份证明”的一种糟糕方式，因此研究者转向了一种可以在不泄露任何无关信息的情况下证明声明的新系统。 更具体地说，假设我们有函数`C`，有两个输入`C(x,y)`。令`x`为公开输入，`y`为秘密证据，函数的输出为真或假。给定一个特定的公共输入`x`，证明者必须证明他知道一个秘密证据`y`使得`C(x,y) == true`。从证明者的角度来看，实现零知识需要**随机性**。验证者方面，也需要随机性来产生对证明者的查询。 被广泛展示的[第一个应用](https://www.cs.cmu.edu/~goyal/s18/15503/scribe_notes/lecture23.pdf)是一个[NP完全](https://en.wikipedia.org/wiki/NP-completeness) 的称为[图三着色](https://en.wikipedia.org/wiki/Graph_coloring)问题。这是一个巨大的突破，因为这个可以应用于NP 类中的_任何问题_。简直就是“一石N鸟”。 在区块链领域，由于零知识证明能够提供可扩展性以及在隐私模型中的实用性，因此有了许多实现。具体来说，与不用零知识证明系统的情况相比，验证者执行的计算工作呈指数级减少。另一方面，证明者需要相当多的计算开销来执行证明。我稍后会详细讨论这个问题。 零知识协议 ----- 目前存在大量的零知识协议，但这篇文章中我将重点关注 **SNARK** 和 **STARK**，并在后续文章中深入探讨其他协议。 **简洁非交互知识论证**，SNARK，是一种流行的证明机制，其纳入了于2011年[首次提出](https://eprint.iacr.org/2011/443.pdf) 的零知识证明。在底层，zk-SNARK 使用椭圆曲线来保证安全性并依赖于可信设置。一开始，创建导出交易所需证明和验证所述证明的密钥。这些密钥包含一个[参考字符串](https://eprint.iacr.org/2019/099.pdf)，将验证密钥和发送私有消息的密钥联系起来。为此，必须有删除所创建的密钥的方法，且密钥的创建者必须是可信的（因此称为**可信设置**）。这种在创建阶段对信任的依赖仍然是对 zk-SNARKs 的一大批评点。此外，参考字符串是不可更新的，这意味着如果程序需要更新，则需要重新运行可信设置阶段。 然而实际实践中，zk-SNARK 很少会独自出现。在计算中往往需要检查许多步骤，但是单独检查每个步骤的工作将花费大量时间。解决方案以**多项式**的形式出现。将计算[编码](https://eprint.iacr.org/2019/953.pdf)为多项式可以节省大量信息和时间。相比于数字之间的无数个方程，我们可以代替为“[代表](https://vitalik.ca/general/2021/01/26/snarks.html)”它们的多项式表达式。 还有，通常会通过检查每个系数来使用多项式验证方程，但这又需要太长时间。**多项式承诺**在这里开始发挥作用。多项式承诺可以被视为用来“[哈希](https://vitalik.ca/general/2021/01/26/snarks.html)”一个多项式的独特方法，允许在更短的时间内进行验证，无论多项式有多大。此外，多项式承诺_本质上_是保护隐私的，因为证明比多项式本身小得多。尽管可以添加随机性，多项式承诺只会泄漏多项式的少量信息。如需更深入地了解多项式承诺和验证，请查看[此](https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma)内容。 多项式承诺使用三种主要协议之一：[bulletproof](https://eprint.iacr.org/2017/1066.pdf)、[KZG](https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html)和[FRI](https://drops.dagstuhl.de/opus/volltexte/2018/9018/pdf/LIPIcs-ICALP-2018-14.pdf)。比较和对比每一个都会使本文变得有点难懂，且超出了本文的范围，因为每个都值得去深入研究。 2018 年，因为厌倦了现状，一群研究者试图在零知识系统中加入**透明性**。透明性意味着不必依赖受可信方进行初始设置，从而消除了开放后门的威胁。这导致了**可扩展透明知识论证**，或[STARKs](https://eprint.iacr.org/2018/046.pdf)，的发明。STARK 使用哈希函数作为其安全性来源，这与 SNARK 使用的双线性配对不同。名字里的**可扩展**指的是如下两件事： 1. 与 SNARK 相比，证明者运行时间在复杂性上要低得多。 2. 验证时间是多项式对数。STARKs[使用了](https://vitalik.ca/general/2017/11/22/starks_part_2.html)FRI，提升了信息存储量和性能。 当前应用 ---- 虽然像[Zcash](https://z.cash/)这样的 zk-SNARK 先驱已经存在了一段时间，是zk-STARK 的发明使得开发空间迎来了爆炸式的增长。零知识协议方面的工作不仅限于**rollups**。事实上，[一些 L1](https://minaprotocol.com/)已经是基于零知识证明来构建的了，以及刚萌芽的[游戏](https://blog.zkga.me/announcing-v6)项目。 [StarkWare](https://starkware.co/)是 zk-STARK 的先驱，开发了两个核心产品：**StarkNet**，一个无需许可的去中心化 zk-rollup，以及 **StarkEx**，一个独立的 zk-rollup SaaS。此外，StarkWare 是名为 **Cairo** 的生产级零知识虚拟机 (zkVM) 的第一家生产商。Cairo 声称通过实现图灵完备的[冯诺依曼](https://en.wikipedia.org/wiki/Von_Neumann_architecture) 架构以达到这一点。每个程序与它处理的数据一起驻留在 VM 的内存中。[今天任何人](https://www.cairo-lang.org/playground/)都可以访问Cairo，目前正被一些有名的 StarkEx 客户所使用，如[dydx](https://dydx.exchange/)、[Immutable](https://www.immutable.com/)和[DeversiFi](https://deversifi.com/)。其他使用他们自己版本的 zkVM 的新应用包括[Polygon Miden](https://github.com/maticnetwork/miden)和[RiscZero](https://www.risczero.com/)，后者正在尝试构建通用 zkVM。 与自启动的 zkVM 思想相反的是 **zkEVM**。zkVMs 是从头开始做针对零知识优化的新的区块链虚拟机，或者只是适配 Solidity 工具和兼容性。另一方面，zkEVM 实现了完整的 EVM[操作码](https://ethereum.org/en/developers/docs/evm/opcodes)集。使用 EVM 操作码有几个好处： * 实现与 EVM 生态系统和工具的完全兼容 * 继承以太坊安全模型 * 效率可能类似于基于编译器的方法 不出所料，zkVM 和 zkEVM 阵营之间似乎存在很大的分歧。 ![](https://storage.googleapis.com/papyrus_images/eb432e1ddf0cec0a5e795119d96a04fbb720346682d2b97fd9856b26a9ec035a.png) zkEVM 相对于 zkVM 的最大优势是 **EVM 等效性**。历史证明，通过低 gas 费激励和为开发人员提供简单的起始体验来瞄准庞大的现有 dApp 社区是卓有成效的，这正是 zkEVM 建设者所期望的。 目前最流行的 zkEVM 项目是[zkSync](https://zksync.io/)，它使用 zk-SNARKs 作为2层解决方案进行验证和扩展。此外，zkSync 选择将数据可用性置于链下，并由 zkSync 代币质押者使用权益证明 (zkPorter) 进行保护（这意味着空投可能马上到来）。此实现的设计属于 StarkWare 开发的名为[Volition](https://medium.com/starkware/volition-and-the-emerging-data-availability-spectrum-87e8bfa09bb)的解决方案。 最后，一个新玩家[Scroll](https://scroll.io/)正在开发一个通用的 L2 zkEVM。Scroll 采用了一种新方法来使用 GPU 的能力来在链下生成零知识证明。最近在零知识证明方面的突破，如[Poseidon hash](https://eprint.iacr.org/2019/458.pdf)、[Plookup](https://eprint.iacr.org/2020/315.pdf)和[PLONK](https://eprint.iacr.org/2019/953.pdf) ，已经将成本降低到足以使 zkEVM 成为现实。此外，GPU 和 ASIC/ [FPGA 加速器](https://www.paradigm.xyz/2022/04/zk-hardware)的进步正在改善硬件条件，进一步降低成本。Scroll 仍处于开发阶段，计划在未来几个月内推出他们的 zkEVM 测试网。 未来的应用 ----- 零知识证明最初是为了**保护隐私**而开发的。尽管主流媒体可能将当前的用例集中在“允许更大的 TPS ”上，但事实仍然是零知识证明具有更广阔的应用范围。 一个这样的应用是[这个工具](https://github.com/eigenvector-labs/zk-ID)，它通过零知识电路来匿名检查钱包中的资产或链上交易以验证用户的身份。 **零知识身份**具有极其强大的潜力，并且在现实世界中可以立即找到用例。例如，假设我是一名债务人，试图证明自己的信誉，同时仍将银行信息和活动保密。我会证明我已经从多家受信任的银行偿还了大笔贷款，但不会透露这些银行的名字或这些贷款的规格。  支持未来零知识身份的四个关键组件：https://0xparc.org/blog/zk-id-2 零知识领域的另一个重大进展是**zk-SNARK 证明者的高效隐私代理**。如前所述，证明时间相当缓慢。使用 `SHA2` 来哈希 10kb 数据需要 140 秒，而不是所需的几毫秒。解决这个问题的方法是将证明过程外包。不幸的是，这带来了另一个困境：秘密总是会泄露给外包的机器。于是需要的是外包**隐私**证明。通过仔细的实现，目前已经可以将证明代理给手机等设备，其[速度](https://www.youtube.com/watch?v=iT_s92f3wds&list=PLj80z0cJm8QFnY6VLVa84nr-21DNvjWH7&index=2&ab_channel=ZeroKnowledge)比本地计算快 26 倍。这个新颖的框架由[Pratyush Mishra](https://twitter.com/zkproofs?lang=en)在 2022 年 4 月的 zkSummit 上首次提出。 结语 -- 我们在开发基于零知识证明的应用方面还处于非常早期的阶段。尽管如此，进展的步伐还是很快的。原先专家认为在 5 年内无法达到的阶段目前已经实现了。当然，还有很多事情要做。开发社区之间仍然存在很多冲突，因为[阵营正在形成](https://twitter.com/kelvinfichter/status/1522389735897022464?t=k8bJ1Ow8hrQvggF62TD91Q&s=19)，观点正在被政治化。只有时间会证明哪一方是正确的。可以肯定的是，当历史学家回顾过去时，他们会将这一时期的零知识实现视为加密货币壮观历史中的开创性部分。 --- *Originally published on [Kurt Pan](https://paragraph.com/@kurtpan/snarks-starks)*