From The Beginning: Zero-Knowledge

Published in

Occam.fi

8 min readAug 31, 2022

This article is the first in a series which will cover the totality of Zero-Knowledge (ZK) proofs, SNARKs, STARKS, and everything in-between! This article specifically will give a history of ZK in general use and then its history specifically within cryptocurrencies. Let’s begin!

What’s a ZKP?

In general, ZKP refers to either a zero-knowledge proof or zero-knowledge protocol. Regardless, both are the methods by which one party (the prover) can prove to another party (the verifier) that a given statement is true. All while the prover avoids conveying any additional information apart from the fact that the statement is indeed true.

The essence of ZKPs is that it is trivial to prove that one possesses knowledge of certain information by simply revealing it. The challenge is to prove such possession without revealing the information itself or any additional information.

The world of ZKPs is populated with many different protocols. All of these protocols are broken down into four categories: Succinct Non-Interactive ARguments of Knowledge (SNARK), Scalable Transparent ARgument of Knowledge (STARK), Verifiable Polynomial Delegation (VPD), and Succinct Non-interactive ARGuments (SNARG). The most popular ZKPs are SNARKs and STARKs. Before we dive any deeper, we’ll wind the clock back and figure out how ZKPs first came about!

Where Did ZKPs Come From?

The ZKP was initially conceived back in 1985 by three Computer Scientists: Shafi Goldwasser, Silvio Micali (Founder of Algorand) and Charles Rackoff in their paper “The Knowledge Complexity of Interactive Proof-Systems”. The paper introduced the Interactive-Proof hierarchy of IP systems and conceived the concept of knowledge complexity: a measurement of the amount of knowledge about the proof transferred from the prover to the verifier.

These scientists also gave the first ZKP for a concrete problem, deciding the quadratic nonresidues mod m. Then with a paper by Laszlo Babai and Shlomo Moran, the landmark paper invested interactive proof systems for which all five of the authors would go on to win the first Gödel Prize (an annual prize for outstanding papers in the area of theoretical computer science) in 1993.

Next, Oded Goldreich, Silvio Micali, and Avi Wigderson took it one step further, showing that, assuming the existence of unbreakable encryption, one can create a zero-knowledge proof system for the NP-complete graph colouring problem (way of colouring the vertices of a graph such that no two adjacent vertices are of the same colour) with three colours. Since every problem in NP (nondeterministic polynomial time — a complexity class used to classify decision problems) can be efficiently reduced to this problem. This means that under this assumption, all problems in NP have zero-knowledge proofs. The reason for the assumption is that, as in the above example, their protocols require encryption. A commonly cited sufficient condition for the existence of unbreakable encryption is the existence of one-way functions, but it is conceivable that some physical means might also achieve it.

On top of this, the gentlemen mentioned above also showed that the graph nonisomorphism problem, the complement of the graph isomorphism problem (the computational problem of determining whether two graphs are a bijection between their vertex sets), has a zero-knowledge proof. This problem is in co-NP but is not currently known to be in either NP or any practical class.

More generally, Russell Impagliazzo and Moti Yung as well as Ben-Or et al. would go on to show that, also assuming one-way functions or unbreakable encryption, there are zero-knowledge proofs for all problems in IP = PSPACE. In other words, anything that can be proved by an interactive proof system can be proved with zero knowledge.

Not liking to make unnecessary assumptions, many theorists sought a way to eliminate the necessity of one-way functions. One way this was done was with multi-prover interactive proof systems which have multiple independent provers instead of only one. This allows the verifier to “cross-examine” the provers in isolation to avoid being misled. It can be shown that, without any intractability assumptions, all languages in NP have zero-knowledge proofs in such a system.

To bring this more currently in line with recent developments of cryptocurrencies, in an internet-like setting where multiple protocols can be executed concurrently, building ZKPs is more challenging. Along this line of research, the development of witness-indistinguishable proof (WIP) protocols came about. The property of these WIPs is related to that of ZK, yet WIPs do not suffer from the same problems of concurrent execution. However, in WIPs the ZK condition is weakened and the only guarantee is that the verifier will not be able to distinguish between provers that use different witnesses. In particular, the protocol may leak various forms of information about the witnesses.

A final popular variant to come out of these papers is the non-interactive ZKPs. Blum, Feldman and Micali were able to show that a common random string shared between the prover and the verifier is enough to achieve computational ZK without requiring interaction.

In The Realm of Cryptocurrencies

The first currency to truly popularize ZK within the sphere of cryptocurrencies was Zcash and their zk-SNARKs approach to cryptography. Zcash was the first widespread application of zk-SNARKs, a novel form of zero-knowledge cryptography. The strong privacy guarantee of Zcash is derived from the fact that shielded transactions in Zcash can be fully encrypted on the blockchain; yet still be verified as valid under the network’s consensus rules by using zk-SNARK proofs.

The acronym zk-SNARK stands for “Zero-Knowledge Succinct Non-Interactive Argument of Knowledge”. This refers to a proof construction where one can prove possession of certain information, e.g. a secret key, without revealing that information, and without any interaction between the prover and verifier. In May 2022, Zcash began the process of upgrading its underlying cryptography and moving to a new proof composition called Halo 2.

Halo 2 is a high-performance zk-SNARK implementation — written in Rust (a programming language) — which eliminates the need for a trusted setup while also setting the stage for scalability in Zcash.

