Introduction
Zero-knowledge Succinct Non-interactive Arguments of Knowledge (zk-SNARK) is the genuinely innovative way of showing that something is true without giving any other information. The question here is, "why is it useful in the first place?".
Zero-knowledge proofs are applicable to a wide variety of situations, including proving an assertion about private information, anonymous authorization, anonymous payments, and outsourcing computation.
The underlying method is a "marvel" of mathematics and cryptography that has been studied for the past four decades, starting with its introduction in 1985 in the principal work "The Knowledge Complexity of Interactive Proof-systems" [1] and the subsequent introduction of non-interactive proofs [2] that are especially important in the context of blockchains.
In every zero-knowledge proof system, there is a prover who wants to persuade a verifier that a statement is true while giving no other information. For example, Bob is given a hash H of some value and wants to know if Alice knows what value s hashes to H. Normally, Alice would demonstrate this by handing s to Bob, who would then compute the hash and compare it to H. Assume, however, that Alice does not wish to expose the value s to Bob; instead, she simply wants to demonstrate that she is aware of the value. She can do this with a zk-SNARK. A procedure should have three characteristics:
- Completeness — if the statement is true, then a prover can convince a verifier.
- Soundness — a cheating prover can not convince a verifier of a false statement.
- Zero-knowledge — the interaction only reveals if a statement is true and nothing else.
The zk-SNARK word was first used in From Extractable Collision Resistance to Succinct Non-Interactive Arguments of Knowledge, and Back Again, which built on Short Pairing-Based Non-interactive Zero-Knowledge Arguments and followed the Pinocchio protocol Quadratic Span Programs and Succinct NIZKs without PCPs and Pinocchio: Nearly Practical Verifiable Computation, making it useful for general computing.
Alibaba's cave
The core notions of zero-knowledge proofs are presented in a well-known narrative first published by Jean-Jacques Quisquater and colleagues in their work "How to Explain Zero-Knowledge Protocols to Your Children." In a zero-knowledge proof, the two parties are commonly referred to as Peggy (the prover of the proposition) and Victor (the verifier of the statement).
Peggy has discovered the secret word that can be used to open a magical cave door in this narrative. The cave is in the shape of a ring, with the entrance on one side and the magical door on the other. Victor is curious if Peggy knows the secret word; however, Peggy, a very private person, does not want to expose her knowledge (the secret word) to Victor or the fact of she knew to the public at large.
From entrances A and B, they designate the left and right routes. Victor first waits outside the cave while Peggy enters. Victor cannot see whatever path Peggy takes; therefore, he doesn't know which one she takes. Victor then enters the cave and yells the name of the road he wants her to take back, either A or B, which he chooses randomly. If she truly understands the magic word, this task is simple: she opens the door, if necessary, and returns along the intended path.
Assume, however, that she was unfamiliar with the term. She would thereafter be allowed to return by the named way only if Victor gave the name of the same path she had entered. She would have a 50% chance of guessing right since Victor would choose A or B at random. If they repeated this technique 20 times in a row, her chances of correctly anticipating all of Victor's requests would become vanishingly small (1 in 220, or roughly 1 in a million).
Thus, if Peggy repeatedly appears at the exit Victor names, he can conclude that it is extremely probable that Peggy does, in fact, know the secret word.
Principles of zkSNARK
A zk-SNARK consists of three algorithms, G, P, and V, defined as follows:
The key generator G generates two publicly available keys, a proving key pk, and a verification key vk, using a secret parameter lambda and a program C. These keys are public parameters that must be generated only once for each program C.
The proving key pk, a public input x, and a private witness w are all inputs to the prover P. The procedure creates proof that the prover knows a witness w and that the witness meets the program, prf = P(pk, x, w).
V(vk, x, prf) is a verifier that returns true if the proof is correct and false otherwise. As a result, if the prover knows a witness w, C(x,w) == true, this method returns true.
Take note of the generator's secret parameter lambda. This setting can make using zk-SNARKs in real-world applications difficult. This is because anyone with knowledge of this parameter can create bogus proofs. A person who knows lambda can build a proof fake prf such that V(vk, x, fake prf) evaluates to true without knowing the secret w, given any program C and public input x.
As a result, actually running the generator necessitates an extremely safe procedure to ensure that no one discovers and stores the parameter elsewhere. This motivated the Zcash team's extensive ceremony for generating the proving key and verification key while ensuring that the "toxic waste" parameter lambda was destroyed.
Circom (Circuit Compiler) and snarkjs
Circom is a new domain-specific language for constructing arithmetic circuits, as well as a Rust-based compiler for it.
CircomLib is an open-source template library, freely available to practitioners and developers made by iden3. A number of circuit templates in the collection operation have been analyzed and proved by the iden3 research team.
SnarkJS written in Javascript and Pure Web Assembly, wasmsnark written in native Web Assembly; and rapidSnark written in C++ and Intel Assembly are all implementations of the proving systems accessible in iden3's libraries. RapidPLONK and a run-time architecture for ARM processors are currently in development.
circom and snarkjs are both indispensables when constructing a zkSNARK system.
To install circom and snarkjs, run:
npm install -g circom
npm install -g snarkjs
zkutil is a new tool to work with zkSNARK circuits generated by circom compiler, which can help generate proof and verify a lot easier.
To install zkutil, run:
curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh
cargo install zkutil
An example of zkSNARK
Let's design a circuit to prove that we can factor an integer c when installing circom and snarkjs. First, we need to create a circuit needed to verify that we know two numbers (let's call them a and b) that multiply to give c while keeping a and b hidden. A circuit is equivalent to a statement or deterministic program that has an output and one or more inputs for our purposes.
There are two types of inputs in a circuit: private and public. The difference between them is that a private input is hidden from the person validating the statement's accuracy (the verifier). The concept is that given a circom circuit and its inputs, we can run it and provide proof that we ran it correctly using snarkjs. Then, we can prove to the verifiers that we know one or more private inputs that satisfy the circuit's requirements using the proof, the output, and the public input(s), without exposing anything about the private input (s). In other words, even if the verifier does not know the circuit's secret inputs, the proof, output, and public input(s) will suffice to persuade her that our statement is true (hence the term zero-knowledge proof). Now that we know what a circuit is and why it's useful.
Let's start by designing one.
Create a new file named circuit.circom with the following content:
template Multiplier() {
signal private input a;
signal private input b;
signal output c;
c <== a*b;
}
component main = Multiplier();
To make the process easier, we will use zkutil - a tool to work with zkSNARK.
Let's say we have an input file input.json which looks like this:
{"a" :3, "b":11}
Run the following command to perform a complete zkSNARK process:
circom circuit.circom —-rw # Compile the circuit, generate file circuit.json
zkutil setup # Generate a local trusted setup, generate file params.bin
snarkjs calculatewitness # Calculate witness from input.json, generate file witness.json
zkutil prove # Generate a snark proof, files proof.json, public.json
zkutil verify # Verify a proof, return whether the proof is correct or not
zkutil generate-verifier # Generate a solidity verifier contract Verifier.sol
zkutil export-keys # Export keys to snarkjs/websnark compatible format, file proving_key.json and verification_key.json
References
[1] Introduction to zk-SNARKs, consensys.net, accessed July 25th, 2022.
[2] Iden3 Documentation, docs.iden3.io, accessed July 26th, 2022.