使用ZK-SNARKs保护隐私的几种方法

ZK-SNARKs 的隐私使用方法

一些使用 ZK-SNARKs 进行隐私保护的方法

特别感谢 Barry Whitehat 和 Gubsheep 的反馈和审查。

ZK-SNARKs 是一种强大的加密工具，也是人们在区块链领域及其他领域构建应用程序中日益重要的一部分。但它们很复杂，无论是在工作机制上，还是在如何使用它们上。

我之前的文章解释 ZK-SNARKs专注于第一个问题，试图以一种合理易懂但仍然理论完整的方式解释 ZK-SNARKs 背后的数学。这篇文章将专注于第二个问题：ZK-SNARKs 如何适用于现有应用程序，它们能做些什么示例，它们不能做什么，以及一些判断具体应用程序是否可以进行 ZK-SNARK 的一般准则。

特别是，这篇文章专注于 ZK-SNARKs 在保护隐私方面的应用。

ZK-SNARKs 的作用是什么？

假设你有一个公共输入 x，一个私有输入 w，以及一个 (公共) 函数 f(x,w)→{True,False}，它对输入进行某种验证。使用 ZK-SNARK，你可以证明你知道一个 w，使得 f(x,w)=True，而不揭示 w 的具体值。此外，验证者可以比自己计算 f(x,w) 的速度快得多来验证证明，即便他们知道 w。

这为 ZK-SNARK 赋予了两个特性：隐私性和可扩展性。如上所述，在这篇文章中，我们的示例将重点关注隐私性。

会员资格证明

假设你有一个以太坊钱包，你想证明该钱包具有人类注册的证明，而不透露你是哪个注册人。我们可以如下数学地描述该函数：

• 私有输入 (w)：你的地址 A 和指向地址的私钥 k
• 公共输入 (x)：所有具有经过验证的人类证明资料的地址集合 {H1...Hn}
• 验证函数 f(x,w):
  • 将 w 解释为对 (A,k) 的描述，而 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-证明会员资格，值得注意的是，最近有一种更高效的替代方案方案，称为Caulk。未来，一些使用场景可能会迁移到类似 Caulk 的方案。

ZK-SNARKs 用于币

项目如 Zcash 和 Tornado.cash 允许你拥有隐私保护的货币。现在，你可能会想使用上面的“ZK 人类证明”，而不是证明访问人类证明资料，改为证明对币的访问。但我们遇到了一个问题：我们必须同时解决隐私和双重花费问题。也就是说，不能有可能同时花费同一代币两次。

我们可以这样解决：每个拥有代币的人都有一个私有秘密 s。他们在本地计算“叶子” L=hash(s,1)，在链上发布并成为状态的一部分，以及 N=hash(s,2)，我们称之为无效化器。状态存储在 Merkle 树中。

要花费代币，发送者必须进行一个 ZK-SNARK，其中：

• 公共输入 包含无效化器 N、当前或最近的 Merkle 根 R 和一个新叶子 L'（目的是让接收者拥有一个秘密 s'，并将 L'=hash(s',1) 传递给发送者）
• 私有输入 包含一个私有秘密 s、一个叶子 L 和一个 Merkle 分支 M
• 验证函数 检查：
  • M 是一条有效的 Merkle 分支，证明环境 L 是当前 Merkle 根 R 所在树中的一个叶子
  • hash(s,1)=L
  • hash(s,2)=N

事务包含无效化器 N 和新的叶子 L'。我们实际上并不证明有关 L' 的任何信息，而是“将其混合”到证明中，以防止在事务进行中第三方修改 L'。

要验证交易，链检查 ZK-SNARK，同时还需检查 N 是否没有在之前的花费事务中被使用。如果交易成功，N 将被加入已花费的无效化器集中，确保无法再次被使用。L' 将被放入 Merkle 树。

这里发生了什么？我们使用 zk-SNARK 将两个值 L（在代币创建时入链）和 N（在代币花费时入链）联系起来，而不揭示 L与N 是如何联系起来的。只有知道生成两者的秘密 s 的情况下，才能发现 L 和 N 之间的联系。每个创建的代币只能被消费一次（因为每个 L 只有一个有效对应的 N），但在特定时刻哪个代币正在被消费是保持隐藏的。

这也是一个重要的原语，需要理解。我们下面描述的许多机制将基于非常类似的“私有消费仅一次”工具，尽管出于不同目的。

具有任意余额的币

上述内容可以很容易地扩展到具有任意余额的币。我们保留“代币”的概念，只是每个代币都有一个（私有）余额。实现这一目标的简单方法是让链条为每个代币存储不仅仅是叶子 L，还要存储一个加密的余额。

每个交易将消耗两个代币，并创建两个新代币，并将两个（叶子、加密余额）对加入状态。ZK-SNARK 还将检查进入的余额之和是否等于出去的余额之和，并确保两个输出余额均为非负值。

