A Simple Explanation of the BitVM Proposal
"Compute Anything on Bitcoin"
Summary
The BitVM proposal, titled "BitVM: Compute Anything on Bitcoin," introduces a way to express complex, Turing-complete Bitcoin contracts without changing the Bitcoin network's consensus rules. Instead of executing computations on the Bitcoin network, this approach focuses on verifying computations, similar to optimistic rollups. This post includes a simple explanation of the key points in the proposal.
Wait, What Does “Turing Complete” Mean?
"Turing complete" is a term used in computer science to describe a system or programming language that has the capability to perform any computation that a Turing machine can do. A Turing machine is a theoretical mathematical model of computation that can simulate the logic of any computer algorithm.
A system or programming language being Turing complete means that it possesses the following key properties:
Universal Computation: It can simulate the behavior of any other Turing complete system or programming language. In other words, it can perform any computation that can be described algorithmically.
Arbitrary Algorithm Execution: It can handle arbitrary and unbounded data and execute algorithms with loops and conditional branches. This means it's not limited in its ability to process data or perform calculations.
Recursion: It supports recursion, allowing functions or procedures to call themselves, which is a fundamental concept in programming.
Computational Completeness: It can solve problems that are computationally undecidable, meaning problems for which there's no algorithm that can always provide a correct answer.
Being Turing complete is a significant benchmark for a programming language or computational system because it signifies that it has the expressive power and versatility to solve a wide range of problems and perform any computation that can be precisely defined.
Languages like Python, Java, C++, and many others are considered Turing complete, as they can execute any algorithm that a Turing machine can perform, given enough time and resources. In contrast, simpler programming languages or systems may not be Turing complete, limiting the types of problems they can solve and computations they can perform.
BitVM Proposal
Introduction: The current smart contract capabilities of Bitcoin are limited to basic operations like signatures, timelocks, and hashlocks. BitVM opens up new possibilities by allowing more expressive Bitcoin contracts and off-chain computation. It can be used for various applications, including games, verification of Bitcoin contract validity, bridging Bitcoin to other blockchains, creating prediction markets, and implementing novel opcodes.
Architecture: BitVM leverages fraud proofs and a challenge-response protocol similar to optimistic rollups but doesn't require changes to Bitcoin's consensus rules. It uses hashlocks, timelocks, and large Taproot trees. The prover commits to a program bit by bit, and the verifier challenges the prover with carefully crafted queries to expose any false claims. They pre-sign a sequence of transactions to facilitate this challenge-response mechanism.
A Simpler Explanation of the “Architecture”
For non-technical people (like me), let’s break down the BitVM architecture in simpler terms:
Leveraging Fraud Proofs: BitVM uses a way to detect if someone is trying to cheat in a Bitcoin-based program. Think of it like having a system that can catch someone trying to do something dishonest.
Challenge-Response Protocol: Imagine a back-and-forth conversation where one person (the verifier) asks questions, and the other person (the prover) answers. This is like a game where the verifier challenges the prover to prove they are doing things correctly, and the prover has to respond.
No Changes to Bitcoin Rules: BitVM doesn't mess with the basic rules of Bitcoin. It plays by the same rules as everyone else in the Bitcoin network. It's like adding a new game to a playground without changing the existing games.
Using Special Locks and Timers: BitVM uses a couple of special tools. Think of a lock on a door. These special locks are called "hashlocks" and "timelocks." Hashlocks ensure that something will only happen if a secret code is revealed. Timelocks are like timers that control when something can be done.
Large Taproot Trees: Think of a Taproot tree as a way to organize information. BitVM uses a big tree with lots of branches to keep track of what's happening in a complex program. Each branch represents a part of the program.
Prover Commits Bit by Bit: The person who wants to show that a program works (the prover) does it step by step. It's like showing your work when you solve a math problem. They commit to each part of the program as they go.
Verifier Challenges with Questions: The person checking that everything is okay (the verifier) doesn't just trust the prover. They ask questions and challenge the prover to prove they are doing things correctly. If the prover is dishonest, they can get caught by these challenges.
Pre-Signed Transactions: Before starting the game, the prover and verifier set up a series of moves in advance. They sign these moves ahead of time. It's like having a set of rules for the challenge-response game that they both agree on. This makes the game fair.
In simple terms, BitVM is like a game where one person proves they're doing something correctly, and the other person checks by asking questions. They both agree on the rules of the game in advance, and special tools are used to make sure no one cheats. It's a way to do complex things with Bitcoin while making sure everything is done honestly.
Bit Value Commitment: The BitVM system allows the prover to set the value of a specific bit to 0 or 1. This commitment is crucial for extending the execution runtime of Bitcoin's virtual machine (VM) across multiple transactions. The prover can later reveal the preimage of a hash to set the bit's value, and equivocation (revealing both preimages) is punishable.
Logic Gate Commitment: Any computable function can be represented as a Boolean circuit, and BitVM demonstrates that it works for simple NAND gates. The commitment of a NAND gate is simple, containing commitments for inputs and the output. This system can express any circuit.
What’s a “NAND gate”?
A NAND gate is a fundamental logic gate in digital electronics and computer science. It gets its name from a combination of "NOT-AND." Here's a simple explanation of what a NAND gate does:
Input and Output: A NAND gate takes in one or more binary inputs (0 or 1) and produces a single binary output (0 or 1).
Logic Operation: The operation of a NAND gate is such that it gives the opposite result of an AND gate. An AND gate produces a 1 output only when all of its inputs are 1, but a NAND gate produces a 0 output when all of its inputs are 1. In all other cases, it produces a 1 output.
Truth Table: The behavior of a NAND gate can be summarized in a truth table.
Symbol: The symbol for a NAND gate is a small shape with two inputs and a single output, often represented as a half-circle with a dot (•) at the end of the arrow, indicating negation.
NAND gates are crucial in digital circuit design because they are considered universal gates. This means that you can use NAND gates to create any other type of logic gate, such as AND gates, OR gates, and NOT gates. They are the building blocks for more complex digital circuits and are widely used in computers and electronic devices.
Binary Circuit Commitment: A full program is represented by composing gate commitments, and all the steps in execution are committed to in a Tapleaf (see below for an explanation of this). This results in a minimal on-chain footprint despite complex computations.
Challenges and Responses: To disprove incorrect claims, the verifier can challenge the prover by pre-signing a sequence of transactions. These transactions form a challenge-response game. If either party stops participating, the other party can win the challenge and take both Bitcoin deposits.
Inputs and Outputs: The prover can set inputs by revealing the corresponding bit commitments, ideally off-chain. In non-cooperative scenarios, the verifier can force input revelation on-chain. The exchange of encrypted data upfront allows the prover to reveal the decryption key later.
Limitations and Outlook: The model proposed here uses simple NAND circuits, which are not efficient for expressing functions. However, more high-level opcodes and larger bit commitments could be used for more efficient implementations. The model is currently limited to a two-party setting, but there's potential for further generalization and integration with off-chain protocols.
Conclusion: The proposal concludes by highlighting that Bitcoin can be considered Turing-complete when using fraud proofs in large Taptrees (see below). The model's main constraint is its limitation to a two-party setting, with hopes for further generalization in future research.
What are “Large Taptrees?”
In the context of the BitVM proposal, a "large Taptree" refers to a data structure that is used to represent and organize various components of a complex computation. The Taptree is an integral part of the BitVM architecture, and it's used to commit to the program and its execution. Here's a more detailed explanation:
Taptree: A Taptree is a data structure in Bitcoin's Taproot framework, which is designed to enhance privacy and scalability. In this context, the Taptree is a hierarchical structure that can contain a large number of "Tapleafs," each representing a specific part of a program or computation. These Tapleafs are effectively individual leaves in the tree, and they contain the commitments to various components of a computation.
Large Taptree: The term "large Taptree" indicates that this data structure can become extensive and contain a significant number of Tapleafs, each of which corresponds to a part of the program. The purpose of having a large Taptree is to allow for the representation of complex computations. In the BitVM proposal, a program is broken down into its individual components, such as bit value commitments, logic gate commitments, and so on. Each of these components is committed to in the Taptree.
The large Taptree in BitVM serves as a means of organizing and committing to the various elements of a computation in a structured way. It allows for the verification of the execution of any program by providing a mechanism to reference and validate the individual commitments made by the prover during the execution of the program.
By structuring the computation in this way, BitVM can efficiently verify the execution of complex programs on the Bitcoin network while keeping the on-chain footprint minimal. It's a key element in achieving Turing completeness within the Bitcoin ecosystem as described in the proposal.
Summary
In summary, BitVM provides a way to perform complex computations on the Bitcoin network while keeping most of the computation off-chain and only resorting to on-chain execution in the event of disputes. It opens up exciting possibilities for expanding Bitcoin's capabilities without altering its core consensus rules. I’m sure the debate around this proposal will be robust, as noted in this recent article. The fact that this kind of innovation is possible without changing the underlying protocol is truly amazing and shows more use cases for layer two protocols. We already know the promise of the Lightning Network, as I discussed here:
Not financial or legal advice, for entertainment only, do your own homework. I hope you find this post useful as you chart your personal financial course and Build a Bitcoin Fortress in 2023.
Thanks for supporting my work. Always remember: freedom, health and positivity!
Please also check out my Building a Financial Fortress Podcast on YouTube here and on all your favorite streaming platforms. I do a weekly Bitcoin news update every week on current items of interest to the Bitcoin community, usually 30 to 60 minutes depending on the number of topics to cover. Please check it out if you haven’t already. Also now on Fountain, where you can earn Bitcoin just for listening to your favorite podcasts.
Follow me on Nostr:
npub122fpu8lwu2eu2zfmrymcfed9tfgeray5quj78jm6zavj78phnqdsu3v4h5
If you’re looking for more great Bitcoin signal, check out friend of the show Pleb Underground here.
Lightning tips appreciated here:
