Vitalik Buterin：如何使用 zk-SNARKs 技术保护隐私？

zk-SN ARKs 在隐私保护中能做什么，不能做什么？

原文标题：《 聚焦：ZK-SNARK 技术 》

撰文：Vitalik Buterin，以太坊联合创始人

编译：去中心化金融社区

ZK-SNARK 是一种强大的加密工具，它在区块链和区块链以外构建的应用程序中变成日益重要的一部分。但它们是复杂的，无论是从它们的工作原理，还是从我们如何使用它的角度来看，都是复杂的。

这篇文章将关注 ZK-SNARK 如何适应现有的应用程序，有哪些例子说明它们能做什么，不能做什么，以及有哪些通用的指导方针来判断 ZK-SNARK 是否适合某些特定的应用程序。

这篇文章特别关注 ZK-SNARK 在保护隐私中的应用。

ZK-SNARK 是做什么的？

假设有一个公共输入 x，一个私有输入 w，和一个 (公共) 函数 f (x,w)→{True,False}，其会对输入执行某种验证。使用 ZK-SNARK，就可以证明你知道一个 w，对于某些给定的 f 和 x，f (x,w)=True，在此过程中不用透露 w 到底是什么。另外，验证者可以更快地验证证明，这比他们自己计算 f (x,w) 要快得多，就算他们知道 w。

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

成员资格的证明

假设你有一个以太坊钱包，你想要证明这个钱包是人性证明（proof-of-humanity）注册，同时不透露注册的到底是哪个人。我们可以用数学方法描述这个函数：

• 
  
• 私有输入 (w)：你的地址 A，你的地址私钥 k
• 公共输入 (x)：所有经过验证的人性证明配置文件 {H1…Hn} 的地址集合
• 验证函数 f (x,w)
• 将 w 解释为一对 (A，σ)， x 为有效配置文件列表 {H1…Hn}
• 验证 A 是 {H1…Hn} 中的一个地址
• 验证 privtoaddr (k) = A
• 如果两个验证都通过，则返回 True，如果任何一个验证失败则返回 False

证明者生成他们的地址 A 和相关的密钥 k，并提供 w=(A,k) 作为 f 的私有输入。他们从链中获取公共输入，就是当前已验证的人性证明配置文件集 {H1…Hn}。他们运行 ZK-SNARK 证明算法，此算法 (假设输入是正确的) 生成证明。证明者将证明发送给验证者，并且提供他们获得验证配置文件列表的区块高度。

验证者还会读取链，获取证明者指定高度的列表 {H1…Hn}，并检查证明。如果检查通过，验证者就相信证明者有一些已验证的人性证明文件。

在我们继续讨论更复杂的例子之前，我强烈建议先看看上面的示例，直到完全理解其中的所有内容。

使成员证明更有效

上述证明系统的一个缺点是验证者需要知道整个配置文件集 {H1…Hn}，他们需要花费 O (n) 时间将这组配置文件「输入」到 ZK-SNARK 机制中。

我们可以通过将包含所有配置文件的链上 Merkle 根作为公共输入 (这可能只是状态根) 来解决这个问题。我们添加另一个私有输入，一个 Merkle 证明 M，证明证明者的帐户 A 在树的相关部分。

用于 ZK 证明成员资格的 Merkle 证明的一个非常新且更有效的替代方案是 Caulk。将来，其中一些用例可能会迁移到类似于 Caulk 的方案中。

ZK-SNARK 和币

Zcash 和 Tornado.cash 等项目允许我们拥有保护隐私的货币。现在，你可能认为你可以使用上面的「ZK 人性证明」，但它不是证明对人性证明配置文件的访问，而是用它来证明对币的访问。现在我们有一个问题：我们必须同时解决隐私和双花问题。也就是说，我们不应该花两次币。

我们是这样解决的。任何拥有币的人都有一个私有秘密「s」。他们在本地计算「leaf」 L=hash (s,1)，它被发布在链上，并成为状态的一部分，N=hash (s,2)，我们称之为 nullifier。状态存储在默克尔树中。

要花一枚币，发送者必须做一个 ZK-SNARK，其中：

• 公共输入包含一个 nullifier N，当前或最近的 Merkle 根 R，和一个新的叶子 L '(目的是接收方有一个秘密 s '，并传递给发送方 L ' =hash (s '，1))
• 私有输入包含一个秘密 s，一个叶子 L 和一个默克尔分支 M
• 验证功能会检查：
• M 是一个有效的 Merkle 分支，证明 L 是根为 R 的树的叶子，其中 R 是当前状态的 Merkle 根
• hash (s,1)=L
• hash (s,2)=N

交易包含了 nullifier N 和新的叶子 L’。我们实际上并不证明关于 L ' 的任何东西，但我们将其「混合」到证明中，以防止交易在进行时被第三方修改。

为了验证交易，链检查 ZK-SNARK，另外检查 N 是否在之前的支出交易中被使用。如果交易成功，则将 N 添加到已花费的 nullifier 集，这样它就不能再被用。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 条消息。

协议

