Zero Knowledge Proofs: Empowering the Future of Data Privacy and Scalable Infrastructure, Part 1

10 min readJul 17, 2023

In this post, we will delve into the fundamental concepts of Zero Knowledge Proofs (ZKPs), their versatile use cases, and explore various types of ZKPs. We will also examine intriguing applications of ZKPs in the Blockchain domain, such as ZK-rollups, zkEVMs, and ZK-bridges. Additionally, we will take a look at the notable projects actively shaping the ZK landscape. Lastly, we will touch upon key concepts that frequently arise in the ZK literature.

Fundamentals of Zero Knowledge Proofs(ZKPs)

A zero-knowledge proof, also known as ZKP, is a cryptographic way to prove a statement is true without giving away any details. In the world of cryptography, zero-knowledge proofs are used to demonstrate that something is true without exposing any related facts or secrets. Here is a really nice video explaining ZKP on different difficulty levels. The two parties involved in a ZKP are:

Prover: A prover is an entity in a ZKP protocol that aims to convince a verifier of its knowledge of a secret without revealing the secret itself.
Verifier: A verifier is an entity in a ZKP protocol that examines the evidence presented by the prover to determine the validity of their claim without gaining any knowledge about the underlying secret. The verifier can be convinced of the truthfulness of the underlying statement by simply verifying specific properties of the proof.

A Zero Knowledge Proof protocol has the following three characteristics:

Completeness: When the underlying statement is true and both the prover and verifier act honestly, the verifier can confirm or become convinced of the truthfulness of the statement
Soundness: A dishonest prover cannot manipulate an honest verifier into believing that an invalid statement is valid
Zero-knowledge: The verifier’s knowledge is limited solely to the validity of the statement.

Use-cases for zero-knowledge proofs

Privacy: ZKPs can be used to enhance privacy in blockchain transactions by concealing the transaction details, sender, recipient, and transaction amounts while still ensuring the validity of the transaction. Some projects focusing on this use case are Zcash, Monero, Tornado Cash, Mina.
Scalability: Through transaction aggregation, off-chain computation, and the use of zero-knowledge proofs, ZK rollups effectively scale the blockchain by reducing on-chain congestion, increasing transaction throughput, and maintaining security guarantees. This combination allows blockchain networks to handle a larger number of transactions in a more efficient and cost-effective manner, enabling scalability and supporting wider adoption of blockchain technology. Some projects focusing on this use case are Starkware.
Interoperability: ZKPs can enable secure and private interoperability between different blockchain networks allowing for seamless transfer of assets or data. By using ZKPs, sensitive information about the transferred assets or data can be kept confidential, ensuring privacy and confidentiality during the interoperability process. Some projects focusing on this use case are zkBridge, Electron Labs, Polymer Labs.
Identity: By employing ZKPs, users can prove their identity or membership in a network without revealing any personal or identifying information, reducing the risk of identity theft or unauthorised access. ZK-DID is a project working on this use case.

As discussed above Zero-Knowledge Proofs (ZKPs) have various applications in the field of blockchain technology. Let’s further explore the ZKPs use case for scalability and interoperability:

ZK-rollups: A rollup is a layer-2 scaling solution that executes transactions off layer-1 chain. After executing the transactions, proof of execution is posted to the layer-1 chain. ZK-rollups use validity proofs, a validity proof refers to a cryptographic proof that demonstrates the validity of a batch of transactions or a computation within a ZK-rollup construction, the cryptographic proof for the batch of transactions is verified by the bridge contract of the layer-1 chain to validate every state transition.
zkEVMs(EVM-compatible zk-Rollup): Smart contracts are written in higher level languages like Solidity. The compiler converts the high level code to bytecode. The bytecode is further broken down into Opcodes which the EVM (computes the state of Ethereum network and executes smart contract code) is able to interpret and execute. A zkEVM is an EVM-compatible virtual machine that supports zero-knowledge proof computation. Here is a post from Vitalik where he classifies zkEVMs in to four categories i.e. Type 1, Type 2, Type 2.5, Type 3, Type 4.

