#30 - An Introduction to BitVM

A Gentle Guide to Arbitrary Computation on Bitcoin

Stanford Blockchain Club

Nov 06, 2023

Stanford Blockchain Review
Volume 3, Article No. 10

🧙‍♂️Author: Tyler Whittle – Taproot Wizards
🌟Technical Prerequisite: Low/None

*Cover Image: DALLE 2 x Taproot Wizards*

Introduction

You can’t execute arbitrary programs on Bitcoin!!! Or can you…

BitVM would like a word.

BitVM Abstract

BitVM is a computing paradigm to express Turing-complete Bitcoin contracts. This requires no changes to the network’s consensus rules. Rather than executing computations on Bitcoin, they are merely verified, similar to optimistic rollups. A prover makes a claim that a given function evaluates for some particular inputs to some specific output. If that claim is false, then the verifier can perform a succinct fraud proof and punish the prover. Using this mechanism, any computable function can be verified on Bitcoin.
Committing to a large program in a Taproot address requires significant amounts of off-chain computation and communication, however the resulting on-chain footprint is minimal. As long as both parties collaborate, they can perform arbitrarily complex, stateful off-chain computation, without leaving any trace in the chain. On-chain execution is required only in case of a dispute. [1]

Though it might be hard to distill from the abstract above, BitVM marks a paradigm shift in what we thought was possible on Bitcoin. In this article, I’ll walk you through what BitVM enables and why it’s a game changer for the Bitcoin ecosystem.

Chess, Programs, & Smart Contract Languages

Put simply, the BitVM allows arbitrary computation to be executed on Bitcoin. “Arbitrary computation” is a mouthful though, and it doesn’t really help a non-technical reader. So let me give you an example: Chess.

Chess is an example of a well-defined program with set constraints and a win condition. You have certain pieces that can move in certain ways around an 8x8 board. You know the game is over when a king is captured or neither player is able to win. You can consider chess a program with some arbitrary computation (e.g. there is not a chess.move_knight(F4) command built into Bitcoin).

Now let’s say Vicky and Paul want to play a game of chess against each other. What’s more, they want to make a big bet on it: 1 BTC to the winner! Given this game has such large stakes, they want a way to verify who won.

*"Vicky And Paul Playing Chess In A Magical World Where The Winner Gets A Lot Of Bitcoin" - StarryAI*

Before blockchains, Vicky & Paul’s best bet was to find a trusted third party (let’s call him Terrance) who would observe the game, declare a winner, and custody/pay out the 1 BTC. But what if Terrance wasn’t so trustworthy? Maybe Terrance decides to run away and keep the 1 BTC for himself. Maybe Paul bribed Terrance to declare him the winner no matter what. Neither of these situations (or the myriad of others that could potentially arise) are ideal.

Enter blockchains! A primary advantage of blockchains is that they shift the need to trust another human to the need to trust cryptography and code.

So why don’t we see an on-chain chess game on Bitcoin like we do on Ethereum {1}[2]? The answer lies in Bitcoin’s underlying language: Script [3].

Bitcoin Script

As an analogy, think of Bitcoin/Script like your high-school calculator and Ethereum/Solidity like your iPhone (or Android if you’re like me). Your iPhone can run any program an app developer can cook up. Your calculator, on the other hand, is limited to some numbers and a few mathematical functions. Maybe there are a few extra buttons for some calculus on there, but no one is mistaking your TI-83 for an iPhone, even if it can draw fancy graphs.

Script calculator buttons (left) vs. Solidity functional code (right) — *Script calculator buttons (left) vs. Solidity code (right)*

Ethereum’s smart contract language, Solidity, is considered “Turing complete” [4]. While this isn’t strictly true, it’s used in this context to mean Solidity can run pretty much any program imaginable. Chess, a Defi protocol, a zero-knowledge proof verifier - these can all be implemented directly on Ethereum.

Script, however, is not considered Turing complete. This means it wasn’t possible to run all those cool programs you see on other chains on Bitcoin (until now!). Within Script, there is a list of “opcodes”. These are essentially the buttons of the Bitcoin calculator. You’ll see opcodes for simple things like addition (OP_ADD) and cryptographic operations like hashing (OP_SHA256).

There are ~100 opcodes on Bitcoin, and they are specifically designed to limit the complexity of the computation that can be done. For example, as of writing there is not an opcode to multiply two numbers, nor is there an opcode to add to strings together. Satoshi removed these and many other opcodes very early in Bitcoin’s life due to network safety concerns.

