Introduction

After part 1 of the series, which introduced the Zero-Knowledge Proof concept, this blog will dive deeper into different ZKP types, its main protocols (such as zk-SNARKs), and their various implementations.

Types of Zero-Knowledge Proof

Not all Zero-Knowledge Proofs are the same. There are two main types of Zero-Knowledge Proof, and they both have pros and cons depending on the use case they apply.

Interactive Proofs

This type of ZK-Proof involves a “prover” and a “verifier” continuously interacting with each other until the verifier finishes verifying the data (sometimes this data is also called “witness”).

Advantages

• Easy to execute A verifier simply interacts with a prover until the first one is convinced that the data is correct.

Disadvantages

• Limited transferability To prove the same information again to another verifier, the entire process must be repeated.
• Not scalable Interactive ZKPs require both verifier and prover to be online at the same time, which makes the entire process non-scalable.

Non-interactive Proofs

In this ZKP type, the verifier doesn’t need to interact with the prover all the time until the first is convinced. In this ZKP type, the data/witness can be verified publicly without a prover being online.

Advantages

• Scalable It does not require a prover or verifier to be online all the time.
• Transferable If the prover verifies the proof of the witness once, it can be made public, and the same process is not to be repeated for the different verifier.

Disadvantages

• Requires a lot of computation power To verify the data non-interactively, a machine must solve mathematical equations many times, which may take up to several minutes to verify the witness (an annoying amount of time for web and desktop applications).

Interactive ZKPs can be used in real-life examples, as it is easier to keep both the prover and verifier interacting. For example, it is used for Nuclear disarmament. But non-interactive ZKPs are used more frequently nowadays, as they are more suitable for usage on the internet and in applications. Moreover, modern ZKP protocols, such as Bulletproofs and zk-SNARKs, originated from non-interactive ZKP.

Zero-Knowledge Proof Protocols

This section will dive deeper into the most used ZKP protocols.

Pre-requisites

Before explaining how protocols work, we will clarify some of the terms:

• Range proof — a proof that verifies that a provided statement belongs to a specified range but does not reveal the value itself. For example, during online payments, a bank doesn’t tell how much money there is in your account to a shop. They verify that you have enough money (verify that the bill is within the range of (0; m], where “m” is the amount on your bank account).
• Trusted setup — a trusted setup is a party (or parties) that generates random secrets and then is supposed to delete them. It is called “trusted” because users blindly trust this party to handle secret deletion; otherwise, it may cause severe vulnerabilities. Check this or this resource for a better understanding. Protocols/implementations using a trusted setup are considered less reliable and not trustless.
• (Secure) Multiparty Computation (MPC / SMPC) — “(Secure) Multiparty Computation is a cryptographic protocol that distributes computation across multiple parties where no individual party can see the other parties’ data.” (source, also, check this source for a better high-level understanding of the MPC concept)

zk-SNARKs

Zk-SNARK is the oldest and the most renowned ZKP protocol. More than that, zk-SNARKs are so far the fastest and provide the shortest proof on an output. For instance, according to Ronald Mannak’s article Groth16, the primary general-purpose zk-SNARK construction has its proof size at ~0.2kB, its prover runtime — ~2min, and its verifier runtime — ~10ms. However, zk-SNARKs are usually seen as insecure, as they depend on a trusted setup, making them vulnerable, not to mention that SNARKs are not quantum-secure. Nevertheless, zk-SNARKs are not insecure by their origin, as it is possible to implement them with MPC (for example), and recent zk-SNARK constructions have already become entirely trustless (check SuperSonic for more). Powers of Tau, Zcash used for some time, is one of the examples of applying the MPC concept to SNARK’s logic.

Additionally, as well as zk-STARKs, SNARKs are used for zk-rollups. Both protocols were utilized for Ethereum rollups. However, Ethereum was not the only one to implement zk-rollups (check the source to learn more)

N.B. It is worth mentioning that Groth16 is the fastest and the shortest proof-wise zk-SNARK implementation. More zk-SNARK constructions produce bigger proofs and do it longer while being more reliable.

Bulletproofs

Bulletproofs were designed to be “short like a bullet, with bulletproof security assumptions.” The protocol, which was first suggested in 2017, was one of the first to have the size of the proof increase logarithmically rather than in a linear way, which was used by earlier protocols utilizing range proofs. This means that in the long run, Bulletproofs are supposed to take up less space for transactions, making them more scalable. Monero, as an example, after implementing Bulletproofs, reduced its transaction size by five times.

Moreover, it is said that Bulletproofs do not require a trusted setup. They use MPC instead, making them more reliable. To improve the security aspect, Bulletproofs use discrete logarithms and Fiat-Shamir heuristics. This security makes proofs unbreakable, although Bulletproofs are still not post-quantum secure.

