基于circom、snarkjs实现零知识证明不透漏具体地理位置的区域监控

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

第一章 背景

1. 实现目标：基于地理位置坐标实现对用户所在区域的零知识监控，即用户无需无需上报个人详细的地理位置信息，即可证明自己在合法的区域。

2. Zk算法：Zk算法基于Groth16实现，该算法目前是公认的在加密领域应用最多的算法，包括著名ZCash，其生成的证据最小，认证时间较快。

第二章 开发准备

1. 依赖组件：circom 、snarkjs

2. 开发环境：Visual Code

   环境安装

   1. 安装Node(如果已经安装请跳过)

      sudo apt update
      sudo apt install nodejs npm -y
      node --version
      

   2. 安装Rust(如果已经安装请跳过)

      sudo apt install curl -y
      sudo apt install cmake build-essential -y
      curl --proto '=https' --tlsv1.2 https://sh.rustup.rs -sSf | sh
      

   3. 安装Circom(如果已经安装请跳过)

      git clone https://github.com/iden3/circom.git
      cd circom
      source $HOME/.cargo/env
      cargo build --release
      

      在这一步特别提醒一下，如果用户已经安装了请确保安装了正确的版本，因为之前用户可能通过执行npm install circom命令来安装的，这种方法提示也是安装成功，但是版本和库都不对，此时需要通过执行which circom命令来查看具体安装的位置，然后进入到对应的目录把相关的文件夹全部删除掉，通过执行npm uninstall circom是没有效果的。最后可以通过执行circom --version，如果显示的是类似2.*.*就代表OK了。

   4. 更新Circom

      cargo install --path circom
      circom --help
      

   5. 安装Snarkjs(如果已经安装请跳过)

      sudo npm install -g snarkjs
      

      如果执行到此处都没有错误的话，那么就是安装环境OK了。

### 第三章 计算和证明

#### 1\. 设计电路

在VS code中新建文件InRange.circom，编写如下电路代码

```auto

template Main() {
    signal input latitudeRange[2];
    signal input longitudeRange[2];

    signal input fishingLocation[2];

    signal output out;

    component gt1 = GreaterEqThan(9);
    gt1.in[0] <== fishingLocation[0];
    gt1.in[1] <== latitudeRange[0];
    gt1.out === 1;
}

template GreaterEqThan(n) {
    signal input in[2];
    signal output out;

    component lt = LessThan(n);

    lt.in[0] <== in[1];
    lt.in[1] <== in[0]+1;
    lt.out ==> out;
}

template LessThan(n) {
    assert(n <= 252);
    signal input in[2];
    signal output out;

    component n2b = Num2Bits(n+1);

    n2b.in <== in[0]+ (1<<n) - in[1];

    out <== 1-n2b.out[n];
}

template Num2Bits(n) {
    signal input in;
    signal output out[n];
    var lc1=0;

    var e2=1;
    for (var i = 0; i<n; i++) {
        out[i] <-- (in >> i) & 1;
        out[i] * (out[i] -1 ) === 0;
        lc1 += out[i] * e2;
        e2 = e2+e2;
    }

    lc1 === in;
}

component main = Main();
```

#### 2\. 编译电路

执行如下命令进行编译

```auto
circom InRange.circom --r1cs --wasm --sym
```

> With these options we generate three types of files:
> 
> `--r1cs`: it generates the file `multiplier2.r1cs` that contains the [R1CS constraint system](https://docs.circom.io/background/background#rank-1-constraint-system "R1CS constraint system") of the circuit in binary format.
> 
> `--wasm`: it generates the directory `multiplier2_js` that contains the `Wasm` code (multiplier2.wasm) and other files needed to generate the [witness](https://docs.circom.io/background/background#witness "witness").
> 
> `--sym` : it generates the file `multiplier2.sym` , a symbols file required for debugging or for printing the constraint system in an annotated mode.
> 
> `--c` : it generates the directory `multiplier2_cpp` that contains several files (multiplier2.cpp, multiplier2.dat, and other common files for every compiled program like main.cpp, MakeFile, etc) needed to compile the C code to generate the witness.

1. 执行成功后，会生成如下截图的文件1：

3. 设计输入

设计电路的输入是下一步计算证明的必要前提，在相同目录下新建input.json输入文件，编写如下输入，本案例中即一些地理位置数据：

{
    "latitudeRange": [ 20, 21],
    "longitudeRange": [ 176, 190],
    "fishingLocation": [ 20, 180]
}

4. 计算获得证据(Computing the witness)

1. 利用WebAssembly计算证据，即执行如下命令：

   node generate_witness.js InRange.wasm ../input.json ../witness.wtns
   

   该命令会输出witness.wtns，下一步运算需要用到。

5. 证明电路(Proving circuits with zk)

1. Phase1: Powers of Tau

   First, we start a new "powers of tau" ceremony，即执行如下命令，生成 pot12_0000.ptau

   snarkjs powersoftau new bn128 12 pot12_0000.ptau -v
   

   Then, we contribute to the ceremony，即执行如下命令，生成pot12_0001.ptau，此处会提示输入随机字符，随意输入即可。

   snarkjs powersoftau contribute pot12_0000.ptau pot12_0001.ptau --name="First contribution" -v
   

2. Phase2: circuit-specific

   start the generation of this phase，即执行如下命令，生成pot12_final.ptau

   snarkjs powersoftau prepare phase2 pot12_0001.ptau pot12_final.ptau -v
   

   Next，we generate a .zkey file that will contain the proving and verification keys together with all phase 2 contributions.即执行如下命令，生成

   snarkjs groth16 setup InRange.r1cs pot12_final.ptau multiplier2_0000.zkey
   

   Contribute to the phase 2 of the ceremony，即执行如下命令：

   snarkjs zkey contribute multiplier2_0000.zkey multiplier2_0001.zkey --name="1st Contributor Name" -v\
   

   Export the verification key，执行如下命令:

   snarkjs zkey export verificationkey multiplier2_0001.zkey verification_key.json
   

3. Generating a Proof

   Once the witness is computed and the trusted setup is already executed, we can generate a zk-proof associated to the circuit and the witness，即执行如下命令：

   snarkjs groth16 prove multiplier2_0001.zkey witness.wtns proof.json public.json
   

4. Verifying a Proof

   To verify the proof，执行如下命令：

   snarkjs groth16 verify verification_key.json public.json proof.json
   

   The command uses the files verification_key.json we exported earlier,proof.json and public.json to check if the proof is valid. If the proof is valid, the command outputs an OK.

   最终证明输出结果截图如下：

第四章 参考：

1. https://iden3.io/circom

2. https://www.samsclass.info/141/proj/C523.htm