The Magic of zkSnarks: From Equation to Verification
The Magic of zkSnarks: From Equation to Verification
With a zkSnark — a non-interactive adaptive argument of knowledge — we provide a short proof from a Prover to one or more verifiers that we have specific knowledge of some private data and of a function (f). The proof is fast to prove. So, let me take you through the steps taken to create a zero-knowledge proof with zkSnarks.
To run this tutorial, you need to first install two Node.js programs:
npm install snarkjs
npm install circomCreating the circuit
The first part of creating a zero-knowledge proof in zkSnarks is to break down the function into logical steps. This involves creating an arithmetic circuit, and which will be made up of basic arithmetic operations of addition, subtraction, multiplication, and division. In this case, we will use an equation of:
d=a²+b
and where a and b are private input values. We then want to prove that we know the result of the equation for inputs of a and b, without actually revealing a, b or d. For example, if a=3 and b=11, the answer will be:
d=3×3+11=20
Our proof would then be that we know that d=20, when a=3 and b=11 (but without giving away these values). First, we will create a circuit from this equation (from a file named mult.circom):
pragma circom 2.0.0;
template Mult() {
signal input a;
signal input b;
signal output d;
var c=0;
c = a*a;
d <== c+b;
}
component main = Mult();The arithmetic circuit is then:
Next, we can compile the circuit:
> circom mult.circom --r1cs --wasm --sym --c
template instances: 1
non-linear constraints: 0
linear constraints: 0
public inputs: 0
public outputs: 1
private inputs: 2
private outputs: 0
wires: 2
labels: 5
Written successfully: .\mult.r1cs
Written successfully: .\mult.sym
Written successfully: .\mult_cpp\mult.cpp and .\mult_cpp\mult.dat
Written successfully: .\mult_cpp/main.cpp, circom.hpp, calcwit.hpp, calcwit.cpp, fr.hpp, fr.cpp, fr.asm and Makefile
Written successfully: .\mult_js\mult.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, mult.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:
{"a": 3, "b": 11}We can also export our R1CS file into a JSON file format with:
> snarkjs r1cs export json mult.r1cs mult.json
{
"n8": 32,
"prime": "21888242871839275222246405745257275088548364400416034343698204186575808495617",
"nVars": 4,
"nOutputs": 1,
"nPubInputs": 0,
"nPrvInputs": 2,
"nLabels": 4,
"nConstraints": 1,
"useCustomGates": false,
"constraints": [
[
{
"2": "21888242871839275222246405745257275088548364400416034343698204186575808495616"
},
{
"2": "1"
},
{
"1": "21888242871839275222246405745257275088548364400416034343698204186575808495616",
"3": "1"
}
]
],
"map": [
0,
1,
2,
3
],
"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 mult_js folder, and create a witness file:
> node generate_witness.js mult.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",
"20",
"3",
"11"
]
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): tteesstt112233
[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:
60736f5b 7484eb59 1e4e57b4 22a6d71f
bdac9cf9 9d8c3583 e4b15191 2094cb2a
b5c51d30 8bc9deee e6df74f9 7e7ccf1d
89ce3c5a 06893553 16c96731 419f3fc7
[INFO] snarkJS: Next Challenge Hash:
75422bee 499a44f2 bdf6d0f5 6b32d5fa
7f8b092b 1c92a093 da1ee4da b64fc2bf
982892a1 7d23a4c3 96006c4f 971c10ee
6d2ae5dd 4a327727 94cedefd 05fdbd12
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 -vWill then create a proving and a verification key (and which are created within a zkey file):
> snarkjs groth16 setup multiplier2.r1cs pot12_final.ptau multiplier2_0000.zkeyAnd then set up 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
Next we create the keys:
> snarkjs groth16 setup mult.r1cs pot12_final.ptau mult_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 mult_0000.zkey mult_0001.zkey --name="Test Name" -v
Enter a random text. (Entropy):
Applying key: L Section: 0/2
Applying key: H Section: 0/4
Circuit Hash:
948f8091 7fa93ed2 c1459ef5 0ce43732
d86879cd 267c0625 8ea5c5da d35c6fdc
a61310cf 095f7d39 dc4d4bf9 641c7d4c
df2aae27 fa9d59dd 925d156c 8ecf506b
Contribution Hash:
6bcba108 6554a7c6 aa2bb90d 7c901871
2f0d9bc8 d6f2290b b3850a59 c0c0bdd9
8e61897b eefb0691 5863b31a 2ea8033e
2f880c29 9621d0a7 6ff6e071 007fcd4f
Finally, we can export the verification key:
> snarkjs zkey export verificationkey mult_0001.zkey verification_key.json
We can now view the verification key file:
{
"protocol": "groth16",
"curve": "bn128",
"nPublic": 1,
"vk_alpha_1": [
"4930972919657545726860728636203202889989795230486834516884623257662010190968",
"17784464477734652112678078638948832338689828495400343595590810154267715615773",
"1"
],
"vk_beta_2": [
[
"18389735958499306728010265966534631076957479993331219391194646786717212290454",
"9377762495436441301891640165839693718450498177510036079594436038367782263806"
],
[
"12918025179235334873924565184099963869927560708469813538777622359611980563600",
"9540299846849550800883433886871516082732747826796133848225752385718676233704"
],
[
"1",
"0"
]
],
"vk_gamma_2": [
[
"10857046999023057135944570762232829481370756359578518086990519993285655852781",
"11559732032986387107991004021392285783925812861821192530917403151452391805634"
],
[
"8495653923123431417604973247489272438418190587263600148770280649306958101930",
"4082367875863433681332203403145435568316851327593401208105741076214120093531"
],
[
"1",
"0"
]
],
"vk_delta_2": [
[
"6678561741832709084950120792594057740372012012476808764391217711675983692110",
"19148562476715307366333124452364601954136306739968359421280546942781306687117"
],
[
"5563686774264337713632059638379062839883993286221464997715904103056019482412",
"21833682533925220432016594073010435262143992710094235623186050651622850207784"
],
[
"1",
"0"
]
],
"vk_alphabeta_12": [
[
[
"21035614430046395676452458856349037799926906859868468846877507191464853481937",
"7367376076358797456371954886520136044173614048593332592178094606599134546984"
],
[
"5808825009653597050362562643979192678810121406759169545733784434854763413918",
"15128225491901928330780610339864969395330419807108978760255288410444914516625"
],
[
"14978815026753531164200162544695939844698822789400754850228256443689058138231",
"16113300741635819930196783951232141998238231281531753181323378044203883884342"
]
],
[
[
"8442579491476795281405460092751645692381846639953353246612942751519012569788",
"11827292701507789496064142034155273588916516375204067786052314521160910352971"
],
[
"20072517047914614006053365712147494445532735080074807478164761993842384472110",
"13665874946665444505746003584809490872324268348019328507331521810995839980467"
],
[
"10225689113248454267459923513638914637857045930066471172993596968519514548462",
"6383370432527878416577498240685833420691833124835369534381884954863421906203"
]
]
],
"IC": [
[
"18715829740044647887122344913298058336630317728738304325862477358219862297827",
"16221092531741964322070455355625510828324417870530275245397592617997280882899",
"1"
],
[
"673958305085585829783514648122080086902081959530482708587291142529753209278",
"6811756694984425962860666144580149688381174003774696142976434024786320245650",
"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 mult_0001.zkey witness.wtns proof.json public.json
The output will be proof.json, and which contains the proof of our knowledge:
{
"pi_a": [
"18179065977147657779359641627266856730189560012430348972168729148195594119398",
"4325130652974965851962487796548080753812713465953132240508427612753615137668",
"1"
],
"pi_b": [
[
"18395390851775000847122561780630950260849796100997778613417368640548299239475",
"17639909396142653244025863699056463248483166788147768144883360518935838049735"
],
[
"9408131275963864266616099995774753746213060751552818483760857814043622474916",
"8981404227605788652195858905745591103367179864186050631891035451705025332378"
],
[
"1",
"0"
]
],
"pi_c": [
"1737020500140345915930097080595151095303222939533212987558942021306795966145",
"145473143193388753772867796175071880043993095936447841945077555539388439000",
"1"
],
"protocol": "groth16",
"curve": "bn128"
}and public.json:
[
"20"
]
We can also check the verification key to see that it is valid for the proof:
> snarkjs zkey verify mult.r1cs pot12_final.ptau mult_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:
c2d18bee ad37bdb0 ff2f6443 7ba50f8a
a6ee3552 8356a79c e14ed342 58adecd3
6c5068ac f7113bbb c68d2752 9abc0a6f
9ec007a6 73401931 67d58666 5fa6b5d5
[INFO] snarkJS: Circuit Hash:
c2d18bee ad37bdb0 ff2f6443 7ba50f8a
a6ee3552 8356a79c e14ed342 58adecd3
6c5068ac f7113bbb c68d2752 9abc0a6f
9ec007a6 73401931 67d58666 5fa6b5d5
[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:
A sample run gives:
go-circom-prover-verifier
zkSNARK Groth16 prover
true
And it works, and that’s it!
Conclusions
zkSnarks are one of the hottest topics in computer science and cybersecurity at the present time and can be used to prove knowledge- such as you having a private key or your password — without actually revealing it. If we add in the power of smart contracts, we are able to create a whole new world of trust.
So, here is the full tutorial: