原著：Vitalik

===========
ZK-SNARKs 是一种强大的密码学工具，并且是人们在区块链空间内外构建的应用中越来越重要的一部分。但是无论是就它们的工作方式而言，还是就如何使用它们而言，都很复杂。我之前解释 ZK-SNARKs 的文章关注于第一个问题，也就是说试图以一种可以理解并且不破坏理论上的完整性的方式来解释 ZK-SNARKs 背后的数学。这篇文章将关注第二个问题：ZK-SNARKs 如何适用于现有的应用，有哪些它们可以做什么、不能做什么的例子，以及确定一些特定的应用是否可以应用 ZK-SNARK 的一般准则是什么？具体来讲，这篇文章聚焦于 ZK-SNARK 在保护隐私方面的应用。

ZK-SNARK 有什么作用？

假设你有一个公共的输入 x，一个秘密的输入 w，以及一个（公共的）函数 f(x,w)→{True,False}用来对输入执行某种验证。使用 ZK-SNARK，你可以证明对于给定的 f 和 x，你知道一个 w，使得 f(x,w)=True，并且不需要公开 w。此外，验证者可以以比自己直接计算 f(x,w) 这个函数快得多的速度验证这个证明，尽管他们不知道 w【1】。

The function being evaluated:取值函数 Public input:公共输入 Private input 秘密输入 ZK-SNARK proves that the output is True：ZK-SNARK 证明输出值是 True

这给出了 ZK-SNARK 两个属性：隐私和可扩展性。如上所述，在这篇文章中，我们的示例将聚焦于隐私。

成员证明（proof of membership）

假设你有一个以太坊钱包，并且你想证明这个钱包有一个身份证明注册，而不透露你是哪个注册的人。我们可以用数学方法描述函数如下：

• 秘密输入值（w）：你的地址 A，以及相应的私钥 k

• 公共输入值（x）：具有经过验证的身份证明的所有地址的集合{H_1…H_n}

• 验证函数 f(x,w)：

• w 表示为序对 (A,σ)， x 表示为地址集合{H_1…H_n}

• 验证 A 是集合{H_1…H_n}当中的一个地址

• 验证 privtoaddr(k)=A

• 当两步验证均通过时，返回 True，否则返回 False

证明者生成他们的地址 A，以及相应的私钥 k，并提供 w=(A,k) 作为 f 的秘密输入。他们从链上获取公共输入，以及当前的经过验证的身份证明的所有地址的集合{H_1…H_n}。他们运行 ZK-SNARK 算法来生成证明（假设输入都是正确的）。证明者将证明发送给验证者，并且提供他们获取经过验证的地址集合的块高度。验证者同样从证明者提供的块高度对应的区块读取集合{H_1…H_n}并验证证明。如果检验通过，该验证者相信证明者拥有一些经过验证的身份证明地址。在我们继续讨论更复杂的示例之前，我强烈建议您仔细阅读上面的示例，直到您了解所涉及的每一处细节。

提高成员证明的效率

上述证明系统的一个缺陷是验证者需要知道整个集合{H_1…H_n}，并且他们需要以 O(n) 时间将集合“输入”到 ZK-SNARK 机制中。我们可以通过将包含所有集合元素的链上 Merkle 根（这可能只是状态根）作为公共输入来解决这个问题。我们添加另一个秘密输入，一个 Merkle 证明 M，证明证明者的帐户 A 在 Merkle 树的对应位置。

图中蓝色虚线表示链上，紫色虚线表示用户本地存储，黄色方框表示 A 的 Merkle 证明 On-chain root：链上状态根 Private key：用户私钥

对于此部分更熟悉的读者：一个用于零知识成员证明的，非常新且更有效的 Merkle 树的替代方案是 Caulk。将来，诸如此类的一些应用可能会迁移到 Caulk 类的方案。

ZK-SNARKs 在货币系统的应用

