原著：Vitalik
译者：孟铉济（Sputnik）
译者特别感谢司淑敏对翻译工作的校对和建议。
原著特别感谢Barry Whitehat 和 Gubsheep 的反馈与审阅。
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:取值函数
ZK-SNARK proves that the output is True：ZK-SNARK证明输出值是True
这给出了 ZK-SNARK 两个属性：隐私和可扩展性。如上所述，在这篇文章中，我们的示例将聚焦于隐私。
成员证明（proof of membership）
假设你有一个以太坊钱包，并且你想证明这个钱包有一个身份证明注册，而不透露你是哪个注册的人。我们可以用数学方法描述函数如下：
-
• 秘密输入值（w）：你的地址A，以及相应的私钥k
-
• 公共输入值（x）：具有经过验证的身份证明的所有地址的集合{H_1…H_n}
-
-
• w表示为序对(A,σ)， x表示为地址集合{H_1…H_n}
-
-
-
• 当两步验证均通过时，返回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证明
对于此部分更熟悉的读者：一个用于零知识成员证明的，非常新且更有效的Merkle树的替代方案是 Caulk。将来，诸如此类的一些应用可能会迁移到Caulk类的方案。
ZK-SNARKs在货币系统的应用
Zcash 和 Tornado.cash 等项目允许您拥有具有隐私保护性质的货币。现在，您可能认为您可以采用上面的“ZK 身份证明”，但不是证明对身份证明文件的使用权，而是使用它来证明对币的使用权。但是我们有一个问题：我们必须同时解决隐私和双花问题。也就是说，应该不能够把币花费两次。
接下来是我们的解决方案。任何拥有货币的人拥有一个秘密s。他们在本地计算“叶子”L=hash(s,1)，这个值接下来会上链并且成为状态的一部分。同时，他们计算N=hash(s,2)，我们称之为无效符。该状态被存在一个Merkle树当中。
Merkle tree nodes：Merkle树节点
Space to add future leaves: 用来存放将来的叶子节点的空间
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是当前的状态树树根
-
-
这笔交易包含了无效符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制作证书。
-
-
-
-
• 检查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 设置如下：
-
-
-
-
• 帖子内容（“混合”到证明中以将其绑定到帖子，但我们不对它进行任何计算）
-
-
-
• 外部身份（带有地址A）或上一篇帖子使用的无效符N_prev
-
• 一个Merkle证明M，用来证明A或N_prev上链
-
-
-
• 检查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^64），那么你就知道该无效符是使用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需要考虑审核操作
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”，疑有误。
Reviewer丨Prof. Xu Ke, Brian Seong
Script | Vitalik
Translator 丨 Sputnik Meng
Editor | Neil Chen
原文始发于微信公众号（THU学生区块链）：使用 ZK-SNARKs 保护隐私的一些方法
