Greetings, Dear Reader! I embarked on my journey as an Aleo developer roughly a year and a half ago. At that time, I swiftly realized that without any knowledge of zk-SNARK technology, it would be extremely challenging to create cutting-edge private applications on Aleo, and I set myself the goal of understanding it as best I could. In that time, I have acquired a fair degree of familiarity with the world of zero-knowledge proofs and have tirelessly labored to compose this series of articles. Now, I am delighted to present to you the fruits of my labor over the past year and to share the knowledge that I have gained, and I hope that my series of articles will assist you in gaining a grasp of this technology from scratch, so you can become a proficient Aleo developer.
I anticipate approximately 10 articles in total, where we will delve from the very beginning through the history and theory to the practice, and be able to write your own zk-SNARK in Python. In a separate series, we will delve into writing applications using the Leo language.
In today’s world, trust plays a vital role — it is a key factor necessary for the functioning of markets. It is hard to miss the trend of markets toward globalization, resulting in trust issues becoming increasingly visible. Participants are forced to rely on intermediaries and formal institutions. Modern cryptography has the potential to significantly improve the efficiency of economic relationships by significantly increasing speed and reducing the resource consumption of intermediaries. One solution to this problem is zero-knowledge proofs. The theory of zero-knowledge proofs is a section of cryptography involving various algorithms designed to create proof of possession of specific knowledge without revealing the knowledge itself.
The term “zero knowledge” was introduced by MIT scientists Shafi Goldwasser, Silvio Micali, and Charles Rackoff in 1985. [GMR85] The scientists were working on theoretical systems involving two players. The first player, Prover, wins if he is able to convince the second player, Verifier, that a certain mathematical statement is true. All previous work on cryptography had focused on the idea that only the Prover player could lie, but Goldwasser, Micali, and Rackoff created a mirror challenge in which the Verifier player could not be trusted.
To illustrate the matter, consider the following example: the player Prover has a specific value x, as well as a hash with the value y=hash(x). The classical approach to proving to the player Verifier that x is such that y=hash(x) involves giving the Verifier the value of x. Verifier receives x and calculates its hash, checks the received values, and makes sure that Prover really knows such x. In their work GMR85, they present a system that allows player Prover to win without player Verifier recognizing x.
The terms ‘zero-knowledge proofs’, ‘zero-knowledge systems’, and ‘zero-knowledge protocols’ are used synonymously
In GMR85, three properties were proposed that every zero-knowledge system must meet:
Completeness — if a statement is true, an honest Verifier (one who properly follows the protocol) will be convinced of this by an honest Prover, meaning the system must be logically complete.
Soundness — if a statement is false, no deceitful Prover can convince an honest Verifier that it is true, except for a small probability.
Zero-knowledge — if a statement is true, no Verifier learns anything beyond the fact that the statement is true. In other words, knowing the statement (not the secret) is sufficient to imagine a scenario showing that the Prover knows the secret. This is formalized by demonstrating that every Verifier has some simulator that, given only the statement to be proved (and no access to the Prover), can create a transcript that “looks like” an interaction between an honest Prover and a given Verifier.
It is very important to correctly interpret what proof is in the context of zero-knowledge and how it differs from a conventional mathematical proof.
A mathematical proof is an inferential argument for a mathematical statement, showing that the given logical assumptions guarantee the conclusion. The argument may utilize other previously established theorems, but in principle, every proof can be constructed using only certain fundamental or original assumptions known as axioms [WMP]. For example, a proof that a subset of a countable set is also countable.
Proof of knowledge goes beyond mathematical proof and relies only on what the Prover knows. For example, a proof of knowledge of the factorization of a certain number N.
As one can see, a proof of knowledge differs from a generally accepted mathematical proof. In the case of factorization, a proof of facts would say that number N can be decomposed into factors, while a proof of knowledge would say that I know exactly how to decompose it into factors. Therefore, it is the player’s epistemic conviction of the truth of the given statement that is crucial, rather than its actual truth. Thus, the pragmatic aspect of the given situation is important here.
In GMR85, a cryptographic protocol is considered — a set of defined rules and conventions consisting of cryptographic algorithms, often sequences of cryptographic primitives. The protocol is based on a set of rules governing the use of cryptographic transformations and algorithms in information processes for exchanging messages between two or more participants, as well as a description of the structures used. An important property is that the protocol GMR85 operates on the example of the vertex coloring problem, which is an NP-complete problem. Knowing that the vertex coloring problem is an NP-complete problem and the NP-completeness property that we can transform any NP problem into an NP-complete problem, we can conclude that this protocol can be applied to any problem from the NP class. Informally speaking, having a problem that can be answered ‘yes’ or ‘no’ in polynomial time, we can transform it into the form of a vertex coloring problem and run the GMR85 protocol, which will allow us to obtain a zero-knowledge proof for our solution. That there exists a zero-knowledge proof for any NP-complete problem and that, using one-way functions, one can create correct cryptographic protocols has been proven by Oded Goldreich, Silvio Micali, and Avi Wigderson in [GMW91].
The application of the GMR85 protocol in the real world is difficult because the described scheme for creating a zero-knowledge proof is interactive. Interactivity means that the Prover and Verifier must cooperate in order for the Prover to convince the Verifier that he possesses certain knowledge. Taking into account that this approach is itself costly (transforming the NP problem into a graph coloring problem and running the protocol on it), its application in the real world becomes very limited. This is because in order to prove knowledge not to one Verifier but to a certain group, we would have to run the protocol individually for each Verifier in the group. Moreover, if the Prover player were a client and the Verifier player were a server, the server would always have to be online, which also creates a number of difficulties.
To solve this problem, Non-Interactive Zero-Knowledge Proofs, which I will further refer to as NIZK— have been developed. NIZK, unlike interactive proofs, do not require interaction between the Prover and Verifier, allowing the Prover player to publish their proof and the Verifier player to check it at any time.
To illustrate the matter, consider the following example of the Schnorr identity scheme developed by Claus-Peter Schnorr in 1990 [Sch]. Let’s say the Prover player has published his public key and wants to convince the Verifier player that this key truly belongs to him. The fact that the public key belongs to the player means that the player knows the private key, which can be used to obtain the public key according to a previously specified scheme. The Prover player wins if the Verifier player is able to confirm that the given public key belongs to the Prover player without revealing any information about the private key.
The public key has the following format:
where g is a generator of a cyclic group of order q, i.e. all elements of the group are powers of the generator.
A cyclic group is a group generated by a single element, called its generator. This means that by repeatedly performing the group operation on the generator or its inverse, any element of the group can be obtained; in multiplicative notation, elements are powers of the generator, and in additive notation, they are multiples of it. [WCG]
Let p be a prime number and a be the private key of the player Prover, randomly chosen in the range (1, q). The protocol is characterized by the interaction between the Prover and Verifier, during which specific values are generated that allow for the mathematical proof of possession of the private key from which the public key was generated. The protocol proceeds as follows:
The player ‘Prover’ selects a random k within the range (1, q) and sends h to the player ‘Verifier’ such that h = g^k mod p.
The player ‘Verifier’ then selects a random c (challenge) within the range (1, q) and sends it to the player ‘Prover.’
The player ‘Prover’ returns s to the player ‘Verifier’ such that s = ac + k mod q.
The player ‘Verifier’ verifies that g^s = PK_A^c * h mod p.
This scheme works because
This scheme is also an example of interactive proof. Let’s consider a modification of it that clearly demonstrates the transition from interactivity to non-interactivity. The modified non-interactive scheme looks as follows:
The player ‘Prover’ selects a random k within the range (1, q) and calculates h such that h = g^k mod p.
The player ‘Prover’ calculates c (challenge) such that c = H(g^k), where H is a hashing function.
The player ‘Prover’ calculates s = ac + k mod q and publishes it as proof.
The credibility of this proof relies on the assumption that the hashing function is idealized and is truly random, and that the values of c cannot be predicted in advance.
In this way, the player ‘Prover’ can publish the required parameters, and any ‘Verifier’ within the group can verify that the specified public key belongs to the player ‘Prover’.
There exist a variety of non-interactive proof protocols. The most prominent among them are:
zk-SNARKs — zero-knowledge Succinct Non-interactive ARgument of Knowledge
zk-STARKs — zero-knowledge Succinct (Scalable) Transparent ARgument of Knowledge
Bulletproofs
Additionally, there are also:
SNORK — Succinct Non-interactive Oecumenical (Universal) aRguments of Knowledge
PLONK
Marlin
Sonic
FRI-STARK
SuperSonic
Fractal
Many of them are currently actively being developed and are modifications of their predecessors, deriving from zk-SNARK, which currently finds the widest application in practice due to its stability, low computational cost, and proof size.
The following table presents a comparison of the computational complexity of the most popular protocols. [Nad][Wil]
According to this data, zk-SNARK has an advantage in terms of the computational complexity of the proof, verification, and proof size, but it loses in such things as cryptographic assumptions and trusted setup. Let’s consider the disadvantages of zk-SNARK in more detail:
Cryptographic assumptions are certain mathematical assumptions. For example, the issue of collisions in SHA-256, where theoretically it could be proved that collisions should exist, but no one was able to find them in practice. Cryptographic assumptions are statistical in nature, small probabilities are considered negligible, regarded as insignificant, or even non-existent. Typically the weaker they are, the better. The key cryptographic assumption of the zk-SNARK algorithm is the knowledge of exponent (KoE):
The zk-SNARK algorithm operates on elliptic curve cryptography. In order to enforce the ‘Prover’ player to properly follow the protocol, values are used in pairs — having the pair of points (P, Q), where point Q = α * P (let’s call this pair of points the α-pair), under the condition that we don’t know α, obtaining another α-pair (R, S), where S = α * R is only possible if and only if the pair (P, Q) is scaled by a certain factor r and nothing else. Therefore, R = r * P, S = r * Q. This property enforces the ‘Prover’ player to use true values.
In the algorithm, it is very important to convince that the parameter α is truly unknown. Knowing this parameter, one can create fictional proofs of nonexistent knowledge. Therefore, another drawback of this algorithm appears in the form of the need for a ‘Trusted Setup’.
The essence of the ‘Trusted Setup’ is that the parameters necessary for creating the proof, such as the α parameter discussed above, are created in advance. These parameters are called the Common Reference String (CRS). This process can be considered as creating a secret that is known only by the system. There are zero-knowledge proof constructions that do not require a ‘Trusted Setup’ such as zk-STARK and Bulletproofs. However, as previously discussed, zk-SNARK is significantly better in terms of size and verification speed. Particularly interesting for decentralized systems is the constant-time verification of zk-SNARK. This means that regardless of the size of the claimed statement, the amount of work that the ‘Verifier’ has to perform to verify the proof remains the same. For this reason, zk-SNARK remains the preferred tool for many privacy-oriented blockchains such as Aleo. However, the security of these systems largely depends on how the CRS was constructed. Of course, creating these parameters in a reliable, centralized manner is possible, but it is inconsistent with the goal of decentralization. So far, the preferred technique used in zk-SNARK setup ceremonies has been multiparty computation (MPC). The goal of these algorithms is to ensure that the CRS is generated in a decentralized manner so that no participant knows the mathematical structure of the computed CRS. In this case, they try to maximize the number of participants to reduce the infinitesimal probability that all participants do not destroy the parameters used to generate, which are also referred to as toxic waste.
The main problem with early CRS generation algorithms was that they required a predefined number of people in advance, which made them difficult to apply in practice. However, in 2017, Sean Bowe, Ariel Gabizon, and Ian Miers in their article “MMORPG” [BGM19] described a variant of RPP ceremony for Groth16 that consists of two phases. The first phase, called “Power of Tau” (as shown in Fig. 1.1), can be scaled and have an arbitrary number of participants. The second phase directly converts the results of the “Power of Tau” phase into CRS.
This approach solves the aforementioned problem, but has a drawback in that each contributor must contribute in a strictly defined order which may elongate the process by weeks. However, Justin Drake proposed an approach called “Optimistic Pipelining”. This means that the participants could contribute simultaneously, significantly reducing the duration of the operation. The general scheme of such an approach is presented in Fig. 1.2. It can be seen that the Trusted Setup is divided into several separate phases, whereas 3 contributors can contribute simultaneously.
Despite the need for a ceremony being the main drawback of zk-SNARK, the algorithm remains an industry standard due to its high performance, and various CRS generation studies have made it easy and accessible to most people. For example, CRS generation effort is being made for Aleo project, in which at the time of writing notes for articles 2058 people participated with a total contribution of 3.29 TB and an average contribution time of 4.02 hours per participant, which suggests that the drawbacks of the zk-SNARK algorithm can be overlooked. At the time of writing, I personally conducted a contribution that took 9 days of waiting in queue and 43.2 minutes of generation.
With this, we have concluded the first article in the series. In the next one, we will delve deeper into the theory of zk-SNARK and its fundamental components, so that after a few articles we can gather these fundamental components together and obtain the proof itself.
For those who are reading this among the first, I promise to publish new parts no less than once a week or two, See you soon!
[GMR85] — Shafi Goldwasser, Silvio Micali i Charles Rackoff. The Knowledge Complexity of Interactive Proof-systems. 1985.
[Sch90] — Claus-Peter Schnorr. “Efficient Identification and Signatures for Smart Cards”. W:(1990).
[GMW91] — Oded Goldreich, Silvio Micali and Avi Wigderson. “Proofs that Yield Nothing But their Validity or All Languages in NP have Zero-Knowledge Proofs”. W: (1991). https://www.wisdom.weizmann.ac.il/∼oded/gmw1.html
[Nad] — Elena Nadilinski. Demystifying Zero Knowledge Proofs. https://docs.google.com/presentation/d/1gfB6WZMvM9mmDKofFibIgsyYShdf0RV_Y8TLz3k1Ls0
[Wil] — Zooko Wilcox. Privacy for Everyone. https://slideslive.com/38911617/privacy-for-everyone