Zcash 和 Tornado.cash 等项目允许您拥有具有隐私保护性质的货币。现在，您可能认为您可以采用上面的“ZK 身份证明”，但不是证明对身份证明文件的使用权，而是使用它来证明对币的使用权。但是我们有一个问题：我们必须同时解决隐私和双花问题。也就是说，应该不能够把币花费两次。接下来是我们的解决方案。任何拥有货币的人拥有一个秘密 s。他们在本地计算“叶子”L=hash(s,1)，这个值接下来会上链并且成为状态的一部分。同时，他们计算 N=hash(s,2)，我们称之为无效符。该状态被存在一个 Merkle 树当中。

图中蓝色虚线表示链上，紫色虚线表示用户本地存储 On-chain root：链上状态根 Merkle tree nodes：Merkle 树节点 Existing leaves：存在的叶子节点 Space to add future leaves: 用来存放将来的叶子节点的空间 Secret：秘密值 Nullifier（secret until coin is spent）：无效符（直到币被花费前一直保密）

为了花费一个币，发送方必须生成一个满足下述条件的 ZK-SNARK：

• 公共输入包含一个无效符 N，当前的或者最近的 Merkle 树根 R，以及一个新的叶子 L^’（目的是接收方有一个秘密值 s^’，并且将其传递给发送方 L^’=hash(s^’,1)）

• 秘密输入包含一个秘密值 s，一个叶子 L 和一个 Merkle 路径 M

• 验证函数执行以下检查：

• M 是一个有效的 Merkle 路径，证明了 L 是一个以 R 为根的树的叶子，其中 R 是当前的状态树树根

• hash(s,1)=L

• hash(s,2)=N

这笔交易包含了无效符 N 以及新的叶子 L^’。我们事实上没有证明关于 L^’的任何信息，但是我们将其“混合于”这个证明当中，从而保护 L^’免于在交易进行中被第三方修改。为了验证交易，链会检查这个 ZK-SNARK 证明，并且检查 N 未在之前的交易中使用过。如果交易成功，则将其添加到已花费的无效符集中，使其无法再次花费。L^’被添加到 Merkle 树中。这里发生了什么？我们使用 zk-SNARK 来关联两个值，L（在创建币时上链）和 N（在花费币时上链），而没有透露哪个 L 对应哪个 N。只有知道生成两者的秘密值 s，才能发现 L 和 N 之间的对应关系。创建的每个币只能使用一次（因为对于每个 L 只有一个有效的 N 与之对应），但在特定时间哪个币被花费了是保密的。这也是一个需要理解的重要原语。我们在下面描述的许多机制将基于一个非常相似的“私有花费只能是一次性”小工具，尽管目的不同。

具有任意余额的币

上述流程可以很容易地扩展到具有任意余额的币。我们保留“币”的概念，但是此时每个币都有一个（秘密）余额。一种简单的方法是不仅将叶子 L 存储，同时也将币的加密后的余额值也存储在链上。每笔交易将消耗两个币并创建两个新币，并且它将向状态添加两个（叶子，加密余额）序对。ZK-SNARK 还会检查输入余额的总和是否等于输出余额的总和，并且两个输出余额都是非负的。

ZK 反拒绝服务攻击

一个有趣的反拒绝服务攻击的小工具。假设你有一些创建起来并不平凡的链上身份：它可能是一个身份证明配置文件，它可能是一个拥有 32 ETH 的验证者，或者它可能只是一个拥有非零 ETH 余额的账户 . 我们可以创建一个更具 DoS 抵抗力的点对点网络，方法是只接受带有一个证明，证明消息发送者拥有上述配置文件的消息。每个配置文件每小时最多可以发送 1000 条消息，如果发件人作弊，发件人的配置文件将从列表中删除。但是我们如何在此过程中保护隐私呢？首先，设置。设 k 为用户的私钥；A=privtoaddr(k) 是对应的地址。有效地址列表是公开的（例如，它是链上的注册表）。到目前为止，这类似于身份证明的例子：你必须证明你拥有一个地址的私钥，而不能透露是哪一个。但是在这里，我们不只是想要证明您在列表中。我们想要一个协议，可以让您证明您在列表中，但不需要您生成太多证明。所以我们需要做更多的工作。我们将时间划分为一些阶段；每个阶段持续 3.6 秒（因此，每小时有 1000 个阶段）。我们的目标是使每个用户在每个阶段只能发送一条消息；如果用户在同一阶段发送两条消息，他们将被抓获。为了允许用户偶尔发送突发消息，他们可以使用最近过去的阶段，因此如果某些用户有 500 个未使用的阶段，他们可以使用这些阶段一次性发送 500 条消息。

