Introduction to Zero Knowledge Proofs

In cryptography, zero-knowledge proofs solve a seemingly impossible task: verifying that someone owns a piece of information without revealing it. Recently, zero-knowledge proofs have found more widespread use in the blockchain industry to help scale networks using layer 2s.

What are zero-knowledge proofs (ZKP)?

Zero-knowledge proofs, short ZKPs, are cutting-edge technology that allows the verification of information without revealing it while adding a high level of security and privacy. The concept was first introduced in 1985 by Shafi Goldwasser, Silvio Micali, and Charles Rackoff in a paper titled: ”The knowledge complexity of interactive proof systems."

The goal of a zero-knowledge proof is simple: convincing the verifier that a claim is true. Each proof involves two different parties:

• Prover: the one who wants to prove a claim
• Verifier: the party that verifies the claim.

Good zero-knowledge proof algorithms have the following three characteristics:

• Completeness: It’s highly probable that the verifier will accept the proof when it is true - as long as both adhere to the protocol
• Soundness: If the claim is untrue, the prover should be unable to convince the verifier of the opposite, the only exception being extremely unlikely circumstances.
• Zero-Knowledge: The verifier obtains no further information about the secret. All they do is verify that the claim is true.

Their Benefits include:

• Privacy and security as they allow verification of data without revealing it
• Scalability: by allowing the verification of transactions off-chain
• Interoperability: ZKPs can play a crucial role in aiding communication and transfers between different chains.

Interactive vs. non-interactive zero-knowledge proofs

We differentiate between two general types of ZKPs depending on the level of interaction they require between the verifier and the prover.

Interactive zero-knowledge proof

In an interactive zero-knowledge proof, the verifier and prover communicate back and forth to establish the witness’s veracity. Witness refers to the piece of data that the prover wants to prove and can be any data.

Throughout the process, the verifier will send a challenge to the prover. This is a randomly generated value or question the prover must respond to. Because these challenges are randomly generated, they add a further element of unpredictability, increasing the security of the proof by making it impossible for the verifier to predict or precompute.

After the prover sends the result to the challenge, the verifier can verify that the response is valid. All early iterations of ZKP algorithms were interactive, which made them inefficient as they required a lot of communication between the parties. Further research led to the creation of non-interactive ZKPs, drastically reducing the communication between verifier and prover.

Non-interactive zero-knowledge proofs

Non-interactive zero-knowledge proofs require only one round of communication between verifier and prover, making them significantly harder. This is made possible by having a shared key, also called Common Reference String, allowing verification of claims as long as one has said key. Instead of back-and-forth communications, the prover passes the secret into a special algorithm to compute and then sends it to the verifier. The verifier uses the key to verify.

Types of zero-knowledge proof algorithms

Breakthroughs in cryptography have enabled the creation of ever-more sophisticated zero-knowledge proofs, including quantum-secure algorithms.

zk-SNARKS

zk-SNARK is short for Zero-Knowledge Succinct Non-Interactive Argument of Knowledge and describes the first non-interactive proof algorithm, which relied on a shared key to establish public parameters that could be used to verify claims. However, they require an initial trusted setup because they rely on creating a shared key.

They are succinct because the witness (secret) is smaller than the proof so that it can be verified in milliseconds. ZCash was the first to widely adopt zk-SNARKS to enable fully encrypted transactions without losing the ability to confirm their adherence to consensus rules.

Bulletproofs

Bulletproofs were introduced with the words “Short like bullets, yet offering bulletproof security assumptions” as a technology to enhance blockchain privacy by enabling confidential transactions. These proofs don’t require a trusted setup and were designed with cryptocurrencies in mind. They effectively hide amounts transferred, but verification is more time-consuming than with SNARKs.

PLONK

PLONK, or Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of

Knowledge is a zk algorithm that led to a breakthrough in efficient zk-SNARK technology. Instead of requiring the generation of a shared string for each new use case, it constructs a universal proof system that can be used for any type of computation. It’s best known for its efficiency and is currently used by Aztec Network, Matter Labs, and other web3 projects working on private transactions.

zk-STARKS

zk-STARKS stands for Zero-Knowledge Scalable Transparent Argument of Knowledge and is a newer iteration of zk algorithms that removes the need for an initial trusted setup. Additionally, zk-STARKs are highly scalable as they can generate and verify proofs fast, even when the size of the underlying witness is large.