ZK-bridges: Cross chain bridges are currently facing security and scalability issues. In case of cross chain bridging, an on-chain light client could be used to verify the state of the source blockchain on the target blockchain. A ZK-bridge utilises Zero Knowledge Proofs to efficiently perform this verification process using on-chain light clients. ZK-bridges could play a significant role in enabling seamless interoperability and secure asset transfers across different blockchains.

Types of zero-knowledge proofs

Most commonly used ZKPs are zk-SNARKs, zk-STARKs and Bulletproofs.

zk-SNARK stands for Zero Knowledge Succinct (proofs are small and not difficult to verify) Non-interactive Argument of Knowledge. Early versions of zkSNARK required trusted setup but with further advancement in ZK research and projects like Spartan it is now possible to have zkSNARKS without trusted setup.
zk-STARK stands for Zero-Knowledge Scalable Transparent Argument of Knowledge. ZK-STARKs prove the validity of off-chain computation without revealing the inputs. However, ZK-STARKs are considered an improvement on ZK-SNARKs because of their scalability and transparency. zk-STARKS don’t require a trusted setup, the word “Transparent” points towards the use of publicly-available randomness to generate parameters and thereby not requiring trusted setup anymore.
Bulletproof: Bulletproofs are short, non-interactive zero-knowledge proofs that require no trusted setup. Bulletproofs are smaller in size but they are not as cost efficient as validity rollups. Monero is currently utilising bulletproofs.

Some of the big projects building fundamental infrastructure

Starkware: Founded in 2018, the vision of StarkWare is to bring scalability and privacy to blockchains with zero-knowledge STARK proofs. They have two main offerings (a) StarkNet is a permissionless decentralized validity rollup and (b) StarkEx is a SaaS version tailored to be used by protocols e.g. dYdX v3 was using StarkEx. In May 2022 StarkWare raised 100 million in a Series D round led by Greenoaks Capital and Coatue Management bringing its value to $8 billion.

zkSync: Matter Labs (founded in 2020) launched the zkSync project. It is a Layer 2 scaling solution for Ethereum that utilises zero-knowledge proofs (ZKPs). zkSync 2.0 which later rebranded to zkSync Era was launched. The second version introduced zkPorter, which enabled scaling Ethereum by leveraging recursive ZKPs. zkPorter allows for aggregating multiple transactions into a single proof, significantly increasing the scalability potential of zkSync. Matter Labs has raised $258M in total funding over 4 rounds. Their latest funding was a $200M Series C round in November, 2022 led by Blockchain Capital and Dragonfly.

Scroll: They are building a Type 2 zkEVM, a native zkEVM solution for Ethereum i.e. no compiler is needed. A Type 2 zkEVM is fully equivalent to the EVM. It differs from Ethereum in terms of block structure and state tree. In an EVM-equivalent environment most of the Ethereum toolchain could be used without much difficulty. Scroll is also closely working with the Ethereum Foundation’s Privacy and Scaling Explorations (PSE) group(also working on a ZK-EVM). The company has raised $80M so far from investors like Polychain and Sequoia China.

Polygon zkEVM: Polygon acquired Hermez in 2021 in a $250M deal which later rebranded to Polygon zkEVM. Their zkEVM is leveraging an interpreter which translates EVM opcodes into zkASM(Polygon’s own assembly language). Polygon’s approach is to convert every EVM opcode into zkASM opcode and later to EVM bytecode. Polygon claims that their zkEVM is fully compatible with existing Ethereum tooling.

Concepts which frequently appear in the ZK literature

Arithmetic Circuit: The first step of creating a ZKP for a problem in zkSNARKs requires breaking it down to fundamental mathematical representation using basic arithmetic operators. Most zkSNARKs are based on circuit satisfiability problem. Here is the arithmetic circuit for the statement (a*b)+(b+w) = R

