Skip to main content

Fraud Proofs on Bitcoin

Background​

Imagine conducting a computation off-chain, referred to as a state transition function (STF). After completing this computation, you want to publicly verify an assertion about its output on-chain. There are two primary approaches to achieve this:

  1. Validity Proofs:
    A proof is generated alongside the assertion, and a verifier program runs on-chain using both the assertion and the proof as inputs. If the verifier outputs TRUE, the assertion is accepted; otherwise, it is rejected. Zero-knowledge proofs (ZKPs) are the dominant form of validity proofs, though trusted hardware-based proofs, such as those using trusted execution environments (TEEs), also exist.

  2. Fraud Proofs:
    In this approach, the assertion is optimistically accepted and only finalized after a challenge window has elapsed (this is referred to as the "happy path"). During this window, anyone can challenge the assertion if they detect fraud. In the event of a challenge, a dispute resolution game is played on-chain between the challenger and the defender (usually the proposer of the assertion). The loser forfeits their deposit as a financial penalty.

This article discusses fraud proofs on Bitcoin. We’ll start by modeling fraud proofs to better understand the challenges of implementing them on Bitcoin. Then, we’ll explore these challenges in detail, and finally, we’ll outline how to build practical fraud proofs for Bitcoin. While the focus is on Bitcoin, we’ll also reference Ethereum’s techniques where relevant, though without delving deeply into their specifics.

Basic Fraud Proofs​

Fraud proofs have been successfully implemented in optimistic rollups on Ethereum, with notable examples being Arbitrum and Optimism. These systems rely on fraud proofs to ensure the integrity of off-chain computations.

Workflow of Fraud Proofs​

The basic workflow for fraud proofs can be summarized as follows:

  1. Proposing Assertions:
    A proposer executes the STF off-chain and submits an assertion about the STF result to the base layer (Ethereum for Arbitrum and Optimism, Bitcoin for systems like Bitlayer).

  2. Optimistic Acceptance:
    The base layer optimistically accepts the assertion. If no challenges are raised during the predefined challenge window, the assertion is finalized. This is the "happy path."

  3. Disputes and Challenges:
    If someone disagrees with the assertion, they can raise a challenge during the window, triggering a dispute resolution game. This game involves a challenger (the one disputing the assertion) and a defender (usually the proposer).

  4. Dispute Resolution Game:
    The challenger and defender engage in a game to determine the correctness of the assertion. This game is played on-chain.

  5. Outcome and Penalties:
    The loser of the dispute forfeits their deposit as a financial penalty.

Dispute Resolution Game​

The simplest way to resolve a dispute is to replay the entire STF on-chain and determine the correct outcome. However, replaying the STF in its entirety is computationally expensive and infeasible on Layer 1 (L1) blockchains due to limited block space. To address this, systems like Arbitrum and Optimism reduce the on-chain footprint by replaying only a single execution step of the STF.

To achieve this, the STF is broken down into discrete execution steps. This process involves generating an execution trace off-chain by running the STF program step by step. Each step in the trace includes:

  • Input: The pre-execution context (e.g., the state of the virtual machine or blockchain before execution).
  • Output: A commitment to the updated post-execution context.

The challenger and defender then collaboratively search through the execution trace to identify a single disputed step to replay on-chain. After replaying the step, the updated execution context is compared with the post-execution context commitment in the assertion. If the two do not match, the assertion is invalid.

Execution Trace​

Implementing an interpreter for Ethereum Virtual Machine (EVM) bytecode on-chain is challenging due to the complexity of EVM bytecode. To simplify this process, programs are often compiled into simpler instruction sets, such as RISC-V or MIPS, and the execution trace is generated by running the compiled program. This approach helps manage the dynamic nature of EVM bytecode specifications.

Bisection​

To locate the specific step to replay, the challenger and defender use a bisection protocol. Initially, the execution trace is divided into two halves. The parties then iteratively narrow down the search space by bisecting one half until a single step is identified.

Arbitration​

An on-chain smart contract acts as a referee during the dispute resolution game. Its primary responsibility is to prune invalid assertions. If the challenger wins, the assertion is rejected. However, if the defender wins, it does not necessarily mean the assertion is accepted—it simply means the assertion has not been proven invalid. This ensures the safety of the system, as all invalid assertions are pruned. To maintain liveness, other players can propose new assertions.

Replacing STF with a ZK Verifier​

The size of execution traces can vary significantly depending on the block content. Compiling an STF into low-level instructions often inflates the size of the execution trace, making it difficult to predict the number of interactions required in a dispute resolution game. This unpredictability increases costs, especially when the blockchain is congested.

Zero-knowledge proofs (ZKPs) offer a solution to this problem. With ZKPs, the following two statements are semantically equivalent:

  • The STF is correct.
  • The ZK proof of the STF passes verification.

