应用零知识证明实现不透漏具体地理位置的区域监控 - Renaissance Labs

第一章背景

实现目标：基于地理位置坐标实现对用户所在区域的零知识监控，即用户无需无需上报个人详细的地理位置信息，即可证明自己在合法的区域。
Zk算法：Zk算法基于Groth16实现，该算法目前是公认的在加密领域应用最多的算法，包括著名ZCash，其生成的证据最小，认证时间较快。

第二章开发准备

依赖组件：circom 、snarkjs
开发环境：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，编写如下电路代码
```
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. 编译电路

执行如下命令进行编译
```
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 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.

--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：

3. 设计输入

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

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

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

利用WebAssembly计算证据，即执行如下命令：
```
node generate_witness.js InRange.wasm ../input.json ../witness.wtns
```
该命令会输出witness.wtns，下一步运算需要用到。

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

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
```
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
```
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
```
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. 设计电路

2. 编译电路

3. 设计输入

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

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

第四章 参考：

第一章背景

第二章开发准备

第三章计算和证明

第四章参考：