zkSNARKS，Circom（第二部分）

zkSNARKS, Circom（第二部分）

作者：Sergey Boogerwooger, MixBytes 的安全研究员

简介

在 上一篇文章 中，我们讨论了顺序哈希，允许我们构建 Merkle 证明以证明某个私有值在具有给定 Merkle 根的列表中属于该成员，或证明哈希原像的知识。我们尝试了两种哈希函数：Keccak-256 和 MiMC，并对电路大小、见证生成复杂性和证明的大小进行了试验。现在，让我们看看其他哈希函数，然后检查它们在构建成员证明中的使用。

MiMC、Pedersen、Poseidon 及其他 SNARK 相关算法

从最新的实验中了解到，当我们将 Keccak 哈希替换为 MiMC 时，有一些哈希算法的设计更适合电路。但你应该记住它们的使用与我们常见的哈希（如 Keccak、SHA256）有所不同。对于有限域运算（在电路中使用），效果最好的算法是利用有限域上的运算的算法，因此我们可以直接将输入信号传递给电路中的哈希函数（无需将其“拆分”为单独的位）。但是存在许多差异：安全的轮数、碰撞抗性、特定攻击等，深入研究这些问题比本文中呈现的内容要好得多。此外，你还应记住这一领域非常年轻，很多论文的确是“新鲜”的，因此我们对此内容的完整性不敢保证。

研究 这篇 论文关于不同算法提供的足够安全级别的位数和轮数是有帮助的。请注意，有限域算法中的“位数”并不等同于哈希的位长度，因为数字的二进制表现并没有直接的“1对1”映射到椭圆曲线上的点，二进制点的数量少于可能的二进制值。因此，在 SNARK 友好的算法中，我们需要估算“相应的安全性”（比如“这个256位哈希的安全级别是128位”）。我们不能直接告诉你应选择哪个安全级别，此外，所有这些算法的使用目的不同，你需要自己处理它们的安全级别。但我们会尽量提供一些关于在某些情况下错误使用它们的信息，并给出有趣文档的链接。

MiMC

MiMC 的规范在 这里。MiMC 的设计旨在减少乘法次数，从而生成非常紧凑的电路。在我们之前的例子中，我们使用了来自 circomlib 的 MiMC 实现，其使用指数为 7 的 MiMC 变体，代码中使用了 91 轮。在 这里 关于哈希的讨论中，我发现：MiMC/e7r91，448 位输入，730 个约束（目标是 256 位安全级别）和 MiMC/e7r46，448 位输入，370 个约束（目标是 128 位安全级别），似乎即使是 46 轮（128 位安全性）对许多任务来说也足够。

MiMC 轮函数是更复杂算法的基础，现今更重要的是 GMiMC，它在基于 Festel 的构造中使用 MiMC 轮函数，提高了算法的安全性。我们会在其他算法和最小电路实现中看到 MiMC。

Pedersen 哈希

Pedersen 哈希（文章）也是电路中一种流行的算法。Pedersen 哈希返回一个曲线上的点（Baby JubJub 在 circomlib 的 pedersen.circom 中使用）。与 MiMC 一样，它也允许跳过 Num2Bits<->Bits2Num 转换，通过使用信号作为输入来减少约束数量。

Pedersen 哈希具有一些特定属性，使其在解决某些问题（如同态加法）时极其有用。这是一个非常重要的特性，因为你可以进行“承诺 a”：呈现某个值 a 的 Pedersen 哈希，然后进行“承诺 b”，并相乘以得到承诺（a + b）== 承诺（a）* 承诺（b）（在这里简化，因为该方案使用了额外的随机数）。这里 给出了关于 Pedersen 承诺的简要解释。这种“隐藏”加法使我们能够解决一些安全问题：例如在 zk 投票（在不披露的情况下汇总投票）或涉及私有代币余额的操作。

这些特性并不是“免费”的，我们必须为其付出一些安全代价 - 例如，Pedersen 哈希对于固定大小的预图像是足够碰撞安全的。这意味着在实际使用中，如果你可以传递可变位长的预图像或使用某些填充，这可能是危险的。

