Secure, Extensible, Open-Source

BitVMX is a new framework to optimistically execute arbitrary programs in Bitcoin based on the N-party disputable computation paradigm pioneered by BitVM. BitVMX framework provides the foundations to run any CPU on Bitcoin, with a focus to run a fully-compliant RISC-V processor programmable using a standard compilation toolchain.

Our vision is to create a secure, extensible, open-source, peer-reviewed and sidechain-agnostic framework that can be used to develop blockchain bridges, aggregator oracles, and SNARK/STARK verifiers. As soon as BitVMX is able to run a SNARK verifier, a myriad of new use cases can be brought to Bitcoin, from ZK-rollups to crazy use cases such as Zero Knowledge Contingent Payments (i.e. autonomous bug bounties paid for disclosure of vulnerabilities).

How Does BitVMX Work

BitVMX represents a new form of covenant that does not require a soft or hard fork to Bitcoin. Funds can be locked in an UTXO with a spend condition that depends on the result of the execution of a program. While the program must be defined when the UTXO is created, the program input does not. In its simplest form, this is a two-party protocol where a first participant is the operator and the second is the verifier. First, both of them initially collaborate to create a small set of presigned transaction that guide the dispute resolution protocol. Also both compute an initial deposit address. Funds sent to this address will be governed by the predefined program. One of the precreated transactions is the first kick-off transaction that signals the intention for the prover to withdraw the funds. After the setup, the parties can lock funds and security deposits into the protocol and the funds can’t be spent until the withdrawal kick-off transaction is included in the blockchain.

At a later time, when the operator wants to withdraw the locked funds, she posts the kick-off transaction together with the input that makes the program halt with an exit code that represents success. The input is always available to the verifier. The verifier watches the operator and executes the program locally to check the correctness of the execution. If the verifier detects cheating, she will challenge the operator and both of them enter a Dispute Resolution Protocol (DRP) on the Bitcoin blockchain (the DRP protocol is sometimes called the “Verification Game”) .

In the DRP, the verifier becomes the challenger, the goal is to prove that the operator has cheated, and the operator becomes the responder (also known as prover), the goal is to respond to each challenger question, and prove she has not cheated. All responses provided by the responder are signed, so that the challenger can use the responder’s responses in the further stages of the protocol to prove cheating.

The DRP is as follows: both the responder and the challenger locally execute the program associated with the UTXO with a predefined CPU and output the execution trace. The trace is a list of steps until the CPU halts. Each step of the trace represents a step of the execution. For each step, the honest parties compute a step hash, which compresses the previous step hash, along with the outputs of the current step, forming a cryptographically secure hash chain. The goal of the challenger in the DPR is to find a point in the trace where a “malfunction” occurs. This is the point where the computation was being executed correctly until it was no longer. To find the malfunction, the challenger will ask the prover to sign and publish different step hashes chosen by the challenger. To speed up the search, the challenger will use a n-ary dissection search.

The following simplified diagram shows how operator and verifier follow the trace dissection search protocol:

Formally, we define malfunction as a pair of consecutive steps such that the fist step has a correct step hash (which is signed by the responder), and the second step has an incorrect step hash (also signed by the responder). The malfunction is defined from the point of view of the challenger. From the point of view of the responder, there is no CPU fault: either she is cheating when providing the step hashes or she is providing the correct step hashes but the challenger still wants to engage in the DPR for some unknown reason. However, BitVMX DPR is different from other dispute protocols. In TrueBit and BitVM CPU dispute protocols, a Merkle tree of all hash steps is used for the verifier to find the first point of malfunction. In BitVMX we don’t use a tree data structure and the verifier only finds a point of malfunction, which may not be the first. However, the protocol gives enough information for the verifier to be able to prove that the operator has cheated in a number of communication rounds which is logarithmic to the number of executed steps.

Once the challenger knows the malfunctioning step, the next thing she must do to prove cheating is to learn what sub-operation within the step execution was faulty. The CPU does multiple things in one step: it reads a number of words from memory, it reads the program counter (PC), it fetches the opcode, it performs a computation and it writes back the results to one or more memory words. Any of these sub-operations may be incorrect.

Proving an incorrect PC is as simple as comparing the PC in the incorrect step with the PC written by the correct step immediately preceding it. Assuming correct input (the memory words, the PC and the opcode), proving an incorrect computation output is easy by executing the step onchain and comparing the onchain results with the results embedded in the responder’s signed step trace.

Proving an incorrect memory read takes a bit longer, because BitVMX does not merkelize the memory, but nevertheless it’s easy. Embedded in the trace, the responder always includes the step number corresponding to the last trace step when the memory word read was written. The challenger learns this and requests the trace step hash of that memory writing step. If the memory writing step hash is correct, the challenger can easily prove that the responder cheated, because the value written in the writing step must differ from the value read by the step reading the memory word. If the trace step hash is incorrect, then the challenger has found an incorrect step followed by a correct one (remember that originally the challenger found two consecutive steps, one correct and the other incorrect). Therefore the challenger and the responder can engage in a second step searching protocol on the trace, but this time the challenger tries to find a “recovery”, which is defined as a pair of steps where the first is incorrect, but the second is correct. Obviously such a miraculous recovery is infeasible in practice, because it means that the prover found by chance two different hash chains that end with the same hash digest (the correct step hash). Therefore we assume the  prover is cheating. Once the challenger finds this new pair of consecutive steps, she can just challenge the computation of the hash function that links both step hashes.

The following diagram describes the two search processes, the first searching from the start of the trace to the last step (F), finding the malfunction step (q) referencing a last write step (t),  then finding the recovery point (w):

The following flowchart represents the main challenger decision tree (simplified):

From Two-Party to N-Party

The BitVMX protocol can be easily described as a game of two parties, where they initially collaborate to create the transaction templates that establish a covenant DAG that guides the dispute process. Moving from two-party to N-party (N>2) is possible, but not straightforward, as there are multiple design decisions to make, as there can be collusion between parties.  Should there be one or multiple provers? Should all verifiers collaborate during the dispute or should each verifier proceed independently ? Should verifiers trust on the other verifier’s dispute process while it is conducted honestly or should they aggressively challenge as fast as they can to avoid losing valuable challenge time? If not a single UTXO but multiple UTXOs are encumbered by BitVMX covenants, then there are even more design choices to make. Should security bonds be shared? Should operator withdrawals  be rate limited to prevent overloading the verifiers? During the course of our research,  we plan to extend the 2-party protocol to multi-party and support different staking and parallel dispute models.

One of the properties that is inextricable to BitVM and derived protocols is that there is at least one transaction (the kick-off) which must be presigned by a set of parties (a committee), and if all those parties cheat, and later generate a different kick-off transaction, they can steal the funds. Since nobody can formally prove that she has destroyed a private key, users must trust this commitee. The consequence is that BitVM and derived protocols have a 1-of-N honesty assumption, where N is the size of the committee. This is true even if the DRP could be made permissionless and anyone could challenge.