Validity (ZK) Proofs vs. Fraud Proofs

Written by Alchemy

Reviewed by Brady Werkheiser

Published on October 19, 20227 min read

---

Ethereum’s exponential growth presents difficulties in processing and storing data, especially when constrained within block limits that are required to preserve decentralization and data security by verifying each transaction on the blockchain.

Unlike sidechains that run parallel to Ethereum but don’t acquire the benefits of its security and monolithic blockchains which rely on their own consensus mechanisms to guarantee valid states, layer 2 blockchains use proofs as part of their blockchain architecture.

What type of blockchains use proofs?

Proofs are most popularly found in layer 2 blockchains that use rollups to achieve scale and increased throughput while ensuring the state of the base chain is correct. A rollup is a type of scaling solution which batches transactions on a separate blockchain and uses proofs to ensure the truthfulness of transactions.

There are two main types of rollups:

1. Optimistic Rollups - assume all transactions are valid and uses fraud proofs to prove false transactions within 7 days

2. Zero Knowledge (ZK) Rollups - instantly prove if transactions are valid or not using validity proofs

Validity proofs and fraud proofs verify the legitimacy of transactions before they're recorded to the base chain's state.

What is a validity proof?

A validity proof, also known as a zero knowledge (ZK) proof, is a transaction verification method that takes place between a prover, someone who is creating a proof for some information, and a verifier, who verifies the proof with no information shared between the two.

The information shared between a prover and a verifier is called a witness and is typically the solution to a complex mathematical equation. In essence, the prover needs to show they know the witness accurately, and the verifier needs to be able to reliably ascertain whether the prover has knowledge of the witness.

How does a validity proof work?

Validity proofs are designed to be difficult to break and rely on a cryptographic technique known as polynomial commitments. In polynomial commitments, information from each step of a verification computation is encoded into polynomials, and a factored polynomial expression can stand in for a large number of equations between numbers. 

By verifying the polynomial equations, you are implicitly verifying the numerical calculations, but the process for hashing these polynomials is complicated. The three major polynomial hashing schemes used for polynomial commitments are:

1. KZG (Kate) Polynomial Commitments

2. Bulletproofs

3. FRIs

FRI stands for "Fast Reed-Solomon Interactive Oracle Proofs of Proximity."

What blockchains use ZK proofs?

A few examples of blockchains that use Zero Knowledge proofs and rollups are zkSync, StarkNet, and Zcash. 

All ZK rollups have a concerted focus on security and transaction verification, which allows them to be used reliably in a variety of use cases. zkSync and Zcash have more of a focus on transactions, while StarkNet has diversified to support a variety of dapp and DeFi ventures, including Immutable X, a framework for secure NFTs and web3 development for the gaming community. 

What is a fraud proof?

A fraud proof, also known as a fault proof, is a proof submitted by a verifier that challenges a transaction state. Based on the implementation, the fraud proof runs through a segment of the transactions and attempts to validate them.

Here's a simple explanation:

• If the fraud proof spots an error, the transactions inserted into the batch are removed and the batch is reverted to a previous, verifiably correct state.

• If no fraud proofs are submitted during the dispute period, the state change is optimistically assumed to be correct.

How does a fraud proof work?

Fraud proofs work by comparing Merkle roots and verifying the beginning and end state roots through either a single round of computation (like Optimism) or multi-round computation (like Arbitrum). 

The blockchain runs on a data structure known as a Merkle Tree, which contains each transaction as a leaf in the tree and subsequent branches represented by increasingly complex hashes of the tree.

The root node, also known as the Merkle Root, is a hash that effectively condenses the data so users do not have to consistently download the entirety of the main chain. 

If a verifier wants to challenge a transaction state change, they only need to submit the current post-state root and specific parts of the Merkle tree that can be used to compute the correct post-state root. If the two disagree, then the transaction state changes are reverted and the hash is reset to a provably correct state root.

What blockchains use fraud proofs?

Fraud proofs and the optimistic rollup model are substantially cheaper and quicker than transactions on the main chain, which is why they are preferred by blockchains like Arbitrum, Optimism, and Metis Andromeda. 

Optimism and Arbitrum use their own EVM-compatible virtual machines designed for optimistic rollup functionality, especially the ability to batch transactions and increase throughput, while Metis focuses more on the applicability of its L2 system and boasts a variety of features that aid in the creation and development of dapps, DAOs, and a DeFi ecosystem.

How are validity proofs and fraud proofs similar?

ZK and fraud proofs are similar in that both use rollup solutions to scale and both have multiple implementations for different use cases. 

1. Both are Used in Layer 2, Rollup-based Solutions to Increase Scalability

Rollups were designed to remove a majority of the load from the main Ethereum blockchain. Instead of running transactions on the mainnet, rollups move computation off-chain while keeping a small amount of data-per-transaction on Ethereum. By compressing transactions, rollups allow for higher transactions per second (TPS) scalability and lower average gas costs. 

The two main types of rollups are optimistic and ZK rollups.

The key feature of optimistic rollups is that they initially assume all transactions are valid and allow these transactions to be added to the batch. After submission, there is a dispute period in which transactions can be challenged by a fraud proof. 