另一个问题是，Pedersen 和两个对称点的“自然碰撞”：(x, y) 和 (x, -y) - 这在仅使用 x 坐标作为哈希结果时也可能很危险。对此类问题的更详细解释可以在这里找到。

你可以在我们的教育 仓库 中通过运行 run_all.sh pedersenn 进行实验，使用256次顺序哈希，但由于这些哈希的使用方式不同，不能直接与 MiMC 的约束数量进行比较。在 MiMC 中我们使用了91轮，在 Pedersen 中则没有“轮”，但有 n 个输入。它可以用于构建 Merkle 证明，但你始终需要提及此算法的安全属性。我们将在需要多个输入的情形以及同态方案中遇到 Pedersen。

Poseidon

Poseidon（以及其邻近的 STARKAD）算法通过受 AES（S-blocks）和 Keccak（海绵）构造启发的方法改进了 MiMC 的设计，保持了对统计攻击和代数攻击的安全性。它们都在内部使用 HADES 置换，并由于乘法的低数量在电路中非常高效。你可以在 这里 找到 Poseidon 的描述，而对 HADES 基础算法的有趣分析可以在 这里 找到。

我们将在许多现代电路中遇到 Poseidon，得益于其良好的安全性和电路约束数量之间的平衡。在我个人看来，现在是 2023年5月，对于许多需要碰撞抗性、安全且 SNARK 友好的算法的优秀 zk 案例来说，这是最流行的算法。

哈希 结论

正如你可能在上一篇文章中提到的，还有其他 SNARK/STARK 友好的哈希算法，如 Marvellous（具有 Vision 和 Rescue 置换），它们也展现出了良好的前景。

在一些哈希算法中，你可能提到过“海绵”模式（类似于 Keccak 中的那种）。这些算法之所以优秀，是因为它们的模式不仅可用于哈希。只需简单更改输入数据流的顺序和内容，这些算法就可以转变为其他加密原语：流密码、伪随机生成器、MAC（信息验证码），用于密钥派生等。

不幸的是，我们无法深入到这些细节中，这是学术密码学家的工作，也会使文章变得相当不切实际，但我强烈建议至少阅读一些基本文章。你绝对应该了解它们，以选择适合你任务的正确算法。

接下来，让我们看看这些算法在实际任务中的使用。

集合成员证明，Tornado

现在，使用我们工具箱中的哈希，让我们证明一些“集合成员身份”。描述集合成员实际应用的好文章是 这篇，它展示了 Tornado Cash 中实施的过程。让我们还研究一些来自 Tornado 测试的有用代码片段。

用户 生成 他们存款的承诺

• 存款的承诺为 pedersenHash(secret, nullifier)。

用户将1 ETH 与承诺一起发送到合同 这里

• 承诺被添加到合同中的 Merkle 树，在 这里 实现。

现在，用户想证明他们对 nullifier 的知识以“无效化”他们的承诺并取回 1 ETH

• 用户准备证明者的输入（包含 nullifier 和 secret） 这里
• 用户在 这里 生成证明

用户将证明发送到合约的 withdraw() 函数 这里

• 合约检查该 nullifier 哈希是否先前未被使用 这里
• 合约使用 (verifyProof() 函数) 验证证明
• 合约执行取款（包括费用并固定“已使用” nullifier）

现在，让我们看看 这里 的证明电路。主要的私密信号是：nullifier、secret、pathElements[levels] 和 pathIndices[levels]。最后两个参数是 Merkle 证明，它在电路的 这个 部分进行验证（与我们之前示例中的顺序哈希相同）。

这个电路中有一个安全重要的部分 这里，我们看到奇怪的“未使用”的内部信号，如 recipientSquare <== recipient * recipient。原因是 recipient、fee、relayer 和 refund 输入信号并未在电路内部进行任何计算，也未被添加到任何约束中。没有这些约束，输入信号 recipient、fee、relayer 和 refund 将不会用于证明生成。它将导致只有一个见证（内部没有这些值）对应多个可能的输入，同时允许客户端攻击者在不使用这些值的情况下复用同一见证。

这个附加只包括 4 个约束，并使见证“绑定”到输入值，从而减轻未使用值的篡改。平方操作的使用是为了保证在电路中添加约束（如果是简单的内部 recipientSignal <== recipient 的优化器可以排除这个无用的约束）。