💡

Note: Most articles declare that compared to zk-SNARKs, Bulletproofs do not require a trusted setup, which makes it more reliable (e.g., source). However, the official Bulletproof document says that they are built on MPC, and this article states that MPC is a variation of a trusted setup. This brings ambiguity into how MPC is defined, which raises the question: do Bulletproofs rely on a trusted setup or not?

zk-STARKs

Zk-STARK is the youngest of the protocols, being created in 2018. They do not require any trusted setup and are entirely transparent, achieving that by implementing collision-resistant hash functions instead of Elliptic-curve cryptography and pairings, which also makes zk-STARKs quantum-resistant and trustless. While also being faster than zk-SNARKs in the proof generation, STARKs’ proof size is ~50kB, which is ~250 times more than original zk-SNARKs, and due to that, it takes less time for SNARKs to verify proofs. Thanks to the more straightforward cryptographic assumptions it uses, they are seen as more scalable. Despite being relatively young, the STARK protocol is already used in StarkEx and StarkNet solutions, presented by StarkWare, not to mention zk-rollups.

zk-SNARKs vs Bulletproofs vs zk-STARKs

Here is a decent comparison of zk-SNARKs, Bulletproofs, and zk-STARKs.

Comparison of zk-SNARKs, Bulletproofs, and zk-STARKs (Source)

Zero-Knowledge Proof Implementations in Blockchain

Pre-requisites

• Diophantine Argument of Knowledge (DARK) — a technique that leverages integer representations of polynomials and groups of unknown order. (source)
• Interactive Oracle Proof **(IOP) — an interactive proof in which the verifier is not required to read the prover’s messages entirely; instead, the verifier has oracle access to the prover’s messages and may probabilistically query them. (source)

Groth16

As mentioned earlier, Groth16 is one of the first SNARKs and is the most used ZKP construction so far. Its main advantages are in speed and proof size. However, Groth16 still uses a trusted setup, which is a big security concern, and there are even articles showing how to use Groth16 vulnerability.

PLONK

PLONK was one of the SNARKs to bring something new that also made a base for other protocols. Firstly, while dependent on a trusted setup, PLONK brings a universal trusted setup (meaning that other protocols support the output of a trusted setup ceremony) and an updateable reference string (representing that MPC does not need to be recomputed). Secondly, it uses polynomial commitments based on a trusted setup and elliptic curve pairings. Check Vitalik Buterin’s article about PLONK for a better understanding.

There is also a proposal for an “update” to PLONK called Turbo-PLONK. It may be worth looking at.

Halo / Halo2

Halo is one of the first zk-SNARKs, which is entirely trustless and way more scalable than previous SNARK implementations. Halo 2 is a significant update to the original Halo, aimed “to build a robust and secure implementation that the Zcash community can feel confident adopting in the protocol.” (source) While Halo was based on the Sonic algorithm, Halo 2 moved to PLONK as it supports a more flexible circuit design. The new Halo version also implements Recursive zk-SNARKs verification by applying Pasta curves.

More detailed information about Halo 2 can be found on this hackernoon post or even Zcash docs.

SuperSonic

SuperSonic is another transparent zk-SNARK, so it does not require a trusted setup, as well as Halo 2, is based on Polynomial IOP using the DARK polynomial commitment scheme. SuperSonic is the second version of Sonic. Similar to Halo, it also uses polynomial IOP (PIOP) from PLONK, and identical to Bulletproofs, SuperSonic also uses the Fiat-Shamir heuristic. For a more clear picture, check this source.

Bulletproofs

It may come as a surprise, but Bulletproofs is a system based on Bulletproofs protocol. We mentioned how they work above.

Others

There are more good protocols, such as Aurora and Virgo. But we didn’t mention them there as they still lack potential practical implementation.

Implementations Comparison Table

As the table shows, all the implementations have their pros and cons. So, the advice for developers would be to select the most suitable for their use case.

Recollection

💡

There are three main ZKP protocols: zk-SNARKs, Bulletproofs, and zk-STARKs. SNARKs are fast and short but rely on a trusted setup. Bulletproofs are trustless and use Multiparty Computation (MPC). However, they are slower and longer than SNARKs. STARKs are the most secure and can even be faster than SNARKs. As a trade-off, the proof size is too big for blockchain usage.

💡

There are a lot of ZKP implementations. Groth16 is the fastest and the shortest and is used mainly by developers. PLONK brings updateable reference strings but relies on a trusted setup such as Groth16. Halo 2, SuperSonic, and Bulletproofs are completely trustless but have bigger proofs size and a longer verification time.

In the next blog

This article looked at the main existing ZKP protocols and their implementations. We also compared ZKP constructions on a set of parameters valuable for blockchain developers. The following blog will explore cryptographic primitives used in ZKP and will look at how Sigma protocol works.

