Mechanizes fraud-proof games for rollup sequencers and data-availability committees in LEAN4, including verified honest strategies.
Abstract
Blockchains face a scalability limitation, partly due to the throughput limitations of consensus protocols, especially when aiming to obtain a high degree of decentralization. Layer 2 Rollups (L2s) are a faster alternative to conventional blockchains. L2s perform most computations offchain using minimally blockchains (L1) under-the-hood to guarantee correctness. A sequencer is a service that receives offchain L2 transaction requests, batches these transactions, and commits compressed or hashed batches to L1. Using hashing needs less L1 space, which is beneficial for gas cost, but requires a data availability committee (DAC) service to translate hashes into their corresponding batches of transaction requests. The behavior of sequencers and DACs influence the evolution of the L2 blockchain, presenting a potential security threat and delaying L2 adoption. We propose in this paper fraud-proof mechanisms, arbitrated by L1 contracts, to detect and generate evidence of dishonest behavior of the sequencer and DAC. We study how these fraud-proofs limit the power of adversaries that control different number of sequencer and DACs members, and provide incentives for their honest behavior. We designed these fraud-proof mechanisms as two player games. Unlike the generic fraud-proofs in current L2s (designed to guarantee the correct execution of transactions), our fraud-proofs are over pred-etermined algorithms that verify the properties that determine the correctness of the DAC. Arbitrating over concrete algorithms makes our fraud-proofs more efficient, easier to understand, and simpler to prove correct. We provide as an artifact a mechanization in LEAN4 of our fraud-proof games, including (1) the verified strategies that honest players should play to win all games as well as (2) mechanisms to detect dishonest claims.
Problem
Layer-2 rollup sequencers and data availability committees (DACs) can behave dishonestly, threatening L2 correctness, yet existing L2s assume these services are correct.
Approach
The authors design fraud-proof mechanisms, arbitrated by L1 contracts and structured as two-player games, that let a single honest agent expose dishonest sequencer or DAC behavior, plus incentives aligning rational and honest behavior. They provide a LEAN4 mechanization of the fraud-proof games, including verified winning strategies for honest players and dishonesty-detection mechanisms.
Fig. 2. Optimiums.
Results
Fraud-proof games over predetermined DAC algorithms, with mechanized correctness in LEAN4 and analysis of how the mechanisms limit adversaries controlling varying numbers of replicas.