在此版本的 Tornado 中，我们看到了“仅添加” Merkle 树，每次承诺后生成一个新的 Merkle 根，而以前的根在根历史中向后推移。为了构建证明，你需要树的所有叶子；在 Tornado 中，它们可以从合同中的所有过去事件重建（请见 这里）。树叶的每个所有者都可以根据历史重建整个树并返回他们的存款。对于大量叶子而言，这似乎效率较低，但你可以部署任何数量的新验证合约实例，并在树变得过大时切换到新实例，从而解决树容量的问题。最重要的是，实例是无信任的，可以轻松部署任意数量。基于集合成员证明构建混合器的想法十分明显，因为“参与/排除的支付”是大多数区块链应用程序的“自然”方式，且 Tornado 完全证明了它在生产中可以运行。

如果你仅改变数字和名称，Tornado 可以轻松转换为一个售票服务，保持访客的个人数据，或非互动的一次性登录，这一方案非常实用。让我们移动到下一个示例。

集合成员证明，Semaphore

集合成员使用的另一个示例是 Semaphore 项目，允许证明组成员身份以及组成员在组内保密地投票的能力。该过程由清晰而简洁的智能合约管理，这些合约易于阅读。你可以在 这里 阅读与组相关的整个合约逻辑，在那里我们可以找到函数 verifyProof() - 与之前的验证非常相似，同时固定 nullifier（以防止其再次使用）。Semaphore 还使用在 这个 npm 包中实现的增量 Merkle 树，其中你可以使用包含一些开发有用特征的实现。

第一个特性是你可以为创建的树传递自己的哈希函数 这里。当你想在电路中尝试不同的哈希类型时，这很有用。我们看到 Semaphore 为它的树使用了 Poseidon 哈希 这里。

此树的第二个特性是能够设置子节点数量 - 每个节点的子节点数量。这在构建 Merkle 树时是需要的，例如，每个节点拥有五个子节点（五叉 Merkle 树）。它减少了级别数量，有助于更快地生成证明，减小证明大小并提升容量（以此换取 gas 消耗）。在 这篇 文章中，你可以了解到 MiMC、Pedersen 和 Poseidon 在 gas 消耗、树的容量及证明生成效率方面的比较。

接下来，让我们来看一下 Semaphore 的电路 这里。它看起来与 Tornado 类似，我们还可以提到与 Tornado 的相同 部分 以防止信号哈希的篡改。

椭圆曲线、密钥所有权和签名证明

几乎每个 zkSNARKs 实际任务的第二个重要部分是证明私钥所有权和签名验证。任何对以太坊智能合约的调用都包含交易的签名者（tx.origin），无需证明该地址的所有权。但是，基于 ZK 的验证凭证协议的核心是能够公开将某些“隐藏”的地址添加到列表中，并使其拥有者能够在以后的时间证明他们拥有该地址。为完成这项任务，我们需要有与给定公钥（或 ETH 地址）对应的私钥的知识证明。

为了更具实用性，让我们研究以太坊地址的特定证明系统变体。如我们所知，ETH 地址是 keccak256(public_key) 的最后 20 个字节，因此我们需要证明我们知道转化为公输出（ETH 地址）的私密信号（私钥）。以太坊使用 secp256k1 椭圆曲线（与比特币相同），与电路中的哈希类似，因有许多乘法、域大小、对曲线上的点的不同运算，这条曲线并不友好于 SNARK。但在这种情况下我们没有选择，我们确实需要这些证明。让我们看看它是如何在同一 circom-ecdsa 仓库 中实现的。

首先，让我们证明我们拥有某个 ETH 地址。可以通过 eth_addr.circom 来实现。首先，我们看到私钥到公钥的转换使用 secp256k 数学的 ECDSAPrivToPub 电路。在这个电路中，我们看到的 Num2Bits 操作 这里 和处理“为零”条件逻辑分支 这里。然后我们看到从公钥到 ETH 地址的转换使用 Keccak 这里。看起来这些不会是轻量级证明，让我们检查一下。

你可以克隆 circom-ecdsa，分析 build_eth_addr.sh 脚本，提到 input_eth_addr.json 包含我们的私钥（分为4x64位块）并运行

