Fundamentals: What Are Zero-knowledge Proofs?

One of the most exciting developments in the blockchain space is the broad adoption of zero-knowledge proofs (ZKPs). This technology offers superior transparency, immutability, and privacy, but how exactly do ZKPs do this?

In the past decade, blockchain technology has been recognized for its numerous applications in a wide range of sectors. Whether we are discussing the health sector, logistics, automobile production, it seems that everyone has a use-case for blockchain technology. The immutable nature of blockchain solutions, paired with their transparency and decentralization, is nothing short of disruptive, not surprisingly making it one of the most discussed technological developments of recent years. In our day and age, in light of the numerous scandals associated with Web 2.0 titans, privacy has become a core axis of discussion when considering the future of the Internet. In this article, we will explore zero-knowledge proofs and their incredible potential for safeguarding our privacy.

Zero-knowledge Proofs (ZKPs) to the Rescue

Zero-knowledge proofs (ZKPs) have come to the forefront as one of three possible solutions to ensure the privacy of the information exchanged on the blockchain. The other ones are secure multi-party computations (sMPC) and trusted execution environments (TEE). All three of these methods ensure the privacy of information exchanged on the blockchain. Each of these methods possesses different use cases, limitations, and technical specifications. So what exactly is a ZKP? This cryptographic primitive allows one party to prove the knowledge of certain information to the other party without revealing the data in question. A well-known analogy for these concepts comes in the form of cryptography’s most famous celebrity couple, Alice and Bob.

We can illustrate this more colorfully with the following visual guide!

Before we go deeper on why ZKPs may be the answer to this industry challenge, let’s take a walk down memory lane on the story behind these concepts. ZKPs have a story that predates blockchain by several decades. First conceptualized in 1985 by a team of scientists consisting of Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The elegant genius of the solution presented by the intrepid researchers allowed for exchanging “knowledge about knowledge” between a prover and verifier without sharing any sensitive information that both parties want to keep secret. To achieve this goal a zero-knowledge proof must meet three conditions.

1. Completeness: a true statement will result in an honest verifier (one who follows the protocol properly) to be confident of the truthfulness of the facts as an honest prover presents it.
2. Soundness: there is a negligible chance that an honest verifier will accept a false statement put forward by a dishonest prover.
3. Zero-knowledge: a true statement will not reveal any additional information besides the truthfulness of the statement. The statement itself is proof of the secrets truthfulness. It requires no other interaction between the prover and verifier.

The Different Types of Zero-Knowledge Proofs

The crucial feature of ZKPs involves that both parties may verify the truthfulness of a piece of information while remaining ignorant of the contents of the proven information. Alice proves that she knows X to Bob, and even Bob doesn’t learn anything about the contents of X, let alone any third party! This makes employing ZKPs ideal for numerous real-world solutions. It also explains why this privacy-enhancing feature is making waves in the blockchain community.

The original theory presented by Shafi Goldwasser, Silvio Micali, and Charles Rackoff has been expanded upon by subsequent researchers. Years of research resulted in a broad family of security solutions. Before we look at the various developments in this field, we should first point out that there are two main types of ZKPs in existence. These are interactive zero-knowledge proofs in which the prover and verifier interact multiple times. The verifier “challenges” the prover to prove knowledge of a fact multiple times. The process continues until the verifier is confident that the prover has been truthful. The opposite of this procedure are non-interactive proofs. They require the two parties to exchange a single transaction that proves the truthfulness of the prover only once.

The Vibrant World of Privacy-Enhancing Arguments

If you’ve hung out in the blockchain space long enough, you’ve probably encountered the terms zk-SNARKS and zk-STARKS. These are two privacy-enhancing methods that employ a variation on ZKPs. Formally, ZK-SNARKs and STARKs are not exactly ZKPs, as they provide slightly weaker guarantees, although this fact is irrelevant for most real-world applications. Because of this, we treat ZK-SNARKs and STARKs as a subclass of ZKPs. Both zk-SNARKS and zk-STARKS are examples of “non-interactive zero-knowledge arguments.” Such a classification makes them similar to non-interactive ZKPs — as we described above, but are slightly better suited for practical applications. It is critical to understand that at this point, there is a plethora of different constructions of these non-interactive zero-knowledge arguments. The most famous ones are zk-SNARKS and zk-STARKS, but we shouldn’t forget about Sonic, PlonK, Marlin, and others.

All of these solutions have a role to play in various blockchain projects. Let’s shortly explore the differences between these privacy-enhancing methods!

