原文来自IOHK Thomas Kerber，由卡尔达诺大使陈哲Anson翻译
Zk-SNARK 已被证明是区块链和分布式账本的“瑞士军刀”，在隐私、互操作性和可扩展性方面具有应用
自引入以来，零知识证明 (ZKP) 已被用于支持从可验证的外包计算到匿名凭证的潜在应用，在众多需要在隐私和完整性之间取得平衡的设置中。 ZKP 使一方能够向另一方证明某个陈述或主张是真实的，而无需透露该陈述的内容。 ZKP 在各种链上用例中的应用有助于解决隐私、互操作性和可扩展性问题。
在这篇文章中，我们将了解不同类型的 ZKP 及其特定用例。我们还讨论了 zk-SNARKs 及其应用中的一些已知问题，并提出了一种在与区块链协议相当的条件下具有安全特性的区块链机制。本文基于 Thomas Kerber、Aggelos Kiayias 和 Markulf Kohlweiss 撰写的“挖掘隐私：如何引导 Snarky 区块链”研究论文。
不同类型的 ZKP
在区块链设置中，客户端通常会下载并验证发布到网络的每笔交易。这意味着小证明大小和快速验证时间对于零知识协议的实际部署很重要。有几种实用的方案可供选择，在性能和加密假设方面有很大的权衡空间：
• 非交互式零知识论据（NIZKs）：这是最普遍的概念。 NIZK 可能不简洁，但作为一个好处，它可能依赖于标准的加密假设并且通常满足强大的安全保证。
• 简洁的非交互式零知识论点（SNARGs）：以更强的密码假设和通常更弱的安全保证为代价实现简洁。
• 简洁的非交互式零知识知识论证（SNARKs 或有时是 zk-SNARKs）：这些 SNARGs 也是知识和零知识的证明。这个名字也很受欢迎，因为它来自刘易斯卡罗尔的无意义诗《猎蛇》。
• 简洁透明的知识论据（STARK）：这里的透明是指只需要可信散列函数的设置。这是有益的，但可能会带来性能开销。
目前，从验证者的角度来看，最有吸引力的证明系统是（预处理）简洁的非交互式知识论证，或简称 zk-SNARK，它具有较小的恒定证明大小和恒定时间验证成本，即使是任意大的关系。 Zk-SNARKs 已被证明是区块链和分布式账本的“瑞士军刀”，在隐私、互操作性和可扩展性方面具有应用。
用例
zk-SNARK 的用例非常多样化。有时使用 SNARK 来提高系统的性能和简洁性。其他用例使用 zk-SNARK 来改善隐私。有些情况是混合的，这两个方面都起作用。
在区块链环境中，考虑到性能和简洁性，zk-SNARKS 可以极大地促进以下用例：
• 轻客户端：提高参数效率和应用程序的整体结构。高效的证明系统（没有零知识要求）在引导轻客户端方面发挥着重要作用。递归证明系统也可以很好地匹配这个用例，以确保无限递归的安全性以及递归证明中外部函数（例如哈希函数）的使用。
• 智能合约：减轻因公共智能合约执行而可能导致的账本拥塞。将链上代码编译为 SNARK，具有恒定或对数验证时间，可以允许更复杂的验证器。
• 有用工作证明（PoUW）：SNARK 可以成为验证矿工执行的“有用计算”的关键，否则验证链上的成本会很高。
从隐私的角度来看，许多应用程序使用零知识证明来部署安全支付解决方案、交换选项、管理身份、投票、拍卖、可验证的统计数据（一种区块链预言机）或激励性匿名通信。用例可以包括：
• 私人智能合约：SNARK 是当前私人智能合约设计不可或缺的一部分。有两件事是最重要的：通用性，支持用户部署的智能合约，以及易于编译。可以消除智能合约的表达性以减少问题空间，例如，通过禁止无界循环和递归，因此不需要递归 SNARK 组合。从根本上说，高级合约语言的某些子集可以编译成 SNARK 电路。
• 私人支付：资产可以被视为一种特殊形式的身份声明，包括稀缺性建模。私人支付提案还可以支持多资产和不可替代的代币，并将这些代币连接到智能合约。
• 身份管理：在可验证凭证的上下文中，发行者可以通过生成加密对象（凭证）来断言有关主体的声明。主题稍后将他们的凭据呈现给充当验证者的其他用户。然后，验证者能够验证颁发者是否断言了关于呈现凭证的主题的声明。
• 投票和国库：ZK 证明可用于国库投票。例如，加密货币协议的国库系统提供了一种保护隐私的投票方案，其中选民的选票被加密，然后使用同态计算进行统计。国库中的 ZK 证明是基于 DLP 的非交互式 Sigma 协议，用于在协议的各个阶段证明加密消息的正确性（例如，加密选民的选票包含正确组成的选票）。
混合用例包括：
• 区块链预言机：SNARK 可以在聚合来自多个来源的数据时降低验证成本，并且它们可以通过仅包括聚合值和证明而不是所有数据点来减少发布的链上数据的大小。为了实现这两个属性，各方应该能够简洁地证明对多个数据点的签名知识以及各自的平均值/中值/方差。
• 侧链：链挂钩配置中的一条链可以充当另一条链的轻客户端，验证另一条链上的跨链交易，而无需验证整个链。不同之处在于这种挂钩通常是长期维护的，因此可以定期提供证明并以“可更新”的方式提供。有关更多信息，请参阅权益证明侧链。
已知的问题
非交互式零知识需要一些共享随机性或公共参考字符串。对于许多简洁的系统，一个更强的属性是必要的：
不仅需要共享随机值，而且它必须遵守特定的结构。结构化参考字符串 (SRS) 通常由相关的组元素组成，即：gxi 代表所有 i∈𝕫n。
从公共随机性中抽取这样一个参考字符串的明显方法揭示了所使用的指数——而对这些值的了解破坏了证明系统本身的健全性。更糟糕的是，这些系统的安全性通常依赖于（除其他外）指数假设的知识，这表明要创建以这种方式相关的组元素需要知道基础指数，因此任何 SRS 采样器都必须“知道”使用的指数并被信任擦除它们，实际上成为底层系统的单点故障。
安全多方计算 (MPC) 可以并且已经用于减少对此类设置过程的信任。然而，通过 MPC 协议选择安全计算的参与者和验证 SRS 的生成保留了中心化的元素。在需要 SNARK 的去中心化系统的设置中，使用 MPC 仍然是一个有争议的元素。
通过安全 SRS 生成解决隐私问题
通过要求块创建者在初始设置期间对不断发展的 uSRS 执行更新，可以使用分布式账本安全地初始化可更新的结构化参考字符串 (uSRS)。等待最终uSRS达成协议后，就可以放心使用了。
这一点的证明依赖于 Nakamoto 式分类账的基本操作方式：如果不同的用户能够满足某些条件，他们可以扩展一个区块链，这个条件与一种确保攻击者数量有限的硬度相关联。他们可以执行的扩展。给定这样的结构，我们将 uSRS 更新与时间 𝛿1 之前的每个块相关联。选择这个时间，以便账本的安全属性确保此时在每个竞争链中至少有一个区块是诚实的。
这可以从具有额外领导状态的分类帐功能构建，该领导状态源自矿工嵌入其块中以编码 uSRS 更新的信息。这足够通用以允许其他用途。基本思想是表明，在其领导状态下执行 uSRS 更新的账本等同于不执行更新的账本，但伴随着安全的 uSRS。在时间 𝛿1 之后，用户再等待一段时间 𝛿2，直到公共前缀确保所有各方都同意参考字符串。
提议分类帐抽象概念
我们构建可更新的结构化参考字符串功能依赖于 Garay 等人在比特币主干分析中定义的公共前缀、链质量和链增长的属性，用于 Nakamoto 风格的共识算法：
• 通用前缀。给定当前两方的链 𝛱1 和 𝛱2，并移除从第一个块开始，它是第二个块的前缀：𝛱1⌊k ≺𝛱2。
• 现有的链条质量。对于任何一方的当前链𝛱，该链中任何连续的 l 个区块都将包含至少一个由诚实方创建的区块。
• 连锁增长。如果一方的链长度为 c，那么在 s 个时隙之后，它的长度至少为 c+𝛾。
去中心化 uSRS 建设
我们提议的结构（在 Mining for Privacy 一文中详细介绍）很简单：每条链都与特定的 uSRS 相关联，当矿工扩展一条链时，他们额外执行 uSRS 更新。在链的起源，可以使用已知的随机性（甚至没有随机性）。这种设计背后的原理很简单：uSRS 的可更新性保证了如果诚实地执行一次更新（都使用真正的随机性，并在执行更新后擦除这种随机性），则可以安全地使用生成的 uSRS。我们依靠存在链质量属性来保证这一点——一旦生成了 l 个块，其中至少一个必须由诚实的矿工创建，因此在 l 个块之后，链的 uSRS 是安全的。
然而，仅仅知道特定链的引用字符串是安全的还不够——对于大多数实际应用，我们希望所有用户都同意引用字符串。这是由公共前缀属性提供的，它保证对于任何 l+k 个块长的链，所有其他用户将具有与该链生成的相同的引用字符串——前提是用户在 l 个块后停止更新！
最后，链增长保证了我们感兴趣的事件——当每个人都同意参考字符串时——最终会发生。它保证用户最终将拥有一条长度为 l+k 的链。具体来说，随着每 s 个时间单位生成块，该事件最迟将在时间 ⌈(l+k)/s⌉ 发生。
这在抽象上一切都很好，但留下了实用性问题：这种抽象分析假设可以以很少甚至没有成本创建更新，并且它们不会影响标准挖掘程序。然而，这对于工作量证明挖掘来说并不完全正确：
- 更新成本相对较高，计算时间为 5-10 分钟，具体取决于目标 uSRS 的大小。
- 可以欺骗更新，更快地执行更新，但不增加引用字符串的安全性。
综合起来，这些因素构成了挑战，特别是在工作量证明设置中，需要在矿工开始挖掘区块之前执行更新。这会延迟非作弊的矿工，而他们的作弊同行已经在挖矿了！因此，挖矿难度（对应区块之间的预期时间）不应该太低，因为越低，作弊矿工的收益越大。另一方面，高难度自然导致达成共识的时间更长。这种权衡如图 1 所示。
如果对难度进行了适当的校准，模拟分析表明这种影响不会损害整体安全性。根据我们愿意容忍的失败概率 (є) 以及我们想要防范的攻击者挖矿能力 (а) 的比例，uSRS 可以在几个小时内或几个小时内通过该程序安全生成月在更悲观的情况下，如图 1 所示。
图 1. 保证至少一次诚实更新所需的时间，作为目标块时间的函数
资料来源：“挖掘隐私：如何引导一个 Snarky 区块链”研究论文
在考虑理性行为时也会出现类似的问题——只寻求利润的矿工也会试图欺骗他们的更新，不是出于恶意，而仅仅是因为如果他们这样做，他们可以更快地产生区块。这可以通过额外奖励良好行为来规避——可以在事后询问矿工的样本，以提供他们更新的随机性，并证明它是以适当的方式进行采样的（例如，使用哈希函数）。如果他们能够这样做，他们可以获得额外的奖励，从而抵消他们因不作弊而可能造成的任何损失。
总之，zk-SNARK 的适用性极大地有利于解决隐私、互操作性和可扩展性问题的不同链上用例。虽然许多 zk-SNARK 所需的可信设置似乎与分布式账本的去中心化性质不一致，但对于具有可更新参考字符串的 SNARK，它可以以完全去中心化的方式执行。虽然原则上也可以使用透明的 SNARK，如 Halo，但上述技术允许依赖可更新的参考字符串的 Plonk 等 SNARK（根据情况可能更有效），也可以安全地用于链应用程序——不再是 SNARK 设置太不透明而无法信任的情况，如果它们曾经是的话。
原文链接：Zk-SNARKs: updatable setups on the blockchain - IOHK Blog