cd scripts/eth_addr
## 复制或下载 powersOfTau28_hez_final_${POWERTAU}.ptau 到 ../../circuits/pot20_final.ptau
sh ./build_eth_addr.sh

我在一台强大的机器上运行了这个脚本，POWERTAU=21，并得到：

...
非线性约束：247380
...
****为示例输入生成见证****
完成（9秒）
...
****为示例输入生成证明****
完成（5秒）
...

以及证明密钥的大小：

172M ../../build/eth_addr/eth_addr.zkey

你可以在 0xPARC（circom-ecdsa 仓库的创建者）第一篇文章中找到实现函数的基本描述 这里。此外，你还可以在这里找到第一个基准测试，并将首次版本的约束数量（416 883）与当前值（247 380）进行比较。数学优化可以帮到你很多，因此，为了构建 SNARKs，你需要跟上最新的方法，将电路替换为更优化的版本。对于椭圆曲线，有许多不同的优化。你可以在 “zk-ECDSA 第 2 部分：内部工作” 文章 中阅读相关内容。

从 circom-ecdsa 电路中学习到的另一个重要点是签名检查的难度。如上文文章所述，签名验证需要模乘 + 逆运算（如 这里 所示），椭圆曲线按标量乘法和曲线点加法（当然还包括哈希消息的 Keccak）。因此，这个电路比“私钥到公钥”的电路要重得多，需要更多的约束。

正如你所见，secp256k1 曲线、其签名和 Keccak 哈希并不是非常 SNARK 友好的算法，即便通过所有优化，直接使用以太坊地址、私钥和签名对证明者来说也是极为沉重的。

为了避免这一瓶颈，SNARK 研究人员提出了其他算法，例如一些新椭圆曲线，需要显著较少的约束，从而能够实现更轻量的签名检查和密钥所有权证明。这是关于不同曲线及其在电路中的使用的长篇故事，这些主题将使我们的文章深入理论，所以我们不妨至少呈现一个 SNARK 友好优化的示例。

一个很好的例子是 Baby JubJub 曲线，在 EIP-2494 中进行了描述。它是一种“扭曲爱德华曲线”（文章），允许使用带有一些有用属性的 EdDSA 算法进行签名。例如，它允许对点的相加和翻倍使用相同的运算（BabyAdd 和 BabyDbl）。这比在 secp256k1 曲线中做同样的操作要简单得多（不等点的点相加在 这里 和点翻倍在 这里）。

让我们看看可以用“椭圆原生” SNARK 友好的算法（如 Baby JubJub）构建的内容。

ZK 投票

投票是零知识协议的关键应用之一。它存在许多问题：投票的隐私性、结果的可验证性、抵制选票收买等。这些协议的整体透明性和可验证性是一个非常复杂的任务，目前尚未完全解决。只有一些非常接近最终解决方案的接近方法，但整个问题集仍未得到解决。曾有许多尝试实施真正可用的安全投票，例如使用同态方案（简单 文章），但基于 SNARK 的方案灵活性更大，因为它们提供了将多个机制组合在单个证明中的手段。我们的例子将是 Vocdoni zk 投票证明概念，该概念在 Aragon 项目博客中被 介绍。强烈建议阅读这篇文章。在这种情况下，该团队试图实现：

• “身份和选票混淆” - 混淆和隐瞒选民的身份，同时也计划混淆投票本身
• “抗胁迫性” - 在选票投递后，结果揭晓后，即使选民也无法证明他投了“赞成”或“反对”，只能证明他们投票的事实及其票数被正确计算
• “无回执性” - 移除“一个选票” = “一个回执（交易）”之间的关系。这确实难以避免。选民与其选票之间的任何关系都必须被打破，同时保持投票结果的公开可验证性。计划通过中间中继、“混淆器”组合多张选票来实现，合并在一包中的选票使其不可区分。

接下来，进入实现阶段。首先，阅读有关实现的技术方面的内容 这里。我们看到许多与此相关的逻辑：我们需要以太坊存储证明、选民的预注册，还有围绕投票的整个生态系统（单独链、聚合投票、在以太坊上提交投票）。这一切都是为了保持上述所有安全限制，所以要做好准备 - 你的项目中的背景逻辑量也可能相当庞大。对于我们来说，最重要的部分是电路和证明系统，因此让我们将注意力集中在它们身上。

