Prove Your Know The Answer To A Maths Problem, Without Giving The Answer

Prove Your Know The Answer To A Maths Problem, Without Giving The Answer

And That The Teacher Will Never Have to Compute It

Let’s say you are a maths teacher, and give your students a problem, and then ask them to solve it. But you don’t want them to prove you with the answer, but a proof that they have the right answer. In this way, the teacher doesn’t have to compute the answer but knows that it is correct and that the answer will not be leaked.

So, we will use a magical zero-knowledge proof method of zkSnarks, and which allows us to produce a proof of knowledge, and for it then to be verified that we know the answer.

In this case, the equation the teacher will use is:

x²+x+5=11

It is obvious that the answer to this is (x+3)(x-2)=11, and so the possible answers are x=-3 and x=2. So, now the pupil needs to provide a solution of x=2, and produce a proof of knowledge for this.

First, we will create a circuit from this equation (from a file named eq.circom):

pragma circom 2.0.0;
/* x^2 + x + 5 == 11 */
// x=2

function sqr(x) {
    return x*x;
}
function mult(a,b) {
    return a*b;
}
template Eq() {
    signal input x;
    signal output y;

    var b;

    b = sqr(x);
    b = b+5;
    b= b+x;
    y <== b;
    assert(y==11);

 }

 component main = Eq();

First, we can compile the circuit:

> circom eq.circom --r1cs --wasm --sym --c

template instances: 1
non-linear constraints: 1
linear constraints: 0
public inputs: 0
public outputs: 1
private inputs: 1
private outputs: 0
wires: 3
labels: 3
Written successfully: .\eq.r1cs
Written successfully: .\eq.sym
Written successfully: .\eq_cpp\eq.cpp and .\eq_cpp\eq.dat
Written successfully: .\eq_cpp/main.cpp, circom.hpp, calcwit.hpp, calcwit.cpp, fr.hpp, fr.cpp, fr.asm and Makefile
Written successfully: .\eq_js\eq.wasm
Everything went okay, circom safe

In this case, we create an R1CS (Rank 1 Constraint System) file (with the -r1cs opinion), along with a folder with the files of generate_witness.js, eq.wasm and witness_calculator.js (with the — wasm opinion). The R1CS format is used to represent all the wires in the circuit, and so that they can be checked for the proof — this is known as a Quadratic Arithmetic Program (QAP).

Next, we create an input file (input.json) to define our proof:

{"x": 2}

We can also export our R1CS file into a JSON file format with:

> snarkjs r1cs export json eq.r1cs eq.json

and a listing of eq.json is:

{
 "n8": 32,
 "prime": "21888242871839275222246405745257275088548364400416034343698204186575808495617",
 "nVars": 3,
 "nOutputs": 1,
 "nPubInputs": 0,
 "nPrvInputs": 1,
 "nLabels": 3,
 "nConstraints": 1,
 "useCustomGates": false,
 "constraints": [
  [
   {
    "2": "21888242871839275222246405745257275088548364400416034343698204186575808495616"
   },
   {
    "2": "1"
   },
   {
    "0": "5",
    "1": "21888242871839275222246405745257275088548364400416034343698204186575808495616",
    "2": "1"
   }
  ]
 ],
 "map": [
  0,
  1,
  2
 ],
 "customGates": [],
 "customGatesUses": []
}

Creating the witness

The next thing we must do is to create a witness for all the values in the circuit for the given inputs. For this we can go into the eq_js folder, and create a witness file:

> node generate_witness.js eq.wasm input.json witness.wtns

This creates witness.wtns, and which will create the values of the witness within the circuit. We can also export our witness into a JSON file format with:

> snarkjs wtns export json witness.wtns witness.json

If we list witness.json, we get:

[
 "1",
 "11",
 "2"
]

Powers of Tau

We can now go through a “powers of tau” ceremony:

