Origin and Development of ZKP: From the 1980s to Present

ZKP: History and Evolution from the 80s to Today

Author: Preethi Kasireddy, Founder of DappCamp; Translation: Blockingcryptonaitive

ZKP (Zero-Knowledge Proofs) gained popularity after the explosion of cryptocurrencies, but their long history dates back to the 1980s. This article explores the origins and development of ZKPs over the years.

The basic premise of ZKPs is that one party (prover) can prove to another party (verifier) that they know a certain piece of information, without actually revealing what that information is. In doing so, the prover can prove their knowledge of a specific fact or data without revealing any other information.

Now, let’s begin exploring the history and development of ZKPs.

• 【Exclusive from ChainDD】Analysis of 525-page EU Regulatory Regulations: Step-by-Step Guide to Writing White Papers, Only 3 Types of Cryptocurrencies Approved
• Comprehensive analysis of the .sats domain
• There have been rumors for 2 years that “Grand Theft Auto 6” will introduce cryptocurrency, why won’t it integrate with Web3?

1980s: Origins of ZKPs

ZKPs gained attention after the explosion of cryptocurrencies because they allow for trustless and anonymous exchanges between two parties, but the concept itself is not new. The history of ZKPs actually dates back to the late 1980s, when Shafi Goldwasser, Silvio Micali, and Charles Rackoff introduced the concept in a paper titled “The Knowledge Complexity of Interactive Proof-Systems.”

The initial concept described by the authors involved something called “interactive protocols,” in which the prover and verifier communicate back and forth (interact) to convince the verifier that the prover knows the correct information. While this approach had its own breakthroughs, it was proven to be time-consuming and resource-intensive, particularly when dealing with large amounts of data. In order for ZKPs to be scalable, they needed to be non-interactive.

Peggy (the prover) and Victor (the verifier)

In 1986, Fiat and Shamir invented the Fiat-Shamir heuristic, a technique that takes an interactive knowledge proof and creates a digital signature based on it, successfully transforming interactive zero-knowledge proofs into non-interactive zero-knowledge proofs. This now made ZKPs non-interactive and laid the foundation for the widespread, scalable use of ZKPs.

Interactive and Non-Interactive ZKPs

2011-2015: zkSNARKs

The next major push for ZKPs happened in 2011, when Nir Bitansky, Ran Canetti, and Alessandro Chiesa presented a paper titled “From Extractable Collision Resistance to SNARKs and Back Again” at the International Cryptology Conference.

How does zkSNARK work?

This paper suggests that we can create SNARKS (succinct non-interactive arguments of knowledge) using something called an extractable collision-resistant (ECR) hash function. SNARKS are essentially “succinct” ZKPs, meaning they are small in size and can be verified in seconds.

This paper suggests that we can create SNARKS (succinct non-interactive arguments of knowledge) using something called an extractable collision-resistant (ECR) hash function. SNARKS are essentially “succinct” ZKPs, meaning they are small in size and can be verified in seconds.

Comparison of ZKP, NIZKP, and zkSNARK

From here, the process of ZKP accelerated and led to the birth of Pinocchio in 2013.

Pinocchio was one of the first concept validation implementations of a zero-knowledge succinct non-interactive argument of knowledge (zk-SNARK) proof system and is considered a breakthrough in the field. It was used a few years ago, but has since been replaced by updated, more efficient versions of zk-SNARKs.

The two main drawbacks of zkSNARKS at the time were:

● Requirements for trusted setup

zkSNARKs require a “trusted setup” between the prover and verifier. This setup phase is used to create a set of initial parameters, which are then used to generate and verify zk proofs.

Generating these parameters requires some secret information. Typically, a group of people generates these secrets and then uses them to generate the parameters. Once the parameters are generated, the secrets are discarded. However, because the secret input needs to be generated by a group of people, we need to “trust” these people.

In blockchain, we want to minimize trust, which is why “trusted setup” is usually not favored.

zk-SNARK proofs depend on an initial “trusted setup” between the prover and verifier, meaning that a set of public parameters is needed to construct zero-knowledge proofs and thus construct private transactions. These parameters are almost like game rules, and they are encoded into the protocol and are one of the necessary factors to prove the validity of a transaction. This can lead to potential centralization issues, as the parameters are typically formulated by very small teams.

Workflow for multi-party trusted setup Source

● Non-post-quantum secure

zkSNARKS is not post-quantum secure because they rely on public-key encryption. Public-key cryptography relies on the difficulty of solving a specific array of discrete logarithm problems. However, with the advent of quantum computers, public-key cryptography is at risk because computers can factor large numbers into prime numbers, which means solving the discrete logarithm problem is no longer difficult.

The ZK industry is working to build protocols that solve both of these problems.

2016-2018: Making SNARKs practical