首先，我们提到检查以太坊存储证明的效率不高（我们需要带有 Keccak256 哈希的证明，而这些太过庞大），也不能直接使用 secp256k1 曲线签名（它们也过于庞大）。因此，该电路使用 Baby JubJub 曲线、在此曲线上用于签名的 Pedersen 哈希，以及用于承诺的 Poseidon 哈希。为了能够利用非 secp256k1 曲线，Vocdoni 使用了一个合同，持有 ETH 地址与对应 Baby JubJub 公钥的映射。这允许在投票之前设置所有选民及其私有 Baby JubJub 公钥。

其次：在当前方案中，当选民发送选票时，投票本身是一个公共信号，但选民的身份是隐藏的。正如所说：“任何人都可以验证任何投票都是由合格的选民唯一投出的”，但无法重建这张选票属于谁。未来计划隐藏投票，但目前投票值本身是公开的。

让我们看看提议的电路的输入信号（来自 这里）：

我们提供这些值给见证生成器：

公共的“人口普查根”和公共的“选举 ID”

• Merkle 根用于“已使用/未使用”选票 + 选举 ID 用于识别当前投票

私有的“Merkle 证明”

• 证明当前投票包括在 Merkle 树中

公共的“投票” + 私有的“私钥”和“投票签名”

• 正在添加到 Merkle 树中的已签名投票（使用 Baby JubJub 进行签名）

公共的“nullifier”

• 作为 hash(私钥, 选举 ID) 构建的值，允许用户跟踪他们的投票并拒绝重复投票

或以下这些值

私有的“揭示密钥”和公共的“承诺密钥”

• “承诺密钥”及其对应的哈希，所有这些在投票结束时将被揭示。

请注意最后一部分，承诺-揭示密钥由“投票矿工”提供。任何人知道所有揭示密钥都可以为投票生成有效证明。如果有人“买”了我的投票，并要求证明我已经投了“赞成”，任何人（包括我）都可以提供“赞成”、“反对”或任何其他正确证明，从而使投票证明在选举后变得毫无意义。当然，投票可以通过“买下私钥”和所有私人数据的方式进行，但这在购买者投票的情况下也是相同的。这也是该协议的一个薄弱环节，因为如果所有矿工都勾结以篡改投票结果并向某人透露所有揭示密钥，则他们可以篡改投票（但即使其中一个诚实，并在选举结束之前将揭示密钥保留为秘密 - 他们也无法做到）。

你可以使用这样的“或”证明使证明在使用后变得无效。在 ZK 中，“无法揭示私人值”有时会转变为奇怪的“任何人都可以揭示并证明任何值” :)

在这里，我们将研究没有“承诺-揭示”输入部分的概念验证电路（仅投票部分）。

我找到 这里 的电路代码。让我们来看一下重要的点：

人口普查电路，输入信号 这里。我们看到：

公共信号：processId[2]、censusRoot、nullifier、votingWeight 和 voteHash[2]

• 我们公示：选举 ID、其 Merkle 根、nullifier、我们的投票“权重”和我们的投票

私有信号：factoryWeight、censusSiblings[realNLevels]、privateKey

• 我们将相关的最大投票权（factoryWeight）、为我们的 nullifier 包含在 Merkle 树中的 Merkle 证明（censusSiblings[realNLevels]）和 Baby JubJub 私钥保持为私有。

代码中的下一个停止点是检查我们的投票权重是否小于工厂权重时，我们遇到子电路 LessEqThan。在 circomlib 的 comparators.circom 中使用的 LessThan 这里 允许执行所谓的“范围证明”。我们看到的 Num2Bits 转换包含至少“位数”的约束和信号，因为为了比较曲线上的两个数字，我们不能简单“相减”，因为在曲线上加法的结果可能会导致 c = a + b 从我们的普通二进制角度来说小于 a 或 b，并且没有其他方法，只能分析位。因此，在 zkSNARKs 电路中进行范围证明的成本很高，因其添加了大量约束，特别是在与不同位长度结合使用时，作为电路中不可优化的组成部分等。同时，出于业务逻辑和安全目的，它们是不可避免的，因为在域算术中没有“溢出”，完全不同的值（二进制）可以在域中“相等”。

