The World of ZK (Zero-Knowledge) Proofing
Co-authored by: Samuel Oscar Yobeliano, Kennard Low, Alden
Nothing following this constitutes financial advice — if construed otherwise, NGMI.
All data presented henceforth are accurate as of 31 December 2022.
Introduction
ZKProof, also known as Zero Knowledge Proof, was first found by a group of scientists in 1985 in their paper “The Knowledge Complexity of Interactive Proof-Systems”. It allows you to let the person on the other end know that you are aware of one or more secrets without actually telling them. It is a quick and safe way to demonstrate the validity of a claim without revealing any secret information.
In ZK, no (zero) information regarding the secret is revealed, yet Person B (Verifier), is absolutely convinced that Person A (Prover) is aware of the relevant secret.
The Zero Knowledge Protocol does not communicate passwords, making password theft extremely impossible. This is great since it secures your conversation, making it impossible for anyone else to know what you’re discussing or what files you’re sending.
What It Aims to Solve
It is a common occurrence in our everyday lives to have to prove something to another party, be it proving your income level when making a loan or something trivial like proving that you have a good recipe for a specific dish that you have worked on. The problem is that, oftentimes, we would like to prove to the other party that you have that information without actually showing that same information. Personally Identifiable Information (PII) shared with third-party services is stored in central databases, which are vulnerable to hacks. With identity theft becoming a critical issue, there are calls for more privacy-protecting means of sharing sensitive information.
This issue is resolved by zero-knowledge proofs, which do not require information to be revealed in order to establish the validity of claims. The statement (also known as a “witness”) is used as input by the zero-knowledge protocol to produce a brief proof of its validity. Without disclosing the data used to make the statement, this proof guarantees that the claim is accurate.
Applications
ZK-SNARK
One of the widely known applications of ZK rollups is ZK-SNARK (succinct non-interactive argument of knowledge), which is utilised by ZKsync. ZKsync is a popular L2 scaling solution which has gained traction in recent years, and is famed for (i) security, (ii) high throughput and (iii) high liveness of the network.
After the transactions are bundled together, a SNARK containing the proof of validity for every transaction is generated for the rollup block. The rollup block will then be posed to the mainchain for verification. However, since the funds are held on the mainchain, this provides a significant security guarantee that is equivalent to that of the underlying L1, ethereum. This also means that the rollup validator is also unable to steal or corrupt the funds.
Transactions are also instantly confirmed and shown to the receiving party, and these received assets can immediately be used for other transactions. Since the nature of this is a promise on the validators’ end, they are required to post a bond which would otherwise be slashed if the transaction is not on the new ZKsync block.
Lastly, to ensure liveliness of the network and withstand the effects of scaling, roles are clearly segmented with their respective responsibilities — Guardians and Validators. Guardians tend to be holders who have staked their ZKsync tokens, and their job is to nominate honest and operational validators. By monitoring the network traffic and preventing censorship behaviour, they are able to preserve the value of their staked shares. Validators are the one doing most of the “grunt” work, which involves rolling up transactions and generating the SNARKS for them. To also keep the consensus mechanism fast, only 30–100 nominated validators are allowed at any given time. In return, validators receive transaction fees in accordance with the denomination of those transactions, while validators receive fees in the form of ZKsync tokens.
ZK-STARK
Another common application of ZK-rollups is ZK-STARK, a technology invented by StarkNet. In essence, it utilises the same underlying technology of ZK-rollups, but ties a cryptographic hash to the proofs. This allows for transparency, which is why it’s termed as STARK (Scalable Transparent Arguments of Knowledge).
ZK-STARKs differ from their counterpart (ZK-SNARK) in 3 different ways, which are that of (i) transparency, (ii) scalability and (iii) structure. ZK-STARK prioritises transparency and scalability by removing the need for a trusted setup (initial generation of keys needed to be used in every transaction verification process), which ZK-SNARKs require. In return, ZK-STARKs use publicly verifiable randomness, which allows them to generate proofs quicker and hence scale faster. In terms of structure, the lean cryptography in ZK-STARKs are also collision resistant, which means that it’s computationally infeasible to find / generate 2 colliding hashes.
On the whole, both ZK-STARK and ZK-SNARK are the 2 most common use cases of ZK-rollups till date. Given its ability to facilitate scaling, its practicality will be increasingly relevant with increasing adoption of cryptocurrencies in the future.
What is a Rollup?
Before diving into ZK-Rollups, let us first introduce the basic concept of rollups.
In essence, a rollup is a Layer-2 hybrid scaling solution that involves the off-chain ‘bundling’ and execution of transactions while keeping a minimal amount of data on its underlying Layer-1 chain, using complex data compression methods.
By moving computation and state-storage off-chain while keeping some transaction data on-chain, rollups were designed to improve transaction speed and throughput significantly. With data compression, there is also a potential fall in user fees due to the reduced amount of data published on-chain (a regular transaction on Ethereum takes 110 bytes, while a transaction on a rollup takes only 12 bytes). Rollups also derive security from their underlying chain i.e Ethereum, since transaction data still has to be validated on-chain eventually on consensus.
According to Vitalik’s Incomplete Guide to Rollups, “rollups are fully general-purpose, and one can even run an EVM inside a rollup, allowing existing Ethereum applications to migrate to rollups with almost no need to write any new code”.
Types of Rollups
There are two types of rollups: Optimistic Rollups and Zero-Knowledge Rollups (ZK-Rollups)
Optimistic Rollups automatically assume that transactions are valid, unless they are challenged by validators with a Fraud Proof.
ZK-Rollups, on the other hand, require all the transactions that were computed off-chain to be verified using Validity Proofs.
Components of a ZK-Rollup
- Smart Contracts
There are two on-chain contracts in charge of running a ZK-Rollup protocol: a main contract and a verifier contract. The main contract stores rollup blocks, tracks deposits, and monitors state updates while the verifier contract verifies ZK-proofs submitted by validators / operators.
2. Off-chain Virtual Machine (VM)
This VM acts as the secondary later for the ZK-Rollup protocol, where transactions are executed and states are stored.
ZK-Rollup State
The ZK-Rollup state includes the accounts and balances on Layer-2, and is represented as a Merkle tree, which is a data structure used to efficiently encode blockchain data.
In the diagram below, T represents “transaction” while H represents “hash”. Hashes on the bottom row are called “leaves” while those in the intermediate rows are called “branches” and the top hash is called a “root”.
The state of a ZK-Rollup is stored in an on-chain contract in the form of a Merkle root, allowing changes to be publicly tracked. This is known as the state root.
How Do ZK-Rollups Work?
Transactions
Users sign transactions and submit them to ZK-Rollup operators that bundle thousands of transactions in a batch, executing them simultaneously. This causes the rollup to transition into a new state, which is updated when operators submit the newly computed state Merkle root to smart contracts on the underlying Layer-1 chain along with compressed transaction data (in the form of calldata*) and a validity proof (in the form of ZK-SNARKs or ZK-STARKs).
The verifier contract confirms the validity of all transactions in the batch by verifying the submitted data and validity proof. Once the state transition is verified, the previous state root is updated to the new state root while exit transactions are executed, sending funds to the recipients’ wallet addresses.
*calldata is a temporary data area of a smart contract which stores function arguments, behaving almost like memory. As calldata is not stored on Ethereum’s state, it does not affect the state but stays on-chain in Ethereum’s history logs.
What Are Validity Proofs?
Validity proofs, also known as ZK-Proofs, are cryptographic proofs that allow provers to prove that they possess certain information without revealing the information itself. They are used in ZK-Rollups to allows the verification of transaction statements without disclosing the transaction data itself.
Three Requirements of Zero-Knowledge Proofs
Completeness: An honest verifier will be persuaded by an honest prover if their claim is true
Soundness: A dishonest prover will not be able to persuade the verifier that a false claim is true
Zero-Knowledge: If the claim is true, the verifier will not know what it is, except for the fact that it is indeed true
Types of ZK-Proofs
ZK-SNARK (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge)
A ZK-SNARK refers to a proof construction where one can prove possession of certain information without revealing that information, and without any interaction between the prover and verifier.
In its name, ‘Zero-Knowledge’ refers to the verifier knowing nothing about transaction data, ‘Succinct’ refers to the small size of proofs, and ‘Non-Interactive’ refers to the absence of interaction between a verifier and a prover.
ZK-SNARKs use elliptic curves
For more on ZK-SNARKs, check out Vitalik’s introduction to ZK-SNARKS and how they work.
ZK-STARK (Zero-Knowledge Scalable Transparent Argument of Knowledge)
ZK-STARKs, invented by StarkWare, enforce the integrity and privacy of computations on blockchains, using novel cryptographic proofs and modern algebra.
In its name, ‘Zero-Knowledge’ refers to the verifier knowing nothing about transaction data, ‘Scalable’ refers to the capacity to handle a large amount of verifications, and ‘Transparent’ refers to its transparent system configuration used.
ZK-SNARKs vs. ZK-STARKs: The Differences
ZK-SNARKs incorporate the use of elliptic curve cryptography which generates secure cryptographic keys using elliptic curve properties while ZK-STARKs use hash functions. ZK-SNARKs also have smaller proof sizes compared to ZK-STARKs, resulting in faster verifications requiring a lower amount of gas.
ZK-Rollup vs. Optimistic Rollup
As mentioned before, ZK-Rollups utilises validity proof which uses the concept of ZK-SNARK to validate each batch of transactions before submitting it to the parent chain.
Conversely, Optimistic Rollup assumes all transactions contained within the rollup are valid and submits batches without any computation. Unlike ZK-Rollups, Optimistic Rollup uses Fraud Proof which can be published by anyone monitoring the chain. The Fraud Proof protocol enables state transitions to be challenged within a predetermined time frame called the Dispute Time Delay (DTD). If the state transition is not challenged within this DTD, the state transition is considered valid. On the other hand, if the state transition is challenged and is proven to be incorrect, the malicious actor will incur a high penalty and the batch will be reverted.
Fraud proof works by comparing the data structure of a blockchain known as Merkle trees, which stores every transaction, each represented by a hash.
A verifier that wants to challenge the validity of the state transition would need to provide the data in green which contains the transactions within the batch and also other parts of the merkle tree needed to prove the accounts were read or modified by the batch. The data in yellow will be reconstructed from the nodes in green and will be used to compute a post-state root that will be compared against the provided post-state root. If the two post-state roots differ, the batch will be considered fraudulent.
ZK-Rollup offers a throughput cap that is similar to Visa, a digital payments service provider. This is significantly higher than Optimistic Rollup as large chunks of transaction data that is used to verify transactions can be omitted, leaving only relevant data required to cause state changes. Optimistic Rollup requires users to publish the complete transaction input in case it needs to be checked for Fraud Proof.
The time needed to withdraw funds from rollups is significantly shorter for ZK-Rollups than Optimistic Rollups. The ZK-SNARK proof can be verified by the network almost instantly, allowing for very quick withdrawal of funds. However, Optimistic Rollups may take up to 2 weeks as time needs to be given to network participants to publish a Fraud Proof and cancel the withdrawal if they suspect fraudulent activities.
Optimistic Rollups do not require any computation to submit the batch to the parent chain whereas ZK-Rollups would perform complex mathematical operations to create a cryptographic proof for each batch of transactions, this translates to higher computational costs for processing transactions.
ZK-Rollup is generally more secure than Optimistic Rollup as well as you do not need to wait for the Fraud Proof window to close nor do we need to rely on the integrity of sequencers (sequencers are responsible for ordering and executing transactions).
While ZK-Rollups are superior in terms of throughput, transaction finality time and security, most developers still turn to Optimistic Rollup due to its ease of programming and EVM compatibility. However, there are currently efforts (Cairo etc.) working to improve on this
Challenges
Large Computing Power Required
In interactive ZKPs where many interactions are needed between the prover and verifier, computationally intensive algorithms are used. The same goes for non-interactive ZKPs which require advanced computational capabilities making ZKPs unsuitable for slow devices. All of this translates to a high capital expenditure required to have the protocol running optimally.
Not 100% Guarantee
ZKPs do not give a 100% guarantee that the prover’s information is true. As mentioned in the above parts, the probability of the prover lying or not having accurate information decreases exponentially with each iteration. While the probability of the statement being wrong is significantly low, it is never zero.
Conclusion
Zero Knowledge Proofing has the potential to revolutionise various industries in its maturity and we are especially optimistic in its use case in blockchain payments. The emergence of zk-Rollups has brought a bullish sentiment for the market in hope for a better blockchain payment process for everyone. However, it is crucial to note that while it currently “unlocks several business cases like inventory management” and more advanced tools that can handle more complex business logic, it doesn’t yet support complex business logic, as said by EY global blockchain lead Paul Brody. There is still some time before zk-proofing can be a fully fledged solution in the blockchain industry.