Zero knowledge rollups are similar to optimistic rollups because they also aggregate transactions into batches for submission, but one main difference between them is that ZK rollups use validity proofs to validate each transaction before it is committed to the rollup without the sharing of personal information. 

2. Validity Proofs and Fraud Proofs Have Multiple Implementations

Validity proofs have multiple implementations including but not limited to SNARKs and STARKs, and fraud proofs have multiple implementations including single rollups, and multi-round rollups.

SNARKs vs. STARKs

Two popular ZK proof implementations are SNARKs and STARKs.

A SNARK is a:

• Succinct

• Non-interactive

• ARgument of

• Knowledge

ZK SNARKs create small, quickly verifiable arguments of knowledge (i.e. computationally sound cryptographic proofs) that don’t need additional information beyond the proof itself. 

Similarly, a STARK is a:

• Scalable

• TRansparent

• Argument of

• Knowledge

The key difference between a SNARK and a STARK is the scalable, transparent properties of STARKs. STARKs are scalable because their proofs scale linearly, while SNARK proofs only scale quasilinearly. Because of this, STARKs are preferred for larger transactions.

In addition, SNARKs are transparent because they can use publicly verifiable randomness to set up interactions between provers and verifiers instead of relying on a more centralized, trusted setup.

Single vs. Multi-Round Rollups

The two main types of optimistic rollups are single and multi-round rollups, used by Optimism and Arbitrum respectively. When a verifier submits a fraud proof to challenge a transaction on Optimism, the entirety of the proof is run on the EVM, which is a relatively quick and easy process that is only limited by the dispute time delay (DTD) of one week. 

On the other hand, Arbitrum’s fraud proof verification process relies on an interactive off-chain dispute verification process where the asserter and challenger repeatedly narrow down sections of the transaction in multiple rounds until they find a section where they disagree. 

How are validity and fraud proofs different?

ZK proofs and fraud proofs have multiple differences, including the amount of computation they need, the time it takes for them to validate a transaction, their security, and their difficulty of implementation. 

1. Validity Proofs Are More Computationally Intensive Than Fraud Proofs

ZK proofs are inherently mathematically challenging to validate, and intense computation is usually required given the technical nature required of a truly zero knowledge verification process. 

Fraud proofs are typically cheaper per batch, at around 40,000 gas, while ZK SNARK proofs require 500,000 gas. However ZK SNARKs are cheaper on-chain because optimistic rollups need to publish all data back to the main blockchain for a fraud proof to legitimize or disprove a result. 

2. Validity Proofs Are Instant, While Fraud Proofs Have a Dispute Time Delay 

A major difference between ZK and fraud proofs is that while ZK proofs validate a transaction immediately, fraud proofs have an intrinsic Dispute Time Delay (DTD) that slows down transactions. Only if no fraud proofs have been submitted by verifiers regarding a given batch, will that batch actually be published to Ethereum.

3. Validity Proofs Are More Decentralized and Data Secure

Because ZK proofs require minimal interaction (e.g. just the sharing of a proof to a validator), and this process can be done securely, they are very decentralized. 

Furthermore, because the proofs are zero knowledge and perfectly accurate, validity proofs protect user privacy and minimize the risk of serious threats like 51% attacks on the L1 chain.

Optimistic rollups, however, require a verifier to submit a fraud proof, which can be intercepted or DDoS’d to prevent a transaction state challenge from going through to the batch. 

4. Validity Proofs Are Harder to Implement

While optimistic rollups, and consequently fraud proofs, can work on any EVM or Optimistic Virtual Machine (OVM), zero knowledge proofs and ZK rollups require specialized virtual machines called zero knowledge Ethereum Virtual Machines (zkEVMs).  These virtual machines can execute smart contracts in a way that works with ZK computation and cryptographic validity proofs.

Up until very recently, zkEVMs were thought to be only theoretically possible, and even now it is challenging to wrap EVMs to support ZK proofs. However, there are new developments in the ZK space that are allowing for increased throughput and scalability improvements for ZK proofs. 

Most notably, Polygon is creating its own rollup technology, which use recursive ZK SNARKs to more efficiently carry out transactions off-chain before returning to the main chain. Recursive proofs work by proving multiple transaction blocks at a time and then proving an aggregated block as well. 

In essence, SNARKs are proving other SNARKs, resulting in one final transaction at the end which is even more efficient than multiple, rolled-up transactions. Polygon’s Polygon Zero uses Plonky2 to create these recursive proofs, and it is the fastest proving scheme currently available. 

Another option is a Validum, a type of ZK Rollup where instead of storing some of the data on-chain, all of the data is stored off-chain instead. A risk factor with this setup is that StarkEx operators can prevent access or modify off-chain data, but this is mitigated by the creation of the Data Availability Committee (DAC), which provides neutral and honest data storage.

What layer-2 scaling solution should I use?

Up until recently, fraud proofs and optimistic rollups were favored because ZK proofs were difficult to implement and much more computationally intense, but a variety of new developments in the zero knowledge space are making ZK rollups more accessible than ever.

With more zkEVMs on the rise, and the guarantee of more secure, informationless, and non-interactive transactions, ZK rollups are an emerging go-to layer-2 scaling solution.