Resources

ZKP Types

1. https://www.geeksforgeeks.org/interactive-zero-knowledge-proof/
2. https://www.geeksforgeeks.org/non-interactive-zero-knowledge-proof/
3. https://en.wikipedia.org/wiki/Zero-knowledge_proof

zk-SNARKs

1. https://medium.com/qed-it/diving-into-the-snarks-setup-phase-b7660242a0d7
2. https://z.cash/technology/paramgen/
3. https://ethereum.org/en/developers/docs/scaling/zk-rollups/
4. https://blog.pantherprotocol.io/zk-rollup-projects-inner-workings-importance-analysis/
5. https://hackernoon.com/zero-knowledge-proofs-the-simplest-explanation-on-the-internet-yf6g37nq

Bulletproofs

1. https://blockonomi.com/bullet-proofs/
2. https://blog.pantherprotocol.io/bulletproofs-in-crypto-an-introduction-to-a-non-interactive-zk-proof/
3. https://eprint.iacr.org/2017/1066.pdf
4. https://bitcoin.stackexchange.com/questions/71344/what-is-a-discrete-logarithmic-assumption-how-does-it-set-up-trustless-proofs

zk-STARKs

1. https://academy.binance.com/en/articles/zk-snarks-and-zk-starks-explained
2. https://blog.pantherprotocol.io/zk-snarks-vs-zk-starks-differences-in-zero-knowledge-technologies/
3. https://blog.pantherprotocol.io/what-are-hash-functions-in-crypto-a-laymans-guide/
4. https://academy.bit2me.com/en/what-are-zk-stark/
5. https://medium.com/coinmonks/reveal-mysterious-zk-starks-42d00679c05b#:~:text=The proof size of a,the original concept was published.
6. https://medium.com/starkware/starks-starkex-and-starknet-9a426680745a

zk-SNARKs vs zk-STARKs

1. https://blog.pantherprotocol.io/zk-snarks-vs-zk-starks-differences-in-zero-knowledge-technologies/
2. https://www.altoros.com/blog/securing-a-blockchain-with-a-noninteractive-zero-knowledge-proof/

zk-SNARKs vs Bulletproofs vs zk-STARKs

1. https://github.com/matter-labs/awesome-zero-knowledge-proofs#multi-party-ceremony-mpc-for-trusted-setup

Monero case

1. https://www.getmonero.org/2017/12/07/Monero-Compatible-Bulletproofs.html

Trusted setup and MPC

1. https://medium.com/qed-it/diving-into-the-snarks-setup-phase-b7660242a0d7
2. https://medium.com/qed-it/how-toxic-is-the-waste-in-a-zksnark-trusted-setup-9b250d59bdb4
3. https://inpher.io/technology/what-is-secure-multiparty-computation/
4. https://www.qredo.com/blog/what-is-multi-party-computation-mpc#privatekeys
5. https://blog.pantherprotocol.io/a-guide-to-understanding-trusted-setups/
6. https://decentralizedthoughts.github.io/2019-07-19-setup-assumptions/

Zero-Knowledge Proof Implementations in Blockchain

1. https://medium.com/coinmonks/comparing-general-purpose-zk-snarks-51ce124c60bd
2. https://en.wikipedia.org/wiki/Zero-knowledge_proof#Zero-Knowledge_Proof_protocols

Groth16

1. https://medium.com/ppio/how-to-generate-a-groth16-proof-for-forgery-9f857b0dcafd

PLONK

1. https://dusk.network/news/zero-knowledge-plonk-demo
2. https://vitalik.ca/general/2019/09/22/plonk.html
3. https://zeroknowledge.fm/news-2-on-optimization-plonk/
4. https://dusk.network/news/plonk-rc
5. https://docs.zkproof.org/pages/standards/accepted-workshop3/proposal-turbo_plonk.pdf

Halo / Halo 2

1. https://electriccoin.co/blog/explaining-halo-2/
2. https://hackernoon.com/halo-principle-explained
3. https://www.coindesk.com/markets/2019/09/14/you-can-now-prove-a-whole-blockchain-with-one-math-problem-really/
4. https://zcash.github.io/halo2/index.html

SuperSonic

1. https://aithority.com/technology/blockchain/the-first-practical-trustless-zk-snark-supersonic-proofs-are-25-times-smaller-and-more-efficient-to-verify-than-any-other-trustless-zero-knowledge-proof-system/
2. https://research.metastate.dev/demystifying-supersonic-part-1/
3. https://eprint.iacr.org/2019/1229

Aurora and Virgo

1. https://eprint.iacr.org/2018/828.pdf
2. https://people.eecs.berkeley.edu/~kubitron/courses/cs262a-F19/projects/reports/project5_report_ver2.pdf