零知识证明应用开发入门

灰太狼 2022-08-29 05:50 284阅读 0赞

过去的一年出现了很多零知识证明应用，在这个教程中， 我们将首先学习零知识证明的基本概念、使用circom搭建算术电路、 使用snarkjs实现零知识证明的全过程，并利用这些知识实现 二层扩容方案zk rollup。

## 1、算术电路：零知识证明核心 ##

零知识程序和其他程序的实现不太一样。首先，你要解决的问题需要 先转化成多项式，再进一步转化成电路。例如，多项式x³ + x +5 可以 表示成如下的电路：

Circom编译器将逻辑转换为电路。通常我们不需要自己设计基础电路。 如果你需要一个哈希函数或签名函数，可以在[circomlib][] 找到。

## 2、证据的生成与验证：零知识证明的流程 ##

在运行零知识证明程序之前，我们需要创建一个可信的设置，这需要 一个电路以及一些随机数。一旦设置完成就会生成一个证明密钥和一个 验证密钥，分别用于生成证据和执行验证。

![81648c579d29d626c78ece2e169dec45.png][]

一旦创建了证明/验证密钥对，就可以生成证据了。

有两种类型的输入：公开输入和私有输入。例如，A向B转账但是不希望 公开账户余额，那么A的账户余额就是私有输入，也被称为见证（Witness）。 公开输入可以是A和B的地址或者转账金额，这完全取决于你的具体设计。

接下来证明人就可以利用证明密钥、公开输入和见证来生成证据：

![8b80c6fe1d0a5695a640f7b28c24a8b8.png][]

最后一步是验证。验证方使用公开输入、证据和验证密钥来验证证据。

![60a300a5e6db548fbbb0ac85ae2bb769.png][]

公开输入、见证（私有输入）、证明密钥、验证密钥、电路、证据这些 基本概念以及相互之间的关系，就是我们继续下面的教程之前需要理解 的零知识证明的基本概念。

## 3、Circom基本概念：算术电路语言 ##

首先我们先了解下Circom的语法。Circom的语法类似javascript和C， 提供一些基本的数据类型和操作，例如for、while、>>、array等。

让我们看一个具体的实例。

假设x、y是保密的（即witness），我们不想暴露x和y的具体值，但是 希望证明 (x *y) + z == out，其中z,out是公开输入。我们假设 out = 30, z = 10, 那么显然 (x*y) = 20，但是这不会暴露x和y的具体值。

circom提供了如下这些关键字用于描述算术电路:

*  signal：信号变量，要转换为电路的变量，可以是private或public
 *  template：模板，用于函数定义，就像Solidity中的function或golang中的func
 *  component：组件变量，可以把组件变量想象成对象，而信号变量是对象的公共成员

Circom也提供了一些操作符用于操作信号变量：

*  <==, ==>：这两个操作符用于连接信号变量，同时定义约束
 *  ←, →：这些操作符为信号变量赋值，但不会生成约束条件
 *  ===：这个操作符用来定义约束

好了，这些就是我们继续零知识证明实践需要了解的circom关键字。

## 4、用circom和snarkjs实现零知识证明应用的全流程 ##

STEP 1：编译电路文件，生成circuit.json：

<table> 
 <tbody> 
  <tr> 
   <td> <pre>1
</pre> </td> 
   <td> <pre>circom sample1.circom
</pre> </td> 
  </tr> 
 </tbody> 
</table>

STEP 2：创建可信设置，使用groth协议生成proving\_key.json和verification\_key.json

<table> 
 <tbody> 
  <tr> 
   <td> <pre>1
</pre> </td> 
   <td> <pre>snarkjs setup — protocol groth
</pre> </td> 
  </tr> 
 </tbody> 
</table>

STEP 3：生成见证（私有输入）。这一步需要输入，因此应当将你的输入 存入input.json，就像下面这样：

<table> 
 <tbody> 
  <tr> 
   <td> <pre>1
2
</pre> </td> 
   <td> <pre>// input.json
{“x”:3, “y”:5, “z”: 100}
</pre> </td> 
  </tr> 
 </tbody> 
</table>

使用下面的命令生成见证文件witness.json：

<table> 
 <tbody> 
  <tr> 
   <td> <pre>1
</pre> </td> 
   <td> <pre>snarkjs calculatewitness
</pre> </td> 
  </tr> 
 </tbody> 
</table>

STEP 4：使用如下的snarkjs命令生成证据：

<table> 
 <tbody> 
  <tr> 
   <td> <pre>1
</pre> </td> 
   <td> <pre>snarkjs proof
</pre> </td> 
  </tr> 
 </tbody> 
</table>

结果是得到proof.json、public.json。在public.json中包含了公开输入，例如：