> snarkjs powersoftau new bn128 12 pot12_0000.ptau -v
[DEBUG] snarkJS: Calculating First Challenge Hash
[DEBUG] snarkJS: Calculate Initial Hash: tauG1
[DEBUG] snarkJS: Calculate Initial Hash: tauG2
[DEBUG] snarkJS: Calculate Initial Hash: alphaTauG1
[DEBUG] snarkJS: Calculate Initial Hash: betaTauG1
[DEBUG] snarkJS: Blank Contribution Hash:
                786a02f7 42015903 c6c6fd85 2552d272
                912f4740 e1584761 8a86e217 f71f5419
                d25e1031 afee5853 13896444 934eb04b
                903a685b 1448b755 d56f701a fe9be2ce
[INFO]  snarkJS: First Contribution Hash:
                9e63a5f6 2b96538d aaed2372 481920d1
                a40b9195 9ea38ef9 f5f6a303 3b886516
                0710d067 c09d0961 5f928ea5 17bcdf49
                ad75abd2 c8340b40 0e3b18e9 68b4ffef

and:

> snarkjs powersoftau contribute pot12_0000.ptau pot12_0001.ptau --name="My name" -v
Enter a random text. (Entropy): test123
[DEBUG] snarkJS: Calculating First Challenge Hash
[DEBUG] snarkJS: Calculate Initial Hash: tauG1
[DEBUG] snarkJS: Calculate Initial Hash: tauG2
[DEBUG] snarkJS: Calculate Initial Hash: alphaTauG1
[DEBUG] snarkJS: Calculate Initial Hash: betaTauG1
[DEBUG] snarkJS: processing: tauG1: 0/8191
[DEBUG] snarkJS: processing: tauG2: 0/4096
[DEBUG] snarkJS: processing: alphaTauG1: 0/4096
[DEBUG] snarkJS: processing: betaTauG1: 0/4096
[DEBUG] snarkJS: processing: betaTauG2: 0/1
[INFO]  snarkJS: Contribution Response Hash imported:
                cbf96c4a 9ad56d38 15a8ae7a 0572333a
                e45fd737 2b5b3ea8 6c608ad0 ab47f90c
                98a30b87 415fffa2 d609601f e1172d2f
                56608dae 74976bdb 62966820 aa0bf7f0
[INFO]  snarkJS: Next Challenge Hash:
                bc62ba51 ce90195f ce0fb019 0b9aa8e8
                b0c6bac7 7c2b7458 3670bb38 ed55e397
                c18e5ffd 28ba4c01 4dd93bfa 2ad2fb0b
                92452036 e7d2ace9 fcce906c 6da59cc0

This creates a file named pot12_0000.ptau.

Phase 2

Next, we will apply our circuit in the next phase:

> snarkjs powersoftau prepare phase2 pot12_0001.ptau pot12_final.ptau -v
[DEBUG] snarkJS: Starting section: tauG1
[DEBUG] snarkJS: tauG1: fft 0 mix start: 0/1
[DEBUG] snarkJS: tauG1: fft 0 mix end: 0/1
[DEBUG] snarkJS: tauG1: fft 1 mix start: 0/1
[DEBUG] snarkJS: tauG1: fft 1 mix end: 0/1
[DEBUG] snarkJS: tauG1: fft 2 mix start: 0/1
[DEBUG] snarkJS: tauG1: fft 2 mix end: 0/1
[DEBUG] snarkJS: tauG1: fft 3 mix start: 0/1
[DEBUG] snarkJS: tauG1: fft 3 mix end: 0/1
 .... details missed out
[DEBUG] snarkJS: betaTauG1: fft 11 mix end: 1/2
[DEBUG] snarkJS: betaTauG1: fft  11  join: 11/11
[DEBUG] snarkJS: betaTauG1: fft 11 join  11/11  1/1 0/1
[DEBUG] snarkJS: betaTauG1: fft 12 mix start: 0/2
[DEBUG] snarkJS: betaTauG1: fft 12 mix start: 1/2
[DEBUG] snarkJS: betaTauG1: fft 12 mix end: 0/2
[DEBUG] snarkJS: betaTauG1: fft 12 mix end: 1/2
[DEBUG] snarkJS: betaTauG1: fft  12  join: 12/12
[DEBUG] snarkJS: betaTauG1: fft 12 join  12/12  1/1 0/1

Will then create a proving and a verification key (and which are created within a zkey file):

