Compact Fraud Proof

What Is a Compact Fraud Proof?

A compact fraud proof is a succinct cryptographic argument demonstrating that a specific block or state transition was computed incorrectly. Rather than re-executing an entire batch of transactions on-chain to prove invalidity, the proof narrows the dispute down to a single computational instruction and provides only the minimal data needed to verify that one step: a Merkle proof of the disputed pre-state, the inputs to the computation, and the resulting post-state.

This approach was formalized in a 2018 paper by Mustafa Al-Bassam, Alberto Sonnino, and Vitalik Buterin titled "Fraud and Data Availability Proofs: Maximising Light Client Security and Scaling Blockchains with Dishonest Majorities." The paper established two foundational concepts: compact fraud proofs for invalid state transitions and data availability proofs via erasure coding. Together, these techniques allow light clients to verify blocks without downloading or re-executing all transaction data, requiring only a single honest full node to broadcast a proof rather than assuming an honest majority.

The "compact" distinction matters because a naive fraud proof would require replaying an entire block on-chain to demonstrate invalidity. A compact fraud proof achieves the same result with constant-sized on-chain verification: roughly 330,000 gas on Ethereum regardless of how many transactions the disputed block contains.

How It Works

All compact fraud proof systems share a core principle: decompose a large computation into individually verifiable steps, then prove that one specific step was executed incorrectly. The two dominant approaches differ in how they identify that step.

Interactive Bisection (Arbitrum BoLD)

Interactive bisection is a multi-round protocol where a challenger and a defender repeatedly halve the disputed computation range until they isolate a single instruction. Arbitrum's BoLD (Bounded Liquidity Delay) protocol, deployed on mainnet in February 2025, implements this in three phases:

1. Block-level challenge: the disputing parties bisect their historical commitments at block granularity, narrowing down to the specific block where their state roots diverge
2. Big-step challenge: within the disputed block, parties continue bisecting to isolate a range of approximately 1 million WASM instructions
3. One-step challenge: final bisection narrows the dispute to a single WASM instruction, which both parties submit to a OneStepProof smart contract on Ethereum L1

The L1 contract deterministically executes that single instruction and resolves the dispute. The honest party's assertion is validated, while the dishonest party's bond is slashed.

Non-Interactive Execution Trace (Optimism Cannon)

Optimism's Cannon system takes a different approach by compiling the Ethereum execution client into MIPS 32-bit machine code. This creates a fully deterministic execution environment: given the same inputs, every participant produces the same execution trace instruction by instruction.

1. The disputed L2 state transition is compiled to a MIPS execution trace
2. Cannon generates state witness hashes (commitments to the computation result at each instruction)
3. Participants bisect the execution trace to isolate the single MIPS instruction where they disagree
4. A witness proof containing register states, memory states, and Merkle proofs is submitted to the MIPS.sol smart contract
5. The contract executes that single instruction to determine the correct post-state

The "non-interactive" label refers to the execution trace itself: because the computation is fully deterministic, any observer can independently reproduce and verify results without requiring continuous back-and-forth with the original prover. The dispute game still involves interactive attack and defend moves, but the underlying computation is independently reproducible.

On-Chain Verification

Regardless of the bisection method, the final on-chain verification step is similar across implementations. A simplified representation of what the verifier contract checks:

// Simplified fraud proof verification logic
function verifyOneStep(
  preStateHash,    // Merkle root of state before instruction
  postStateHash,   // Claimed state after instruction
  instruction,     // The disputed operation
  witness          // Merkle proof of relevant state
) {
  // Re-execute the single instruction deterministically
  actualPostState = execute(preStateHash, instruction, witness)

  // If claimed post-state doesn't match, the fraud proof succeeds
  return actualPostState != postStateHash
}

Challenge Periods and Bonds

Compact fraud proof systems rely on a challenge period: a window during which anyone can submit a proof that a proposed state transition is invalid. If no valid challenge appears within this window, the state transition is accepted as final.

Bonds serve as economic security: proposers stake assets that get slashed if their state assertion is proven fraudulent. This creates a game-theoretic equilibrium where rational actors never submit invalid states because the cost of being caught exceeds any potential gain. The bond amounts reflect different design philosophies: Arbitrum prioritizes safety with high bonds that deter attackers, while Optimism prioritizes accessibility with lower initial bonds that scale during disputes.

Compact Fraud Proofs vs. Validity Proofs

