开源 Winterfell：一个 STARK 的证明者和验证者

Winterfell 是用于安全和隐私应用程序的 STARK 的易于使用的开源实现。 “任何足够先进的技术都与魔法无异。” — 克拉克第三定律 如果普通开发人员可以从通常需要深入了解密码学才能实施的计算完整性 (CI) 证明中受益，会怎样？ CI 证明，其中零知识证明 (ZKP) 是一个子集，是一种密码技术，可以让您完成看似不可能的事情。例如，您可以运行计算并获得一些结果。然后，您可以使用 CI 证明让任何人相信您正确地进行了计算，而无需他们自己重新运行计算。他们可以在短短几毫秒内验证这种正确性，无论原始计算有多复杂或运行时间有多长。为了将 CI 证明的力量带给大众，我们开发了 Winterfell，这是一个通用的 STARK（可扩展的透明知识论证）证明者和验证者。我们很高兴将库的 v0.1 版本发布到 crates.io。这些 CI 证明的另一个重要特性是能够隐藏用于运行计算的部分（或全部）输入。这就是零知识方面。例如，您可以证明一个数字在给定的范围内，而无需透露该数字的确切值（这些类型的证明通常称为范围证明）。或者，您可以做一些复杂的事情，例如比较两个数字序列，一个是公共的，一个是私有的（只有您自己知道），然后向任何人毫无疑问地证明它们之间是否匹配。 ZKP 背后的一般思想早在 1980 年代就已发展起来，但最近对该密码学领域的兴趣激增，部分原因是区块链领域的新兴应用。在过去几年中，出现了十多种新的证明系统。其中一些甚至已部署在生产中，数百亿美元取决于其安全属性。然而，ZKP 远非主流，主要有两个原因： 直到最近，在应用程序中部署 ZKP 还需要具有多年经验的专家密码学家。现在的情况有所好转，因为有大量相对容易获得的材料和更多的项目试图让普通开发人员可以使用 ZKP。但即使是现在，即使对于经验丰富的软件工程师来说，理解不同的证明系统以及与之相关的权衡也需要深厚的专业知识和/或陡峭的学习曲线。

虽然验证 ZK 证明非常快并且需要很少的计算资源，但生成证明是一个计算密集型过程。即使是相对简单的计算，也可能需要几秒钟甚至几分钟（或许多 CPU 内核）来生成证明。只有在密码学和实现改进方面相对较新的进展才能使大部分计算达到 ZKP 的实际可行性。并且有很多正在进行的工作来扩展证明生成实用的计算集。我们开发了 Winterfell 来弥合这些差距，并使常规开发人员可以使用 ZKP。 Winterfell 是 Novi Research 用 Rust 编写的通用 STARK 证明器和验证器。通用意味着 Winterfell 可以为任何计算生成 CI 证明。基本上，对于任何可以用图灵完备语言描述的程序，我们都可以使用 Winterfell 生成 CI 证明（尽管这对于某些程序来说比其他程序要简单得多）。 Winterfell 使用 STARKs，这是一种由 Eli Ben-Sasson、Michael Riabzev 等人开发的计算证明方案。与许多其他 CI 证明系统相比，STARKs 具有许多吸引人的特性，包括： STARKs 依赖很少的密码假设。事实上，我们需要让 STARK 工作的唯一密码原语是抗碰撞哈希函数（例如，SHA256）。这也使 STARK 能够抵御来自使用量子计算机的对手的潜在攻击。与许多其他证明系统不同，STARK 是完全透明的。这意味着我们不需要运行复杂的可信设置仪式来开始使用 STARK。可信设置是其他零知识协议中的一个潜在安全弱点，因为受损的可信设置允许攻击者生成伪造的 CI 证明。 STARK 对此免疫。与其他系统相比，当我们处理统一计算或具有规则结构的计算时，STARK 证明的生成速度非常快。幸运的是，人们编写的绝大多数程序确实具有这样的规则结构。此外，几乎 STARK 证明生成过程的每一步都是大规模并行化的。因此，我们可以通过将其分布到越来越多的 CPU 内核来频繁地加速证明生成。

上面列出的各个属性都不是 STARK 独有的。然而，没有其他证明系统能像 STARK 那样结合精益密码学、透明度和性能。 Winterfell 充分利用了这些好处，同时抽象了大部分复杂性。例如，证明生成可以分布在多个 CPU 内核上，以显着减少证明生成时间（请参阅此处的基准测试）。此外，我们计划在多台机器上启用完全分布式的证明生成，并且已经开始朝着这个方向努力。除了高性能之外，Winterfell 还具有高度的可配置性。也就是说，您可以动态调整 STARK 协议的几乎所有参数，以实现特定的性能和安全目标。通过依赖 Rust 的零成本抽象，我们能够在不牺牲性能或代码清晰度的情况下实现如此高的可配置性。最后，也许是最重要的，您无需成为密码学家即可使用 Winterfell。如前所述，Winterfell 抽象了 STARK 协议的大部分复杂性。用户唯一负责的是以 STARK 证明者/验证者可以理解的格式描述他们的计算。这种格式称为代数中间表示 (AIR)，将程序转换为 AIR 的步骤称为算术化。 Winterfell 公开了一个相对简单的接口来描述任何计算的 AIR。然而，算术化的概念并不是大多数开发人员所熟悉的，所以会有一个学习曲线。为了帮助您入门，我们整理了一个关于如何为非常简单的计算定义 AIR 的端到端教程。我们还在示例 crate 中提供了更有趣的计算示例，从简单的斐波那契数列到复杂的基于哈希的签名聚合。如果您想更深入地了解理论，我们建议您阅读 StarkWare 的两篇优秀博客文章：Arithmetization I 和 Arithmetization II。一旦您对编写 AIR 感到满意，使用 Winterfell 生成 STARK 证明就变得相对容易了。例如，用于斐波那契数列的 AIR 需要不到 100 行代码，并且可以在大约 15 分钟内完成。即使对于上面提到的基于哈希的签名聚合的相对复杂的示例，AIR 也用大约 600 行代码进行了描述（尽管它确实需要几天时间才能完成）。还有一点值得一提：我们将 Winterfell 编写为一组模块化的 crate，所有这些都将在今天发布到 Crates.io。虽然我们使用这些 crate 来构建 STARK 证明系统，但其中许多都足够通用，可以用作其他 CI 证明系统的构建块。例如，对于低度测试，我们使用在 Winter-fri crate 中实现的 FRI 协议，该协议也用作其他几个证明系统（例如 Fractal 和 Aurora）的构建块，旨在透明和后量子。因此，我们希望我们的工作将帮助这些协议的实施者更快、更有效地完成他们的工作。

ZKP 的最新进展是由区块链空间中的紧急用例驱动的。具体来说，ZKP 为区块链最紧迫的两个挑战提供了有吸引力的解决方案：隐私和可扩展性。然而，ZKP 在区块链空间之外也有许多潜在的应用。虽然在大规模计算完整性证明被认为具有实用性之前仍有一些技术挑战需要克服，但我们相信 Winterfell 代表了将学术研究中经过充分研究的主题带入实际部署的重要垫脚石。我们希望安全和隐私社区也能从易于使用的 STARK 开源实现中受益。请查看 Winterfell 存储库，并随时打开问题以供评论并留下反馈！