Following Zcash’s success, many other projects in the same vein as Zcash followed; PIVX, VRSC, and FIRO to name a few. The next major development would be Mina Protocol with its announcement of a blockchain developed on zk-SNARKs. At O(1)Labs, the Mina Protocol team is building CODA, the first succinct blockchain, using ZKPs. No matter how many transactions are recorded on the blockchain it remains, at most, the size of a few tweets (as per O(1)Labs comments). The team at Mina has also developed smart contract applications: zkApps. Mina’s zkApps are zero knowledge-powered smart contracts. They are Turing complete like other smart contracting languages. But, because they have native zero knowledge capability, they bring along additional features such as privacy and off-chain computation. Mina brings to the table one of the first iterations of a blockchain compatible with smart contracts that natively supports ZKPs.

Now with the industry entirely focused on Ethereum’s Merge in the coming months multiple projects, all based on ZKPs have gained significant mindshare; StarkNet, zkSync, Aztec, LoopRing, Polygon Zero and Hermez.

StarkNet

StarkNet began development back in 2017 by the team behind the original nomenclature of zk-SNARKs. StarkNet is a permissionless decentralized ZK-rollup that operates as a Layer 2 network over Ethereum enabling dApps to scale. StarkNet’s gas fees are 100x lower than transactions on the main Ethereum chain making it ideal for increasing the affordability of transaction-heavy dApps. All transactions on StarkNet are periodically batched and given a STARK proof to prove their validity. Using STARK proofs drastically reduces the computational power needed to verify. StarkNet aims to decrease costs by two orders of magnitude compared to Ethereum while increasing transaction speed by one order of magnitude by the end of the year.

zkSync

Next on the list is zkSync. A trustless protocol for scalable low-cost payments on Ethereum. The ZK-rollup technology launched in 2020 by Matter Labs was founded by Alex Gluchowski and Alexandr Vlasov. Their aim is to achieve a VISA-like scale of throughput of thousands of transactions per second. zkSync is also the only zk-rollup protocol that supports full EVM compatibility. With zkSync, you’re able to take existing live smart contracts from Ethereum and seamlessly redeploy them. This makes it attractive to developers who prefer to have the same code across Layer 1 and Layer 2.

Aztec Network

Aztec Network is another ZK-rollup on Ethereum but with a focus on privacy. Aztec enables decentralized applications to access privacy and scale. Aztec’s rollup is secured by its industry-standard PLONK (another form of ZKPs) proving mechanism used by the leading zero-knowledge scaling projects. Originally founded in 2017 as Creditmint, a platform for institutional finance on the blockchain. Aztec’s founders published their seminal paper in 2019 on the universal zk-SNARK. From there Aztec launched zk.money, a multi-asset private payments platform with internal transfer functionality. Then with Aztec Connect, the team introduced a set of tools making it easy to integrate privacy and scalability to any protocol.

LoopRing

LoopRing is a bit of a different beast than its fellow ZKP rollups. The project began in June 2017 and has evolved into a multifaceted Ethereum effort, operating across the stack, from protocol to product. LoopRing’s objective is to design and engineer the best-in-class zkRollup exchange and payment protocol on Ethereum; and to operate products that bring it to users across the world. LoopRing protocol does not rely on any external validators, consensus, or crypto-economic assumptions. Only Ethereum and Zero Knowledge cryptography. LoopRing solves scalability without compromising Ethereum security. Their zkRollup throughput reaches approximately 1000x of Ethereum, or as high as 2,025 trades per second. The cost per transaction is reduced to as little as 1/100th the cost of Ethereum, with trades and transfers costing fractions of a cent.

Polygon Zero

Polygon Zero is a ZK-rollup solution specifically designed to reduce the computational cost of generating validity proofs through recursive proofs. While ZK-rollups can increase scalability, their functionality is limited by the time-intensive and costly proof-generation process. Polygon Zero solves this problem by using recursive proofs, which are faster than existing prover systems. Typically, ZK provers generate proofs for one transaction at a time. However, Polygon’s ZK-rollup (ZKRU) project, Polygon Zero simultaneously generates proofs for all transactions in a batch before rolling those proofs up into a single proof for the main chain. Polygon Zero (formerly Mir Protocol) was started by Brendan Farmer and Daniel Lubarov of Predicate Labs in 2019. The team rebranded after its $400M acquisition by Polygon (formerly MATIC Networks) in December 2021 as part of their broader pledge toward investing in scaling zero-knowledge technology.

Another product out of Polygon, Hermez, is an open-source zk-Rollup optimized for secure, low-cost and usable token transfers on the wings of Ethereum. Hermez zk-rollup is a layer 2 construction on top of Ethereum that solves its scalability through mass transfer processing rolled into a single transaction. The “zero-knowledge proof” (ZK) technology is used to present and publicly record the validity and correctness of the rolled transfers processed on the Ethereum blockchain. By storing just the proof and the compressed data of a batch of transfers, the efficiency and the throughput of the network are multiplied.

The Present Time

In the grand scheme of mathematics, ZKPs haven’t been around for that long. Their inception in 1985 dates them as being nearly 40 years old. But in that short period of time, they’ve already developed quite a history, even more so now with the advent of ZKPs in the realm of cryptocurrencies. While they may be relatively young in general mathematics, they’re even younger within the cryptocurrency industry. Now, with the rising popularity of the ZKP cohort of Ethereum rollups, we can only guess as to what the discussion is going to be around ZKPs as we rapidly approach Ethereum’s merge later this year.