Validity Proofs vs. Fraud Proofs
Published on: May 9, 2024

Validity Proofs vs. Fraud Proofs

Introduction

As the demand for faster and cheaper blockchain transactions grows, various Layer 2 (L2) scaling solutions have emerged. These solutions aim to scale the underlying L1 (almost always Ethereum) by processing transactions offchain while inheriting the base layer’s security. The two primary approaches for verifying the correctness of L2 state transitions are fraud proofs, used by optimistic rollups (ORs), and validity proofs, used by validity rollups (VRs). In this post, we examine the key advantages of validity proofs over fraud proofs and address common misconceptions.

Background

L2 solutions aim to address scalability challenges by executing numerous transactions off of L1, bundling them together, and then processing them as a single transaction on Ethereum’s base layer. There are two main types of proofs used to establish the integrity of L2 state transitions:

  • Fraud proofs: These proofs assume L2 blocks are correct unless proven fraudulent within a challenge period. If a fraudulent state transition is detected, a fraud proof can be submitted to revert the chain to the last valid state.
  • Validity proofs: This approach requires each L2 state transition to be accompanied by a cryptographic proof of its correctness. The L1 chain accepts a state transition if and only if it has valid proof.

It’s important to note that proof systems (e.g., STARK, SNARK) can be used for both fraud proofs and validity proofs. The distinction lies in what is being proven rather than how it is proven.

Security: a fundamental advantage of validity proofs

One of the most significant benefits of validity proofs is the guarantee that an L2 chain can never be in an invalid state, making validity proofs more secure than fraud proofs. In contrast, fraud proofs allow invalid blocks to be temporarily accepted, creating security risks:

  • 51% Attacks: In a 51% attack on an L1 chain via an OR, attackers could produce a fraudulent block and build the required confirmation blocks within the dispute period. This would allow them to steal funds before a fraud proof could be submitted. With validity proofs, a 51% attack can, at worst, censor new blocks or roll back the chain to a previously valid state, but invalid state transitions will never be accepted.
  • Disruption of Dispute Process: Fraud proofs rely on an interactive dispute process that could be disrupted, preventing invalid transitions from being rolled back. Silence is interpreted as approval of the new L2 state.

With validity proofs, a 51% attack can at worst censor new blocks or roll back the chain to a previous valid state. Invalid state transitions will never be accepted, regardless of L1 chain disruptions. On a VR, approval of the new L2 state depends on the validity of the transactions ahead of time.

Enhanced capital efficiency

Validity proofs offer a significant advantage in terms of capital efficiency by enabling much faster withdrawals from L2 to L1:

  • Speedy Withdrawals: Fraud proofs necessitate waiting out a challenge period (often ~1 week or more), while validity proofs allow secure withdrawals in the time it takes to generate a proof (typically 10 minutes or less). This 100x or greater difference in withdrawal times has substantial implications for capital efficiency.
  • Reduced Capital Lockup: Fraud proofs require a significantly larger amount of capital to be allocated to cover potential withdrawals during the extended dispute window.

Although fast withdrawal mechanisms can help mitigate this issue, they have limitations. With certain assets like non-fungible tokens (NFTs), fast withdrawals tied to specific onchain collateral are impossible since the L2 and L1 versions are not equivalent. In these cases, validity proofs still offer much faster withdrawals than fraud proofs in ORs.

Onchain scalability

In this section, we will compare two rollup systems where data is available onchain: OR and STARK validity rollup (StR). Any solution that stores data onchain has the undesirable property of onchain resource consumption growing linearly with the volume of rollup transactions. Onchain data includes some state (e.g., transaction details) and a witness (e.g., digital signatures that prove the consent of the transacting parties). The key difference between OR and StR is that OR witness scales linearly with the number of transactions, whereas StR replaces all those witnesses with a single proof that scales poly-logarithmically with the number of transactions. For sufficiently large batches, StR’s onchain data footprint is considerably smaller than OR’s. To elaborate further, in StR, the witness can attest to checks performed by the rollup operator (e.g., all digital signatures were verified). As a result, a witness (e.g., a validity proof) is required per batch of computations, eliminating the need to append a witness to every single transaction. In modern validity proof systems, the proof is of a practically fixed size (poly-logarithmically, as stated above). Consequently, as the batch grows, the amortized cost of the witness per transaction decreases. In contrast, OR requires a witness per transaction to allow validators to ensure correctness, and thus, there is no amortization benefit to larger batches. Moreover, the witness in OR is considerably larger than the transaction itself. For example, the OR witness must include all user signatures, whereas, in StR, those can be removed (as the proof will attest that they were checked offchain). In transparent payments, the witness is 3-5 times bigger than the payment itself; in more complex applications (e.g., shielded transactions), the witness is often 10 times bigger than the state, if not more. This way, OR consumes significantly more onchain resources than StR and will reach a scalability ceiling well before StR does.

General computation overhead

A common comparison between validity proofs and ORs focuses on their computational overhead: How much additional work is required for a given offchain computation? We will focus on STARK, as that is the validity proof framework currently being implemented by StarkWare. ORs are often said to have a 100x overhead, as having 100 validators monitoring each other is expected to ensure computations are performed correctly. Each validator must conduct the actual computation, resulting in the 100x overhead. It is important to note that a smaller or more predetermined set of validators increases the risk of collusion or external attacks through bribery. In the case of STARK proofs, only one entity-the prover-needs to perform a large computation, as verification is computationally less intensive. The prover’s overhead is often quoted as 10,000x due to the computation complexity of generating the proof. However, in reality, the overhead for the STARK proof system is approximately 100x, similar to ORs, for several reasons:

  • For arithmetic and algebraic operations, the computational overhead is already less than 100x. The Pedersen hash function, currently in use, is only 20x more expensive to STARK-prove than to compute directly.
  • While operations like SHA-256 have considerable overhead, there are plans to replace these hash functions with STARK-friendly alternatives. The chosen STARK-friendly hash function is expected to be about 100x slower to prove than an efficient hash computation, such as SHA-256.

A frequently cited advantage of ORs is their applicability to general computations and being EVM compatible by default. However, the Cairo programming language is used by Starknet, enabling STARK-provable programs for general computation.

Conclusion

Validity proofs offer superior security, capital efficiency, and scalability compared to fraud proofs in the context of L2 blockchain scaling solutions. With the advancement of efficient proof systems like STARKs, the historical barriers to practical validity proofs are being overcome. As blockchain networks continue to evolve and demand for secure, high-performance scaling grows, validity proofs are poised to play a critical role in enabling the next generation of L2 infrastructure.

Validity proofs

ON THIS PAGE

Contact us