Bitcoin Nodes & Avoiding Arbitrarily Long Compute

So why did Satoshi make Bitcoin so restrictive? The answer lies in the economics of Bitcoin. Bitcoin’s security relies on decentralization. It relies on users like you and me to run nodes and VERIFY that the transactions submitted to the network are valid. A full node runs the computation of every transaction in every block on the network. And unlike Ethereum, the fee a user must pay to get their transaction included is only loosely related to the amount of computation required to execute the transaction {2}.

*This transaction from 2015 required 5,569 signatures to be validated. It took nodes over one minute to validate! The Segwit upgrade was created in part to solve this problem.*

Now think what might happen if someone got a transaction included in a block that took 2 hours for a node to run. That would effectively be a DDoS on the Bitcoin network! Nodes are expected to verify a block in a timely manner because miners can’t add a new block until the previous one is verified. By restricting the language of Bitcoin, Satoshi ensured the amount of computation required for a node to verify a block would never spiral out of control.

This is where BitVM comes into play. What Robin and the clever team at ZeroSync have figured out is a way to allow those arbitrary programs to be executed on Bitcoin without making every full node run every line in the program.

BitVM achieves this through some crazy wizardry. First it simulates Boolean logic gates (the building block of computers) within Script [5]. Then, it uses something called hashlocks and the structure of Taproot addresses to verify the arbitrary computation. Finally, through an elegant challenge protocol, the Bitcoin network can adjudicate which party (Paul or Vicky in our example) is correct [6].

What does BitVM enable?

With all that background knowledge out of the way, we’re brought back to BitVM. BitVM has created a way to verify arbitrary computation on Bitcoin. Very simply, before BitVM, Paul Paul and Vicky couldn’t have played their chess game and had the result verified by Bitcoin. But now they can!

BitVM will allow them to deposit 0.5 BTC each into a 2/2 multisig address that they both control. If they both agree that Vicky won, they both sign a transaction that sends the 1 BTC to Vicky. Easy peasy! If they disagree, however, there is a way to verify every chess move that happened on Bitcoin and force Paul to send Vicky the 1 BTC. This is what makes BitVM so special.

While chess is a cool example, the design space on BitVM is limitless. It will allow users to verify that almost any program ran correctly all directly on Bitcoin! We’re just a few weeks in, and we’re already seeing strong groups hacking away on toy programs to test out this new system.

As for me, I’m most excited about the potential for BitVM to: (1) enable trust-minimized bridges, and (2) verify zero-knowledge proofs. These are the two key components of a Zero Knowledge (ZK) rollup {3}.

Up until now, zkRollups haven’t been built on Bitcoin because there was no way to trustlessly get BTC from the main chain to the rollup, nor to verify zkProofs. With BitVM, we just may be able to do both!

If BitVM can supercharge Bitcoin to enable zkRollups, a new era of fully on-chain Bitcoin applications is about to explode. Defi, DAOs, gaming, etc. will all be coming to Bitcoin – and this is the true promise that BitVM holds [7].

About the Author

Tyler is making Bitcoin magical again at the Taproot Wizards. He possesses an unerring belief that crypto will revolutionize the internet and money itself. Prior to the Taproot Wizards, he completed his PhD in entrepreneurship and organizations at Stanford and worked as an investor at Floodgate.

Footnotes

{1}: It would be simple to extend this chess implementation on Ethereum to pay out a predetermined amount of ETH to the winner.

{2}: The reason why Ethereum can allow for arbitrary programs is that the gas fee you set for a transaction represents a limit. Want to run through 1 million iterations of a “for” loop? No problem! The nodes will get started on that right away. But if you hit your gas limit at iteration 756,203 - the network will just stop executing your program. You still paid all that gas, but you never got a result. On Bitcoin, the fee paid to the network is for the guarantee that your transaction will be executed on all nodes. Thus, bitcoin has no way to self-regulate based on how much work you are asking nodes to do. For example, the signature hashing algorithm used on Bitcoin is very inefficient. One surly Bitcoiner decided to submit a transaction that required 5,569 signatures to be validated, and it took nodes over a minute to validate! Segwit was created in part to solve this problem.

{3} If you aren’t familiar with zkRollups, I recommend this article where I cover why Bitcoin will ultimately need zkRollups. TL;DR: zkRollups are the holy grail of scaling Bitcoin. If BitVM turns Bitcoin from a calculator into an iPhone, then zkRollups will transform that iPhone into a supercomputer.