ZK-SNARK如何适应现有的应用程序？

ZK-SNARK是一种强大的加密工具，并且是人们在区块链空间内外构建的应用程序中越来越重要的一部分。但是它们很复杂，无论是就它们的工作方式而言，还是就如何使用它们而言。本文我们将着重探讨 ZK-SNARK 在保护 隐私 方面的应用。

ZK-SNARKs该如何适应现有的应用程序，它们可以做什么，不能做什么的一些例子，以及确定 ZK-SNARK 是否SNARKing一些特定的应用程序是可能的？

来源：medium

作者：uncle Fibonacci

编译：陈一晚风

ZK-SNARK有什么作用？

假设您有一个公共输入x、一个私有输入w和一个（公共）函数 f(x,w)→{True,False}，它对输入执行某种验证。使用ZK-SNARK，您可以证明您知道一个w，使得对于某些给定的f和x，f(x,w)=True，而无需透露w是什么。此外，验证者可以更快地验证证明，即使他们知道w，他们也可以自己计算f(x,w)。

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

会员证明

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

1.私人输(w)：您的地址 A，以及您地址的私钥k；

2.公共输入(x)：具有经过验证的人性证明配置文件 {H1…Hn} 的所有地址的集合；

3.验证函数f(x,w) ；

4.将 解释为对(A,σ)，并将x解释为有效配置文件列表 {H1…Hn}；

5.验证A是 {H1…Hn} 中的地址之一；

6.验证privtoaddr(k)=A；

7.如果两个验证都通过，则返回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。将来，其中一些用例可能会迁移到类似于填缝的方案。

代币的ZK-SNARK

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

以下是我们如何解决这个问题。任何拥有代币的人都有一个私人秘密。他们在本地计算“叶子”L=hash(s,1)，它在链上发布并成为状态的一部分，以及N=hash(s,2)，我们称之为nullifier。状态存储在Merkle树中。

要花费代币，发件人必须制作ZK-SNARK，其中：

1.公共输入包含一个无效符N、当前或最近的Merkle根R和一个新叶L'（目的是接收者有一个秘密 s'，并传递给发送者 L'=hash(s',1)）；

2，私有输入包含一个秘密 s、一个叶子 L 和一个默克尔分支M。

验证功能检查：

1.M是一个有效的Merkle分支，证明L是具有根R的树中的叶子，其中R是状态的当前Merkle根；

哈希(s,1)=L；

哈希(s,2)=N。

交易包含无效符N和新叶L'。我们实际上并没有证明关于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个时期）。我们的目标是允许每个用户每个epoch只发送一条消息；如果用户在同一时期发送两条消息，他们将被捕获。为了允许用户偶尔发送突发消息，他们可以使用最近的epoch，因此如果某些用户有500个未使用的epoch，他们可以使用这些epoch一次性发送500条消息。

协议

我们将从一个简单的版本开始：我们使用无效符。用户生成一个N=hash(k,e)的无效符，其中k 是他们的密钥，e是纪元数，并将其与消息m一起发布。ZK-SNARK再次混合hash(m) 而不验证关于m的任何内容，因此证明绑定到单个消息。如果用户使用相同的无效符将两个证明绑定到两条不同的消息，他们可能会被抓住。

现在，我们将继续讨论更复杂的版本。下一个协议不仅可以轻松证明某人是否两次使用了相同的时期，而且在这种情况下实际上会显示他们的 私钥 。我们的核心技术将依赖于“两点成一条线”的技巧：如果你在一条线上显示一个点，你就显示的很少，但是如果你在一条线上显示两个点，你就显示了整条线。

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

回顾一下，这里的ZK-SNARK如下：

公众意见：

{A1…An}，有效账户列表

m，证书正在验证的消息

e，用于证书的纪元号

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截距（这是私钥）：

因此，如果有人重用一个epoch，他们就会泄露他们的私钥供所有人查看。根据具体情况，这可能意味着资金被盗、验证者被削减，或者只是将私钥广播并包含在智能合约中，此时相应的地址将从集合中删除。

我们在这里完成了什么？一个可行的脱链匿名反拒绝服务系统，可用于区块链对等网络、聊天应用程序等系统，无需任何工作证明。RLN（速率限制无效器）项目目前基本上正在构建这个想法，尽管有一些小的修改（即，他们同时使用无效器和两点在线技术，使用无效器更容易捕获双重- 使用一个时代）。

ZK负面声誉