Thanks to generating provably random parameters for proving and verifying, zk-STARKs also offer high transparency. However, this comes at the cost of requiring more computation power during the verification process as zk-STARKs generate larger proofs.

Use-cases for Zero-Knowledge Proofs

Even outside of the blockchain industry, zero-knowledge proofs have found applications.

Finance

The Dutch bank ING uses zero-knowledge proofs to allow customers to prove that a secret number lies within a known range. This is useful throughout mortgage applications by enabling applicants to verify that they fall in a specific salary range without revealing their exact salary.

Other finance use cases include using zero-knowledge proofs in the context of KYC and AML. Instead of requiring customers to verify from scratch whenever they sign up for a new service, ZKPs could pave the way for a more seamless user experience, allowing users to verify their personhood without having to reveal sensitive information.

Online Voting

Zero-Knowledge Proofs can also power online voting systems by allowing users to vote anonymously while ensuring that everyone’s vote is included - and making it verifiable.

Machine Learning

In the context of Machine Learning, Zero-Knowledge Proofs allow the owner of an algorithm to share the results of their model without revealing the entire model or further information about it - allowing owners to keep their edge.

Internet of Things

ZKs can also help manage the ever-increasing number of smart devices connected to the internet, ranging from Alarm systems that call the Police or rings that track all your vital data. They can play a role in maintaining user privacy by verifying that only authorized devices can access specific data and enable secure communication. Additionally, they might aid in reducing the energy demands of IoT devices.

Use-cases for Zero-Knowledge Proofs in Blockchain

Anonymous transactions

Privacy coins designed for anonymous payments have been using ZKPs for their transactions since the beginning. Monero, for example, goes even further and shields all details around a transaction while still enabling nodes to validate the transaction.

dApps like Tornado Cash have implemented ZKPs to obfuscate transaction details. In Tornado, users deposit funds into the protocol and can then withdraw mixed funds. ZKPs are used to verify a user’s right to withdraw.

Outsource computing

Blockchain nodes are limited in computing power and can hit their limits when demand is high, and the network cannot scale to accommodate it. ZKPs allow outsourcing of computation and enable original nodes to verify the results. This is the mechanism zk-Rollups rely on to increase the throughput of an underlying chain.

Rollups process transactions off-chain and then submit the results of their works as proof of execution to the mainchain - increasing the transactions the system can handle.

Data Compression

Thanks to their ability to create proofs that are smaller than the witness, ZKPs are also used to compress data. Filecoin, for example, uses ZKPs to establish proof of storage of specific files by users without hindering scalability. Mina Protocol is also using ZKPs but to help reduce the size of its ledger by compressing all of its verification data into less than 22KB.

Prevent front-running and minimize MEV

A major challenge with public blockchain networks is that they open up ample opportunities for savvy traders to front-run and squeeze more fees out of less savvy traders. Front-running on a blockchain can be achieved by simply paying the miner to have one's transaction included earlier than the one you’re front-running.

However, by hiding transaction details, ZKPs can prevent bots from looking up trades and front-running them. In a similar vein, ZKPs could help prevent MEV (maximal extractable value), often described as an invisible tax that miners can extract from unknowing users. One of the reasons it occurs is that miners have full visibility of the transactions waiting to be included in blocks (in the mempool). Using ZKPs, these could be submitted, proven, and verified without revealing details to the miners.

Downsides of ZKPs

While Zero-Knowledge Proofs are great for many things in blockchain and beyond, they come with a few drawbacks:

• Computation: ZKPs are more resource-intensive than using other proving systems, especially when it comes to complicated proofs. This can result in longer processing times, affecting scalability and user experience. Additionally, verification can get expensive, with zk-Rollups on Ethereum paying up to 500,000 gas to verify one single zk-SNARK and more for zk-STARKs.
• Trust assumptions: Depending on the algorithm used, they are not entirely trustless. In an ideal case, multiple honest participants will join a trusted setup ceremony, but there is no way for users to be sure.
• Complexity: ZKPs add another layer of complexity to often already complex decentralized systems. They make protocols harder to audit, which could increase the risk of critical vulnerabilities being found.

Every use case of ZKPs requires a careful evaluation of benefits and downsides. Nevertheless, ZKPs remain an exciting advancement in technology, and with further progress in hardware, some of the downsides might even disappear completely.