使用zkSNARKs的群签名
原文：https://0xparc.org/blog/zk-group-sigs
翻译：Kurt Pan
zkSNARKs 将密码学问题转化为编程任务。 zkSNARK 电路的可编程性使它们能够模拟和扩展各种以前需要构建新的数学协议的密码原语。在这篇文章中，我们分解了一个基本的 zkSNARK 构造，它实现了一个旧的密码原语——“群签名方案”。我们还演示了基于该方案的匿名留言板的概念验证实现。
Part1引言
在许多在线社区中，允许成员同时以可信和匿名的方式参与似乎是自相矛盾的。你的声誉与你的身份密切相关——很难验证来自无法追踪来源声明的可信度。
一方面，匿名性允许 4chan 和 Reddit 等平台上的“匿名用户”和“一次性账户”们以他们和平常不一样的方式来表达自己的想法，并使举报人能够公开披露公司或政府的不法行为，同时保护自己免受报复。另一方面，很难验证与已知或可信的身份无关的声明的可信度，而且完全匿名也可能成为希望传播错误信息或骚扰其他社区成员的不良行为者的工具。理想情况下，我们希望让高风险讨论的参与者能够在不放弃隐私的情况下证明他们的可信度。
引入群签名。在密码学群签名方案中，参与者可以生成消息签名，以证明他们是一群已知参与者中的成员之一，而无需透露他们的具体身份。《联邦党人文集》就是历史上著名的一次群签名行动——文件由Publius签名，这是Alexander Hamilton, James Madison, 和John Jay (h/t Dan and Varun)等人的集体化名。
这篇文章中，我们将展示一些使用 zkSNARKs 实现易于编写的群签名的技术（大约 40 行 circom 代码！）。这些群签名 SNARK 可以插入到 web 应用中，与身份提供者（以太坊帐户、社交媒体帐户等）集成，并增加各种可选属性，如可追溯性、可否认性等。
值得注意的是，使用 zkSNARKs 将群签名协议的扩充和配置变成了一个_编程任务_，而不再是一个_数学问题_。 例如，不必发明一种全新的密码方案来增加“可否认性”的属性，你只需添加或修改几行 ZK 电路代码即可。我们的群签名演示只是更广泛模式的一个示例——zkSNARK 使开发人员能够编写新的密码原语，而无需考虑椭圆曲线、双线性配对、多项式承诺或其他密码数学。
1概念验证：ZKMessage
实用的群签名方案有许多有趣的用例。加密朋克持有者或拥有百万粉丝的 Twitter 用户可以发布带有签名的匿名消息，这些签名可以证明各自的属性，但不会透露有关其身份的任何其他信息。更进一步，可以想象一位高级政客在公众投票前建立共识期间使用群签名匿名表示支持拟议的立法，在证明他们是政党成员的同时，保护他们的隐私以避免短期的政治反弹。
作为一个简单的概念验证，我们构建了ZKMessage：一个允许用户生成匿名群签名的留言板。
https://zkmessage.xyz/
用户首先通过对新生成的密钥对的证明发推来声明 ZKMessage 公钥。当用户希望提交一个帖子时，他可以选择最多 39 个其他用户群成一个群，在客户端为他们的消息生成一个群签名零知识证明，然后将消息和签名发送到服务器，服务器将签名的帖子存储在一个Postgres数据库中。然后，网络服务器将这些签名帖子提供给希望查看留言板的用户；用户可以在客户端验证签名，但他们无法将原始发帖人的范围缩小到比发帖人指定的群更小。
ZKMessage 具有以下属性：
群签名是不可伪造的。 没有人可以代表他们不属于的群签署消息。 群签名提供密码学匿名性。 对于任何给定的群签名消息，没有人（除了签名者）可以确定群中的谁产生了该消息。 可以审查消息和签名（尽管这很容易修复）。 因为帖子是由中心化代理（我们的网络服务器）存储和提供服务的，所以服务器可以否认发布帖子。但是，该协议不需要这种集中化。你最终可以将服务器换成去中心化数据层（即一个智能合约或 p2p 网络）。
我们希望这个演示可以启发更多的应用——我们将在下面讨论数字投票系统、隐私保护认证系统等潜在扩展——但还有很多工作要做。
ZK电路代码：https://github.com/gubsheep/zk-group-sigs 网络服务器/前端客户端代码：https://github.com/joeltg/zkmessage.xyz
Part2背景
2群签名
群签名是一种古老且经过充分研究的密码学原语。群签名的构造已经存在了几十年，可以追溯到 Chaum 和 Van Heyst 1991 年的初始论文。不同的群签名方案在几个维度上有所不同，并提供不同的保证：
群需要提前固定吗？一些方案要求提前声明好群，并有特定于群的设置过程（有时甚至需要受信任的群管理员）。其他方案是动态的，允许在给定已知地址簿的情况下为每个签名动态生成群（参见环签名）。 该方案是否允许具有额外权限的受信任实体（或多个实体）？例如，一些方案允许受信任的群协调员虽然不能伪造签名，但可以使用陷门撤销签名的匿名性（可追溯性）。 参与者能否确认一个先前生成的群签名确实是由他们单独签名的，而无需透露他们的私钥？ 参与者能否在不透露他们的私钥的情况下否认一个群签名，证明他们不是签名消息的人？ 签名必须要多少比特长才能达到所需的安全级别？签名的长度是否随群的大小而变化？
已经做了大量的理论工作来构造具有各种不同属性、渐近效率等的协议。[1]然而，就我们所知，这些协议在实践中并没有发现太多实际应用[2]，尽管事实上，有许多“明显”的潜在应用。我们希望 zkSNARK 工具可以使可编程群签名更容易实现并集成到 dapp 中，从而可能解锁一些应用，这些应用无法从头开始合理地实现整个密码学签名方案（和工具栈）。
3zkSNARKs
zkSNARKs 是一个强大的新工具，它可以让你证明你已经在一个秘密输入上正确地执行了一些公开的代码，并获得了一些公开声明的输出作为计算的结果。zkSNARK 非常强大，因为它们允许我们为任何数学函数生成零知识证明。
在数字签名的例子中，前几代的密码学家必须创建特定的数学协议来为私钥/公钥关系产生零知识证明；而产生该关系零知识证明的方法并不能轻易“重新编程”以构建用于模幂运算的 ，SHA256的，或Dark Forest游戏的密码学战争迷雾机制的零知识证明。同样，每个群签名方案在历史上都依赖于特定的密码机制，构建具有不同属性集合的群签名方案可能需要从头开始并使用不同的数学构建块。
相反，zkSNARKs 使你能够为任意代码生成零知识证明——允许开发者在“密码计算机”上编程，而无需深入了解底层数学机制的理论知识。用一个粗略的类比：如果发明一种新的密码方案就像构建一个 ASIC，那么编写一个 SNARK 就像在一个图灵完备的通用计算机上写程序。
接下来我们将展示 SNARK 如何使“可编程”群签名成为可能。
Part3电路构造
我们的概念验证 ZKMessage 电路是用 Circom 编写的，Circom 是一种用于定义零知识协议的语言。我们提出了三个电路：第一个电路(sign)是最重要的，也是唯一一个对模拟群签名协议严格必需的电路。该协议可以通过revealSigner和denySigning电路作为插件进行扩充。
sign：在证明群成员身份的同时证明消息。revealSigner：证明你的特定私钥用于签署特定的群签名消息。denySigning：证明你的特定私钥未用于签署特定的群签名消息。
在我们的方案中，每个用户都由一个公钥标识，它被简单地定义为用户私钥的哈希值。多亏了 zkSNARKs，将公钥定义为在私钥上运行单向函数的输出就足以满足我们的目的了——我们不需要公私钥之间的任何其他的数学关系。
4签名
这是消息签名电路的概述：
**输入:**
- hash1, hash2, hash3, ... ： 群中用户的公开哈希 (公开输入)
- msg ： 要广播的消息 (公开输入)
- secret ： 用户的私钥(私有输入)
**输出:**
- msgAttestation
电路需要证明几件事，我们将在下面详细解释：
- myHash := mimc(secret)
- (myHash - hash1)(myHash - hash2)(myHash - hash3)... == 0
- msgAttestation := mimc(msg, secret)
我们首先获取用户的私钥并对其应用MiMC哈希（一种SNARK 友好的哈希），导出公开哈希。然后我们获取用户的公开哈希并将其与所有存在的公开哈希列表进行比较。一旦我们验证该列表中确实存在公开哈希，这意味着用户是该群的有效成员，我们使用私钥“签署”消息并将签名返回。
电路分解
为了从概念上演示电路，我们将输入哈希的数量固定为 3，尽管它实际可以是任意的。我们将在下面分解示例 Circom 代码的片段；完整的电路见链接。
https://github.com/0xPARC/zk-group-sigs/blob/6c68294897149c65ae11a6fc283fa28cc6a089e5/circuits/sign.circom
我们首先声明一些输入，一个是私有的，其余是公开的。hash1, hash2,hash3是代表该群的其他用户的公开哈希。secret是发送者的私钥，msg是用户要证明的消息。
电路的第一部分将 MiMC 哈希应用于用户的私钥并将结果（公开哈希）存储在myHash信号中。
component mimcSecret = MiMCSponge(1, 220, 1);
mimcSecret.ins[0] <== secret;
mimcSecret.k <== 0;
myHash <== mimcSecret.outs[0];
然后我们检查用户私钥的 MiMC 哈希值myHash是否等于公开哈希值之一。如果是这样，这意味着用户是群的一部分，就验证了成员资格。由于 zkSNARKs 只能证明涉及算术运算（ +，- 和* ）约束的满足，我们的检查看起来会像这样：
signal temp;
temp <== (myHash - hash1) * (myHash - hash2);
0 === temp * (myHash - hash3);
最后，通过使用用户的私钥对消息应用 MiMC 哈希，我们对消息进行签名并返回。输出需要依赖于用户想要证明的特定消息，以防止重放攻击；没有这个，相同的证明就可以用来证明不同的消息。
component mimcAttestation = MiMCSponge(2, 220, 1);
mimcAttestation.ins[0] <== msg;
mimcAttestation.ins[1] <== secret;
mimcAttestation.k <== 0;
msgAttestation <== mimcAttestation.outs[0];
5revealSigner
第二个电路证明一个人的特定私钥被用于为一个消息生成群签名，从而允许用户以密码学的方式来揭示自己。
电路代码 : https://github.com/0xPARC/zk-group-sigs/blob/6c68294897149c65ae11a6fc283fa28cc6a089e5/circuits/reveal.circom
**输入:**
- myHash ： 用户私钥的 MiMC 哈希 (公开)
- msg ：需要验证的待签名消息(公开)
- msgAttestation ：需要验证的签名过的消息(公开)
- secret：用户私钥 (私有)
**输出:**
（无）
该电路证明了如下：
- msgAttestation == MiMC(msg, secret)
- myHash == MiMC(secret)
该电路类似于消息签名电路。我们首先使用 MiMC 验证用户私钥的哈希确实是公钥。然后我们验证消息和用户私钥的 MiMC 哈希正是消息证明。这说明消息已由正确的用户正确签名。
6denySigning
最后一个电路允许用户否认对特定消息的所有权。例如，如果匿名成员发送了不恰当的内容，其他成员可能想要否认该消息以清除他们的名字并挑出肇事者。
该电路与消息揭露电路几乎完全相同，只是我们不证明用户发送了消息，而是证明用户没有发送消息。输入与上述电路相同，但对要证明的语句稍作修改：
- msgAttestation != MiMC(msg, secret)
- myHash == MiMC(secret)
示例代码：https://github.com/0xPARC/zk-group-sigs/blob/6c68294897149c65ae11a6fc283fa28cc6a089e5/circuits/deny.circom
Part4协议增强
上面我们介绍了一系列 ZK 电路，这些电路使大小为3的群能够匿名签署消息并在消息发布后揭露/否认消息。在本节中，我们考虑了可能的协议增强，可用于将我们的构造产品化，以及我们的 ZK 电路如何与区块链和去中心化后端集成。
7揭露和否认的开启和关闭
允许特定用户轻松否认他们发送过消息可能是不可取的。考虑恶意方想要发现发送消息的人的身份并可以可靠地向签名群成员施加压力/强制的情况。他们可以系统地强制群成员“否认”他们发送的消息（例如威胁解雇未提交有效否认证明的人），从而发现发送消息的人。
要禁用人们事后否认消息的能力，我们可以删除sign电路中msgAttestation对secret的依赖——例如，通过设置msgAttestation := mimc(msg)[3]。请注意，这也消除了人们事后揭露他们发送消息的能力。
读者可以思考的一个有趣的练习是如何构建一个电路，让用户能够揭露他们发送了一条消息，同时消除了否认消息的能力[4]。
8Merkle 树和任意大的群
另一个协议扩展是允许电路检查任意大身份集的成员资格。使用上一节中概述的方法，我们可以尝试通过简单地增加公开输入数组的大小来增加最大身份集大小，或者通过将所有公钥“压缩”到单个输入中，将它们插入哈希函数中在零知识证明中运行。然而，这是不可取的，因为输入数据的大小或 SNARK 的计算复杂性必须与数组的大小成线性关系——即使是相对较小的大约 1000 个公钥的上限也会变得难以管理。
在大集合中验证成员资格的一个常见技巧是使用 Merkle 累加器。通过验证是否包含在 Merkle 树中而不是哈希列表中，我们可以扩展我们的最大集合大小。
以下是我们修改后的协议的工作方式：
给定 N个签名者想要为其创建群签名的公钥，签名者将计算包含N个密钥的 Merkle 树（和根），并将树/根发布到公开位置（智能合约、IPFS、Github 等）。当拥有 N个哈希中其中一个的私有秘密的人想要签署消息时，他将使用已发布的树和他的哈希的秘密来生成与他的秘密相对应的 Merkle 证明。请注意，这发生在零知识电路之外。使用上述 Merkle 证明，用户将使用具有以下输入和输出的电路生成集合成员零知识证明：
**输入：**:
- merkleRoot ：身份集合中所有哈希的merkle根(公开输入)
- message ： 要签名的消息(公开输入)
- secret ：用户私钥 (私有输入)
- merkleProof ：用户生成的Merkle证明 (私有输入)
**输出:**
- msgAttestation
零知识证明将证明以下论断：
- myHash := mimc(secret)
- msgAttestation := mimc(msg, secret)
- merkleVerify(merkleProof, myHash, merkleRoot) == true // 验证merkleProof证明了myHash包含在merkleRoot中
请注意，电路的输入现在是固定大小的：merkleRoot只是一个单个的哈希，merkleProof是一个哈希数组，等于Merkle树的深度。Merkle 树可以容纳的哈希数量等于2^d，其中d是树的深度，因此即使是深度为 30 的树也足以满足大多数实际用途。
Tornado Cash 用于验证 Merkle 证明的 Circom 电路实现在这里。
https://github.com/tornadocash/tornado-core/blob/master/circuits/merkleTree.circom
应用开发人员可以对一个易于审计的群进行快照（例如，“所有 在时间戳 X 时拥有一个 Cryptopunk的ETH 地址”），为该群生成一个 Merkle 树，在链上发布根，然后在 IPFS 上发布树。然后，任何人都可以通过引用这些可公开访问的数据来生成和验证该群的群签名。
9可信群管理员
一些群签名构造还定义了群管理员的概念，协议授予他额外的权限以对签名者进行去匿名化，或者证明给定的群成员没有产生签名。
具有这些权限的群管理员可以很容易地在 zkSNARK 群签名协议中实例化，只需要求协议参与者将使用硬编码的群管理员的公钥加密的他们的加盐公钥作为 signSNARK 的附加输出。为此，协议开发人员需要使用进行加密和解密的零知识电路。
https://github.com/nulven/EthDataMarketplace#encryption-proof
Part5进一步探索
10中心化 vs 去中心化后端
为了演示，我们的概念验证使用中心化后端。
使用中心化后端存储所有零知识证明和消息有许多权衡点——最明显的是，允许服务器运营商审查不受欢迎的消息。（在这种情况下，我们确实计划审查辱骂性消息）。如果我们想要抗审查，那么使用像智能合约或点对点网络这样的去中心化后端可能是可取的。
请注意，存储签名消息的服务器的存在不会影响签名方案的密码学性质，因为群成员身份的验证是在 SNARK 内部完成的。服务器不知道哪个用户的身份签署了哪个消息[5]。服务器也不能在它不属于的群中生成“假”成员资格证明。
11身份属性证明
对任意大小的群（使用如上所述的 Merkle 累加器）允许匿名群签名的一个有趣的推论是身份属性证明的可能性，而不仅仅是在任意个人集合中的成员资格证明。
例如，零知识留言板可以配置为仅允许来自以下群的帖子：
目前拥有加密朋克的人 在 2018 年或更早的时候使用过以太坊的人 美国参议员 在 Twitter 上拥有至少 1 万粉丝的人
为了实现这一点，应用开发人员将维护一个 Merkle 根，该根包含每天更新的当前 Cryptopunk 持有者的所有哈希值。发布到留言板需要随附的零知识证明，证明发布者可以控制该 Merkle 根中的包括的私有地址，如上所述。
注意到，身份属性不能直接在密码学中强制执行，因为可以在任何公钥集合上构建证明。但是，我们可以选择仅识别对应于有效群的签名作为社会惯例。例如，一个中心化的后端可以在将帖子保存到数据库之前检查构建签名的 Merkle 树是否有效。去中心化的后端可以在客户端执行检查，隐藏来自被认为无意义的群的消息（例如，来自 50 名参议员加上另一个公钥的群签名）。
这种设计还有助于阻止许多对抗性场景。一个例子是敌手写了一条可能被合理地归于另一个用户的消息，并将其发布在一个包含他们的目标的群下——我们在早期的原型中看到了这种情况。在这种情况下，零知识论坛可能会成为相对匿名的恶意攻击者扮演知名人士的一种方式。将群签名从成员身份证明重新定义为身份属性证明有助于减轻这种攻击，因为签名现在证明具有此身份属性的人发布了消息，而不是该群中的某个人发布了消息（此外，它还有助于阻止使用小型或人为构建的群）。
12基于区块链的扩展
这些例子还暗示了区块链可以用作可靠的中立的对身份的账本的方式。例如，可以将智能合约配置为仅接受来自其根在链上注册表中被列入白名单的群的消息；此类注册表可以由 DAO 或治理代币控制。dapp 可以实施这种模式来减少来自敌对用户的垃圾邮件或滥用行为。
零知识论坛可以通过 NFT/资产所有权或 DAO 成员资格进行门控，现实世界的公钥目录也可以在链上发布并由预言机（监控现实世界公众人物列表的个人或组织）管理.
13零知识民意调查和投票
在我们的探索中，我们专注于零知识消息发送，但一个相关的应用系列是投票和民意调查。今天，许多大学和专业群织使用 Helios（一种密码学可验证的匿名投票系统）进行选举。Helios的基于 SNARK 的 版本将解锁许多额外的功能和属性（例如MACI，事后将不可能证明你曾以某种方式投票）。
https://appliedzkp.github.io/maci/index.html
SNARK 的模块化开辟了许多新的应用。如果社区组织有公开的民意调查，任何人都可以表达他们对不同问题的地方治理的支持率怎么样？如果市议会成员和社区领袖全年都可以就他们的观点得到匿名的民意调查怎么样？虽然所有这些都可以在没有零知识密码学（使用环签名和/或可信服务器）的情况下实现，但 SNARK 显着降低了实验的障碍。
14zkECDSA 群签名
最后一点是，我们当前构造中使用的哈希方案要求用户生成和发布特定于应用的公钥，在我们的例子中，是使用 MiMC 哈希函数进行哈希的的任意私有数据。出于互操作性的目的，用户应该能够使用他们现有的公钥对消息进行签名，例如他们的 SSH 私钥或以太坊地址。
这就需要在 SNARK 中实现相应的公钥签名方案。一种这样的方案是以太坊使用的 ECDSA 曲线，这将使匿名群签名可以与大型现有身份注册机构一起使用，例如目前拥有ENS的 227k 个地址。
在我们实现零知识留言板的时候，还没有这样的 SNARK。但是，现在有使用多种不同的语言和证明者的，在 SNARK 中实现 ECDSA 签名验证的几个实现正在进展之中。我们期待他们的发布，这将向更广的受众开放匿名群签名和零知识密码学技术。
Part6链接和脚注
有关群签名原语的形式化和概述，请参阅: https://cseweb.ucsd.edu/~mihir/papers/gs.pdf。 几乎没有正常可用的关于历史上的群签名协议的开源库存在，快速的文献检索也几乎没有发现实际应用的案例。最著名的例子可能是门罗币，它使用环签名；除了门罗币，这个库（https://github.com/IBM/libgroupsig) 列出了一个生产用例，以及这个（https://crypto.stanford.edu/~dabo/pubs/papers/groupsigs.pdf） BBS 签名的实现，大约一年前发布，似乎被用于一些新兴的加密/区块链项目。 这可能看起来令人困惑，因为这意味着消息证明不再特定于签名者；一个自然的问题是该方案是否因此容易受到重放攻击。该方案实际上仍然是安全的，因为零知识证明本身仍然是特定于签名者的——试图为消息生成假证明的恶意签名者可以生成 msgAttestation，但无法生成有效证明。使用msg信号输入在电路中执行任意计算将证明与特定消息联系起来；使用secret信号输入执行任意计算将证明与特定签名者联系起来。允许揭露但不允许否认：要修改零知识构造以允许用户揭露他们提交了一条消息，但不能否认，只需添加一个 salt参数（用户随机设置）作为消息签名电路的私有输入，和secret和message一起进行哈希以生成msgAttestation. 然后，要揭露消息，用户必须提供他们的私钥、盐和消息，并且揭露电路将验证mimc(secret, message, salt) = msgAttestation. 请注意，否认是不可能的，因为不可能证明你不知道一个salt可以与message和你自己的私钥secret来产生证明。请注意，如果用户没有通过 Tor 或其他代理访问服务器，则可能从 IP 日志等侧信道推断出此数据。但是，这超出了我们构造的范围，我们只是为了解决潜在的密码问题。