Major Milestones: Zero-Knowledge and Crypto
This article is the second in the series of articles we’re publishing here at the Occam DAO exploring Zero-Knowledge Proofs (ZKPs); the first article is available here. In this article, we’re going to cover the many milestones in the development of ZKPs and their eventual translation into the world of cryptocurrencies. We’ll begin by turning back the clock to 1985 with the original conception of ZKPs.
April 1985: ZKPs are first conceived of by several computer scientists: Shafi Goldwasser, Silvio Micali, and Charles Rackoff in their research paper “The Knowledge of Complexity of Interactive Proof-Systems”. This paper introduced the IP hierarchy of interactive proof 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. They also gave the first zero-knowledge proof for a concrete problem, that of deciding quadratic nonresidues mod m.
December 1985: Oded Goldreich, in an unpublished manuscript, explains how several other problems lie in the interaction of NP and co-NP complexity systems. Goldreich’s paper shows a proof system in which he verifies that a two-prime modulus is not a Blum integer (a natural number n is a Blum integer if n = p × q is a semiprime for which p and q are distinct prime numbers congruent to 3 mod 4. That is, p and q must be of the form 4t + 3, for some integer t).
June 1986: Further development of the concept of ZKPs with Laszlo Babai and Shlomo Moran’s research paper: “Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes”. This paper further fleshed out the concept of an interactive proof system in computational complexity theory.
October 1986: Oded Goldreich, Silvio Micali and Avi Wigderson published another paper: “Proofs that Yield Nothing But Their Validity”. The paper showed that assuming the existence of unbreakable encryption, one can create a zero-knowledge proof system for the NP-complete graph colouring problem with three colours. Since every problem in NP can be efficiently reduced to this simplified form, it shows that under this assumption, all problems in NP have zero-knowledge proofs.
August 1987: Russel Impagliazzo, Moti Yung and Ben-Or et al. would go on to show in their paper: “Direct Minimum-Knowledge Computations” that, 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 proven by an interactive proof system can also be proven with zero knowledge.
September 1988: Ben-Or, Goldreich, Goldwasser et al. then went on to further cement the idea that there exists zero-knowledge proofs for all proofs in IP = PSPACE in their paper: “Everything Provable is Provable in Zero-Knowledge”.
April 1990: Uriel Fiege and Adi Shamir would go slightly off the now well-tread path of ZK with Witness Indistinguishable Proofs in their paper: “Witness Indistinguishable and Witness Hiding Protocols”. The property of witness-indistinguishability is related to that of zero-knowledge, yet witness-indistinguishable protocols do not suffer from the same problems of concurrent execution.
May 1993: With the wealth of papers accumulating under the school of Zero-Knowledge, the first ever Godel Prize is awarded to scientists: Goldwasser, Micali, Rackoff, Babai and Moran. Both of these team’s papers formed the intellectual basis for interactive proof systems and thus gave credence to Zero-Knowledge within the school of mathematics.
November 2004: Cynthia Dwork, Moni Naor and Amit Sahai published a paper: “Concurrent Zero-Knowledge” which initiated the exploration of the internet’s effect on cryptographic systems. The paper posited that in an internet-like setting where multiple protocols may be executed concurrently, building ZKPs is more challenging.
May 2013: Bryan Parno, Jon Howell, Craig Gentry and Mariana Raykova published their paper on a new ZKP system Pinocchio: “Pinocchio: Nearly Practical Verifiable Computation” which would be the first of many zk-SNARK protocols to be developed.
October 2016: Zcash, which had been in development since early 2013, is first mined and within a week the crypto is in high demand and traded at nearly five thousand dollars per coin. Zcash was based on Bitcoin’s codebase but used a shielded transaction model based on zk-SNARKS, specifically the Pinocchio protocol. Zcash was the first widespread application of zk-SNARKs.
July 2017: Mina Protocol enters the market originally under the name Coda Protocol. The protocol is unique in that it limits block capacity to only 22 kilobytes in size. The Mina Protocol introduced a mechanism called Recursive Zero-Knowledge Proof to the equation. Recursive Zero-Knowledge Proofs streamline data transmission even further. Instead of turning every transaction and block into a 22-kilobyte snapshot, the network makes an overview snapshot of multiple transactions. Since all of these snapshots are now in one 22-kilobyte snapshot, the blockchain remains light.
January 2018: StarkWare is by Eli Ben-Sasson (co-inventor of STARK, previously prof. of CS at Technion, founding scientist of Zcash), Uri Kolodny (serial entrepreneur), Michael Riabzev (co-inventor of STARK), and Alessandro Chiesa (founding scientist of Zcash and prof. of CS at UC Berkeley). StarkWare was founded with the goal of scaling Ethereum using zk-STARK technology.
November 2018: Creditmint rebrands to Aztec Protocol, a ZK privacy system built on Ethereum. AZTEC (short for Anonymous Zero-knowledge Transactions with Efficient Communication) was launched to enable confidential Ethereum transactions. The protocol shares similarities with Zcash, but AZTEC does not use zk-SNARKs; rather, it includes a set of algebraic zero-knowledge proofs specific to AZTEC.
December 2019: Loopring 3.0 is released; it was the first protocol to allow zk-rollup decentralized exchanges on the Ethereum mainnet. The third version of the protocol tackles the scalability problem of decentralized exchanges. Previous versions of the protocol already did the order matching off-chain. However, the settlement was completely on-chain. This still has a high computational and storage cost on-chain. Protocol 3.0 solves this by moving almost all data off-chain as well as moving all computations for all requests off-chain using zero-knowledge proofs (zk-SNARKs).
June 2020: StarkEx V1.0 is released. StarkEx is StarkWare’s scalability engine. It launched on Ethereum’s mainnet in June 2020. It powered DeversiFi’s decentralized exchange at launch. StarkEx was StarkWare’s first commercial release and the first mainnet deployment of STARKs. VeeDo was also released and is StarkWare’s STARK-based Verifiable Delay Function (VDF) service. It launched on the Ethereum mainnet in June 2020. The first application based on VeeDo was a proof-of-concept for a randomness beacon.
June 2020: The first version of zkSync, based on the PLONK zk-SNARK protocol, is launched on the Ethereum mainnet. zkSync is one of the first hybrid combinations of the EVM with zk-SNARK technology allowing for a less challenging transition of development from the traditional EVM space.
July 2020: zkSync’s v1.1 is released following the Great Reddit Scaling Bake-Off.
August 2020: StarkWare’s Cairo platform is released and can generate STARK proofs for general computation on Ethereum. It supports programs and applications written in an assembly-like programming language, which goes by the same name, Cairo.
November 2020: The Aztec network’s founders release a whitepaper on Plookup: “A Simplified Polynomial Protocol for Lookup Tables”. Plookup enables extending PLONK’s arithmetic gates with lookup gates from precomputed tables. This opens a path to efficient proofs about “SNARK non-friendly functions” like SHA-256.
December 2020: StarkEx 2.0 launched in December 2020. The new version features the Cairo proof generation and programming platform that currently powers ImmutableX and dYdX’s layer-2 implementation. It also includes ERC-721 support, faster L1-L2 Connectivity, and improved onboarding for new users.
April 2021: zkSync completed its design specification for zkPorter. zkPorter is a sharding-based solution for large increases in TPS(~20,000). Designed as part of zkSync v2.0 upgrade.
May 2021: zkSync launches their alpha release, v2.0, of the zkEVM enabling EVM-Compatibility in the rollup environment as part of their larger zkSync 2.0 effort.
May 2021: The Aztec Network, in conjunction with several others, releases a paper on “Efficient Polynomial Commitment Schemes for Multiple Points and Polynomials”. The concept, known as SHPLONK, is a new scheme which extends the original polynomial commitment scheme to enable enhanced efficiency when opening multiple polynomials at multiple points.
August 2021: Polygon announced its acquisition of Hermez, a zero-knowledge (ZK) rollup, using zk-SNARKS. Hermez will be absorbed into the Polygon ecosystem under the name Polygon Hermez, where it will become a part of Polygon’s line of products. 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.
November 2021: Polygon Miden is announced. Polygon Miden is a STARK-based ZK Rollup. ZK Rollups are very promising solutions but their main drawback is that it is hard for them to support arbitrary logic and transactions, including those of the EVM (Ethereum Virtual Machine). Polygon Miden solves this challenge using its core component — Miden VM, a STARK-based virtual machine. Miden VM supports arbitrary logic and transactions and has one important additional feature — for any program executed on the VM, a STARK-based proof of execution is automatically generated.
December 2021: Polygon announced a $400 million acquisition of Mir, a project focusing on zero-knowledge proofs. The announcement was made at Polygon’s “zk day” virtual event. Mir’s system generates recursive zero-knowledge proofs that “allow many Ethereum transactions to be verified with a single tiny proof.” This will purportedly make Mir one of the fastest and most efficient layer 2 options.
December 2021: In cooperation with Ernst & Young, Polygon Nightfall is announced. Using ZK-Optimistic Rollups, Polygon Nightfall can achieve a cost of approximately 9000 gas per transaction while also maintaining privacy. The cost improvements achieved with Nightfall 3 result from the greater efficiency of ZK-Optimistic roll-ups, which retain the layer 1 security incentives and utilise mathematical proficiency for running private transactions on the public Ethereum network.
January 2022: Polygon announces Plonky2. Plonky2 is a recursive SNARK that is 100x faster than existing alternatives and natively compatible with Ethereum. It combines PLONK and FRI for the best of STARKs, with fast proofs and no trusted setup, and the best of SNARKs, with support for recursion and low verification cost on Ethereum.
February 2022: zkSync launched zkSync 2.0 on a public testnet. In this first stage, their team began the process of implementing pieces of the production architecture onto the testnet. The idea was to build small working systems that could be tested at each major milestone while getting feedback from developers.
May 2022: zkSync launches their zkEVM architecture upgrade. Following their live testnet the team learned many new things that led them to make significant improvements to the zkEVM that set us up for better scalability, better performance, better security, and lay the foundation for future features.
May 2022: Polygon Hermez 2.0 is announced as a zero-knowledge Ethereum Virtual Machine (zkEVM). A virtual machine that executes Ethereum transactions in a transparent way, including smart contracts with zero-knowledge-proof validations. Hermez 2.0’s objective is to minimize the users and dApps friction when using the solution. Over and above what its predecessor, Hermez 1.0, was designed to do, the main functionality of Hermez 2.0 is to provide smart contract support.
June 2022: The Aztec team releases their whitepaper on Plonk: “Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge,” which covers the highly efficient universal SNARK, and introduces a new circuit arithmetization and the notion of ‘selector polynomials’, bound together by a permutation argument.
July 2022: Scroll’s zkEVM solution is announced. Scroll is an EVM-equivalent zkRollup to scale Ethereum. Technically speaking, Scroll is built upon two major pieces: The core piece is the zkEVM, which is used to prove the correctness of EVM execution in Layer 2, and the second piece is Scroll’s complete L2 architecture. Scroll has been building it in the open with the Privacy and Scaling Explorations group at the Ethereum Foundation for over a year. But to turn the zkEVM into a full zkRollup on Ethereum, they also need to add that second piece: a complete L2 architecture capable of supporting the zkEVM.
July 2022: zkSync announces their 100 Days to Mainnet effort, in which they release a detailed blog post describing the coming upgrades to their zkSync 2.0 effort on their path to their mainnet 2.0 release. They also announced their Better Compatibility effort in which they added support for Solidity and Vyper making porting dApps and codebases to zkSync 2.0 drastically easier.
July 2022: Polygon rebrands Hermez to the Polygon zkEVM. Their vision for a zkEVM with complete EVM-equivalence is simple. Developers can seamlessly deploy any Ethereum smart contract to a Layer 2 that scales infinitely using ZK proofs. Any tooling or dApp on Ethereum is used in exactly the same way on a zkEVM. Users and developers alike can reap the futuristic benefits of ZK proofs, all while benefiting from the decentralization, security, and familiarity of Ethereum.
August 2022: The Starkware team publishes a paper titled: “Scalable and Transparent Proofs over All Large Fields, via Elliptic Curves”. The paper explores Elliptic Curve Digital Signature Algorithm (ECDSA), which is the essential cryptographic algorithm that powers Bitcoin and ensures that only the rightful owner can access and manage their funds, and how ECDSA can be efficiently verified from within the STARK ecosystem. With these EC-STARKs, builders can run an off-chain protocol for Bitcoin and keep proofs in STARK. This means that the STARK ecosystem can be the foundation for dApps to be efficiently deployed on top of Bitcoin.
Takeaways
Looking at the timeline of the Zero-Knowledge space from its inception to now, we can see rapid development following its original conception in the late 80s. Now ZK is seeing quite the revival as the Ethereum community in particular is pouring money into its capabilities to help scale Ethereum. Time will tell which group is going to come out on top — Aztec, Loopring, Polygon’s Cohorts, StarkWare or zkSync. Regardless, all of them are certainly adding to the wealth of knowledge propelling Ethereum into its next phases and with discussions being held over at IOHK concerning ZKPs, Cardano investors may get to see the fruits of this research and development expand to the Cardano network as well.