> snarkjs groth16 setup eq.r1cs pot12_final.ptau eq_0000.zkey
[INFO]  snarkJS: Reading r1cs
[INFO]  snarkJS: Reading tauG1
[INFO]  snarkJS: Reading tauG2
[INFO]  snarkJS: Reading alphatauG1
[INFO]  snarkJS: Reading betatauG1
[INFO]  snarkJS: Circuit hash:
ac024737 f6a5a4ce 860483b8 515e6915
6205c88a 2e6b7055 f4a03fdb e78c3e4b
c9a7986e 9e8a2cd0 4e28fe88 1cd6c96a
9e569461 1f01666b 6a7ed94a 3504e134

And then contribute to the ceremony:

> snarkjs zkey contribute eq_0000.zkey eq_0001.zkey --name="Test Name" -v
Enter a random text. (Entropy): test123
[DEBUG] snarkJS: Applying key: L Section: 0/1
[DEBUG] snarkJS: Applying key: H Section: 0/4
[INFO]  snarkJS: Circuit Hash:
                6b39cea9 2d2a058b 096e4cf5 f39ff7df
                66870ba3 ea9d4d40 007659e9 c6592122
                6ab6c692 3de6f62d 7609f7dd f738465e
                0807f226 7263e59c e09af79c 50b5e19c
[INFO]  snarkJS: Contribution Hash:
                20e0f314 c3a91919 8da22444 887c4ab6
                b093960c 47b24fbe 0894ee56 deb1ff3a
                a385451a a02daccd 8b954ccb 8013e382
                fef58dd6 cbd76520 5a31d9d3 58b8b9c6

Finally, we can export the verification key:

> snarkjs zkey export verificationkey eq_0001.zkey verification_key.json

We can now view the verification key file:

{
 "protocol": "groth16",
 "curve": "bn128",
 "nPublic": 1,
 "vk_alpha_1": [
  "18822731420618338224930486550872403145262587476763285064990807110752874054005",
  "21748197847981248365771460412337868182705725846208682507687994995625872579030",
  "1"
 ],
 "vk_beta_2": [
  [
   "21074817427075550121375409642139755216727358023774604706579858941421770919465",
   "18882209114691514288681727543317955730991193854379004803060105579998351557858"
  ],
  [
   "21704334076431919857151449769616260386003074776403613507536921467468045633715",
   "6695836438018292283932126445611437089361208811370137129518278716688345262650"
  ],
  [
   "1",
   "0"
  ]
 ],
 "vk_gamma_2": [
  [
   "10857046999023057135944570762232829481370756359578518086990519993285655852781",
   "11559732032986387107991004021392285783925812861821192530917403151452391805634"
  ],
  [
   "8495653923123431417604973247489272438418190587263600148770280649306958101930",
   "4082367875863433681332203403145435568316851327593401208105741076214120093531"
  ],
  [
   "1",
   "0"
  ]
 ],
 "vk_delta_2": [
  [
   "8510185836105469908075562823146551782918689630855715313829761105464255117901",
   "5885111729498348439308269673405178953968405878004952554051635443131619363995"
  ],
  [
   "8626508936902338659805112708507043539106840858159284403313228332959769367597",
   "5753651569915161631158961962205981965878176228293348692162620430354867580799"
  ],
  [
   "1",
   "0"
  ]
 ],
 "vk_alphabeta_12": [
  [
   [
    "18452944918219705961624807672689699199237181659572016531005431304192007402963",
    "10276363944763110525381798788220634871919245794239161961345385044495941078082"
   ],
   [
    "14723059146975426275007368524605506439415195898852968975514486556838627888503",
    "13922795479220840503517593083965744520320820445753059557971472529508263987545"
   ],
   [
    "13175560303031749296895751367166930187368240221049797885003722651747923014233",
    "9450054411026601149641101687500349982577456133197483505098483397394787457697"
   ]
  ],
  [
   [
    "16819763682162228089783749805520658561419387553504300549760394351216110266200",
    "14778729113331404719918708447839051694730663981104597554864438778096379028594"
   ],
   [
    "11702178386295273892297478993360215322258140783195692861752901534130443085122",
    "9698440978464597295027937662559866121939716721466626748624361084723326365891"
   ],
   [
    "19776297181566295611765299002397372077773519771886876474191520431365440726425",
    "10450705712264069463458597429060950073458072335614751401901596295987774816393"
   ]
  ]
 ],
 "IC": [
  [
   "5830490511427825038737789206889489110282870142585169083697045878425817982066",
   "7076289592061160605212396281535022384797817175018522666273627417907803681540",
   "1"
  ],
  [
   "1750535515534826074387079683016744815358814327516453133341350616882277499198",
   "16558157574953045178056433859616209258810094717106668064095694780035398623129",
   "1"
  ]
 ]
}

