[ZK] Part 1: ZK-Proofs

This article is Part 1 of a series that will cover the basic principles of zk-proofs and how they are applied in the context of blockchain.

Introduction

In recent years, there has been a growing interest in zero-knowledge proofs (zk-proofs) as a powerful solution for scaling throughput and enhancing privacy and security in the blockchain. In simple terms, zk-proofs are a method in cryptography that allows one party (the prover) to prove to another party (the verifier) that something is true, without revealing any additional information.

Although the concept of zk-proofs is not new, having been introduced in a 1985 MIT research paper by Shafi Goldwasser, Silvio Micali, and Charles Rackoff, their application in blockchain technology is a recent development.

The compatibility between zk-proofs and blockchain technology allows for a versatile range of applications, each delivering unique benefits. The most common applications of zk-proofs in blockchain are privacy protection, achieved through the masking of transaction data, and scaling, accomplished by validating the legitimacy of bundled transactions. These advantages can be attained while simultaneously preserving transparency and auditability in the blockchain.

What are Zero-Knowledge Proofs

A zk-proof is a type of cryptographic proof that allows one party to prove the authenticity of a statement to another party without revealing any additional information beyond the validity of the proof. To achieve this, zero-knowledge protocols rely on mathematical algorithms that take some data as input and return ‘true’ or ‘false’ as output.

In order for zero-knowledge protocols to work, they must meet three requirements:

• Completeness: If the input is true, the zk-proof always returns ‘true’
• Soundness: If the input is false, it is impossible for the zk-proof to return ‘true’
• Zero-knowledge: No additional information is shared between the two parties

How do Zero-Knowledge Proofs Work?

The concept of zk-proofs has its roots in interactive proof systems that involve a series of interactions between two parties. These repeated interactions, combined with cryptographic techniques would enable these parties to determine the validity of a statement.

To help illustrate the concept of zk-proofs, let’s consider the scenario where Person A (the prover) needs to prove to Person B (the verifier) that they are over 18 years old, without disclosing their exact age. In this case, the statement in the zk-proof could be “I am over 18 years of age.”

To demonstrate the truth of the statement, Person A could choose to enter a bar, while Person B remains outside. The fact that Person A is able to enter the bar is evidence that they are over 18, as individuals under 18 are not allowed to enter bars. However, this evidence is not conclusive, as it is possible that Person A was able to enter the bar due to luck.

To further verify the statement, Person B could challenge Person A to enter another bar, and then another, and so on. By repeating this process, and if Person A is able to successfully enter every bar that Person B challenges them with, they can probabilistically prove to Person B that the statement “I am over 18 years of age” is indeed true.

It is important to note that the above example is an oversimplified illustration of how zk-proofs work. In actuality, the process of proving the statement “I am over 18 years of age” involves complex mathematical computations, rather than simply visiting multiple bars. These computations are designed to ensure that valid inputs invariably produce true outputs, and invalid inputs unfailingly result in false outputs. Furthermore, as each round of challenges progresses, the likelihood of the prover succeeding by chance decreases exponentially.

However, interactive proving had certain limitations that made it unsuitable for blockchain application. For instance, while a verifier might be reasonably certain of the truth of a prover’s statement, the validity of proofs was only probabilistically correct. The process also required the parties to interact repeatedly, which can be time-consuming and inefficient, and the proof could not be independently verified and audited, since generating a new proof required a fresh set of messages between the prover and verifier.

In order to address these limitations, non-interactive zk-proof systems were developed which minimized the need for interaction between the prover and verifier, requiring only a single exchange. These novel zk-proof systems were designed with more complex cryptographic mechanisms and introduced various innovations that improved their practicality in blockchain applications. Notably, these innovations included deterministic accuracy, reduced proof size, and diminished computational overhead, all of which made zk-proofs more reliable and efficient in the context of blockchains.

Types of Zero-Knowledge Proofs

There are numerous types of zk-proofs, but the three most commonly applied in blockchain are zk-SNARKS, zk-STARKS, and Bulletproofs. While all three are designed for similar use cases, they differ in their underlying mathematical constructions, properties, and the trade-offs they offer.

Zk-SNARK

Zk-SNARKs (Succinct Non-interactive ARgument of Knowledge) are a type of cryptographic proof that are used for privacy-preserving computations. SNARKs rely on a trusted party in the setup process to generate cryptographic parameters using elliptic curves.

Advantages of SNARKs

• Small proof size and fast verification time due to elliptic curve parameter
• High security due to infeasibility in finding discrete logarithm of a random elliptic curve element from a publicly known base point

Disadvantages of SNARKs

• Security of protocol is only as strong as trustworthiness of the party generating parameters
• Longer prover time due to trusted setup process to generate proof

Zk-STARK

Zk-STARKs (Zero-knowledge Scalable Transparent ARgument of Knowledge) are a type of cryptographic proof that uses publicly verifiable and transparent computation. STARK parameters are generated using a transparent algorithm and do not require a trusted party.

Advantages of STARKs

• Scalability due to exponential growth of prover and verification speed with more witnesses
• Transparency
• Quantum-resistant and high security with hash function

Disadvantages of STARKs

• Large proof size
• Higher computing overhead due to algorithmic complexity of hash functions

Bulletproof

Bulletproofs are another form of zk-proof that aims to improve on the limitations of zk-SNARKs and zk-STARKs. They are small in size and do not require a trusted setup.

Advantages of Bulletproof

• Computation and storage efficient due to small proof size
• Transparency

Disadvantages of Bulletproof

• High setup costs
• Longer prover time due to complexity of implementation

Application of Zero-Knowledge Proofs

Zk-proofs have significant implications for blockchain technology, particularly in terms of enhancing privacy, security, and scalability. It can be applied in numerous ways for varying benefits.

One of the key applications of zk-proofs is privacy protection. With traditional blockchain systems, transaction details, including the amount transferred and the addresses involved, are publicly visible on the blockchain. This has been a key characteristic of blockchain systems, because transactions need to be publicly auditable to ensure integrity. However, by applying zk-proofs, it is possible to prove that a transaction is valid without revealing the specific details of the transaction, such as the amount transferred or who the sender or receiver are. This can help protect the privacy of smart contract transactions, which may involve sensitive information like personal data or financial information, and can help prevent MEV attacks.

Another important application of zk-proofs is for scalability with the use of zk-rollups. The growth of blockchain technology has been accompanied by increasing concerns about its scalability, as traditional blockchains can be slow and expensive to process transactions. Zk-rollups can aggregate a large number of transactions off-chain using zk-proofs and then submit a single proof of their validity to the main chain. This helps compress the size of transactions and reduce the computational overhead of processing them.

Zero-knowledge technology is already being utilized by numerous blockchain projects, and it is expected that advancements in this field will continue to receive significant attention in the years ahead.

The upcoming part of this series will cover the steps involved in generating zk-SNARKs for zk-rollup compatibility.

Author: Aaron Lee