协议

我们将从一个简单的版本开始：我们使用无效符。用户生成一个无效符 N=hash(k,e)，其中 k 是他们的密钥，e 是阶段序号，并将其与消息 m 一起发布。ZK-SNARK 再次混入 hash(m) 而不验证关于 m 的任何内容，因此该证明被绑定到单个消息。如果用户使用相同的无效符将两个证明绑定到两条不同的消息，他们将会被抓获。现在，我们将继续讨论更复杂的版本。下一个协议不仅可以轻松证明某人是否两次使用了相同的阶段，而且实际上在这种情况下会揭示他们的私钥。我们的核心技术将依赖于“两点确定一条线”的技巧：如果你在一条线上揭示一个点，你揭示的很少，但是如果你在一条线上揭示两个点，你就揭示了整条线。对于每个阶段 e，我们选择这条线 L_e (x)=hash(k,e)*x+k。直线的斜率为 hash(k,e) , y 轴截距为 k ; 两者都不公开。发件人需要提供 y=L_e (hash(m))=hash(k,e)*hash(m)+k 以及计算正确的 ZK-SNARK 证明，来为消息 m 制作证书。

Certificate: 证书 Epoch1 line：阶段 1 的直线 Epoch2 line：阶段 2 的直线 Private key：私钥

我们总结一下，此处 ZK-SNARK 的设置如下：

• 公共输入：

• {A_1…A_n}，有效的账户的列表

• m，证书正在验证的消息

• e，证书所用的阶段序号

• y，线性函数取值

• 秘密输入：

• k，私钥

• 验证函数：

• 检查 privtoaddr(k) 属于集合{A_1…A_n}

• 检查 y=hash(k,e)*hash(m)+k

但是如果有人使用一个阶段两次呢？这意味着他们发布了两个值 m_1 和 m_2 以及相应的证书值 y_1=hash(k,e)*hash(m_1)+k 与 y_2=hash(k,e)*hash(m_2)+k。我们可以使用这两个点来恢复该直线，从而恢复 y 轴截距（也就是私钥）：

因此，如果有人重用一个阶段，他们就会泄露他们的私钥，变得对所有人可见。根据具体情况，这可能意味着资金被盗、验证者被削减，或者只是私钥被广播并被包含在智能合约中，此时相应的地址将从有效账户集合中删除。我们在这里完成了什么？一个可行的链下匿名反拒绝服务攻击系统，可用于区块链点对点网络、聊天应用等系统，而无需任何工作量证明。RLN（速率限制无效符）项目目前实质上正在构建这个想法，尽管有一些小的修改（即，他们同时使用无效符和两点连线技术，使用无效符更容易检测对于同一个阶段的重用）。

ZK 负面声誉

假设我们想建立 0chan，一个像 4chan 一样提供完全匿名性的互联网论坛（所以你甚至没有永久的用户名），但有一个声誉系统来鼓励更多高质量的内容。这可能是一个这样的系统，其中一些审核 DAO 可以将帖子标记为违反系统规则，并建立“三次违规则出局”机制，它可能是用户能够对帖子投赞成票和反对票，有很多配置。声誉系统可以支持正面或负面的声誉；然而，支持负面声誉需要额外的基础设施来要求用户在他们的证明中考虑所有声誉消息，甚至是负面消息。我们将重点关注的是这个更难的用例，它类似于 Unirep Social 正在实施的用例。

链上发帖：基础

任何人都可以通过在链上发布包含帖子的消息和一个 ZK-SNARK 证明，以证明 (i) 你拥有一些稀缺的外部身份，例如，身份证明，使你有权创建一个帐户，或 (ii) 你之前发表了一些特定的帖子。具体来说，ZK-SNARK 设置如下：

• 公共输入：

• 无效符 N

• 一个最近的区块链状态根 R

• 帖子内容（“混合”到证明中以将其绑定到帖子，但我们不对它进行任何计算）

• 秘密输入：

• 你的私钥 k