The two primary approaches to verifying off-chain computation represent fundamentally different trust models. Fraud proofs assume transactions are correct unless challenged. Validity proofs (used in ZK rollups) mathematically prove every batch is correct before acceptance.

Some protocols are converging these approaches: hybrid systems like OP Kailua (by RISC Zero) use zero-knowledge proofs to resolve fraud disputes in a single transaction instead of multi-step bisection, combining the low happy-path cost of optimistic systems with faster dispute resolution.

BitVM: Fraud Proofs on Bitcoin

BitVM, proposed by Robin Linus in October 2023, adapts compact fraud proof concepts to Bitcoin without requiring protocol changes. It enables Turing-complete computation verification using Bitcoin's existing script capabilities and Taproot.

The original BitVM design decomposes any computation into a circuit of NAND gates, with each gate committed as a Taproot leaf script. The prover commits to bit values using hash preimages: revealing a preimage locks the prover to a specific value (0 or 1). If the prover claims inconsistent values (for example, asserting a NAND gate output is 1 when both inputs are 1), the verifier can prove this contradiction on-chain.

BitVM2, published in August 2024, significantly improved the design by introducing permissionless verification. While the original BitVM required all verifiers to be defined at compile time and up to 70 on-chain transactions to resolve disputes, BitVM2 reduces this to just 3 on-chain transactions and allows anyone to challenge invalid claims. This makes BitVM2 suitable for trustless Bitcoin bridges and rollup verification, where a 1-of-N honesty assumption ensures that even if all but one operator is dishonest, funds remain safe. For a deeper exploration of this technology, see the BitVM trustless verification deep dive.

Use Cases

Optimistic Rollup Verification

The primary application of compact fraud proofs is securing optimistic rollups. Rollup sequencers post state roots to the base layer along with transaction data, and verifiers monitor these assertions. If a sequencer posts an invalid state root, any verifier can submit a compact fraud proof to challenge it, triggering the bisection protocol. Arbitrum and Optimism together secure tens of billions of dollars using this model.

Light Client Security

The Al-Bassam, Sonnino, and Buterin paper was originally motivated by improving light client security. Traditional light clients (SPV) only verify block headers and rely on an honest-majority assumption. With compact fraud proofs combined with data availability sampling, light clients need only a single honest full node to broadcast a proof of invalidity. This substantially weakens the trust assumption from "most miners are honest" to "at least one node will alert you if something is wrong."

Bitcoin Layer 2 Verification

Through BitVM and its successors, compact fraud proof concepts enable trustless verification of off-chain computation on Bitcoin. This opens the door to rollups and bridges secured by Bitcoin's own consensus rather than federated multisig setups. For a comparison of how different Bitcoin L2 solutions handle trust and verification, see the Bitcoin L2 trust model comparison.

Risks and Considerations

Liveness Requirements

Compact fraud proof systems require at least one honest and online verifier during the entire challenge period. If no verifier submits a fraud proof within the window, an invalid state transition becomes final. This contrasts with validity proofs, which provide cryptographic certainty regardless of participant liveness. In practice, multiple independent verifier implementations run in parallel to mitigate this risk.

Delayed Finality

The challenge period (typically 7 days for major rollups) means withdrawals from optimistic rollups to L1 are delayed. Users who need faster finality rely on third-party liquidity providers who front the withdrawal for a fee, accepting the challenge-period risk themselves.

Economic Attack Vectors

L2Beat and independent researchers have identified an economic trilemma in fraud proof design: systems must balance safety (defender resource efficiency), promptness (settlement speed), and decentralization (low participation barriers). High bond requirements like Arbitrum's 3,600 ETH deter attackers but also raise the barrier for honest challengers. Low bond requirements like Optimism's 0.08 ETH are accessible but may be vulnerable to resource exhaustion attacks where well-funded attackers create many simultaneous disputes to overwhelm defenders.

Data Availability Dependency

A fraud proof can only be constructed if the transaction data is available. If a malicious sequencer posts a state root but withholds the underlying transaction data, verifiers cannot generate proofs to challenge it. This is why data availability guarantees (posting full data to L1, or using dedicated data availability layers) are critical for fraud proof security. The original Al-Bassam paper addressed this with data availability proofs using 2D Reed-Solomon erasure coding, where light clients sample small portions of the data to probabilistically verify its availability.

This glossary entry is for informational purposes only and does not constitute financial or investment advice. Always do your own research before using any protocol or technology.