2026-10-03T22:35:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27855 2026-10-02T17:40:21Z ddc:004 open_access

BitVM: Quasi-Turing Complete Computation on Bitcoin Aumayr, Lukas Avarikioti, Zeta Woll, Robin Linus Maffei, Matteo Pelosi, Andrea Stefo, Christos Zamyatin, Alexei Bitcoin quasi-Turing completeness off-chain protocols bridge A long-standing question in the blockchain community is which class of computations is efficiently expressible in cryptocurrencies with limited scripting languages, such as Bitcoin Script. Such languages expose a reduced trusted computing base, thereby being less prone to hacks and vulnerabilities, but have long been believed to support only limited classes of payments. In this work, we confute this long-standing belief by showing for the first time that arbitrary computations can be encoded in today’s Bitcoin Script without introducing any language modification or additional security assumptions, such as trusted hardware, trusted parties, or committees with an honest majority. We present BitVM, a two-party protocol that realizes a generic virtual machine by combining cryptographic primitives and economic incentives. We conduct a formal analysis of BitVM, characterizing its functionality, system assumptions, and security properties. We further demonstrate the practicality of our approach by implementing a prototype and performing an experimental evaluation: in the optimistic case (i.e., when parties agree), our protocol requires just three on-chain transactions, whereas in the pessimistic case, the number of transactions grows logarithmically with the size of the virtual machine. We exemplify the deployment potential of BitVM by building a Bitcoin-sidechain bridge application. This work not only solves a long-standing theoretical problem, but it also promises a strong practical impact, enabling the development of complex applications in Bitcoin. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lukas Aumayr and Zeta Avarikioti and Robin Linus Woll and Matteo Maffei and Andrea Pelosi and Christos Stefo and Alexei Zamyatin 2026 Is Part Of LIPIcs, Volume 395, 8th Conference on Advances in Financial Technologies (AFT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AFT.2026.1 urn:nbn:de:0030-drops-278556 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2026.1 eng https://creativecommons.org/licenses/by/4.0/legalcode