<table> 
 <tbody> 
  <tr> 
   <td> <pre>1
2
3
4
5
</pre> </td> 
   <td> <pre>// public.json
{
  “115”, // → out
  “100” // → z:100
}
</pre> </td> 
  </tr> 
 </tbody> 
</table>

STEP 5：使用如下snarkjs命令进行验证：

<table> 
 <tbody> 
  <tr> 
   <td> <pre>1
</pre> </td> 
   <td> <pre>snarkjs verify
</pre> </td> 
  </tr> 
 </tbody> 
</table>

## 5、零知识证明实践案例：zk rollup实现 ##

zk rollup是一个二层解决方案，不过它和其他的二层方案不同。zk roolup 将所有数据放在链上，使用zk-snark进行验证。因此，不需要复杂的挑战游戏。 在zk rollup中，用户的地址记录在智能合约的merkle树上，使用3字节的索引 来表征用户的地址（地址的原始大小是20字节），因此zk rollup可以通过减小 数据大小来增加交易吞吐量。

为了便于理解，在下面的zk rollup实现中，我们有意忽略一些细节，原始 的zk rollup教程可以参考[ ZKRollup Tutorial][ZKRollup Tutorial]。

首先，有一个记录账号的merkle树，账号记录的内容是（公钥，余额）。每个交易 的内容是（发送方索引、接收方索引、金额）。流程如下：

1、检查发送方账号是否在merkle树上 2、验证发送方的签名 3、更新发送方的余额并验证中间merkle根 4、更新接收方的余额并更新merkle根

circom电路程序的变量定义如下：

<table> 
 <tbody> 
  <tr> 
   <td> <pre>1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
</pre> </td> 
   <td> <pre>// account tree
signal input account_root;
signal private input account_pubkey[2];
signal private input account_balance;

// new account root after sender's balance is updated
signal private input new_sender_account_root;

// tx
signal private input tx_sender_pubkey[2]
signal private input tx_sender_balance
signal private input tx_amount
signal private input tx_sender_sig_r[2]
signal private input tx_sender_sig_s
signal private input tx_sender_path_element[levels]
signal private input tx_sender_path_idx[levels]
signal private input tx_receiver_pubkey[2]
signal private input tx_receiver_balance
signal private input tx_receiver_path_element[levels]
signal private input tx_receiver_path_idx[levels]

// output new merkle root
signal output new_root;
</pre> </td> 
  </tr> 
 </tbody> 
</table>

在这个案例中几乎所有的变量都是私有的，不管是公钥、账户余额还是签名等等， 只有merkle根和更新后的merkle根是公开的。path\_element是构建merkle根的中间值， path\_idx是一个索引数组，用于保存merkle树每一层的索引 —— 这时一个二叉树，因此 只有左右两个分支，0表示左，1表示右。最终的路径像一个二进制字符串：001011。

下面的circom代码检查发送方是否存在：

<table> 
 <tbody> 
  <tr> 
   <td> <pre>1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
</pre> </td> 
   <td> <pre>//__1. verify sender account existence
component senderLeaf = HashedLeaf();
senderLeaf.pubkey[0] &lt;== tx_sender_pubkey[0];
senderLeaf.pubkey[1] &lt;== tx_sender_pubkey[1];
senderLeaf.balance &lt;== account_balance;

component senderExistence = GetMerkleRoot(levels);
senderExistence.leaf &lt;== senderLeaf.out;

for (var i=0; i&lt;levels; i++) {
   senderExistence.path_index[i] &lt;== tx_sender_path_idx[i];
   senderExistence.path_elements[i] &lt;== tx_sender_path_element[i];
}

senderExistence.out === account_root;
</pre> </td> 
  </tr> 
 </tbody> 
</table>

上面的代码也比较简单，哈希发送方的公钥和账户余额，用merkle树 的中间值计算，然后得到merkle根（senderExistence.out）。检查 计算得到的merkle根和输入是否一致（account\_root）。

出于简化考虑，我们省略了merkle树和哈希函数的实现，你可以查看 [HashedLeaf][] 和[GetMerkleRoot][]。

下面的circom代码检查发送方的签名：

<table> 
 <tbody> 
  <tr> 
   <td> <pre>1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
</pre> </td> 
   <td> <pre>//__2. verify signature
component msgHasher = MessageHash(5);
msgHasher.ins[0] &lt;== tx_sender_pubkey[0];
msgHasher.ins[1] &lt;== tx_sender_pubkey[1];
msgHasher.ins[2] &lt;== tx_receiver_pubkey[0];
msgHasher.ins[3] &lt;== tx_receiver_pubkey[1];
msgHasher.ins[4] &lt;== tx_amount
    