接下来：Baby JubJub 私钥 -> 公钥 的转换在 这里 ，然后用 Poseidon 进行哈希 这里。电路的这一简单部分展示了SNARK友好算法的有效性 - Baby JubJub 需要很少的约束（归功于优化的乘法），Poseidon 使用信号且无需进行位转换。这些选择都显著减少了见证的大小和证明生成时间。

接下来：ZkAddress 电路在 这里 （代码在同一文件的上面）。在这里，Baby JubJub 公钥的 Poseidon 哈希被减少到 20 字节（生成 Vocodni 地址，该地址为 20 字节长）。这需要 Num2Bits 和 Bits2Num 子电路，增加了一组额外的约束（用于输出的位<->num）。在这里没有选择，但如果可能的话，最好避免位扩展和减少（这有时可能导致较低的密码安全级别）。

下一个：Merkle 树，以及 Merkle 证明的验证器在 这里。这里，我们使用的是稀疏 Merkle 树 - 其实现 在这里。这个树的优化技巧是该设计将新值“从左到右”添加（新的值添加到下一个“空闲”的索引），使得在右侧具有“稀疏”树（大多数右侧分支为空且包含零），而左侧的“浓缩”分支则有实体值。关于这些想法的描述和讨论在 这里（简短版本在 这里）。现在，利用这一原语我们可以有效地创建包含/排除（INSERT/UPDATE/DELETE）的证明。在当前电路中：我们通过设置 smtClaimExists.fnc <== 0 在 这里 检查包含证明（smtClaimExists.fnc <== 1 用于排除证明），并证明树中的前一个值为零，详见 这里。

最后，nullifier 的检查在 这里：它必须等于由 processId[2] 和 privateKey 生成的哈希。

你可以执行所有步骤来玩弄所提出的概念证明，我只是编译了 census.circom 电路，并收到了大约 40k 的约束，用于 Merkle 树中的 160 层（与来自 第一篇 文章的单个 Keccak 哈希 ~150k 约束进行比较）。我们使用了私有到公有的转换，验证了 Merkle 证明，哈希了一些中间信号——这一切仅仅产生了 40k 约束，从而节省了见证大小和用户的证明生成时间。当然，要成为一个真正的应用程序，还需要添加许多东西：电路的第二部分与提交-揭示密钥、客户端软件、 preparing 证明、管理合约——这些对投票系统都是重要的。但是，核心的 zk 部分似乎足够可用，能够成为一个好的解决方案。

使用 Vocdoni 的完整投票周期的描述在这个 视频 中展示，并在 这里 描述。

结论

在本文中，我们回顾了一些适合 SNARK 的算法，它们在实际项目中的使用，并展示了它们确实可以帮助构建在现实生活中运行的项目。正如我之前所说，这个领域仍在积极研究中，所有使用的算法不能被视为像 Keccak 或 secp256k1 等经过批准的国际标准那样 100% 安全。这就是为什么知名区块链不会很快切换到这些算法；他们在等待这些算法完全被密码学家接受。但是，如果某些区块链的内部完全基于 SNARK 友好的原语，其地址、密钥、哈希可以直接传递到有效电路中，那么这样的系统可以广泛用于任何 zk 目的。目前已经有许多项目关注这些问题，我们将在后续文章中讨论它们。

此外，我们希望向在大学和初创企业中从事该领域研究的学术研究人员表示由衷的敬意。因为我们都需要安全有效的算法，这一点至关重要。然而，与此同时，我们也理解，全球密码学界的接受不能很快。如果你对密码学中的科学工作感兴趣，也许你会想加入他们——这是计算机科学中真正的“顶尖”技术。

在下一篇文章中，我们将更深入地研究其他证明系统（我们在大多数示例中使用了 Groth16）、STARKs，探讨不同的设定要求、证明-验证成本，同时也将研究新的用例。再见…

• MixBytes 是谁？

MixBytes 是一个专注于为 EVM 兼容和 Substrate 基础项目提供全面智能合约审计和技术顾问服务的区块链审计师和安全研究专家团队。加入我们，在 X 上保持关注最新行业趋势和见解。

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