DROPS

Document

DOI: 10.4230/LIPIcs.AFT.2026.1

BitVM: Quasi-Turing Complete Computation on Bitcoin

Authors: Lukas Aumayr, Zeta Avarikioti, Robin Linus Woll, Matteo Maffei, Andrea Pelosi, Christos Stefo, and Alexei Zamyatin

Published in: LIPIcs, Volume 395, 8th Conference on Advances in Financial Technologies (AFT 2026)

Abstract

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.

Cite as

Lukas Aumayr, Zeta Avarikioti, Robin Linus Woll, Matteo Maffei, Andrea Pelosi, Christos Stefo, and Alexei Zamyatin. BitVM: Quasi-Turing Complete Computation on Bitcoin. In 8th Conference on Advances in Financial Technologies (AFT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 395, pp. 1:1-1:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{aumayr_et_al:LIPIcs.AFT.2026.1,
  author =	{Aumayr, Lukas and Avarikioti, Zeta and Woll, Robin Linus and Maffei, Matteo and Pelosi, Andrea and Stefo, Christos and Zamyatin, Alexei},
  title =	{{BitVM: Quasi-Turing Complete Computation on Bitcoin}},
  booktitle =	{8th Conference on Advances in Financial Technologies (AFT 2026)},
  pages =	{1:1--1:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-451-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{395},
  editor =	{Kiayias, Aggelos and Kyropoulou, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2026.1},
  URN =		{urn:nbn:de:0030-drops-278556},
  doi =		{10.4230/LIPIcs.AFT.2026.1},
  annote =	{Keywords: Bitcoin, quasi-Turing completeness, off-chain protocols, bridge}
}

Document

DOI: 10.4230/LIPIcs.AFT.2026.30

Optimal Reward Allocation via Proportional Splitting

Authors: Lukas Aumayr, Zeta Avarikioti, Dimitris Karakostas, Karl Kreder, and Shreekara Shastry

Published in: LIPIcs, Volume 395, 8th Conference on Advances in Financial Technologies (AFT 2026)

Abstract

Following the publication of Bitcoin’s arguably most famous attack, selfish mining, various works have introduced mechanisms to enhance blockchain systems' game-theoretic resilience. The only proof-of-work reward rule with a Nash-equilibrium guarantee, FruitChains, demands reward finality on the order of days. The rules that settle in minutes have no such guarantee, and one of them, Reward Splitting, still outperforms FruitChains on most of the metrics that matter in deployment. This paper closes that gap between theory and practice. We introduce FairChain, a two-level transformation for any proof-of-work Nakamoto-style protocol. At the protocol layer, FairChain records low-difficulty samples called workshares alongside blocks. At the reward layer, it applies Proportional Reward Splitting (PRS): each height’s reward is divided among the competing work objects in proportion to the intrinsic work behind them, with workshares supplying a fresh power estimate at every height. The fork-choice rule and block-production loop are left untouched, so the host chain’s security carries over unchanged. Workshares can be discarded once the corresponding rewards mature, leaving zero on-chain footprint. We prove FairChain is a ρ-coalition-safe ε-Nash equilibrium for sufficiently large parameters, matching FruitChains in theory. To evaluate practical performance, we leverage Markov decision processes and compute the optimal adversarial policy under each utility function, rather than the gain of any one attack. At a six-block confirmation window, FairChain raises the deviation threshold to 38% of mining power and beats every mechanism in that framework on incentive compatibility, subversion gain (except FruitChains above 42%), and censorship susceptibility (except FruitChains below 25%). Our construction has been adopted by a live PoW blockchain, with sub-kilobyte per-block storage overhead in deployment.

Cite as

Lukas Aumayr, Zeta Avarikioti, Dimitris Karakostas, Karl Kreder, and Shreekara Shastry. Optimal Reward Allocation via Proportional Splitting. In 8th Conference on Advances in Financial Technologies (AFT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 395, pp. 30:1-30:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{aumayr_et_al:LIPIcs.AFT.2026.30,
  author =	{Aumayr, Lukas and Avarikioti, Zeta and Karakostas, Dimitris and Kreder, Karl and Shastry, Shreekara},
  title =	{{Optimal Reward Allocation via Proportional Splitting}},
  booktitle =	{8th Conference on Advances in Financial Technologies (AFT 2026)},
  pages =	{30:1--30:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-451-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{395},
  editor =	{Kiayias, Aggelos and Kyropoulou, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2026.30},
  URN =		{urn:nbn:de:0030-drops-278848},
  doi =		{10.4230/LIPIcs.AFT.2026.30},
  annote =	{Keywords: blockchain, proof-of-work, fairness, game-theory, rewards}
}

Search Results

Documents authored by Aumayr, Lukas

BitVM: Quasi-Turing Complete Computation on Bitcoin

Abstract

Cite as

Optimal Reward Allocation via Proportional Splitting

Abstract

Cite as

Thanks for your feedback!

Could not send message