聚焦：ZK-SNARK 技术

Vitalik建议他的订阅者关注ZK-SNARK技术，那今天就让我们仔细看看这一切都是如何运作的吧。

一些使用ZK-SNARK来保护隐私的方法

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与其他形式的加密相结合的应用程序。