component sigVerifier = EdDSAMiMCSpongeVerifier(); 
sigVerifier.enabled &lt;== 1;
sigVerifier.Ax &lt;== tx_sender_pubkey[0];
sigVerifier.Ay &lt;== tx_sender_pubkey[1];
sigVerifier.R8x &lt;== tx_sender_sig_r[0];
sigVerifier.R8y &lt;== tx_sender_sig_r[1];
sigVerifier.S &lt;== tx_sender_sig_s;
sigVerifier.M &lt;== msgHasher.out;
</pre> </td> 
  </tr> 
 </tbody> 
</table>

就像区块链交易需要验证发送方的签名一样，在上面的代码中， 我们首先哈希消息然后进行签名，然后调用不同的封装函数。

更新发送方余额并检查新的merkle根。

<table> 
 <tbody> 
  <tr> 
   <td> <pre>1
2
3
4
5
6
7
8
9
10
11
12
</pre> </td> 
   <td> <pre>//__3. Check the root of new tree is equivalent
component newAccLeaf = HashedLeaf();
newAccLeaf.pubkey[0] &lt;== tx_sender_pubkey[0];
newAccLeaf.pubkey[1] &lt;== tx_sender_pubkey[1];
newAccLeaf.balance &lt;== account_balance - tx_amount;

component newTreeExistence = GetMerkleRoot(levels);
newTreeExistence.leaf &lt;== newAccLeaf.out;
for (var i=0; i&lt;levels; i++) {
 newTreeExistence.path_index[i] &lt;== tx_sender_path_idx[i];
 newTreeExistence.path_elements[i] &lt;== tx_sender_path_element[i];
} newTreeExistence.out === new_sender_account_root;
</pre> </td> 
  </tr> 
 </tbody> 
</table>

前面的两个步骤从发送方的角度检查信息，然后更新发送方的余额 并计算新的merkle根。最下面一行：`newTreeExistence.out === new_sender_account_root;` 作用是检查计算得到的merkle根和输入（new\_sender\_account\_root）是否一致。 通过这个检查，可以避免伪造或不正确的输入。

下面的代码更新接收方余额以及merkle树：

<table> 
 <tbody> 
  <tr> 
   <td> <pre>1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
</pre> </td> 
   <td> <pre>//__5. update the root of account tree
component newReceiverLeaf = HashedLeaf();
newReceiverLeaf.pubkey[0] &lt;== tx_receiver_pubkey[0];
newReceiverLeaf.pubkey[1] &lt;== tx_receiver_pubkey[1];
newReceiverLeaf.balance &lt;== tx_receiver_balance + tx_amount;

component newReceiverTreeExistence = GetMerkleRoot(levels);
newReceiverTreeExistence.leaf &lt;== newReceiverLeaf.out;
for (var i=0; i&lt;levels; i++) {
newReceiverTreeExistence.path_index[i]&lt;==tx_receiver_path_idx[i];
newReceiverTreeExistence.path_elements[i] 
&lt;==tx_receiver_path_element[i];
}

new_root &lt;== newReceiverTreeExistence.out;
</pre> </td> 
  </tr> 
 </tbody> 
</table>

最后一步更新接收方余额，计算并输出新的merkle根。一旦电路构建好， 就像一个黑盒子。如果你输入正确的值，那么输出一定是正确的，因此 用户容易检查以避免恶意中间人。这就是为什么我们需要在电路最后输出 一些东西的原因 —— 在这个案例里我们输出的是merkle根。

zk rollup聚合了很多上述交易并生成单一证据来所见数据大小。在这个 教程中为了便于理解，我们仅处理单一交易，点击[这里][Link 1] 查看完整代码。

--------------------

原文链接：[Hands-on Your first ZK application][]

[circomlib]: https://github.com/iden3/circomlib
[81648c579d29d626c78ece2e169dec45.png]: /images/20220829/127318d4c85c4928af9dd75b37f69695.png
[8b80c6fe1d0a5695a640f7b28c24a8b8.png]: /images/20220829/5a4c7a0ba91f44c7860023c1179a1ed0.png
[60a300a5e6db548fbbb0ac85ae2bb769.png]: /images/20220829/6bb6353bae6a4c188c40f38f31c28526.png
[ZKRollup Tutorial]: https://keen-noyce-c29dfa.netlify.com/#6
[HashedLeaf]: https://github.com/KimiWu123/Samples/blob/master/circom/rollupSample/rollup.circom#L75
[GetMerkleRoot]: https://github.com/KimiWu123/Samples/blob/master/circom/rollupSample/rollup.circom#L43
[Link 1]: https://github.com/KimiWu123/Samples/blob/master/circom/rollupSample/rollup.circom
[Hands-on Your first ZK application]: https://artmoneyprovenance.com/2020/02/06/hands-on-your-first-zk-application/