• 外部身份（带有地址 A）或上一篇帖子使用的无效符 N_prev

• 一个 Merkle 证明 M，用来证明 A 或 N_prev 上链

• 你用这个账户在之前发布过的帖子数量 i

• 验证函数：

• 检查 M 是一个有效的 Merkle 路径，证明了（A 或 N_prev，以提供的值为准）是一个以 R 为根的树的叶子

• 检查 N=enc(i,k)，其中 enc 是一个加密函数（例如 AES）

• 如果 i=0，检查 A=privtoaddr(k)，否则检查 N_prev=enc(i-1,k)

除了验证证明之外，该链还检查 (i) R 实际上是最近的状态根，以及 (ii) 无效符 N 尚未被使用过。到目前为止，这就像前面介绍的隐私保护币，但我们添加了一个“铸造”新帐户的程序，并且我们删除了将您的帐户“发送”到不同密钥的能力 — 相反，所有无效符都是使用你原始的密钥生成的。我们在这里使用 enc 而不是 hash 来使得无效符可逆：如果你有 k，你可以解密你在链上看到的任何指定的无效符，并且如果结果是有效索引而不是随机垃圾值（例如，我们可以检查 dec(N)<2⁶⁴），那么你就知道该无效符是使用 k 生成的。

增加声誉

该方案中的信誉是链上的，并且是清晰的：一些智能合约有一个 addReputation 方法，该方法的输入是 (i) 与帖子一起发布的无效符，以及 (ii) 要添加和减去的声誉值的数量。我们扩展了每个帖子存储的链上数据：我们不单存储无效符 N，事实上，我们存储{N,h ̅,u ̅}，其中：

• • h ̅=hash(h,r) 其中 h 是证明中包括的状态根所在的块高度
• • u ̅=hash(u,r) 其中 u 是该账户的声誉值的分数（对于新账户该值为 0）

r 在这里只是一个随机值，用以防止 h 和 u 和被暴力搜索发现（在密码学术语中，添加 r 使得该哈希成为隐藏承诺）。假设帖子使用根 R 并存储{N,h ̅,u ̅}。在证明中，它链接到以前的一个帖子，相应的存储着数据{N_prev,h ̅_prev,u ̅_prev}。该帖子的证明还需要遍历所有已在 h_prev 和 h 之间发布的信誉条目。对于每个无效符 N ，验证函数将使用用户的私钥 k 解密 N，如果解密输出有效索引，它将进行信誉更新。如果所有信誉更新的总和是δ，证明将最终检查 u=u_prev+δ。

ZK-SNARK proves inclusion of A, an account with a valid proof-of-humanity profile: ZK-SNARK 证明 A 的被包含，其中 A 是一个拥有有效身份证明的账户 ZK-SNARK points to the previous post: ZK-SNARK 指向之前的文章 ZK-SNARK required to take into account moderation action：ZK-SNARK 需要考虑审核操作 Moderation action：审核操作 Post N1 violated the forum rules. One strike: 文章 N1 违反了论坛规则，一次违规。Three strikes and the poster can‘t post anymore：三次违规，发帖者不能再次发帖。

如果我们想要“三次违规则出局”，ZK-SNARK 还需要检查 u>-3 。如果我们想要一个规则，如果发布者有≥100 点信誉，则帖子可以获得特殊的“高声誉发布者”标志，我们可以通过添加“is u≥100？”作为一个公共输入来容纳它。很多种这样的规则都可以被容纳。为了提高方案的可扩展性，我们可以将其分为两种消息：帖子和信誉更新确认 (RCA)。帖子将是链下的，尽管它需要指向过去一周当中生成的 RCA。RCA 将在链上，并且 RCA 将遍历自该发布者之前的 RCA 以来的所有声誉更新。这样，链上负载减少到每周每个帖子一笔交易加上每条声誉消息一笔交易（如果声誉更新很少，例如，它们仅用于审核操作或可能是那种“每日优帖”类似的奖项）。

保证中心化主体是可追责的