Next up is Groth. Groth was introduced in 2016 and was one of the first protocols to make zkSnarks efficient and extremely practical. This was a huge breakthrough and was immediately adopted. In fact, it is still used today in many protocols because of its performance and simplicity, and many tools have been built around it.

The next important milestone for ZKP was the launch of Bulletproofs in 2017. I remember Bulletproofs being heavily promoted in 2017. Bulletproofs are short non-interactive zero-knowledge proofs that can prove that an encrypted value is not revealing any information about the data within a given “range” (for example, I can prove to you that the transaction value is within a certain range without revealing the amount). These “range proofs” can be aggregated into a short proof. The reason why the Bulletproof protocol became so popular was that they made confidential transactions not only possible but also efficient for Bitcoin. The biggest difference in Bulletproof technology is that it does not require a trusted setup. This is important in the blockchain industry because we are focused on building trustless networks, and as you can imagine, the industry quickly adopted Bulletproof technology.

Runtime comparison of SNARKs, STARKs and Bulletproofs

2018: STARK

In 2018, STARKS (Zero-Knowledge Scalable TransBlockingrent ARguments of Knowledge) caused a sensation in the industry by mitigating the two drawbacks of zkSNARKS:

● STARKS is “post-quantum secure”, which means they rely on hash functions rather than elliptic curves as proof mechanisms.

● STARKS do not require a trusted setup. Instead, zk-STARKS use a publicly verifiable random source as initial parameters.

The biggest drawback of zkSTARKS is that their proofs are very large. This makes it unsuitable for blockchain because on-chain storage costs money. However, STARKS stand out over SNARKS and allow the industry to get rid of trusted setups.

Comparison of zkSNARKs and zkSTARKs on various parameters

2019: The Year of SNARKS

2019 was an important year for zkSNARKS, with three major innovations:

● SONIC

The biggest contribution made by Sonic is to support a “universal” and upgradable reference string. This means that you do not need to perform a trusted setup to generate initial parameters for each program. Instead, you only need to perform a trusted setup once and then use the same parameters for all programs. Although this does not completely alleviate the drawbacks of trusted setups, it does make them better.

Sonic also has a constant proof size (which is good because proof size does not increase with program complexity) and introduces batch verification, reducing verification time. However, when you are not performing batching, verification time is very long.

● MARLIN

Marlin is a significantly improved version of Sonic, with proof times reduced by a factor of 10. It also offers faster verification without batching, reducing verification time by a factor of 3.

● PLONK

PLONK stands for “Permutations over Lagrange-bases for Oecumenical Non Interactive Arguments of Knowledge,” which is another improved version of SONIC. One of its features is that its proof times are reduced by a factor of 5. The major innovation here is that PLONK allows custom gates instead of the usual addition/multiplication, which means you can build zk proofs for more complex programs.

PlonK and Marlin both replace Groth16’s circuit-specific trusted setup with a universal setup. With the launch of PLONK, the cryptographic community also realized that they could even build “zkEVM,” which would allow us to take any smart contract code on Ethereum and turn it into zero-knowledge proofs. Vitalik has written a brilliant article explaining the mathematical principles behind it.

This marks the end of the ZKP chaos, but it’s just the beginning!

Various protocol proof sizes and security assumptions, source

2020 to Present

HALO2

In 2020, the Zcash team released HALO 2 (the successor to HALO), which combines the benefits of PLONK and Bulletproofs, then allows for fast verification without a trusted setup.

HALO vs. HALO 2, source

Fast forward to 2022, and we’re starting to see the acceleration of new protocol development once again.

HYPERPLONK

HYPERPLONK, which launched in 2022, is a zkp system whose proofs are fully linear time and support custom gates with heights and lookups. It attempts to increase the flexibility of PLONK, increase its speed, and offer more benefits.

While PLONK itself is very robust, it has some limitations, particularly when proving large statements or attempting to use highly parallel hardware. These limitations are especially important when proving large, complex commands such as rollups and zkEVM. HyperPlonk aims to address this.

PLONKY2

Plonky2, recently released by Polygon in January 2022, is the newest in the ZKP world. It is a recursive SNARK that is 100 times faster than existing alternatives. It combines PLONK and FRI for the best STARK (i.e. fast proof and no trusted setup) and the best SNARK (i.e. support for recursion and low verification costs on Ethereum).

This brings us to today. This is what the ZKP ecosystem looks like today:

ZKP ecosystem

While no one “protocol” is considered the best, understanding all of these protocols, their strengths, and their limitations can help us choose the best one for a particular use case and setup. My team has collected information on all of the protocols I presented today and summarized it here:

Summary of ZKP features

ZKP has a long and rich history, with each protocol pushing the limits, increasing speed, and extending the limitations of this technology. We’ve come a long way from the first iteration that required prover and verifier to exchange information.

“`

In my opinion, we’re just getting started. What do you think is the next big innovation in the ZKP field?

“`

We will continue to update Blocking; if you have any questions or suggestions, please contact us!