Demystifying ZK Proofs: A Beginner's Guide

As technology evolves, so too the tactics of fraudsters.

Keeping transactions secure is a constant battle, but innovations like blockchain offer a glimmer of hope. Yet, even with blockchain's potential, we must always seek new ways to fortify security. Enter Zero Knowledge Proof, or ZKP, a solution that adds an extra layer of protection to blockchain transactions.

Blockchain and cryptography have always gone hand in hand, but introducing ZKP has renewed interest in their partnership. By utilizing cryptographic methods, ZKP ensures that transactions on a blockchain platform are secure and tamper-proof. In short, the marriage of blockchain and cryptography results in secure and unbreakable financial transactions.

What are Zero Knowledge Proofs

In layman's terms, Zero-knowledge proofs (ZKP) are a type of cryptographic proof that allows one party to prove to another party that a statement is true without revealing any additional information beyond the fact that the statement is true. This means that a prover can demonstrate the validity of a statement to a verifier without revealing any information about how the statement is true. This is useful in situations where one party needs to prove something to another party but doesn't want to reveal any sensitive information. Zero-knowledge proofs are used in blockchain technology and cryptography to improve the security and privacy of transactions.

Background

Three scientists, Shafi Goldwasser, Silvio Micali, and Charles Rackoff proposed  Zero Knowledge Proof in their 1985 paper "The Knowledge Complexity of Interactive Proof-Systems" and it's used to make sure that something is true without revealing what it is. They also found a way to prove things in a more secure way by using encryption. But scientists are still working on making this method even better and more secure.

How do zero-knowledge proofs work?

A zero-knowledge proof is a method of demonstrating the validity of a statement without revealing any additional information. This is achieved through the use of algorithms that take some data as input and return either "true" or "false" as output. To be considered a true zero-knowledge proof, the protocol must meet certain criteria:

• Completeness: It ensures that if the input is valid, the protocol will always return "true".
• Soundness: It guarantees that it is theoretically impossible to fool the protocol into returning "true" for invalid input.
• Zero Knowledge: It ensures that the verifier learns nothing about the statement beyond its validity or falsity.

A zero-knowledge proof typically consists of three elements, which go hand in hand with each other:

1. Witness
2. Challenge
3. Response

The prover starts by randomly choosing a question and calculating the answer, which is then sent to the verifier. The verifier then randomly picks another question and asks the prover to answer it. The prover's response allows the verifier to check if they truly have knowledge of the witness, and this process is repeated multiple times to ensure that the prover is not guessing the answers. The above structure is called an interactive zero-knowledge proof as it requires back-and-forth communication between the prover and verifier. An example of this is the "Ali Baba cave story" where a person wants to prove they know the secret phrase to open a door without revealing the phrase.

Types of Zero Knowledge Proof

There are two main types of Zero Knowledge Proofs: Interactive and Non-Interactive.

1. Interactive Zero Knowledge Proofs require the verifier to ask a series of questions about the knowledge the prover possesses, like in the example of finding Waldo, where the prover did a series of actions to prove their knowledge to the verifier.
2. Non-Interactive Zero Knowledge Proofs, on the other hand, do not require an interactive process, which makes it easier to scale in real-world applications. It avoids the possibility of collusion by picking a hash function to randomly pick the challenge by the verifier. In 1986, Fiat and Shamir invented the Fiat-Shamir heuristic, successfully changing the interactive zero-knowledge proof to non-interactive zero knowledge proof.

Why are Non-Interactive ZK Proofs Better?

Interactive zero-knowledge proofs, while innovative, have limitations in their practical application. These limitations include the requirement for repeated interaction between the prover and verifier, as well as a lack of availability for independent verification. To address these issues, Manuel Blum, Paul Feldman, and Silvio Micali proposed the concept of non-interactive zero-knowledge proofs.

In a non-interactive zero-knowledge proof, the prover and verifier share a key, which allows the prover to demonstrate their knowledge of a particular piece of information (referred to as the "witness") without revealing the information itself.

In contrast to interactive proofs, non-interactive proofs only require a single round of communication between the prover and verifier. The prover applies secret information to a designated algorithm to create a zero-knowledge proof, which is then sent to the verifier for validation using a separate algorithm.

The implementation of non-interactive zero-knowledge proofs resulted in a more efficient proof process. It made the proof available for independent verification by anyone with access to the shared key and verification algorithm.

The introduction of non-interactive zero-knowledge proofs marked a significant advancement in the field and served as a catalyst for developing modern zero-knowledge proving systems.

Types of Non-Interactive ZK Proofs

Non-interactive proofs represented a breakthrough for zero-knowledge technology and spurred the development of proving systems used today. We discuss these proof types below:

ZK SNARKs

ZK SNARK stands for Zero-Knowledge Succinct Non-Interactive Argument of Knowledge. It is a type of proof with certain qualities that make it unique and useful. Those qualities include:

• It is zero-knowledge, meaning that the verifier can validate the integrity of a statement without knowing anything else about it. They only need to know if the statement is true or false.
• It is succinct, meaning that the proof is smaller than the information being proven and can be verified quickly.
• It is non-interactive, meaning that the prover and verifier only interact once, unlike interactive proofs that require multiple rounds of communication.
• It is an argument, meaning that the proof satisfies the requirement of soundness, making it very unlikely for cheating to occur.
• It is knowledge, meaning that the zero-knowledge proof cannot be constructed without access to secret information. It is very difficult for a prover who doesn’t have the information to compute valid proof.

For the ZK-SNARK protocol to work, the prover and verifier need to agree on some public parameters, which are known as the Common Reference String (CRS). Generating the CRS is a sensitive operation and needs to be done carefully. To reduce the risks, multi-party computation (MPC) can be used, where multiple parties participate in a trusted setup ceremony. However, the development of ZK-STARKs has enabled proving protocols that work without needing a trusted setup.

ZK-STARKs

ZK-STARK, or Zero-Knowledge Scalable Transparent Argument of Knowledge, is a variant of zero-knowledge proof similar to ZK-SNARKs. ZK-STARKs stand out for their scalability and transparency.

One of the main advantages of ZK-STARKs is their scalability, they are faster at generating and verifying proofs when the size of the witness is larger, with prover and verification times only slightly increasing as the witness grows, unlike ZK-SNARKs where prover and verifier times increase linearly with witness size.

Another key feature of ZK-STARKs is their transparency. They rely on publicly verifiable randomness to generate public parameters for proving and verification instead of a trusted setup, meaning that they are more transparent than ZK-SNARKs.

On the other hand, ZK-STARKs produce larger proofs than ZK-SNARKs, meaning that they generally have higher verification overheads. However, in cases where proving large datasets is required, ZK-STARKs may be more cost-effective than ZK-SNARKs.

Use cases for zero-knowledge proofs

Anonymous payments

The traditional credit card payment system is visible to multiple parties, including the payments provider, banks, and government authorities. This level of financial surveillance, while beneficial for identifying illegal activity, undermines the privacy of ordinary citizens. Cryptocurrencies, on the other hand, were intended to provide a means for users to conduct private, peer-to-peer transactions. However, most cryptocurrency transactions are openly visible on public blockchains, and user identities are often pseudonymous and can be associated with real-world identities.

Privacy-focused blockchains have been developed to address this issue, such as Zcash and Monero, which shield transaction details, including sender/receiver addresses, asset type, quantity, and the transaction timeline. These blockchains use zero-knowledge technology in the protocol, which allows nodes to validate transactions without needing to access transaction data.

Additionally, zero-knowledge proofs are also being applied to anonymizing transactions on public blockchains, such as Tornado Cash, a decentralized, non-custodial service that allows users to conduct private transactions on Ethereum. These opt-in privacy tools are associated with illicit activity. To overcome this, privacy has to become the default on public blockchains eventually.

Identity protection

Identity management systems in place today expose personal information to the risk of breaches, hacking, and other malicious activities. Zero-knowledge proofs can provide a solution to this issue by enabling individuals to validate their identities while keeping sensitive details private.

In the context of decentralized identity, zero-knowledge proofs can be extremely beneficial. Decentralized identity, also known as self-sovereign identity, allows individuals to have control over access to their personal identifiers. An example of this is the ability to prove one's citizenship without revealing sensitive information such as tax ID or passport details, this is achieved by using zero-knowledge technology, which enables decentralized identity.

Authentication

The use of online services often requires individuals to provide proof of their identity and authorization to access the platform. This typically involves submitting personal information such as names, email addresses, birth dates, etc. Additionally, using long and complex passwords to ensure security can lead to difficulties in memorization and the risk of loss of access to the platform.

Zero-knowledge proofs offer a solution to these issues by simplifying the authentication process for both the platform and the users. The generation of ZK-proofs using public inputs, such as data attesting to the user's membership of the platform, and private inputs, such as the user's personal details, enables the user to present proof for authentication when accessing the service. This not only improves the user experience but also reduces the need for organizations to store large amounts of user information.

Verifiable Computation

Verifiable computation, enabled by zero-knowledge technology, is a solution for improving blockchain designs by allowing for the outsourcing of computations while maintaining verifiable results.

This is particularly relevant in the context of blockchain scalability, where the need to improve processing speeds without compromising security is crucial. Off-chain scaling approach is an alternative approach to on-chain scaling, it relies on an outsourced computation model to improve throughput on the base layer without redesigning the core blockchain protocol.

The blockchain submits a zero-knowledge proof to verify the correctness of off-chain execution, this proof is called a validity proof, which guarantees that a transaction is valid and allows the blockchain to apply the result to its state without waiting for disputes.

Conclusion

Zero Knowledge Proofs (ZKPs) have demonstrated significant potential in enhancing the security and privacy of transactions in various industries. These cryptographic methods enable the validation of a statement without revealing any additional information, providing a cost-effective solution for protecting sensitive data. The ease of use and efficient technologies supporting ZKPs make them a highly attractive option for organizations looking to fortify their security measures. As the field of ZKPs continues to evolve, it is crucial for companies to stay informed and seek expert guidance to fully leverage the benefits of this technology.