我们将从一个简单的版本开始：使用 nullifier。用户生成一个具有 N=hash (k,e) 的 nullifier，其中 k 是他们的密钥，e 是时期号，并将其与消息 m 一起发布。ZK-SNARK 再次混合 hash (m)，在此过程中没有验证关于 m 的任何东西，因此证明绑定到单个消息。如果用户使用相同的 nullifier 将两个证明绑定到两个不同的消息，他们可能会被捕获。

现在，我们将转向更复杂的版本。在这种情况下，下一个协议将暴露他们的私钥，而不是简单地证明某人是否使用了相同的时期两次。我们的核心技术将依赖于「两点构成一条线」的技巧：如果你在一条线上显示一个点，你就显示的很少，但是如果你在一条线上显示两个点，你就显示了整条线。

对于每个时期 e，我们取直线 Le (x)=hash (k,e)∗x+k 。直线的斜率为 hash (k,e)，y 截距为 k；两者都不为公众所知。要为消息 m 制作一个证书，发送者提供 y=Le (hash (m))= hash (k,e)∗hash (m)+k，以及一个 ZK-SNARK 证明 y 的计算是正确的。

综上所述，ZK-SNARK 如下:

公共输入:

• {A1…An}，有效帐户列表
• M，表示证书正在验证的消息
• E，用于证书的时期号
• Y，是线函数的求值

私有输入:

• K，你的私钥

验证功能:

• 检查 privtoaddr (k) 是否在 {A1…An} 中
• 检查 y=hash (k,e)∗hash (m)+k

但是如果有人将一个时期使用两次呢？这意味着他们公布了两个值 m1 和 m2 以及相应的证书值 y1=hash (k,e)∗hash (m1)+k 和 y2=hash (k,e)∗hash (m2)+k。我们可以使用这两个点来恢复直线，因此 y 轴截距 (这是私钥)：

因此，如果有人重用一个时期，他们就会泄露他们的私钥，让所有人看到。根据不同的情况，这可能意味着资金被盗，或者只是将私钥广播并包含到了智能合约中，此时相应的地址将从集合中删除。