The key advantage of ZKPs is that verifying a proof is computationally much cheaper than executing the original STF, regardless of the number of transactions processed. This asymmetry is critical for scaling blockchains.

There are two main approaches to incorporating ZKPs into fraud proofs:

  1. Direct ZK Verification:
    The challenger submits a ZK proof directly during a dispute. This eliminates the need for instruction-level bisection between the challenger and defender. For example, Optimism is considering adopting this approach.

  2. Fraud Proofs Against a ZK Verifier:
    In this approach, the STF program is replaced with a ZK verifier in the dispute resolution game. Since the ZK verifier’s execution trace is relatively static, the complexity of the dispute resolution game becomes more predictable. Additionally, this approach simplifies implementation because the ZK verifier can be natively implemented on-chain, avoiding the need for a complex virtual machine interpreter.

However, generating ZK proofs for STFs remains computationally expensive, which adds costs compared to traditional fraud proofs. Nonetheless, this approach offers significant benefits, particularly for non-Turing-complete blockchains like Bitcoin, where implementing an on-chain VM interpreter is challenging.

Modeling Fraud Proofs​

Fraud proofs on Bitcoin are relatively new, and existing models do not adequately describe them. To address this, we need a formal model for fraud proofs. This model will help us better understand and design fraud proofs for Bitcoin.

Problem Definition​

  • A designated proposer performs an off-chain computation and submits an assertion.
  • A challenger disputes the assertion, triggering a search for a single step in the execution trace to replay on-chain.
  • An on-chain contract arbitrates the dispute and determines the winner.

Roles​

  • Proposer: Submits the assertion to Bitcoin.
  • Challenger: Disagrees with the assertion and initiates a dispute.

System Model​

  • Program: Either the STF program or the ZK verifier of the STF program. A digest of the program is shared among participants.
  • Replay Unit: The smallest unit of STF execution that can be replayed on-chain.
  • Replay Target: The specific unit selected for replay.
  • Replay Result: The pre- and post-execution states of the replayed unit.
  • Replay Assertion: A combination of the replay target and the corresponding replay result.

For Ethereum, the replay result includes the stack, heap, and state tree. For Bitcoin, it primarily consists of the remaining stack after executing the script.

Workflow​

  1. Setup: Compile the program into replayable units (e.g., instructions, transactions, or segments).
  2. Commit: The proposer commits to the STF result.
  3. Search: The challenger locates the replay target, either interactively or non-interactively.
  4. Replay: The replay target is executed on-chain, producing a post-execution state.
  5. Arbitrate: The on-chain contract determines the winner based on whether the post-execution state matches the proposer’s commitment.

Search and Replay Tradeoff​

The granularity of replay units affects the tradeoff between search and replay:

  • Instruction-level granularity: Billions of replay units, requiring extensive search but minimal replay effort.
  • Transaction-level granularity: Thousands of replay units, balancing search and replay.
  • Segment-level granularity: Hundreds of replay units, reducing search complexity but increasing replay workload.

Both Optimism and Arbitrum use instruction-level granularity. On Bitcoin, BitVM1 also uses instruction-level granularity, while BitVM2 proposes a segment-level approach to reduce search complexity.

Instruction-Level vs. Segment-Level Fraud Proofs on Bitcoin​

Design Principles​

  1. Challenges must be permissionless, allowing any challenger to search for the replay target without requiring coordination with the proposer.
  2. The dispute resolution game should conclude within one week, requiring no more than three interactions between the challenger and defender.

Segment-Level Configuration​

  • Replay Unit: Segments, with each segment as close to Bitcoin’s upper size limit (4MB) as possible.
  • Program: A ZK verifier for the STF, written in Bitcoin Script.
  • Replay Result: The remaining stack and alt stack after executing the segment.

Segments are organized as a taptree, with the proposer committing to all segment values. The challenger selects a segment to replay, and the segment logic is inverted to verify correctness.

Building Fraud Proofs with ZK Verifiers on Bitcoin​

Creating a ZK verifier for fraud proofs on Bitcoin involves three stages:

  1. Writing the ZK Verifier in Bitcoin Script:
    Due to Bitcoin Script’s limited expressiveness, implementing a ZK verifier requires numerous optimizations, such as efficient arithmetic operations and cryptographic primitives.

  2. Segmenting the Verifier:
    The verifier script is divided into multiple segments, each meeting Bitcoin’s runtime constraints.

  3. Linking Segments:
    The segments are linked to form a complete, consistent ZK verifier. Shared values between segments are pre-committed using bit commitments.

This foundational understanding of fraud proofs on Bitcoin sets the stage for implementing scalable, secure solutions for off-chain computation verification.