1. zk-SNARK: this acronym stands for zero-knowledge succinct non-interactive argument of knowledge and is the oldest construction of non-interactive ZKPs. First formulated in 2012 at UC Berkeley by Alessandro Chiesa, zk-SNARKS employ a mathematical concept known as a bilinear pairing over an elliptic curve as the basis for their security. An important property of zk-SNARKS is the requirement of a trusted setup. This process entails the creation of cryptographic keys that represent the proofs required for verification and conducting private transactions. A hidden parameter links the verification key and the key that conducts the transactions during key creation. There is potential for a security breach at this stage. For example, if we suppose the secret that is linked to the keys is not destroyed at this stage, it can then be used to falsify the verification and transaction process without anyone knowing about the duplicitous nature of such transactions. Even though the trusted setup occurs only once throughout the process, it is still a cause for concern among users. Another weakness of this security solution is its vulnerability towards quantum computing. Once quantum computers are widely available, the security features presented by zk-SNARKS will be void.
2. zk-STARK: stands for zero-knowledge scalable transparent argument of knowledge and is a more recent addition to the ZKP family of proofs. Collectively discovered by Eli Ben-Sasson, Iddo Bentov, Yinon Horeshy, and Michael Riabzev, they based their invention on hash functions. This feature gives zk-STARKS an instantaneous advantage over zk-SNARKS, as the former guarantees protection against quantum computing. Despite the added security, a significant disadvantage of zk-STARKS is the larger poof size requiring users to possess more computing power and higher gas fees.
3. Sonic/Marlin: this solution emerged with the intention of solving scalability issues. One of Sonic’s advantages lies in its use of smaller global parameters. Because of these qualities we can store, update, and verify Sonic’s parameters at a lower cost. Additionally, all of this happens without specialized gear; even a humble laptop will do.
4. PlonK: this acronym stands for Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge (quite the mouthful). PlonK is a variation of the Universal Zero-Knowledge proof algorithm. By being universal, PlonK only requires that a trusted setup occurs once.

Blockchain Applications for zk-SNARKS and zk-STARKS

Due to the fact that zk-SNARKS had a six-year head-start on zk-STARKS, it comes as no surprise that they have found a wider base of adoption. The first application of zk-SNARKS came in the guise of the Zcash blockchain. Other blockchains followed suit, which resulted in a healthy dose of research and development that ironed out many of the initial challenges faced by this ZKP solution. Ethereum, for example, is heavily invested in zk-SNARKS research. One of the advantages of this solution was the small proof size which resulted in very fast verification results.

Despite the initial success, the aforementioned security concerns have turned the spotlight on zk-STARKS. One of the pioneers in developing zk-STARKS solutions is STARKWARE. Recently, they benefited from a $12 million grant offered by the Ethereum Foundation to continue exploring this promising technology. Besides offering resistance against the rise of quantum computing, zk-STARKS also replace the controversial trusted setup procedure. In lieu of a trusted setup zk-STARKs offer publicly verifiable randomness that results in a trustlessly verifiable computation system. Improved scalability is also something to look forward to as zk-STARKS will allow developers direct computations and storage off-chain. These off-chain solutions will be able to create STARK proofs that respect the integrity of off-chain transactions.

Aleph Zero and zk-SNARKS

Employing ZKPs is one of the legs upon which the Aleph Zero platform ensures the privacy of its users, the other one being sMPC. Together these two cryptographic primitives complement each other, offering state-of-the-art security for protocol users. By employing this combination, we can guarantee speed and limited privacy by using zk-SNARKS, and in cases that require even more stringent safeguards, sMPC has our backs. Secure multi-party computation allows for the secure storage of data off-chain on several nodes. Access to the data occurs only if all nodes conduct a secure handshake among themselves. This practice ensures that a single malicious actor cannot gain access to the secured information.

“The basic underlying idea was to allow users to update their internal state and then validate […] updates with SNARKs against the blockchain […]. […] Every user will have their own internal state, which will, for example, write down how many tokens of each kind the user has. And whenever a user would like to transact with either another user or with a smart contract, there will be an update of this internal state, which will be validated with a SNARK against […] the blockchain, without revealing what actually happens.”

Adam Gągol, Co-founder, CTO

Aleph Zero has opted for a thoroughly software-based solution to these challenges. This will help clients from becoming trapped due to vendor lock-in while saving costs on maintenance and operations. It will also ensure that trust issues between the client and the hardware vendor don’t arise.

Why Do We Need Zero-knowledge Proofs?

Every day we are coerced into situations where we are forced to forego our privacy as website after website requests that we reveal our private data. Despite all of us participating willingly in these practices, many of these services are nothing short of essential nowadays rendering us without a choice regarding how we approach privacy matters. As a civilization, we have essentially been stripped of all decision-making power regarding what is done with our information. This information is later traded among tech giants. A state of affairs that follows the wisdom of the saying, “if something is free, you’re the product.”

The last few years brought about a debate regarding this dearth of privacy and what can be done to ensure that the exchange of information between two or more parties is limited at best. The application of ZKPs presents an avenue towards greater independence. It is time to wrestle back the right of being able to choose who we deal with and how much information we disclose.

*This article was originally published on the Aleph Zero Blog on March 8th, 2022. Find the original article here.