Zero-knowledge proofs (hereafter ZKPs) are becoming quite popular in the blockchain space. You can get a basic understanding from our previous article on ZKPs here. This article takes further steps to explain ZKPs and the working principle of the zk-SNARK in the area of verified computing.
Authentication is one of the most important and complicated challenges in blockchain and cryptography, similar to digital signatures. There are two ways to solving the leakage of private information:
- Not revealing the information in the first place, but this is not always possible
- Avoiding the exposure of the information by giving proof of knowledge.
The latter is a cryptographic protocol referred to as Zero-Knowledge. A ZKP provides an answer that does not reveal the exact information requested but proves to be able to solve the underlying problem.
The goal of ZKPs is for a verifier to be convinced that a prover possesses the knowledge of a secret parameter, a witness which satisfies a relation, without revealing the witness to the verifier or anyone else. Mathematically, a prover $P$ ****claims to know a witness $w$ ****which satisfies a property of a designated output $y$ ****of a cryptographic hash function $h$ ****such that:
$h(w) = y$
This SNARK technology can be adopted in several scenarios such as the following:
- Authentication
- for example, authenticating virtual machines on a computer network
- Proving statement made about private data
- for example, person A has more than amount X in their bank account
- Anonymous authorization
- for example, proving that person A has the right to access the restricted part of a website without revealing their identity
- Anonymous payments
- for example, paying taxes or other kinds of payment without revealing identity or earnings
- Private transactions on a public blockchain
- for example, tornado cash or private dApps like Aleo
Due to these different possible applications, there are many ways to implement a ZKP. They are categorized into two types:
- Interactive ZKPs
- Non-interactive ZKPs
This article focuses on the Non-interactive ZKPs or zk-SNARKs.
What is a zk-SNARK?
Zero-Knowledge Succinct Non-interactive Arguments of Knowledge (or zk-SNARK) is a method of proving that something is true without revealing further information.
- Succinct means that the zk-SNARK proof must be shorter than the witness w.
- Non-interactive means that the proof is static and can be posted on a read-only website
- Argument of Knowledge means that if the prover p can’t break a cipher cryptosystem, then they must know w to produce a convincing proof.
An example use case of zk-SNARK
Assuming you are in possession of a dataset whose digest string is publicly known, and you want to convince people to know that you own it, you have two options:
- Publish the dataset; if the hashes are equal, then everyone will be convinced. This is only if you want to reveal the dataset.
- Implement the hash function as a zk-SNARK, which is only possible if you know the dataset.
Now that we have learned about the use cases of zk-SNARKs, let’s see how to create one.
How to create a zk-SNARK
This section will introduce the steps involved in constructing a zk-SNARK for a particular use case. Technically, you have a computer program writing in a general purpose programming language such as C++, Rust, or Go. The program collects the witness w as input, applies a hash function h to it, and checks that the output equals y.
Appling a SNARK to a program can’t be done directly unless the program is converted into an equivalent model amenable to probabilistic checking. This refers to a type of circuit satisfactory instance like the R1CS.
The program is initially broken from the logical steps into smaller bits of operations, resulting in an arithmetic circuit. This breaks the program into steps consisting of common arithmetic operations of addition, subtraction, multiplication, and division. As an example, the cubic equation:
$x^3 + x + 5 = 35$
can be converted to a program:
“`Go
func arithmeticCircuit(x int) int {
y := x**3
return x + y + 5
}
“`
This process is called Flattening. The resulting program only supports basic arithmetic operations, indicial exponentiation, and variable assignment; all of which is sufficient in representing any bounded computation. The resulting program is a series of decipherable statements that can be likened to logic gates in an electric circuit.
This transformation from the program to the arithmetic circuit is called the front end of the system. Afterwards, the Rank 1 Constraint System (R1CS) is built to check that the right direction is used in the arithmetics. The R1CS is a group of three vectors with a single vector as it’s solution such that if
- s is the solution vector
- a, b, and c are the three vectors
- then s . a * s . b – s . c = 0.
The next step involves converting the R1CS to a Quadratic Arithmetic Program form having the same logic as the program, but uses polynomials instead of the dot notation above.
The final step is to then run a SNARK — the probabilistic proof system — for circuit-satisfiability again. This is referred to as the back end of the system. Example SNARKs include Groth 16, Marlin, PlonK, Ligero, Hyrax, etc.
Developing zk-SNARKs for circuit satisfiability
SNARKs are designed in almost the same steps. The exempted ones are the linear-PCP based SNARKs like GGPR13, the Groth16, Pinocchio, etc. which are among the first main practical implementations of zk-SNARKs. The steps, however, include:
- Design a polynomial IOP for R1CS or circuit-satisfiability,
- Combine the polynomial IOP with a polynomial commitment scheme; the combination will give a succinct but interactive argument,
- Remove the interaction using the Fiat-Shamir transformation to get a static proof.
Conclusion
With zk-SNARKs, a company can hide the code logic of their smart contracts. An example of such companies is Aleo, which allows you to deploy dApps without knowing the underlying logic of the smart contract. zk-SNARKs can also be used in Compliance applications like in proving solvency or in zero-knowledge taxes.
While real numbers are used in this article to aid understanding, real world adoption involves finite field elements that are more complex than the example here. This is why zk-SNARKs are referred to as the spooky moon math.
zk-SNARK technology can help reduce the storage size required by modern blockchains by a significant margin.