ZK 反拒绝服务

一个有趣的反拒绝服务 gadget。假设你有一些在链上创建时不简单的身份：它可以是一个人类证明资料，可以是一个持有 32 ETH 的验证者，也可以只是一个非零 ETH 余额的账户。我们可以创建一个更具抗 DoS 的点对点网络，仅在发送者提供具有此类资料的证明时才接受消息。每个资料将允许每小时发送最多 1000 条消息，如果发送者作弊，则发送者的资料将从列表中删除。但我们如何使其隐私保护？

首先，是设置。设 k 为用户的私钥；A=privtoaddr(k) 为对应地址。有效地址列表是公开的（例如，是链上的注册）。到目前为止，这与人类证明示例类似：你必须证明你拥有一个地址的私钥，而不揭示具体是哪个地址。但在这里，我们不只想要证明你在列表中。我们希望协议能让你证明自己在列表中但防止你进行过多证明。因此，我们需要做更多工作。

我们将时间分为几个 epoch；每个 epoch 持续 3.6 秒（每小时 1000 个 epoch）。我们的目标是允许每个用户每个 epoch 只能发送一条消息；如果用户在同一 epoch 中发送两条消息，他们会被抓住。为了允许用户偶尔发送消息，会允许他们使用近期内的 epoch，因此如果某个用户有 500 个未使用的 epoch，他们可以利用这些 epoch 同时发送 500 条消息。

协议

我们从简单版本开始：使用无效化器。用户生成 nullifier 通过 N=hash(k,e)，其中 k 是他们的密钥，而 e 是 epoch 编号，并与消息 m 一并发布。ZK-SNARK 再次在未验证任何关于 m 的内容的情况下混入 hash(m)，使得证明仅绑定到单个消息上。如果用户用相同的无效化器制作两个绑定到不同消息的证明，他们会被抓住。

现在，让我们进入更复杂的版本。不仅使得证明某人使用相同的 epoch 变简单，此下一协议事实上将公开他们的私钥。我们的核心技术将依赖“两个点形成一条直线”的技巧：如果你揭示直线上的一个点，你揭示的极少，但如果你揭示直线上的两个点，你就揭示了整条直线。

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

简而言之，ZK-SNARK 如下：

• 公共输入 :
  • {A1...An}，有效账户列表
  • m，验证证书的消息
  • e，用于证书的 epoch 编号
  • y，直线函数评估
• 私有输入 :
  • k，你的私钥
• 验证函数 :
  • 检查 privtoaddr(k) 是否在 {A1...An} 中
  • 检查 y=hash(k,e)∗hash(m)+k

但如果有人重复使用单个 epoch 呢？这意味着他们发布了两个值 m1 和 m2 以及相应证书值 y1=hash(k,e)∗hash(m1)+k 和 y2=hash(k,e)∗hash(m2)+k。我们可以使用这两个点来恢复直线，因此得到 y 轴截距（即私钥）：

k=y1−hash(m1)∗y2−y1hash(m2)−hash(m1)

所以如果某人重复使用一个 epoch，他们就会泄漏出他们的私钥，让所有人看到。根据情况，这可能意味着被盗的资金、被斩的验证者，或仅是私钥被广播并包含在智能合约中，此时相应地址将被移出。

我们在这里能够取得什么成就？一个可行的链外匿名反拒绝服务系统，适用于像区块链这样的点对点网络、聊天应用等，而不需要任何工作证明。RLN (率限制无效化器) 项目目前正在构建这一理念，尽管进行了小幅修改（即它们同时使用无效化器和两个点做一条线的技术，利用无效化器更容易捕捉到对 epoch 的重复使用）。

ZK 负声誉

假设我们想构建 0chan，一个像 4chan 一样提供完全匿名的互联网论坛（所以你甚至没有持久的名称），但有一个声誉系统以鼓励更高质量的内容。这可以是一个由某些治理 DAO 标记帖子违反系统规则的系统，实施“ 三次机会制”，用户能够对帖子进行赞成和反对；有很多配置。

声誉系统可以支持正面或负面的声誉；然而，支持负声誉需要额外的基础设施，以要求用户在他们的证明中考虑所有声誉信息，甚至是负面信息。重点在于这个更困难的用例，这与在Unirep 社交中实施的情形类似。

链接帖子：基础

任何人都可以通过在链上发布包含该帖子的消息以及一个证明（证明你拥有某个稀缺的外部身份，例如人类证明，拥有创建账户的资格）来自发布帖子，或者证明你曾做过某个特定的先前帖子。具体而言，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)<264），那么你就知道这个无效化器是使用 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 还将检查 u>−3。如果我们希望规则是如果帖子具有 ≥100 声誉，发布者可以获得特殊的“高声誉帖子”标志，我们可以通过添加“u≥100？”作为公共输入来满足这一点。许多此类规则都可以得到满足。