Boolean Hypercube: It represents all possible combinations of boolean values for n dimensions e.g. the boolean hypercube for the set {0,1}³ will be {000, 001, 010, 011, 100, 101, 110, 111}
Elliptic Curve Cryptography: It is a cryptographic method that leverages the properties of elliptic curves to secure our digital information, such as private messages, sensitive data, or online transactions.
Fiat-Shamir Transformation: It is a technique used in cryptography to convert an interactive proof system into a non-interactive proof system.
Finite Field: In a finite field, the number of elements is limited. Binary field is a finite field where the elements can only be either 0 or 1. This means that addition, subtraction, multiplication, and division operations within the binary field will result in either 0 or 1.
Folding Scheme: The folding scheme reduces the size of the data by folding each block into a smaller value while preserving certain properties. Let’s understand Folding using the Modulo Operation example: Suppose we have a message consisting of a sequence of digits 981526937, after partitioning into 5 parts i.e. 98,15,26,93,7 and folding operation using modulo 10 e.g. for 98, 9+8=17, modulo 10 will result in first digit 7. The compressed representation of 981526937 will be 76827
GKR Protocol: GKR (Garg, Kalai, and Raz) protocol is used as a building block to perform efficient polynomial evaluations. It enables the prover to convince the verifier of the correctness of polynomial evaluations without revealing the polynomials themselves.
Hash Function: A hash function is a mathematical function that takes an input and produces as a hash value, which is unique to the input data. e.g. The SHA-256 hash value for hello world is b94d27b9934d3e08a52e52d7da7dabfac484efe37a5380ee9088f7ace2efcde9
Interactive Proofs: In an interactive proof system, the prover and verifier engage in multiple rounds of communication. The prover sends information (challenges) to the verifier, and the verifier checks the responses to determine the validity of the statement.
NP class problems: The NP class refers to a class of computational problems that can be verified in polynomial time.
Non-interactive proof: With the Fiat-Shamir transformation, the prover can generate a non-interactive proof by computing the responses to the challenges without any further communication. The verifier can independently compute the same challenges using the hash function and compare the responses provided by the prover to validate the proof.
Opcodes: Operational Codes (Opcodes) represent the individual instructions that the EVM can execute. Each opcode corresponds to a specific operation, such as arithmetic, logical operations, memory access, or control flow. Here is the full list of Ethereum Opcodes.
PLONK: PLONK (Permutation-based, LOgarithmic, Noninteractive argument of Knowledge) is a new general-purpose zero-knowledge proof scheme. Here is the article Vitalik wrote on PLONK.
Polynomial time: Polynomial time means that the time it takes to solve a problem grows at a reasonable rate as the problem gets bigger. It’s like having an algorithm that can handle larger and more complex tasks without taking too much time to find a solution.
Polynomial Commitment Scheme: The Polynomial Commitment Scheme allows you to generate commitments to polynomial evaluations at specific points without revealing the polynomial’s coefficients. Others can verify the evaluations by recalculating the commitments using the shared commitments and evaluation values, ensuring the correctness of the evaluations without learning the polynomial’s details.
Powers of Tau: In the trusted setup phase, a group of participants collaboratively performs a multi-party computation protocol. Each participant contributes a random value known as a “contribution” and applies a series of cryptographic operations to derive a combined “toxic waste” value. The resulting toxic waste value is transformed into a set of public parameters, known as the Powers of Tau.
R1CS: R1CS stands for “Rank-1 Constraint System,” which is a mathematical representation of a computational problem.
Random Oracle: It is a function that takes any input and produces an unpredictable and unique output.
Sum Check Protocol: The Sum Check Protocol is a technique used in interactive proof systems to efficiently verify the sum of values computed by a prover without revealing the individual values themselves. It allows a verifier to interact with a prover to determine if the sum of certain values meets a specific criterion.
Simulation Paradigm: The simulation paradigm is an approach used in cryptography to analyse the security of cryptographic protocols. It involves designing protocols such that the behaviour of adversaries can be effectively simulated, allowing for the evaluation of security properties without direct participation of the adversaries themselves.
Trusted Setup: In the trusted setup phase, a group of participants collaboratively performs a multi-party computation protocol. Each participant contributes a random value known as a “contribution” and applies a series of cryptographic operations to derive a combined “toxic waste” value.

Validity Proof: A validity proof refers to a cryptographic proof that demonstrates the validity of a batch of transactions or a computation within a ZK-rollup construction.
Witness: In the context of NP class problems, a witness is a solution or piece of evidence that demonstrates the truth of a statement.

… to be continued

Refrences: