The overlooked history of Turing Completeness in Bitcoin

Turing completeness, a term that resonates in the hallowed halls of computer science departments worldwide, essentially means that a system can simulate a Turing machine or calculate a Turing function: a theoretical device that can perform any calculation given enough time and resources.

In short, Turing completeness implies that a device is a computer.

Bitcoin, often mistakenly pigeonholed as a mere digital currency, possesses this capacity for Turing computation by using transactions and script functions (and it always has.)

Now, the BitVM team, a cohort of BTC industry devs, would have you believe they are the first to unlock this potential within a Bitcoin-style system. This claim not only sidesteps years of prior work but also disregards the intellectual lineage that paved the way for such advancements. Quite frankly, the BitVM team should at least acknowledge the pioneering work from Dr. Craig Wright and the broader BSV blockchain ecosystem for doing most of the requisite R&D into such systems.

Can #Bitcoin handle Turing-complete smart contracts? With BitVM, it can! 🎉

Created by @Robin_Linus, the mind behind @ZeroSync_, BitVM performs most computational work off-chain, ensuring secure and efficient operations with minimal impact.

👉 https://t.co/Bk4qZGWEfz pic.twitter.com/RhOuwnfs0M

— Bitfinex (@bitfinex) October 13, 2023

Let’s rewind to 2015, when Dr. Wright, often a controversial figure but an undeniable thought leader in the space, openly talked about Bitcoin’s Turing completeness in a now-infamous on-stage exchange with Nick Szabo. Notably, Dr. Wright is a Doctor of Computer Science and explains the dual stack opportunity that exists with languages like Forth (of which bitcoin script is a variation), and then Szabo retorts that Wright should produce a white paper on the esoteric concept because he doesn’t think Bitcoin is a Turing complete system. Joseph Vaughn Perling interjects that both men are actually correct depending on what is being looked at and how the system is implemented.

The point is that Turing complete computation is not a new concept in Bitcoin.

But wait, there’s more!

Fast forward to 2018, and an Oxford University Doctor of Computer Science named Clemens Ley took the concept further by introducing the “Bitcoin Computer” protocol, which showcased how Bitcoin can indeed compute Turing functions. He presented this concept live in Japan at the “Satoshi’s Vision Conference” organized by Bitcoin Unlimited. He gracefully explains that while the script itself isn’t Turing complete, the system as a whole can compute Turing functions in a few novel ways.

Ryan X Charles gave a similar presentation that appears to have been scrubbed from the internet.

In 2020, Brenton Gunning rolled out the “RUN” protocol, illustrating how, theoretically and practically, anything could “Run on Bitcoin” using JavaScript and on-chain computation of smart contracts. The Run protocol has generated hundreds of millions of transactions on the BSV blockchain, which shares the genesis block and SHA256 hashing algorithm with BTC today. The existence and proliferation of this computation is not unknown.

Its announcement can be seen to this day.

The narrative didn’t stop there. Xiaohui Liu, yet another Doctor of Computer Science, introduced the sCrypt smart contract language to the world in 2019, and while it wasn’t the most rapidly adopted solution for implementing Turing completeness in a Bitcoin system, it is now the most powerful! The sCrypt language, which Liu has said is “Solidity, but for Bitcoin,” cleverly uses Bitcoin Script to demonstrate that Bitcoin can support unbounded, Turing-computable applications.

Here’s a presentation from 2019.

Liu has even been so kind as to post various proofs of Turing completeness in a Bitcoin system in public on X.com!

If you don’t believe Bitcoin is Turing-complete after reading this article or don’t get it, I don’t have the time to try to convince you, sorry. https://t.co/xWxSwF3KI8

— sCrypt Official | OP_CAT 🐱 (@scryptplatform) September 17, 2021

Yet, all these pioneering efforts seem to have been relegated to the footnotes of Bitcoin’s history by the small blockers who control the media narrative in the blockchain economy, and they have been overshadowed by the trumpeting arrival of Robin Linus’ BitVM.

BitVM touts itself as a groundbreaking initiative to introduce novel Turing completeness to BTC, but a close examination reveals that their work bears a striking resemblance to these prior developments. The protocol seems to cherry-pick elements from each of the aforementioned groundbreaking works without acknowledging the hard-fought insights and innovations of those who have been in the trenches of Bitcoin development for eight to nine years. This is not just an oversight; it’s intellectual negligence not to acknowledge such extensive prior work in a white paper.

"Any computable function can be verified on Bitcoin"https://t.co/Itf9UHos0C pic.twitter.com/CLQv49Ydsg

— яobin linus (@robin_linus) October 9, 2023

Of course, we can always count on Adam Back to rain on everyone’s parade if an idea wasn’t invented by Greg Maxwell.

for people getting (over) excited, this is cool but effectively a generalization of a two-party game – it says right in the abstract – so it's a bit like Greg Maxwell's 2016 ZKP contingent payments implemented example https://t.co/OeHRsbFjud

— Adam Back (@adam3us) October 9, 2023

Conclusion

In academia and science, failing to cite prior art is a cardinal sin. In the world of open-source technology, where collaboration and attribution are pillars of progress, this omission is equally grievous. The BitVM team should do the honorable thing: recognize the foundational work of Dr. Wright and the various builders from the BSV blockchain community. Despite political and worldview differences between the BTC and BSV camps, Ignoring the giants upon whose shoulders they stand not only diminishes their own credibility but also sows division in one of the few places where we could be united in pursuit of innovation and truth.

BitVM may well be a significant step forward in Bitcoin’s ongoing evolution, but claiming to be the “first” in an area as foundational as Turing completeness isn’t just factually incorrect; it’s a disservice to the hardworking developers and visionaries who have long understood Bitcoin’s unrealized potential.

In conclusion, as the conversation about Bitcoin’s capabilities broadens and deepens, let’s not rewrite history in the process. There’s room for everyone at the table of innovation, but seats should be offered to those who arrived first. And in the case of Turing completeness in Bitcoin, those seats are clearly marked for Dr. Wright, Clemens Ley, Brenton Gunning, Xiaohui Liu, and a number of others who legitimately risked their reputations to stand firmly on the proposition that bitcoin was capable of Turing complete computation, and in many cases, this position cost them a great deal personally and professionally.

The fact that people in the BSV blockchain economy took heat for this topic for years made it cost essentially nothing for BitVM to swoop in and propose a technical solution while spending very little political capital.

So, Linus, the ball is in your court. Do the right thing and acknowledge prior work.

Watch Dr. Craig Wright: A Proof of Turing completeness in Bitcoin Script