The Beginner's Guide to ZK-Snark: Setting Up Your First Proof System

This Blog will guide you on building your first zero knowledge proof and a verification system to verify it.
If you are not aware of what zero knowledge proofs(zkp) are, then check introduction to zkp.

Aim of this blog is to create a zkp system that allows prover to prove to verifier that he knows a pre-image of a hash wihtout actually revealing the pre-image.

workflow

Note: we are setting up a non interactive proof system.

There are three steps in creating a zkp system:
1) generate the proving and verification key
2) generating the proof
3) verifying the proof

FIRST STEP:
In this step we need a circuit and a secret value(λ).

A circuit in zero-knowledge proof is a program that specifies a calculation to be performed on some data inputs. The circuit is used by the prover to generate a proof that they have correctly performed the calculation, without revealing any information about the data inputs. The verifier can then use the proof to confirm that the computation was performed correctly, without learning anything about the data inputs.

These circuits can be complex made of logic gates like (AND, OR) but fortunately we have a programming language called CIRCOM which is DSL(Domain specific language) used to create aritmetic circuits.More about arithmetic circuits.

let' set up the environment to write the circuit and complete it

Pre-requisites.
1) nodejs
2) circom compiler (follow steps)

After successfully installing the dependencies we need to start a nodejs project.

npm init -y

now you need to install circomlib(v2.0.5) to use certain predefined circuits.

npm install circomlib

Now create a file named circuit.circom and write the following code.

pragma circom 2.0.0;

include "node_modules/circomlib/circuits/pedersen.circom";

template Hasher(){
    signal input secret;
    signal output out;

    component pedersen = Pedersen(1);
    pedersen.in[0] <== secret;
    out <== pedersen.out[0];
}

component main = Hasher();

The program defines a template called "Hasher" which takes an input signal called "secret" and outputs a signal called "out". It uses a component called "Pedersen" which is included from the circomlib library, and sets it up to use 1 input.
The code then connects the "secret" input to the first input of the "Pedersen" component, and the output of the "Pedersen" component to the "out" output of the template.
Finally, the program defines a component called "main" which is an instance of the "Hasher" template.
Overall, this program creates a circuit that takes a secret input, hashes it using the Pedersen hashing function, and outputs the resulting hash.

we need to compile the circuit and get the low level represetation of the circuit.

circom circuit.circom --r1cs --wasm

after compiling we get 2 files(circuit.r1cs, circuit.wasm). r1cs(rank 1 constraint system), In simple terms, it is a way to express any computation as a set of linear equations that satisfy certain constraints. These constraints can be thought of as rules that define the inputs and outputs of the computation. We also get a wasm binary(web assembly).

Now one part of step one is completed i.e we have a circuit and now we need a secret value(λ).
This secret value is generated with the help of a ceremony called as trusted setup.

Trusted setup is a process used in some zero knowledge proof systems to generate the initial proving and verifying keys required for generating and verifying proofs. The purpose of trusted setup is to establish a secure foundation for the system by generating these keys in a way that ensures they are unpredictable and unbiased. This is typically done by having a group of trusted individuals generate the keys together, with each individual contributing a piece of random data. Once all the pieces are combined and processed using cryptographic techniques, the resulting keys can be used to generate and verify proofs without the need for any additional trust assumptions. The goal of trusted setup is to ensure that the system is secure and trustworthy, even if some of the participants in the trusted setup process are malicious.

the file generated during trusted setup process is called a ptau file(powers of tau). We already have a generated ptau file(only for testing purpose).

wget https://hermez.s3-eu-west-1.amazonaws.com/powersOfTau28_hez_final_12.ptau

Now we have the circuit and ptau file to generate the proving and verification keys (zkey file).

before that we need to install snarkjs

snarkJS is a JavaScript library for zk-SNARK proof generation and verification.

npm install snarkjs

After successfully installing the files now we need to generate the keys.

npx snarkjs groth16 setup circuit.r1cs powersOfTau28_hez_final_12.ptau circuit_0000.zkey

Groth16 is a type of zk-SNARK (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge) proof system used for generating and verifying proofs of computation. It is named after its creator, Jens Groth.

circuit_0000.zkey is a binary file that contains the proving and verification keys.

First step is successfully completed 🎉

SECOND STEP
In this step we need to generate proof.

create an index.js file and run the following code

const snarkjs = require('snarkjs')

async function generateProof(){
const { proof, publicSignals } = await snarkjs.groth16.fullProve(
    { secret: 12345 }, 
    "circuit_js/circuit.wasm", 
    "circuit_0000.zkey");
  console.log(publicSignals);
  console.log(proof);
}

generateProof()

generateProof().then(() => {
    process.exit(0);
});

output should look like this.

[
  '5470837527801859476637479809685048117954687279553045117433714472916822705394'
]
{
  pi_a: [
    '705318533694831637201207114678172400618551110993861322781866568756555043874',
    '11516110700725150090242458771069054303979174691445387001497479659508896518046',
    '5596622138762287749906806880510123588992685037536757227047926354733627986895',
    '1'
  ],
  protocol: 'groth16',
  curve: 'bn128'
}

Proof(π) is successfully generated and now we need to generate the verification key from the proving key(circuit_0000.zkey).

Proving key is like private key and verification key is like public key(In context of assymetric key cryptography)

generate verification key

npx snarkjs zkey export verificationkey circuit_0000.zkey verification_key.json

now we have successfully completed step 2 🎉

STEP 3
Verifying the Proof(π) which is generated in step 2.

Note: We can write code to verify the proof on a normal backend or we can also do on-chain verification with the help of smart contract.

let's create web2 backend verification system first.

create a verify.js file

const snarkjs = require('snarkjs')
const fs = require("fs");

async function verify(){
const { proof, publicSignals } = await snarkjs.groth16.fullProve(
    { secret: 12345 }, 
    "circuit_js/circuit.wasm", 
    "circuit_0000.zkey");


    const vKey = JSON.parse(fs.readFileSync("verification_key.json"));
    const res = await snarkjs.groth16.verify(vKey, publicSignals, proof);
      if (res === true) {
        console.log("Verification OK");
      } else {
        console.log("Invalid proof");
      }
}
verify()

verify().then(() => {
    process.exit(0);
});

output:
Verification OK

Congratulations you have completed all the 3 steps 🎉

For detailed explanation of on-chain verification, check here