一个可行的链下匿名反拒绝服务系统，适用于区块链点对点网络、聊天应用程序等系统，不需要任何工作证明。RLN 项目目前基本上就是在构建这个想法，尽管进行了少量修改 (也就是说，他们同时使用了 nullifier 和两点在线技术，使用 nullifier 更容易捕获双重使用一个时期的问题）。

ZK 的负面声誉

假设我们想要建立 0chan，一个像 4chan 一样提供完全匿名的网络论坛 (你甚至没有永久的名字)，但是有一个声誉系统来鼓励更多高质量的内容。这可能是一个系统，一些审核 DAO 可以标记违反系统规则的帖子，并建立一个三振出局的机制。

声誉系统可以支持正面或负面声誉；然而，支持负面声誉需要额外的基础设施，要求用户在证明中考虑所有的声誉信息，就算它是负面的。我们将重点关注这个更难的用例，它类似于 Unirep Social 正在实现的用例。

链接帖子：基础知识

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

• 公共投入
• nullifier N
• 最近的区块链状态根 R
• 帖子内容 (「混合」到证明，将其绑定到帖子中，但我们不做任何计算)

私有输入:

• 你的私钥 k
• 一个外部身份 (地址 A)，或者前一篇文章使用的 nullifier Nprev
• 一个 Merkle 证明 M 证明链上包含 A 或 Nprev
• 你之前使用此帐户发布的第 i 个帖子

验证功能:

• 检查 M 是一个有效的 Merkle 分支，证明（A 或 Nprev，以提供者为准）是根为 R 的树的叶子
• 检查 N=enc (i,k)，其中 enc 是一个加密函数 (例如.AES)
• 如果 i=0，检查 A=privtoaddr (k)，否则检查 Nprev=enc (i−1,k)

除了验证证明之外，该链还检查两个方面 (i) R 实际上是一个最近的状态根，(ii) nullifier N 还没有被使用。到目前为止，这就像前面介绍的保护隐私的币一样，但我们添加了一个「铸造」新帐户的过程，并且我们删除了将你的帐户「发送」到不同密钥的能力 —— 相反，所有 nullifier 都是使用原来的密钥来生成。

我们在这里使用 enc 来使 nullifier 可逆，而不是 hash：如果你有 k，你可以解密链上任何特定的 nullifier，如果结果是一个有效的索引而不是随机的垃圾（例如，我们可以只检查 dec (N)<264），你就会知道 nullifier 是使用 k 生成的。

添加声誉

在这个方案中，声誉是链上的，并且是明确的：一些智能合约有一个方法 addReputation，它以 (i) 随帖子发布的 nullifier 和 (ii) 要加减的声誉单位数量作为输入。

我们扩展了每个帖子存储的链上数据：我们存储 {N,h¯,u¯}，而不是仅存储 nullifier N，其中：

• h¯=hash (h,r) 其中 h 是证明中引用的状态根的区块高度
• u¯=hash (u,r) 其中 u 是帐户的声誉分数（新帐户为 0）

这里的 R 只是一个随机值，添加它是为了防止 h 和 u 被强制搜索发现 (在密码学术语中，添加 R 使哈希成为一个隐藏承诺)。

假设帖子使用根 R 并存储 {N,h¯，u¯}。在证明中，它链接到以前的帖子，存储数据 {Nprev,h¯prev,u¯prev}。帖子的证明也需要遍历在 hprev 和 h 之间发布的所有声誉条目。对于每个 nullifier N，验证函数将使用用户的密钥 k 解密 N，如果解密输出一个有效的索引，它会将应用声誉更新。如果所有声誉更新的总和为 δ，那么最终证明为 u=uprev+δ。

如果我们想要一个「三振出局」规则，ZK-SNARK 也会检查 u>−3。如果我们想要一个规则，即如果帖子的 rep≥100，那么该帖子可以获得一个特殊的「高声誉帖子」标识。

为了提高方案的可扩展性，我们可以将其分为两类消息：帖子和 RCA。一个帖子将是链下的，尽管它需要指向过去一周制作的 RCA。RCA 将是链上的， RCA 将遍历自该发布者之前的 RCA 以来的所有声誉更新。通过这种方式，链上负载减少到每周每个帖子的一笔交易加上每条声誉消息的一笔交易。

对中心化的各方负责

有时，你需要构建一个具有某种中心化「运营者」的方案。其背后原因可能有很多：有时是为了可扩展性，有时是为了隐私（具体来说，是为了运营者所持有的数据的隐私）。

例如，MACI 强制抵抗投票系统要求投票者在链上提交他们的投票，并加密到中心化运营者持有的密钥中。运营者将解密链上所有的投票，将其计数，并展示最终结果，同时使用 ZK-SNARK 来证明他们所做的一切都是正确的。这种额外的复杂性对于确保强大的隐私性 (称为强制抵抗) 来说是非常必要的：用户不能向其他人证明他们是如何投票的，即使他们想这样做。

多亏了区块链和 ZK-SNARK，确保了我们对运营者的信任度可以保持在非常低的水平。恶意的运营者仍然可以打破强制抵抗，但是因为投票是在区块链上发布的，所以运营者不能通过审查投票来作弊，而且因为运营者必须提供 ZK-SNARK，所以他们不能通过错误计算结果来作弊。

结合 ZK-SNARK 与 MPC

ZK-SNARK 的一个更高级的使用涉及到的是在计算中进行证明，其中输入在两方或多方之间分配，我们不希望任何一方学习其他方的输入。在两方的情况下，你可以通过乱码电路满足隐私要求，在 N 方情况下使用更复杂的多方计算协议来满足隐私要求。ZK-SNARK 可以与这些协议结合起来进行可验证的多方计算。

这可以启用更高级的信誉系统，多个参与者可以在他们的私有输入上执行联合计算。现在有效地实现这一目标的数学计算仍处于相对初级阶段。

我们不能将什么设为私有？

ZK-SNARK 对创建用户拥有私有状态的系统非常有效。但是 ZK-SNARK 不能保持没有人知道的私有状态。要对一段信息进行证明，则证明者必须以明文的形式知道这段信息。

Uniswap 就是一个不容易私有化的例子。在 Uniswap 中，有一个逻辑中心的「东西」，就是做市商账户，它不属于任何人，Uniswap 上的每笔交易都是与做市商账户进行交易的。你不能隐藏做市商账户的状态，因为那样的话，就必须有人以明文的形式持有这个状态以进行证明，并且每笔交易都需要他们的积极参与。

你可以用 ZK-SNARK 的乱码电路做一个中心化操作的、安全的、私有的 Uniswap，但谁也不清楚这样做的好处能否抵消执行它所需要的代价。这甚至可能不会带来任何真正的好处：合约需要能够告诉用户资产的价格是什么，而逐块的价格变化可以告诉用户交易活动是什么。

区块链可以让状态信息全球化，ZK-SNARK 可以让状态信息私有化，但我们真的没有任何好的方法可以让状态信息全球化同时实现私有化。

将原语放在一起

在上面的小节中，我们看到了一些本身就是强大且有用的工具的示例，但它们也可以作为其他应用程序的构建块。例如，nullifier 对于货币来说很重要，现在它们在其他用例中也在重复出现。

在负面声誉部分使用的「强制链接」技术适用范围非常广。它对于许多应用程序非常有效，其中用户的「配置文件」会随着时间的推移以复杂的方式发生变化，你希望强制用户遵守系统的规则，同时保护隐私。用户甚至可以被要求用完整的私有 Merkle 树来表示他们的内部「状态」。这篇文章中提出的「承诺池」小工具可以用 ZK-SNARK 来构建。如果某些应用程序不能完全在链上并且必须有一个中心化的运营者，那么完全相同的技术也可以用来保持运营者的诚实。

ZK-SNARK 是一个非常强大的工具，它将责任和隐私的好处结合在了一起。同时它们也确实有其局限性，但在某些情况下，聪明的应用程序设计可以绕过这些限制。我希望看到更多的应用程序使用 ZK-SNARK，并最终在未来几年内构建出将 ZK-SNARK 与其他形式的加密相结合的应用程序。