zkSNARKS，Circom（第一部分）

mixbytes
发布于 2023-04-25 12:42
阅读 32

本文深入探讨了 zkSNARKs 技术的基本概念、原理及在 Circom 中的实现，逐步引导读者从最基础的电路构建入门到实际应用，包括加密验算的证明过程。作者通过示例代码和详细步骤，帮助开发者理解如何有效地使用这个技术。文章结构清晰，内容丰富，适合希望深入学习 zkSNARKs 的读者。

## zkSNARKS, Circom （第一部分）

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

![](https://img.learnblockchain.cn/2025/03/09/39.jpg)

## 简介

zkSNARKs和证明系统是一项非常有趣的技术。但就像任何年轻技术一样，缺乏文章和最佳实践。大多数文献都是对zkSNARKs技术的简化解释，或者是高度专业化的文章和研究，直到你动手尝试工作之前很难理解。本文系列的目的就是填补这一普通知识和专业知识之间的空白，使你能够从“你好，世界”开始，逐步走向你的第一个电路，准备你自己的代码库，并处理zkSNARKs开发中常见的问题。

如果你还没有阅读过，请首先在[这里](https://docs.circom.io/background/background/)阅读简单的基础知识。你应该了解一些类似于以下的内容：

- “我有一些私有数据，当通过该算法处理时，产生这个公共输出”
  - “我知道这样的输入信号，当通过电路处理时，产生这个输出信号”
    - “我可以提供一个证明，由有效信号构成，证明我知道方程约束系统的解决方案”
      - …

简而言之，我有一个“电路”——类似于现实生活中的电子电路，接受一些输入信号，通过不同的逻辑和算术门，并生成一些输出信号。我接受一些输入信号，在电路上进行计算，生成一个“见证”：一组所有对该电路有效的信号。然后，使用这个“见证”，我计算出一个更短的证明。我将这个证明和输入输出的公共部分呈现给验证者。验证者接受公共值和证明，并对这些与电路验证数据（验证密钥）一起进行验证。

值得注意的是，不同证明系统的验证需要一个“设置”，生成当前电路的验证密钥。该验证密钥允许任何拥有该验证密钥的人检查任何有效的输入输出组合的证明（其中一部分可以保持私有）。

这就是“ARK”（知识的论证）部分的“简洁非交互式知识论证”（SNARKs）。

“N”意味着“非交互式”——这是SNARKs的另一个特性。这意味着证明可以在没有任何先前交互的情况下发送给验证者——没有“挑战-响应”协议，没有伪随机的“随机数”、“盐”、“挑战”值（这些在Web2中到处可见，而在区块链中，缺少额外交易是一个关键特性）。所有公共的输入-输出-证明都在一个交易中发送。这是使用SNARKs进行扩展方案时一个超级重要的特性。

“S”（简洁）又如何呢？在某些情况下，验证证明的速度可以比计算见证和证明快很多倍。客户端可以进行超重的计算，例如处理成千上万的用户交易，执行复杂度为O(N)的计算，并生成一个固定大小的单一证明，证明所有状态变化都已正确执行，根据状态转移函数而来。一些证明系统中的验证时间为O(1)！你可以使用一个O(1)的固定大小、固定验证时间的证明来证明O(N)的计算步骤。这是超级“简洁”。

那么，“zk”（零知识）呢？“zk”部分用小写字母书写，因为在我们控制的证明系统中，我们自己决定我们的“可证明”函数是否提供零知识。所有证明逻辑工作得是绝对相似的，无论提供的信号是私有的还是公共的。我们通过设计我们的电路函数，使得私有输入不能从公共信号中计算出来，从而“免费”获得“zk”特性。如果我们证明我们知道a和b，比如c <== a * b，那么如果a和c是公共的，任何人都可以计算b，而这个电路就不是“zk”。但如果我们计算某个c <== hash(a)，那么a可以保持私密。许多加密操作是基于[单向函数](https://en.wikipedia.org/wiki/One-way_function)构建的，我们可以使一些输入保持私密，从而无法从公共数据中重构它们（例如，从公钥推导私钥或从哈希本身推导哈希前图）。

## 神奇的地方在哪里？

如果这些证明系统这么酷，为什么我们不见到它们随处可见？这是因为电路函数的复杂性大大影响了各个阶段所需的计算。开发证明系统的艺术涉及构建生成高效电路的算法组合。这可以为用户提供可靠的验证密钥、证明和生成时间。目前仅有一小部分算法能够有效实施，使用户能够从浏览器和钱包中进行zk交易，而无需使用庞大的多GB大小的密钥，等待几个小时以生成证明，并进行繁重的验证。使用证明系统在L2区块链节点中进行扩展时可以做得更多，“打包”多个状态转移至一个单一的证明，然后“呈现”给L1。潜在地，许多酷东西也可以在传统Web2中完成，但“他们太忙了” :)

让我们看看可以做什么，成本是多少。

## 你好，乘法的世界！

首先，让我们在[这里](https://docs.circom.io/getting-started/writing-circuits/)通过所有基本的“你好，世界”步骤。强烈推荐观看Jordi Baylina的非常有价值的[视频](https://www.youtube.com/watch?v=-9TJa1hVsKA)（对他和Iden3团队表达我们的敬意）。

在编写\*.circom代码时，我们并不编写执行计算的代码。相反，我们编写一个电路生成器，经过生成后，它将允许我们证明在这个电路上的任何计算。我们不编写“计算c = a*b的函数”，而是编写“生成一个程序的代码，计算c <== a*b，并允许证明我们在一些输入上执行了这个程序”。这个过程更像是编写一个宏，而不是可执行代码。

我不会提供Circom文档中的基本指令。相反，我只会提供[运行的命令行](https://docs.circom.io/getting-started/proving-circuits/)。这将帮助你节省重复相同步骤的时间。此外，我已删除一些本文章不需要的选项，并更改了一些操作的顺序。这将确保在电路发展的各个迭代中，公共部分只需执行一次（即，Power Of Tau的第一次生成）。

为了清楚理解下面所有命令的作用，最好查看关于开发流程的另一段信息丰富的[视频](https://youtu.be/fPxhd5aWbqM?t=167)。

让我们开始并执行第一部分，该部分与电路无关（我们不需要对简单电路重复此操作）。

```cpp
## 安装所有先决条件（Rust，circom，snarkjs）
snarkjs powersoftau new bn128 12 pot12_0000.ptau -v
snarkjs powersoftau contribute pot12_0000.ptau pot12_0001.ptau --name="首次贡献" -v
snarkjs powersoftau prepare phase2 pot12_0001.ptau pot12_final.ptau -v
```

在第一行中，我们生成了一个ptau设置文件，POWERTAU=12。tau的作用决定内部多项式的大小并限制电路中的约束最大数量。这影响见证、证明和见证生成代码的大小。对于第一个示例，12已经足够，但后续迭代将需要更多的幂次。

第二行，“contribute”，增加了另一个参与者向ptau文件添加了其熵。此贡献程序允许不仅是电路的创建者，还允许任何其他N个参与者设置证明系统，并且如果N中至少有一个将诚实“遗忘”且不披露其随机熵，则整个证明系统被认为是安全的。在接下来的代码库和脚本中，我们将省略“contribute”阶段，以简化和加快过程，但在生产设置中它们仍然对项目的安全性至关重要。此外，一些证明系统不需要额外的贡献进行设置。

第三行的“phase2”，在所有贡献后最终确定ptau的生成。

现在，依赖于电路的部分（当multiplier2.circom中的代码更改时会重复）：

让我们创建一个Rank1约束系统，将其保存为.r1cs文件并生成.wasm文件，使用户能够计算见证：

```css
circom multiplier2.circom --r1cs --wasm
```

我们生成了multiplier2.r1cs，该文件包含一组方程，该方程应有一个解：使所有约束方程正确的信号组合。证明对此解决方案的知识证明我们实际进行了满足所有约束的计算。

现在，我们转到可信设置的第二部分。首先，我们使用我们的multiplier2.r1cs文件生成multiplier2_0000.zkey。然后，在贡献之后，我们生成最终的.zkey，multiplier2_0001.zkey，这将用于证明。最后，在最后一行中，我们导出verification_key.json（将用于验证）。

```bash
snarkjs groth16 setup multiplier2.r1cs pot12_final.ptau multiplier2_0000.zkey
snarkjs zkey contribute multiplier2_0000.zkey multiplier2_0001.zkey --name="第一贡献者名称" -v
snarkjs zkey export verificationkey multiplier2_0001.zkey verification_key.json
```

仔细阅读设置[文档](https://github.com/iden3/snarkjs#15-setup)是至关重要的，因为Groth16证明系统需要贡献阶段，而Plonk和FFLONK系统则不需要具有贡献的“可信设置”。

所有必要的组件现在就位后，证明和验证过程可以在客户端进行。让我们继续操作multiplier2_js目录。

```sql
cd multiplier2_js

## 创建包含 {"a": "3", "b": "11"} 的 input.json 文件
echo "{\"a\": \"3\", \"b\": \"11\"}" > input.json

## 计算见证，包含所有信号
node generate_witness.js multiplier2.wasm input.json witness.wtns

## 生成证明
snarkjs groth16 prove ../multiplier2_0001.zkey witness.wtns proof.json public.json

## 检查证明！
snarkjs groth16 verify ../verification_key.json public.json proof.json
```

我们在input.json中构造了一些a和b（_a=3, b=11_），然后生成了witness.wtns（包含a、b和c <== a*b信号值），然后使用multiplier2_0001.zkey（在可信设置期间创建的）从witness.wtns中生成了proof.json。

之后，我们将结果值c（在public.json中，这是我们电路中唯一的公共信号）和proof.json呈现给验证过程。然后，拥有verification_key.json的任何人都可以检查，我们有一个具有a、b的证人，使得公共c <== a*b。

你可以通过更改input.json或public.json的内容来测试其他值，检查证明是否合法。但也请记住，电路中的算术运算是在有限域上进行的，过大的值将不会导致溢出。我们稍后会返回探讨这些细节。

## 深入探讨

首先，阅读circom语言[文档](https://docs.circom.io/circom-language/signals/)，因为在电路中许多常见的事情都是不可能的。本文并非对语言的回顾，但一些注释在阐明我们将要讨论的问题时非常重要。

你应该记住，电路有一个已知的操作数量（在编译时确定！），因此不能有未知迭代次数的循环、用“新”信号替代预定义信号等。所有信号只能向前流动，所以任何对同一信号的“第二写入”都是不可能的（信号是不可变的）。此外，电路仅允许信号的二次组合；你可以使s <== a * b + c，但无法使s <== a * b * c + d（记住在[这里](https://docs.circom.io/background/background/#signals-of-a-circuit)中图示的电路一部分的图形模式）。

另一个超级重要的事情是运算符<--和===的含义（当我们写<==时，意味着确切的<---首先，然后是===）。<--从其他信号和变量中生成一个新信号，仅用于计算下一个信号（在生成见证时使用）。而===则添加了一个约束，用于证明此计算（用于构建验证密钥）。缺少对信号计算的约束检查===可能导致你的证明方正确计算见证，但在错误的、特殊设计的数据上，证明检查可以返回“假阳性”结果。详细内容在这个[视频](https://youtu.be/6XxVeBFmIFs?t=1044)中做了更详细的说明。

让我们继续开发我们的下一电路。

## 提升 a*b 计算

我将利用我们的教育代码库[这里](https://github.com/mixbytes/circom-farm)（在Ubuntu 20.04上测试过）来自动化以上所有步骤，做成一个单独的bash脚本，允许我们测量执行时间和生成文件的大小。

主要的run_all.sh [脚本](https://github.com/mixbytes/circom-farm/blob/61ec5aca562ad33dde36455a4439759c52019a88/run_all.sh#L1)接受CIRCUIT_NAME - .circom模板文件的名称，并执行以下操作：

- 从snarkjs [代码库](https://github.com/iden3/snarkjs#7-prepare-phase-2)下载大型“ptau”文件（代替生成）以获得POWERTAU的tau
- 为每次新的运行重新创建一个新的空BUILD_DIR，在这里生成所有的zkeys、wasm、输入和证明
- 编译.circuit
- 执行生成证明的.zkey
- 生成输入
- 生成见证
- 生成证明
- 检查证明
- 输出文件大小、见证生成时间、证明时间、验证时间

这很无聊，但你真的需要类似的自动化，因为在开发期间，你需要检查证明系统的所有参数，比如见证生成时间、证明时间、验证时间、文件大小、约束数量等。包含电路的代码库通常都有类似的脚本（比如[这个](https://github.com/0xPARC/circom-ecdsa/blob/d87eb7068cb35c951187093abe966275c1839ead/scripts/eth_addr/build_eth_addr.sh#L1)），因为盲目开发SNARKs是没有用的。最好学习run_all.sh脚本，找到可以修改的输入、tau值、添加你的额外调试，或者简单地按你想要的方式重写它。在库中，你将找到第一个示例中的multiplier2.circom。你可以通过运行./run_all.sh multiplier2并进行实验。

现在，我们试着证明一个具有更多乘法的计算，比如(a*b)^N。你可以尝试修改之前的multiplier2.circom来实现此功能，在循环中添加累加器变量，并尝试将乘法放入单个“信号累加器”中，就像我们在其他语言中那样，但这将是痛苦的，因为这样的流程无法转换为单向的预定义电路。解决方案是使用固定的N作为电路模板参数，并生成一个固定的N（如“将私有的(a*b)提升到N=32的幂”）的证明系统。

我在powerabn.circom中做了这个（可能是错误的），你可以在[这里](https://github.com/mixbytes/circom-farm/blob/61ec5aca562ad33dde36455a4439759c52019a88/circuits/powerabn.circom#L1)找到它。你可以通过./run_all.sh powerabn运行该示例。

```cpp
powerabn.circom
pragma circom 2.0.0;

template PowerABN(N) {
    signal input a;
    signal input b;

signal output c;

signal d[N + 1];
    signal e[N + 1];

var i = 1;

d[0] <== 1;
    e[0] <== 1;

while (i <= N) {
        d[i] <== a * d[i-1];
        e[i] <== b * e[i-1];
        i++;
    }

c <== d[i-1] * e[i-1];
}

component main = PowerABN(32);
```

让我们首先来看看电路参数。snarkjs info -c powerabn.r1cs的输出向我们展示了：

```cpp
[INFO]  snarkJS: # of Wires: 68
[INFO]  snarkJS: # of Constraints: 63
```

而在之前的乘法示例中multiplier2中是：

multiplier2.circom

```nginx
pragma circom 2.0.0;

template Multiplier2 () {
   signal input a;
   signal input b;
   signal output c;

c <== a * b;
}
component main = Multiplier2();
```

和

```cpp
[INFO]  snarkJS: # of Wires: 4
[INFO]  snarkJS: # of Constraints: 1
```

在multiplier2中，我们取了a和b（2条电线），将其与信号c连接（+1电线）和另外一条（+1电线）用于c的输出，并检查唯一的1个约束时 c <== a * b

在powerabn电路中，我们有66条电线——它是a、b和c（+4电线）以及（+31 * 2）表示内部信号包d[]和e[]（写31次）。而 _31 * 2 + 1 = 63_ 约束（d[]和e[]写入和c的输出）

不要忘记研究snarkjs[选项](https://github.com/iden3/snarkjs#11-view-information-about-the-circuit)，以检查R1CS电路。在某些情况下，你可能需要打印出约束系统的信息，或者至少你应该理解见证的大小，因为每个证明者应该在客户端生成这样的见证。

下一步——让我们增加N并查看我们的电路。在[这里](https://github.com/mixbytes/circom-farm/blob/61ec5aca562ad33dde36455a4439759c52019a88/circuits/powerabn.circom#L25)将powerabn.circom中的N更改为“10000”。如果我们在run_all.sh中使用POWERTAU=12，我们将无法构建电路，因为电路对于这个tau仪式太大。20001 * 2 > 2 **12。在这种情况下，你需要用更多的tau重设证明系统。对于大量约束，第一阶段可能会花费很长时间，即使你下载文件 - 它们非常大。稍后我们需要至少POWERTAU=21来玩加密证明，因此你需要在run_all.sh中设置POWERTAU=21才能继续。之前的电路都可以正常工作，因为它们更小，但加密原语需要较大尺寸的powersoftau*文件。

现在，以N=10000为例，你会发现 *witness.wtns 和 *powerabn.wasm 的大小大大增加：

```cpp
...
非线性约束: 20001
...
[PROFILE] 4.0K build/powerabn_verification_key.json
...
[PROFILE] 见证生成时间: 0:00.03
...
[PROFILE] 证明时间: 0:00.92
...
[PROFILE] 验证时间: 0:00.40
...
[PROFILE] 116K powerabn.wasm
[PROFILE] 628K powerabn_witness.wtns
```

将其与之前的设置N=32进行比较：

```cpp
...
非线性约束: 63
...
[PROFILE] 4.0K build/powerabn_verification_key.json
...
[PROFILE] 见证生成时间: 0:00.02
...
[PROFILE] 证明时间: 0:00.43
...
[PROFILE] 验证时间: 0:00.39
...
[PROFILE] 36K powerabn.wasm
[PROFILE] 4.0K powerabn_witness.wtns
```

而且，现在你可以在powerabn.circom中尝试增加更多的N，例如200000。现在证明-验证的时间是显著的：

```cpp
非线性约束: 400001
...
[PROFILE] 4.0K build/powerabn_verification_key.json
...
[PROFILE] 见证生成时间: 0:00.14
...
[PROFILE] 证明时间: 0:07.55
...
[PROFILE] 验证时间: 0:00.42
...
[PROFILE] 1.6M powerabn.wasm
[PROFILE] 13M powerabn_witness.wtns
```

但你可能已经注意到一行无聊的“始终相同”线，verification_key.json的大小为4.0K，验证时间约为0:00.40s。

我们所有的电路，都有较大的POWERTAU和大量的约束，验证密钥的大小恒定为4Kb，而验证时间也是常量时间！

这就是zkSNARKs的“银弹”。4Kb的大小可以方便地放入智能合约或微服务中，如果验证时间足够小，我们可以无交互地证明大规模计算，仅需在“服务器”端保留几千字节的代码。这使得我们可以利用SNARKs进行大量操作的处理证明，“打包”成单一证明。

但你应该记住，这仅在电路的大小和约束系统不会变得过大时有效。当输出来增加更多的tau、约束和信号时，你可以轻易地获得一个可用的SNARK，但在实际环境中它可能是完全无用的，因为证明过程对客户端来说实在是太过繁重。有效设计电路，保持所有这些事情的平衡是组合实用证明系统的核心。

## 走向实践 - 哈希

哪些算法具备构建真正有用电路的特性？数学很好，但加密操作更好。电路中的数学受到有限字段的限制，并需要对常见算法进行适应才能在电路中使用。许多加密算法在有限字段上操作，使用场域乘法，允许单向转换（对于ZK极其有用），并允许创建有效的固定大小电路。这就是为什么存在许多与加密相关电路的原因，以及使用SNARKs的广泛计算缺乏。

我们将尝试使用keccak哈希，并尝试对某个输入进行N次哈希。我从这个[代码库](https://github.com/0xPARC/circom-ecdsa)（一个允许证明不同加密操作的电路库）中借用了keccak哈希电路的实现（只是复制了所有需要的文件并通过npm install将circomlib添加到依赖项中）。我们稍后将多次返回。

查看一下[keccak.circom](https://github.com/0xPARC/circom-ecdsa/blob/d87eb7068cb35c951187093abe966275c1839ead/circuits/vocdoni-keccak/keccak.circom#L65)模板及在C中的[实现](https://github.com/davidsteinsland/keccak/blob/86a0f91eced1c72c75249de504f577a5f63268c9/keccak.c#L159)（例如“吸收”阶段）。它们是相似的，因为哈希和对称加密算法从设计上看都是“电路”，对有限位集合进行多次相同操作。让我们证明某些内容的哈希。

让我们看看：

```css
keccakn.circom
```

```cpp
pragma circom 2.0.0;

include "vocdoni-keccak/keccak.circom";
include "../node_modules/circomlib/circuits/bitify.circom";

template KeccakN(N) {
    signal input a;
    signal keccak_in[256];
    signal keccak_out[256];
    signal output out;

component toNBits = Num2Bits(256); // (1)
    component fromNBits = Bits2Num(256);

// 需要构建N个keccak电路以执行N次哈希
    component keccak[N];

toNBits.in <== a;

var i;
    keccak[0] = Keccak(256,256);
    for (i=0; i<256; i++) {
        keccak[0].in[i] <== toNBits.out[i];
    }

var j;
    for (j=1; j<N; j++) {  // (2)
        keccak[j] = Keccak(256,256); // (3)
        for (i=0; i<256; i++) {
            keccak[j].in[i] <== keccak[j-1].out[i];
        }
    }

for (i=0; i<256; i++) {
        fromNBits.in[i] <== keccak[j-1].out[i];
    }
    out <== fromNBits.out;
}

component main = KeccakN(1); // (4)
```

我们在(1)处看到了非常有用的基本电路Num2Bits()和Bits2Num()，它们允许我们将信号值转换为位数组。然后，我们初始化第一个keccak电路 keccak[0] = Keccak(256,256)；稍后，在(2)中，我们添加了N-1个额外的keccak电路，将前一个电路的输出传递到下一个。keccak电路的输入为位，每次重用keccak都需要添加256个新信号和约束。

你可以使用./run_all.sh keccakn（并设置POWERTAU=21）运行它。注意即使对于N == 1，这个电路也很大（单个操作需要151k约束和较大的见证大小）：

```cpp
非线性约束: 151104
...
[PROFILE] 4.0K ../keccakn_verification_key.json
...
[PROFILE] 见证生成时间: 0:00.23
...
[PROFILE] 证明时间: 0:02.65
...
[PROFILE] 验证时间: 0:00.42
...
[PROFILE] 844K keccakn.wasm
[PROFILE] 4.7M keccakn_witness.wtns
```

使用N==16，你将收到电路对于此tau仪式太大。2413824 * 2 > 2 ** 21，让我们尝试N==8：

```cpp
...
非线性约束: 1207040
...
[PROFILE] 4.0K ../keccakn_verification_key.json
...
[PROFILE] 见证生成时间: 0:01.80
...
[PROFILE] 证明时间: 0:19.26
...
[PROFILE] 验证时间: 0:00.41
...
[PROFILE] 4.9M keccakn.wasm
[PROFILE] 37M keccakn_witness.wtns
```

在这里，我们有一个更长的证明时间，巨大的见证大小，以及大的keccakn.wasm大小。所有这些都会影响客户端，而客户端的能力远不如我们的服务器。

我选择keccak256算法来演示在证明系统中直接使用现有加密算法有多棘手。我们构建了一个证明系统，允许用户证明他对于某个哈希或“哈希的洋葱具有N层”存在一个前象。这一证明非常有用，允许你证明你确实拥有带有这个哈希的数据。但为了进一步前进，我们需要进行更多的顺序哈希迭代的电路，因为“在这就是梅克尔树”。

## （稀疏）梅克尔树

你应该知道梅克尔树是什么（否则最好选择另一篇文章）。当我们拥有一些2^N元素的列表时，梅克尔证明的大小为N，而检查梅克尔证明正好是顺序哈希（当我们上升到梅克尔根）。我们实现了一个有N个顺序keccak哈希的电路，但使用我们较小的N=8的树仅允许256个叶子。

这就是为什么现代zkSNARKs使用哈希函数，它们的乘法更少，操作于有限字段，但仍然是安全的。一个例子：MiMC哈希函数，专为SNARKs而设计（见[文章](https://eprint.iacr.org/2016/492.pdf)）。让我们尝试用MiMC重复N次哈希（可以使用./run_all.sh mimcn运行）：

```cpp
mimcn.circom
pragma circom 2.0.0;

include "../node_modules/circomlib/circuits/bitify.circom";
include "../node_modules/circomlib/circuits/mimc.circom";

template MiMCN(N) {
    signal input a;
    signal output out;

component mimc[N];

var k = 1;
    mimc[0] = MiMC7(91); // 轮数
    mimc[0].x_in <== a;
    mimc[0].k <== k;

var j;
    for (j=1; j<N; j++) {
        mimc[j] = MiMC7(91);
        mimc[j].x_in <== mimc[j-1].out;
        mimc[j].k <== k;
    }

out <== mimc[j-1].out;
}

component main = MiMCN(256);
```

我们使用N=256进行哈希迭代，拥有：

```cpp
非线性约束: 93184
...
[PROFILE] 4.0K ../mimcn_verification_key.json
...
[PROFILE] 见证生成时间: 0:00.06
...
[PROFILE] 证明时间: 0:02.24
...
[PROFILE] 验证时间: 0:00.42
...
[PROFILE] 408K mimcn.wasm
[PROFILE] 2.9M mimcn_witness.wtns
```

这确实好得多！一个带有 _2^256_ 叶子的梅克尔树比一个带有 _2^8_ 叶子的树要好得多，而客户端的所有参数似乎都能应付。

还有几种对SNARK友好的加密原语，我们将在接下来的文章中讨论它们。

在使用Keccak和MiMC顺序哈希时，我们发现了现代SNARKs中最常见的模式——“成员资格证明”。通过一组值（这些值可能是私有的），我们可以证明某个元素属于由单个梅克尔根定义的列表。通过使用“稀疏梅克尔树”的模式，我们还可以有效地进行包含和排除证明。

该方案允许构建架构，服务器仅保留一个超级紧凑、固定大小的数据——梅克尔根 + 验证密钥，而全部数据和证明逻辑则存在于客户端。证明私有事实，例如“我的地址在列表中”，“我已将我的地址添加到列表中”或“我从列表中删除了我的地址”，使得创建投票、经过验证的凭证、链上混合器和其他超可扩展、固定大小的用户服务成为可能。

## 结论

不幸的是，客户端的复杂性依然是一个大问题。即使在智能合约端有有效的验证者，客户端在证明复杂内容时所需的计算过程依然过于艰巨。这就是为什么SNARKs现在被广泛用于构建L2解决方案，因为L2节点拥有足够的资源为大型操作包计算证明。纯“在浏览器中”的zk-证明也已在生产中存在。一个很好的例子是Tornado.Cash，它使用适合真实用户任务的证明，从浏览器中运行。

在[下一篇“第二部分”文章](https://learnblockchain.cn/article/12476)中，我们将继续研究更多的加密电路及其在实际应用中的用法。

P.S. 在玩Circom时不要忘记一件重要的事情——不要用“cirquit”来替代“circuit” :)

- 谁是MixBytes？

[MixBytes](https://mixbytes.io/) 是一个区块链审计和安全研究专家团队，专注于为EVM兼容和基于Substrate的项目提供全面的智能合约审计和技术咨询服务。请关注我们在[X](https://twitter.com/MixBytes)上的最新行业趋势与见解。

>- 原文链接： [mixbytes.io/blog/zksnark...](https://mixbytes.io/blog/zksnarks-circom-and-go-practice-part-1)
>- 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

zkSNARKS, Circom （第一部分）

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

简介

如果你还没有阅读过，请首先在这里阅读简单的基础知识。你应该了解一些类似于以下的内容：

“我有一些私有数据，当通过该算法处理时，产生这个公共输出”
- “我知道这样的输入信号，当通过电路处理时，产生这个输出信号”
- “我可以提供一个证明，由有效信号构成，证明我知道方程约束系统的解决方案”
  - …

这就是“ARK”（知识的论证）部分的“简洁非交互式知识论证”（SNARKs）。

那么，“zk”（零知识）呢？“zk”部分用小写字母书写，因为在我们控制的证明系统中，我们自己决定我们的“可证明”函数是否提供零知识。所有证明逻辑工作得是绝对相似的，无论提供的信号是私有的还是公共的。我们通过设计我们的电路函数，使得私有输入不能从公共信号中计算出来，从而“免费”获得“zk”特性。如果我们证明我们知道a和b，比如c <== a * b，那么如果a和c是公共的，任何人都可以计算b，而这个电路就不是“zk”。但如果我们计算某个c <== hash(a)，那么a可以保持私密。许多加密操作是基于单向函数构建的，我们可以使一些输入保持私密，从而无法从公共数据中重构它们（例如，从公钥推导私钥或从哈希本身推导哈希前图）。

神奇的地方在哪里？

让我们看看可以做什么，成本是多少。

你好，乘法的世界！

首先，让我们在这里通过所有基本的“你好，世界”步骤。强烈推荐观看Jordi Baylina的非常有价值的视频（对他和Iden3团队表达我们的敬意）。

在编写*.circom代码时，我们并不编写执行计算的代码。相反，我们编写一个电路生成器，经过生成后，它将允许我们证明在这个电路上的任何计算。我们不编写“计算c = ab的函数”，而是编写“生成一个程序的代码，计算c <== ab，并允许证明我们在一些输入上执行了这个程序”。这个过程更像是编写一个宏，而不是可执行代码。

我不会提供Circom文档中的基本指令。相反，我只会提供运行的命令行。这将帮助你节省重复相同步骤的时间。此外，我已删除一些本文章不需要的选项，并更改了一些操作的顺序。这将确保在电路发展的各个迭代中，公共部分只需执行一次（即，Power Of Tau的第一次生成）。

为了清楚理解下面所有命令的作用，最好查看关于开发流程的另一段信息丰富的视频。

让我们开始并执行第一部分，该部分与电路无关（我们不需要对简单电路重复此操作）。

## 安装所有先决条件（Rust，circom，snarkjs）
snarkjs powersoftau new bn128 12 pot12_0000.ptau -v
snarkjs powersoftau contribute pot12_0000.ptau pot12_0001.ptau --name="首次贡献" -v
snarkjs powersoftau prepare phase2 pot12_0001.ptau pot12_final.ptau -v

第三行的“phase2”，在所有贡献后最终确定ptau的生成。

现在，依赖于电路的部分（当multiplier2.circom中的代码更改时会重复）：

让我们创建一个Rank1约束系统，将其保存为.r1cs文件并生成.wasm文件，使用户能够计算见证：

circom multiplier2.circom --r1cs --wasm

snarkjs groth16 setup multiplier2.r1cs pot12_final.ptau multiplier2_0000.zkey
snarkjs zkey contribute multiplier2_0000.zkey multiplier2_0001.zkey --name="第一贡献者名称" -v
snarkjs zkey export verificationkey multiplier2_0001.zkey verification_key.json

仔细阅读设置文档是至关重要的，因为Groth16证明系统需要贡献阶段，而Plonk和FFLONK系统则不需要具有贡献的“可信设置”。

所有必要的组件现在就位后，证明和验证过程可以在客户端进行。让我们继续操作multiplier2_js目录。

cd multiplier2_js

## 创建包含 {"a": "3", "b": "11"} 的 input.json 文件
echo "{\"a\": \"3\", \"b\": \"11\"}" > input.json

## 计算见证，包含所有信号
node generate_witness.js multiplier2.wasm input.json witness.wtns

## 生成证明
snarkjs groth16 prove ../multiplier2_0001.zkey witness.wtns proof.json public.json

## 检查证明！
snarkjs groth16 verify ../verification_key.json public.json proof.json

我们在input.json中构造了一些a和b（a=3, b=11），然后生成了witness.wtns（包含a、b和c <== a*b信号值），然后使用multiplier2_0001.zkey（在可信设置期间创建的）从witness.wtns中生成了proof.json。

深入探讨

首先，阅读circom语言文档，因为在电路中许多常见的事情都是不可能的。本文并非对语言的回顾，但一些注释在阐明我们将要讨论的问题时非常重要。

你应该记住，电路有一个已知的操作数量（在编译时确定！），因此不能有未知迭代次数的循环、用“新”信号替代预定义信号等。所有信号只能向前流动，所以任何对同一信号的“第二写入”都是不可能的（信号是不可变的）。此外，电路仅允许信号的二次组合；你可以使s <== a b + c，但无法使s <== a b * c + d（记住在这里中图示的电路一部分的图形模式）。

让我们继续开发我们的下一电路。

提升 a*b 计算

我将利用我们的教育代码库这里（在Ubuntu 20.04上测试过）来自动化以上所有步骤，做成一个单独的bash脚本，允许我们测量执行时间和生成文件的大小。

主要的run_all.sh 脚本接受CIRCUIT_NAME - .circom模板文件的名称，并执行以下操作：

从snarkjs 代码库下载大型“ptau”文件（代替生成）以获得POWERTAU的tau
为每次新的运行重新创建一个新的空BUILD_DIR，在这里生成所有的zkeys、wasm、输入和证明
编译.circuit
执行生成证明的.zkey
生成输入
生成见证
生成证明
检查证明
输出文件大小、见证生成时间、证明时间、验证时间

这很无聊，但你真的需要类似的自动化，因为在开发期间，你需要检查证明系统的所有参数，比如见证生成时间、证明时间、验证时间、文件大小、约束数量等。包含电路的代码库通常都有类似的脚本（比如这个），因为盲目开发SNARKs是没有用的。最好学习run_all.sh脚本，找到可以修改的输入、tau值、添加你的额外调试，或者简单地按你想要的方式重写它。在库中，你将找到第一个示例中的multiplier2.circom。你可以通过运行./run_all.sh multiplier2并进行实验。

现在，我们试着证明一个具有更多乘法的计算，比如(ab)^N。你可以尝试修改之前的multiplier2.circom来实现此功能，在循环中添加累加器变量，并尝试将乘法放入单个“信号累加器”中，就像我们在其他语言中那样，但这将是痛苦的，因为这样的流程无法转换为单向的预定义电路。解决方案是使用固定的N作为电路模板参数，并生成一个固定的N（如“将私有的(ab)提升到N=32的幂”）的证明系统。

我在powerabn.circom中做了这个（可能是错误的），你可以在这里找到它。你可以通过./run_all.sh powerabn运行该示例。

powerabn.circom
pragma circom 2.0.0;

template PowerABN(N) {
    signal input a;
    signal input b;

    signal output c;

    signal d[N + 1];
    signal e[N + 1];

    var i = 1;

    d[0] &lt;== 1;
    e[0] &lt;== 1;

    while (i &lt;= N) {
        d[i] &lt;== a * d[i-1];
        e[i] &lt;== b * e[i-1];
        i++;
    }

    c &lt;== d[i-1] * e[i-1];
}

component main = PowerABN(32);

让我们首先来看看电路参数。snarkjs info -c powerabn.r1cs的输出向我们展示了：

[INFO]  snarkJS: # of Wires: 68
[INFO]  snarkJS: # of Constraints: 63

而在之前的乘法示例中multiplier2中是：

multiplier2.circom

pragma circom 2.0.0;

template Multiplier2 () {
   signal input a;
   signal input b;
   signal output c;

   c &lt;== a * b;
}
component main = Multiplier2();

和

[INFO]  snarkJS: # of Wires: 4
[INFO]  snarkJS: # of Constraints: 1

在multiplier2中，我们取了a和b（2条电线），将其与信号c连接（+1电线）和另外一条（+1电线）用于c的输出，并检查唯一的1个约束时 c <== a * b

在powerabn电路中，我们有66条电线——它是a、b和c（+4电线）以及（+31 2）表示内部信号包d[]和e[]（写31次）。而 _31 2 + 1 = 63_ 约束（d[]和e[]写入和c的输出）

不要忘记研究snarkjs选项，以检查R1CS电路。在某些情况下，你可能需要打印出约束系统的信息，或者至少你应该理解见证的大小，因为每个证明者应该在客户端生成这样的见证。

下一步——让我们增加N并查看我们的电路。在这里将powerabn.circom中的N更改为“10000”。如果我们在run_all.sh中使用POWERTAU=12，我们将无法构建电路，因为电路对于这个tau仪式太大。20001 * 2 > 2 *12。在这种情况下，你需要用更多的tau重设证明系统。对于大量约束，第一阶段可能会花费很长时间，即使你下载文件 - 它们非常大。稍后我们需要至少POWERTAU=21来玩加密证明，因此你需要在run_all.sh中设置POWERTAU=21才能继续。之前的电路都可以正常工作，因为它们更小，但加密原语需要较大尺寸的powersoftau文件。

现在，以N=10000为例，你会发现 witness.wtns 和 powerabn.wasm 的大小大大增加：

...
非线性约束: 20001
...
[PROFILE] 4.0K build/powerabn_verification_key.json
...
[PROFILE] 见证生成时间: 0:00.03
...
[PROFILE] 证明时间: 0:00.92
...
[PROFILE] 验证时间: 0:00.40
...
[PROFILE] 116K powerabn.wasm
[PROFILE] 628K powerabn_witness.wtns

将其与之前的设置N=32进行比较：

...
非线性约束: 63
...
[PROFILE] 4.0K build/powerabn_verification_key.json
...
[PROFILE] 见证生成时间: 0:00.02
...
[PROFILE] 证明时间: 0:00.43
...
[PROFILE] 验证时间: 0:00.39
...
[PROFILE] 36K powerabn.wasm
[PROFILE] 4.0K powerabn_witness.wtns

而且，现在你可以在powerabn.circom中尝试增加更多的N，例如200000。现在证明-验证的时间是显著的：

非线性约束: 400001
...
[PROFILE] 4.0K build/powerabn_verification_key.json
...
[PROFILE] 见证生成时间: 0:00.14
...
[PROFILE] 证明时间: 0:07.55
...
[PROFILE] 验证时间: 0:00.42
...
[PROFILE] 1.6M powerabn.wasm
[PROFILE] 13M powerabn_witness.wtns

但你可能已经注意到一行无聊的“始终相同”线，verification_key.json的大小为4.0K，验证时间约为0:00.40s。

我们所有的电路，都有较大的POWERTAU和大量的约束，验证密钥的大小恒定为4Kb，而验证时间也是常量时间！

走向实践 - 哈希

我们将尝试使用keccak哈希，并尝试对某个输入进行N次哈希。我从这个代码库（一个允许证明不同加密操作的电路库）中借用了keccak哈希电路的实现（只是复制了所有需要的文件并通过npm install将circomlib添加到依赖项中）。我们稍后将多次返回。

查看一下keccak.circom模板及在C中的实现（例如“吸收”阶段）。它们是相似的，因为哈希和对称加密算法从设计上看都是“电路”，对有限位集合进行多次相同操作。让我们证明某些内容的哈希。

让我们看看：

keccakn.circom

pragma circom 2.0.0;

include "vocdoni-keccak/keccak.circom";
include "../node_modules/circomlib/circuits/bitify.circom";

template KeccakN(N) {
    signal input a;
    signal keccak_in[256];
    signal keccak_out[256];
    signal output out;

    component toNBits = Num2Bits(256); // (1)
    component fromNBits = Bits2Num(256);

    // 需要构建N个keccak电路以执行N次哈希
    component keccak[N];

    toNBits.in &lt;== a;

    var i;
    keccak[0] = Keccak(256,256);
    for (i=0; i&lt;256; i++) {
        keccak[0].in[i] &lt;== toNBits.out[i];
    }

    var j;
    for (j=1; j&lt;N; j++) {  // (2)
        keccak[j] = Keccak(256,256); // (3)
        for (i=0; i&lt;256; i++) {
            keccak[j].in[i] &lt;== keccak[j-1].out[i];
        }
    }

    for (i=0; i&lt;256; i++) {
        fromNBits.in[i] &lt;== keccak[j-1].out[i];
    }
    out &lt;== fromNBits.out;
}

component main = KeccakN(1); // (4)

你可以使用./run_all.sh keccakn（并设置POWERTAU=21）运行它。注意即使对于N == 1，这个电路也很大（单个操作需要151k约束和较大的见证大小）：

非线性约束: 151104
...
[PROFILE] 4.0K ../keccakn_verification_key.json
...
[PROFILE] 见证生成时间: 0:00.23
...
[PROFILE] 证明时间: 0:02.65
...
[PROFILE] 验证时间: 0:00.42
...
[PROFILE] 844K keccakn.wasm
[PROFILE] 4.7M keccakn_witness.wtns

使用N==16，你将收到电路对于此tau仪式太大。2413824 * 2 > 2 ** 21，让我们尝试N==8：

...
非线性约束: 1207040
...
[PROFILE] 4.0K ../keccakn_verification_key.json
...
[PROFILE] 见证生成时间: 0:01.80
...
[PROFILE] 证明时间: 0:19.26
...
[PROFILE] 验证时间: 0:00.41
...
[PROFILE] 4.9M keccakn.wasm
[PROFILE] 37M keccakn_witness.wtns

在这里，我们有一个更长的证明时间，巨大的见证大小，以及大的keccakn.wasm大小。所有这些都会影响客户端，而客户端的能力远不如我们的服务器。

（稀疏）梅克尔树

这就是为什么现代zkSNARKs使用哈希函数，它们的乘法更少，操作于有限字段，但仍然是安全的。一个例子：MiMC哈希函数，专为SNARKs而设计（见文章）。让我们尝试用MiMC重复N次哈希（可以使用./run_all.sh mimcn运行）：

mimcn.circom
pragma circom 2.0.0;

include "../node_modules/circomlib/circuits/bitify.circom";
include "../node_modules/circomlib/circuits/mimc.circom";

template MiMCN(N) {
    signal input a;
    signal output out;

    component mimc[N];

    var k = 1;
    mimc[0] = MiMC7(91); // 轮数
    mimc[0].x_in &lt;== a;
    mimc[0].k &lt;== k;

    var j;
    for (j=1; j&lt;N; j++) {
        mimc[j] = MiMC7(91);
        mimc[j].x_in &lt;== mimc[j-1].out;
        mimc[j].k &lt;== k;
    }

    out &lt;== mimc[j-1].out;
}

component main = MiMCN(256);

我们使用N=256进行哈希迭代，拥有：

非线性约束: 93184
...
[PROFILE] 4.0K ../mimcn_verification_key.json
...
[PROFILE] 见证生成时间: 0:00.06
...
[PROFILE] 证明时间: 0:02.24
...
[PROFILE] 验证时间: 0:00.42
...
[PROFILE] 408K mimcn.wasm
[PROFILE] 2.9M mimcn_witness.wtns

这确实好得多！一个带有 2^256 叶子的梅克尔树比一个带有 2^8 叶子的树要好得多，而客户端的所有参数似乎都能应付。

还有几种对SNARK友好的加密原语，我们将在接下来的文章中讨论它们。

结论

在下一篇“第二部分”文章中，我们将继续研究更多的加密电路及其在实际应用中的用法。

P.S. 在玩Circom时不要忘记一件重要的事情——不要用“cirquit”来替代“circuit” :)

谁是MixBytes？

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

原文链接： mixbytes.io/blog/zksnark...

登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

本文参与登链社区写作激励计划，好文好收益，欢迎正在阅读的你也加入。