Generating a proof

Now we have the files that will allow us to create a proof based on our witness file:

> snarkjs groth16 prove eq_0001.zkey witness.wtns proof.json public.json

The output will be proof.json, and which contains the proof of our knowledge:

{
 "pi_a": [
  "4349167891871622965318284585066459422559348013824445996071185101667027109184",
  "13801537366633999645738880719395977534963713435009439384437996003396758542787",
  "1"
 ],
 "pi_b": [
  [
   "728631337796523090095552527161788413460696930740895571425134346423305258915",
   "12278656406679014224937679061076805130037161199041495369695898414485533885137"
  ],
  [
   "13450790836644207200516579114032656482562965369898690501988059135976319122705",
   "13600284094179733203831654799888328608998763840288278789445009437597751675936"
  ],
  [
   "1",
   "0"
  ]
 ],
 "pi_c": [
  "5411843055616040241319187201369010900159938236699876520731220349926276012063",
  "11319011742756048524468240760674760714331129969342924897163506752054932950259",
  "1"
 ],
 "protocol": "groth16",
 "curve": "bn128"
}

and public.json:

[
 "11"
]

We can also check the verification key to see that it is valid for the proof:

> snarkjs zkey verify eq.r1cs pot12_final.ptau eq_0000.zkey

[INFO]  snarkJS: Reading r1cs
[INFO]  snarkJS: Reading tauG1
[INFO]  snarkJS: Reading tauG2
[INFO]  snarkJS: Reading alphatauG1
[INFO]  snarkJS: Reading betatauG1
[INFO]  snarkJS: Circuit hash:
                6b39cea9 2d2a058b 096e4cf5 f39ff7df
                66870ba3 ea9d4d40 007659e9 c6592122
                6ab6c692 3de6f62d 7609f7dd f738465e
                0807f226 7263e59c e09af79c 50b5e19c
[INFO]  snarkJS: Circuit Hash:
                6b39cea9 2d2a058b 096e4cf5 f39ff7df
                66870ba3 ea9d4d40 007659e9 c6592122
                6ab6c692 3de6f62d 7609f7dd f738465e
                0807f226 7263e59c e09af79c 50b5e19c
[INFO]  snarkJS: -------------------------
[INFO]  snarkJS: ZKey Ok!

Verifying the proof

Finally, we can take the proof, the public value, and the verification, and prove that the proof is valid:

> snarkjs groth16 verify verification_key.json public.json proof.json
snarkJS: OK!

Using Golang for verification

Now let’s create a program in Golang which will read-in the verification key, the public value, and the proof:

package main
import (
 "fmt"
 "io/ioutil"
 "github.com/iden3/go-circom-prover-verifier/parsers"
 "github.com/iden3/go-circom-prover-verifier/verifier"
)
func main() {
 fmt.Println("zkSNARK Groth16 verify")
 proofJson, _ := ioutil.ReadFile( "proof.json")
 vkJson, _ := ioutil.ReadFile("verification_key.json")
 publicJson,_ := ioutil.ReadFile("public.json")
 public, _ := parsers.ParsePublicSignals(publicJson)
 proof, _ := parsers.ParseProof(proofJson)
 vk, _ := parsers.ParseVk(vkJson)
 v := verifier.Verify(vk, proof, public)
 fmt.Printf("%v",v) 
}

A sample run gives:

go-circom-prover-verifier
zkSNARK Groth16 prover
true

The details here:

https://asecuritysite.com/zero/zksnark04