有时，您需要构建一个具有某种中心化的“操作者”的方案。这可能有很多原因：有时是为了可扩展性，有时是为了隐私性 — — 特别是操作者持有的数据的隐私。例如，MACI 抗强制投票系统需要选民在链上提交他们的投票，该投票由中心化的操作者控制的密钥加密。操作者将解密链上的所有选票，将它们计数，并显示最终结果，并附上证明他们做的一切正确的 ZK-SNARK。这种额外的复杂性对于确保强大的隐私属性（称为强抗强制性）是必要的：即使用户愿意，用户也无法向其他人证明他们是如何投票的。多亏了区块链和 ZK-SNARK，对操作者的信任度可以保持在非常低的水平。恶意的操作者仍然可以打破抗强制性，但由于投票是在区块链上公布的，运营商不能通过审查投票来作弊，并且由于运营商必须提供 ZK-SNARK，所以他们不能通过错误计算结果来作弊。

将 ZK-SNARK 与多方安全计算（MPC）结合

ZK-SNARKs 的更高级使用涉及对计算进行证明，其中输入值在两方或多方之间产生，并且我们不希望任何一方获知其他方的输入值。你可以在两方情况下通过混淆电路满足隐私要求，在 N 方情况下使用更复杂的多方安全计算协议来满足隐私要求。ZK-SNARKs 可以与这些协议结合起来进行可验证的多方安全计算。这可以构建更高级的信誉系统，其中多个参与者可以对其秘密输入执行联合计算，它可以使得具有隐私保护功能但经过身份验证的数据市场，以及许多其他应用都成为可能。但是请注意，高效地执行此操作的数学运算仍相对而言处于起步阶段。

我们不能将什么变为隐私的？

ZK-SNARK 通常对于创建用户拥有私有状态的系统非常有效。但是 ZK-SNARKs 不能保持没有任何人知道的私有状态。 要对一条信息进行证明，证明者必须以明文形式知道该信息。Uniswap 是一个不能（轻易）私有化的简单例子。在 Uniswap 中，有一个逻辑上中心化的“事物”，即做市商账户，它不属于任何人，Uniswap 上的每一笔交易都与做市商账户进行交易。您无法隐藏做市商账户的状态，因为这样就必须有人以明文形式保存状态以进行证明，而且每笔交易都需要他们的主动参与。你可以使用 ZK-SNARK 混淆电路制作一个中心化操作但安全且隐私的 Uniswap，但目前尚不清楚这样做的好处是否值得付出相应的代价。甚至可能没有任何真正的好处：合约需要能够告诉用户资产的价格是多少，而价格的逐块变化可以说明交易活动是什么。区块链可以使状态信息全局化，ZK-SNARK 可以使状态信息隐私化，但是我们真的没有任何好的方法可以同时使状态信息全局化和隐私化。编者：您可以使用多方安全计算来实现共享隐私状态。但这需要一个诚实多数门限假设，并且在实践中可能不稳定，因为（与例如 51% 攻击不同）恶意大多数可以串通以破坏隐私而不会被发现。

将这些原语放在一起

在上面的章节中，我们看到了一些本身就是强大且有用的工具的示例，但它们也被用来作为构建其它应用的一部分。例如，无效符对货币很重要，但事实证明它们在各种用例中一次又一次地出现。负面信誉部分中使用的“强制上链”技术应用非常广泛。对于许多应用程序来说，它是有效的，其中用户具有复杂的“配置文件”，这些配置文件会随着时间的推移以复杂的方式发生变化，并且你希望要求用户在保护隐私的同时遵守系统规则，这样就没有人看到哪个用户正在执行哪个操作。甚至可能要求用户拥有代表其内部“状态”的整个私有 Merkle 树。这篇文章中提出的“承诺池”小工具可以使用 ZK-SNARKs 构建。如果某些应用程序不能完全在链上并且必须有一个中心化的操作者，那么完全相同的技术也可以用来保持操作者的诚实。ZK-SNARK 是一个非常强大的工具，可以将追责性和隐私性的好处结合在一起。它们确实有其局限性，尽管在某些情况下，巧妙的应用设计可以解决这些限制。我希望在未来的几年当中，看到更多使用 ZK-SNARK 的应用，以及最终将 ZK-SNARK 与其他形式的密码学相结合的应用。

— — — — 【1】译者注：原文为“even if they know w”，疑有误。