为了提高方案的可扩展性，我们可以将其分成两种消息：帖子和声誉更新确认（RCA）。帖子的状态将是链外的，尽管要求其指向一条在过去一周内制作的 RCA。RCA 将是在链上的，而且之一将访问自上一个 RCA 以来所有声誉更新之数据。这样，链上的负担减少为每周每个帖子只需一个事务，以及每个声誉消息的一个事务（如果声誉更新较少，则达成较低水平，例如，仅用于审核操作，或可能用于“今日帖”的奖励）。

追究中心化方的责任

有时，你需要构建一个有某种中央“操作员”的方案。这可能出于多种原因：有时是为了可扩展性，有时是为了隐私——具体来说，是操作员持有的数据的隐私。

例如，MACI 抗胁迫投票系统要求选民使用加密到中央操作员持有的秘密密钥的方式在链上提交自己的投票。操作员将在链上解密所有投票，总结结果，并揭示最终结果，并提供一个 ZK-SNARK 证明他们一切正确执行。这种额外复杂性对于确保一种强大的隐私特性（称为抗胁迫性）是必需的：用户甚至无法向其他人证明他们是如何投票的，即使他们想要这样做。

由于区块链和 ZK-SNARK，用户对操作员的信任程度可以保持得很低。一个恶意的操作员仍然可能破坏抗胁迫性，但因为投票已发布在区块链上，所以操作员无法通过审查投票来作弊，而且因为操作员必须提供 ZK-SNARK，他们不能通过错误计算结果来作弊。

将 ZK-SNARKs 与 MPC 结合

ZK-SNARKs 的更高级用途涉及对输入在两个或多个方之间进行分割的计算进行证明，而我们不希望每个方了解其他方的输入。你可以在两方的情况下用 garbled circuits 满足隐私要求，而在 N 方的情况下则使用更复杂的多方计算协议。ZK-SNARKs 可以与这些协议结合，进行可验证的多方计算。

这可能启用更高级的声誉系统，其中多个参与者可以对其私有输入进行联合计算，还可以实现保护隐私但又经过身份验证的数据市场，以及许多其他应用程序。那样说，请注意，高效做到这一点的数学仍然相对处于初级阶段。

什么不能做到隐私保护？

ZK-SNARKs 通常对创建用户具有私有状态的系统非常有效。但是 ZK-SNARKs 无法持有_无人_知道的私有状态。为了创建一个关于某个信息的证明，证明者必须知道该信息的明文。

一个简单的例子是 Uniswap。 在 Uniswap 中，有一个单一的逻辑中心化“东西”，即市场做市商账户，归任何人所有，而 Uniswap 上的每一笔交易都与做市商账户进行交易。你无法隐藏做市商账户的状态，因为那样某人必须以明文方式保持该状态以进行证明，并且他们的主动参与在每笔交易中都是必需的。

你可以使用 ZK-SNARKed garbled circuits 来创建一个由中央操作的，但安全和私密的 Uniswap，但尚不清楚这样做的好处是否值得成本。这甚至可能没有真正的好处：合约需要让用户知道资产的价格，价格的逐区块变化揭示了很多关于交易活动的信息。

区块链可以使状态信息成为全球的，ZK-SNARK 可以使状态信息成为私有的，但我们没有什么好的方法可以同时使状态信息变得全球且私有。

编辑：你可以借助多方计算来实现共享私有状态。但这需要一个诚实多数阈值假设，并且在实践中可能不太稳定，因为（与例如 51％ 攻击不同）恶意多数可以串通泄漏隐私，而不会被发现。

将原语结合在一起

在上述各节中，我们看到了一些强大且有用的工具的示例，但它们也旨在作为其他应用中的构建模块。例如，无效化器在货币中非常重要，但事实证明，它们在各种用例中不断出现。

“强制链接”技术在负声誉部分用于广泛的应用。它适用于许多输入复杂“档案”的应用程序，这些档案随着时间的推移而以复杂的方式变化，而你希望迫使用户遵循系统规则，同时保持隐私，以便不会有人查看用户在执行哪项操作。用户甚至可能被要求拥有整个私有 Merkle 树以表示他们的内部“状态”。 本文提到的 “承诺池” gadget 可以用 ZK-SNARK 构建。如果某个应用无法完全放在链上而必须有一个中心化的操作员，那么可以使用完全相同的技术来保持操作员的诚实。

ZK-SNARKs 是一个真正强大的工具，可以结合问责制和隐私的好处。它们确实有其局限性，但在某些情况下，巧妙的应用设计可以绕过这些局限性。我预计在未来几年将看到越来越多应用使用 ZK-SNARKs，甚至是将 ZK-SNARKs 与其他形式的加密结合的应用。

• 原文链接： vitalik.eth.limo/general...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～