Bitcoin’s ecosystem is thriving. ETFs, the Halving, Ordinals, Inscriptions, and Runes are making all the waves. But a more significant development is emerging on Bitcoin’s L1, where programmability is finally taking shape after years of effort. Adding programmability to Bitcoin will enhance how rollups handle transactions and finality, paving the way for increased use and development of rollups on the Bitcoin network.

As we consider the evolving solutions using on-chain verification, it’s crucial to understand the broader landscape of scalability technologies. State channels, for example, provide a secure way to process payments instantly and privately while reducing costs. They function like private pathways between two parties, allowing direct transactions without waiting for network confirmations. However, state channels typically involve only two parties and require difficult processes for opening and closing channels. They also have limitations in verifying complex computations, restricting their use in scenarios requiring complex conditional logic.

In contrast, sidechains offer greater independence, scalability, and flexibility in design. They even support better smart contract capabilities than Bitcoin. However, this increased flexibility comes at the cost of security. Sidechains lack Bitcoin’s robust security because they utilize independent consensus mechanisms that are significantly less robust compared to Bitcoin’s consensus mechanism. This trade-off highlights the ongoing challenge in achieving a balance between scalability, functionality, and security within the Bitcoin ecosystem.

Now in terms of new developments on BTC, a few months back Robin Linus created BitVM, which kickstarted a wave of progress in that direction. Following the initial design, researchers have improved it to newer versions BitVM1, BitVM2, BitVMX, BitSNARK, ,Snarknado, CatVM and OP_CAT. Each one of these helps us get closer to more expressive programmability on Bitcoin. We can create programs that operate off-chain and only check their validity on-chain if there’s a disagreement, much like using fraud proofs to catch and resolve errors.

In another direction, Casey Rodoamar found a way to inscribe data onto BTC blocks. Again, the BTC community had been doing this for a few years using OP_RETURN, but it had its data limitations. Ordinals use improvements from the Taproot and SegWit updates, allowing them to store additional data in Bitcoin transactions more efficiently. This led to an explosion in token standards like Ordinals, BRC-20s and a bunch of others. This same method can, not surprisingly, be used by Bitcoin rollups as its DA layer. This would have its limits in terms of scalability, but it still works with BTC securing it.

With BitVM and its successors, stage is setting up for Rollups to thrive in BTC

BTC can now support the DA, settlement & verification, bridging for rollups.

These parts are not fully developed, but still, this is a 0 to 1 development, a journey from impossible to imperfect.

This report is focused on shedding light on technological breakthroughs that allow scaling BTC using zk rollups. It’s divided into 4 major parts.

• The first part is arguably the most exciting area in BTC in many years and forms the core of the report. It is focused on bringing native expressive programming on BTC L1. A number of efforts have evolved in a short span and continue to be evolving at rapid pace. These efforts are also community wide, and not just an isolated event.
• The second part will be focused on the different types of DAs. We will take a look at how these would work and provide an overview of their tradeoffs.
• The third part will be focused at the current state of bridging for state-channels, rollups and their shortcomings. We then move to the BitVM based bridges, its issues and different implementations. Since this is a rapidly changing area, we expect this to evolve over time.
• Finally, we take a look at some of the zk rollups building on top of BTC using these components.

Programmability: From Impossible to Inevitable

Bringing programmability on BTC has been a focus of developers for a long time. A few months back it was considered impossible, but now there are many implementations, evolution and almost a feeling that its just a matter of time before we see it.

MATT

MATT is the predecessor of current efforts in bringing programmability to BTC. MATT, which is short for Merkleize All The Things, enables adding smart contract capabilities to Bitcoin with some protocol changes. The key idea revolves around introducing covenants, which allow attaching constraints and data to transaction outputs. This needs new opcodes like OP_CHECKCONTRACTVERIFY (OP_CTV) that force outputs to have certain scripts and attach arbitrary data. CatVM enables MATT using only OP_CAT.

Instead of storing all contract details directly on the blockchain, MATT uses Merkle trees. These are like hierarchical summaries where only the top summary (Merkle root) is stored on-chain. These replace 3 core things:

• Smart contract script
• Data required for the contract
• Execution trace of the contract

Only these small constant-sized Merkle roots are stored on-chain, while the full data and computation remain off-chain. This approach enables efficient on-chain commitment to large amounts of data while allowing off-chain data availability and verification.

For computationally intensive operations, MATT proposes fraud proof systems where parties can challenge and prove incorrect executions without requiring full on-chain computation.

