MIT IAP 2023 Modern Zero Knowledge Cryptography课程笔记

Lecture 2: Circom 1 (Brain Gu)

Review zkSNARKs
- Properies
  - zk: hides inputs
  - Succinct: generates short proofs that can be verified quickly
  - Noninteractive: doesn’t require a back-and-forth
  - ARgument of Knowledge: proves you know the input
Generate a ZKP for satisfiability of the R1CS
- x_i + x_j = x_k
- x_i * x_j = x_k
zkSNARKs Example
zkSNARKs prove constraints
- Example 1
- Example 2
  - A bug in the code: x3 should be constrained to x3 != 0

Circom Demo

ZKRepl: zkrepl.dev

Example 1

pragma circom 2.1.6;

template Example() {
    signal input x1;
    signal input x2;
    signal input x3;
    signal input x4;

    signal input y1;
    signal input y2;

    signal input out;
    
    y1 === x1 + x2;
    y2 === y1 * x3;
    y2 === out + x4;
}

component main {public [out] } = Example();

/*
INPUT = {
    "x1" : "2",
    "x2" : "4",
    "x3" : "8",
    "x4" : "5",
    "y1" : "6",
    "y2" : "48",
    "out": "43"
}
*/

Output

STDOUT: 
template instances: 1
non-linear constraints: 1
linear constraints: 0
public inputs: 1
public outputs: 0
private inputs: 6
private outputs: 0
wires: 6
labels: 8
Written successfully: ./main.r1cs
Written successfully: ./main.sym
Written successfully: ./main_js/main.wasm
Everything went okay, circom safe
Compiled in 0.32s
ARTIFACTS: 
Finished in 0.43s
main.wasm (34.45KB)
main.js (9.18KB)
main.wtns (0.27KB)
main.r1cs (0.35KB)
main.sym (0.10KB)
PLONK KEYS: 
main.plonk.zkey (13.59KB)
main.plonk.vkey.json (2.00KB)
main.plonk.sol (23.38KB)
main.plonk.html (477.04KB)

Example 2: Num2Bits

pragma circom 2.1.6;

template Bits4(){ //range check
    signal input in;
    signal bits[4];
    var bitsum = 0;
    for (var i = 0; i < 4; i++) {
        bits[i] <-- (in >> i) & 1;
        bits[i] * (bits[i] - 1) === 0;
        bitsum = bitsum + 2 ** i * bits[i];
    }
    bitsum === in;
}

template Num2Bits() {

    signal input in;

    signal input b0;
    signal input b1;
    signal input b2;
    signal input b3;

    component check = Bits4();
    check.in <== in;

    in === 8 * b3 + 4 * b2 + 2 * b1 + b0;

    b0 * (b0 - 1) === 0;
    b1 * (b1 - 1) === 0;
    b2 * (b2 - 1) === 0;
    b3 * (b3 - 1) === 0;

}

component main { public [b0, b1, b2, b3] } = Num2Bits();

/*
INPUT = {
    "in" : "11",
    "b0" : "1",
    "b1" : "1",
    "b2" : "0",
    "b3" : "1"
}

*/

Output

STDOUT: 
template instances: 2
non-linear constraints: 8
linear constraints: 0
public inputs: 4
public outputs: 0
private inputs: 1
private outputs: 0
wires: 8
labels: 11
Written successfully: ./main.r1cs
Written successfully: ./main.sym
Written successfully: ./main_js/main.wasm
Everything went okay, circom safe
Compiled in 1.08s
ARTIFACTS: 
Finished in 1.16s
main.wasm (35.85KB)
main.js (9.18KB)
main.wtns (0.33KB)
main.r1cs (1.57KB)
main.sym (0.19KB)
PLONK KEYS: 
main.plonk.zkey (66.00KB)
main.plonk.vkey.json (2.00KB)
main.plonk.sol (28.36KB)
main.plonk.html (548.77KB)

Some improvement

pragma circom 2.1.6;

template RangeCheck(nBits){ //range check
    signal input in;
    signal bits[nBits];
    var bitsum = 0;
    for (var i = 0; i < nBits; i++) {
        bits[i] <-- (in >> i) & 1;
        bits[i] * (bits[i] - 1) === 0;
        bitsum = bitsum + 2 ** i * bits[i];
    }
    bitsum === in;
}

template Num2Bits(nBits) {

    signal input in;
    signal input b[nBits];

    component check = RangeCheck(nBits);
    check.in <== in;

    var accum = 0;
    for (var i = 0; i < nBits; i++){
        accum += (2 ** i) * b[i];
    }

    in === accum;

    for (var i = 0; i < nBits; i++){
        0 === b[i] * (b[i] - 1);
    }

}

component main { public [b] } = Num2Bits(4);

/*
INPUT = {
    "in" : "11",
    "b": ["1","1","0","1"]
}
*/