假设我们要建立0chan，一个像4chan一样提供完全匿名的互联网论坛（所以你甚至没有持久的名字），但有一个声誉系统来鼓励更多高质量的内容。这可能是一个系统，其中一些审核DAO可以将帖子标记为违反系统规则并建立三击即出机制，它可能是用户能够对帖子投赞成票和反对票；有很多配置。

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

链接帖子：基础知识

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

公共投入：

无效符N；

最近的区块链状态根R；

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

私人输入：

你的私钥k；

外部身份（地址为 A）或上一篇文章使用的无效符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)无效符N尚未使用。到目前为止，这就像之前介绍的隐私保护代币，但我们添加了一个“铸造”新帐户的程序，并且我们删除了将您的帐户“发送”到不同密钥的能力 - 相反，所有无效符都是使用生成的你原来的钥匙。

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

添加声誉

该方案中的声誉是链上明确的：一些智能合约有一个方法addReputation，该方法将(i)与帖子一起发布的无效值作为输入，以及(ii)要添加和减去的声誉单元的数量。

我们扩展了每个帖子存储的链上数据：我们存储{N,h¯,u¯}，而不是仅存储无效符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。如果我们想要一个规则，如果一个帖子≥100的代表，一个帖子可以获得一个特殊的“高声誉海报”标志，我们可以通过添加“is u≥100?”来适应它。作为公共输入。可以适应多种这样的规则。

为了提高方案的可扩展性，我们可以将其分为两种消息：帖子和信誉更新确认(RCA)。一个帖子将是链下的，尽管它需要指向过去一周制作的RCA。RCA将在链上，并且RCA将遍历自该发布者之前的RCA以来的所有声誉更新。通过这种方式，链上负载减少到每周每张海报的一笔交易加上每条声誉消息的一笔交易（如果声誉更新很少，例如，它们仅用于审核操作或可能是“发布日”风格奖品）。

追究中心化各方的责任

有时，您需要构建一个具有某种中央“操作员”的方案。这可能有很多原因：有时是为了可扩展性，有时是为了隐私——特别是运营商持有的数据的隐私。

例如， MACI抗强制投票系统要求选民在链上提交他们的投票，并加密到中央运营商持有的密钥中。运营商将解密链上的所有选票，将它们计数，并显示最终结果，以及证明他们做的一切正确的 ZK-SNARK。这种额外的复杂性对于确保强大的隐私属性（称为强制抗性）是必要的：即使用户想要，用户也无法向其他人证明他们是如何投票的。

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

将ZK-SNARK与MPC相结合

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

这可以启用更高级的信誉系统，其中多个参与者可以对其私人输入执行联合计算，它可以启用隐私保护但经过身份验证的数据市场，以及许多其他应用程序。也就是说，请注意，有效执行此操作的数学运算仍处于起步阶段。

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

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

Uniswap是一个不能（轻易）私有化的简单例子。在Uniswap中，有一个逻辑中心的“事物”，即做市商账户，它不属于任何人，Uniswap上的每一笔交易都与做市商账户进行交易。您无法隐藏做市商账户的状态，因为这样就必须有人以明文形式保存状态以进行证明，而且每笔交易都需要他们的积极参与。

您可以使用ZK-SNARKed乱码电路制作一个中央操作但安全且私密的Uniswap，但目前尚不清楚这样做的好处是否值得付出代价。甚至可能没有任何真正的好处：合约需要能够告诉用户资产的价格是多少，而价格的逐块变化可以说明交易活动是什么。

区块链可以使状态信息全局化，ZK-SNARKs可以使状态信息私有化，但是我们真的没有任何好的方法可以同时使状态信息全局化和私有化。

将原语放在一起

在上面的部分中，我们看到了一些本身就是强大且有用的工具的示例，但它们也旨在用作其他应用程序的构建块。例如，无效符对货币很重要，但事实证明它们在各种用例中一次又一次地出现。

负面声誉部分使用的“强制链接”技术非常适用。对于许多应用程序来说，它非常有效，因为用户拥有复杂的“配置文件”，这些配置文件会随着时间的推移以复杂的方式发生变化，并且您希望强制用户遵守系统规则同时保护隐私，这样就没有人看到哪个用户正在执行哪个操作。甚至可能要求用户拥有代表其内部“状态”的整个私有Merkle树。这篇文章中提出的“承诺池”小工具可以使用ZK-SNARKs构建。如果某些应用程序不能完全在链上并且必须有一个中心化的运营商，那么完全相同的技术也可以用来保持运营商的诚实。

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