We’ll take a look at different versions of BitVM with underlying components & eventually addressing advanced versions that have evolved in short time. These include BitVM0, BitVM1, BitVM2, BitVMX, CatVM. We’ll then compare them across variables like settlement time, number of transactions, and its security guarantees.

All these approaches share a similar abstract structure:

• Program decomposition and commitment: The program is broken down into smaller, executable steps. A commitment scheme is constructed to bind the state of execution at each step. This commitment can take various forms, such as:
  • Merkle trees
  • PIOPs
  • Hash functions

  These commitments capture the state of execution at each step, ensuring that the prover cannot alter the computation’s outcome.

• Deposit locking and conditional transactions: The prover and verifier deposits are locked in pre-signed transactions with conditions that determine who gets the deposits. These transactions are set up such that they can only be executed if specific conditions are met.
• Verifier’s search: The verifier searches over the computations & checks if any step is incorrect or if the prover has committed to multiple values. The verifier checks the computations for errors or discrepancies using a bisection algorithm. This method efficiently narrows down the search by repeatedly dividing the problem in half.
• Conflict resolution and deposit allocation: Once the verifier finds a step that conflicts with its computation, it runs that part of computation on-chain. If the computation reveals that the verifier is correct, it wins the prover’s deposit. Otherwise, the prover gets back its deposit after the verifier exhausts the search.

BitVM

Bitcoin Script Constraints

Bitcoin Script is inherently limited in its capabilities, designed to be simple and secure. However, these constraints pose significant challenges for implementing complex cryptographic operations and running executable programs on the blockchain.

• Disabled Opcodes: Important functions like OP_CAT are disabled, preventing direct Merkle tree verification and others.
• Limited Operations: Lacks bitwise operations (XOR, AND) and arithmetic functions (DIV, MOD), restricting complex computations.
• No Loops or Jumps: Linear execution only, making iterative processes difficult.
• Stateless Nature: Variables in one script/transaction cannot be transferred to others, complicating state management.
• Lack of Introspection: The stack can’t access transaction data to enforce logic, limiting script capabilities.

Although it is possible to extend the functionality of the script to accommodate the arbitrary computation, it would require addition of opcodes and a soft fork. BitVM is special because it uses existing tools to create a simple solution that can be improved over time. It doesn’t need any changes to Bitcoin’s core system or major updates.

But to be clear, BitVM doesn’t compute everything on BTC. Most of the computations happen off-chain. It tries to minimise the on-chain footprint as much as possible using Taproot trees. The prover and verifier, who run these programs, engage in data heavy off-chain communication. BitVM uses a fraud proof mechanism which determines correctness of computation only in cases of dispute where certain computations are carried out on-chain using script. These are either divided between multiple transactions of back and forth interaction, or a single run of script to decide the outcome.

BitVM’s has gone through rapid evolution in a short time span. The first version was simplistic, using NAND gates to represent the programs. The following version ran the fraud proofs over the CPU trace. BitVM2 was a step up improvement in security – allowing permissionless verification & requiring just a single interaction to determine the outcome. This greatly reduced the time & cost for fraud proofs. BitVMX was another proposal that used different data structures to represent computations. It has a smaller data footprint.

Before diving into BitVM0, let’s build up some intuition of the approach and tools used.

Computers & Logic gates

At the most basic level, all computer operations, regardless of complexity, are built using simple logic gates like NAND gates. Think of these gates as basic building blocks, similar to how LEGO bricks can be combined to build complex structures. The NAND gate is a universal logic gate, meaning it can perform logic and arithmetic operations using NAND gates as building blocks.

High-level programs written by developers are first compiled into a lower-level representation, such as assembly language or intermediate code. These lower-level representations are then translated into machine code, which is a sequence of binary instructions (1s and 0s) that can be directly executed by the computer’s central processing unit (CPU).

Inside the CPU, these binary instructions are processed by NAND gate circuits. Each NAND gate operates on two bits – either 0 or 1 – to first calculate their logical AND, and then invert it. By combining a large number of these gates in different configurations, they can implement the full range of computations required by any program.

BitVM0: The Moonshot

BitVM0 builds on this idea. First, it builds a NAND gate on BTC using Bitcoin script, so that it can be used to carry out simple computations. Complex programs are written in high-level languages, compiled down to intermediate representations like Bristol format, and finally to binary circuit in BTC script. Both the prover & verifier have these circuits. They pre-sign transactions with deposits & commitment to this circuit to begin the fraud proof.

The key to the verification process is finding incorrect NAND gate script or if the prover is lying about the values. Each program could contain billions of NAND gates in circuit. To search f