Tuesday, November 16, 2021

The $65B Prize

Senator Everett Dirksen is famously alleged to have remarked "a billion here, a billion there, pretty soon you're talking real money". There are a set of Bitcoin wallets containing about a million Bitcoins that are believed to have been mined by Satoshi Nakamoto at the very start of the blockchain in 2008. They haven't moved since and, if you believe the bogus Bitcoin "price", are currently "worth" $65B. Even if you're skeptical of the "price", that is "real money". Below the fold, I explain how to grab these million Bitcoin and more for yourself.

In the trial of Kleiman vs. Wright, currently under way in the Southern District of Florida, both sides stipulated that Craig Wright is Satoshi Nakamoto and thus controls the million Bitcoin. Kleiman's estate argues that, since Wright claimed that Kleiman helped create Bitcoin, he is entitled to half of them. Except in the context of the trial, Wright's claim to be Satoshi Nakamoto is implausible. He has been challenged to show that he has the private keys for Nakamoto's wallets by moving some of their coins. He has repeatedly failed to do so, and has failed to respond to court orders regarding them.

For the purpose of this post I assume that Wright is not Satoshi Nakamoto, and that the lack of motion of the coins in Nakamoto's wallets means either that Nakamoto is no longer with us, or has lost the relevant keys.

The security of cryptocurrencies has two aspects, both threatened by the rise of quantum computing:
  • The security of the blockchain itself, which was the subject of my talk at the "Blockchain for Business" conference. In principle, quantum computers can out-perform mining ASICs at Proof-of-Work, allowing for 51% attacks on blockchains secured using PoW.
  • The security of the public-key encryption used to protect transactions. In principle, quantum computers can use Shor's algorithm to break the encryption currently in use, allowing them to steal the contents of wallets.
The abstract of 2019's Quantum attacks on Bitcoin, and how to protect against them by Divesh Aggarwal et al reads:
The key cryptographic protocols used to secure the internet and financial transactions of today are all susceptible to attack by the development of a sufficiently large quantum computer. One particular area at risk are cryptocurrencies, a market currently worth over 150 billion USD. We investigate the risk of Bitcoin, and other cryptocurrencies, to attacks by quantum computers. We find that the proof-of-work used by Bitcoin is relatively resistant to substantial speedup by quantum computers in the next 10 years, mainly because specialized ASIC miners are extremely fast compared to the estimated clock speed of near-term quantum computers. On the other hand, the elliptic curve signature scheme used by Bitcoin is much more at risk, and could be completely broken by a quantum computer as early as 2027, by the most optimistic estimates. We analyze an alternative proof-of-work called Momentum, based on finding collisions in a hash function, that is even more resistant to speedup by a quantum computer. We also review the available post-quantum signature schemes to see which one would best meet the security and efficiency requirements of blockchain applications.
Aggarwal et al contine to track the likely date for the signature to be broken, currently projecting between 2029 and 2044.

So we have a decade or so before quantum computing threatens the blockchain security provided by Proof-of-Work. Since what Proof-of-Work does is to make Sybil attacks uneconomic, the fact that quantum computers will initially be very expensive compared to conventional ASICs means that the threat would in practice be delayed beyond the point where they were faster until the point where they were enough cheaper to make Sybil attacks economically feasible.

But the reward for building a "sufficiently large quantum computer" to break elliptic curve signatures would be the content of the wallets whose signatures were broken, The expectation is that, before this happened, wallet owners would transfer their HODL-ings to new wallets using "post-quantum cryptography", rendering them immune from theft via quantum computing. Problem solved!

Not so fast! I am assuming that the keys for Nakamoto's wallets are inaccessible through death or loss. Thus Nakamoto cannot migrate the million Bitcoin they contain to wallets that use post-quantum cryptography. Thus the first person to control a "sufficiently large quantum computer" can break the encryption on Nakamoto's wallets and transfer the million Bitcoin to a post-quantum wallet they own. Who is to know that this wasn't Satoshi Nakamoto taking a sensible precaution? The miscreant can then enjoy the fruits of their labor by repaying the costs of development of their quantum computer, and buying the obligatory Lamborghini. These would take only a small fraction of the $65B, and would be seen as Nakamoto enjoying a well-deserved retirement.

But wait, there's more! Chainalysis estimates that about 20% of all Bitcoins have been "lost", or in other words are sitting in wallets whose keys are inaccessible. That is around another 3.6 million stranded Bitcoin or at the current "price" about $234B. These coins need to be protected from theft by some public-sprited person with a "sufficiently large quantum computer" who can transfer them to post-quantum wallets he owns. The reward for being first to rescue Nakamoto's and the other stranded Bitcoin is actually not $65B but almost a third of a trillion dollars. Even by Dirksen's standards that is "real money". Certainly enough to accelerate the development of a "sufficiently large quantum computer" before 2029.


David. said...

D. T. Max reports on some of the Bitcoins that will be part of the $65B reward in Half a Billion in Bitcoin, Lost in the Dump.

David. said...

Dan Goodin reports that The cryptopocalypse is nigh! NIST rolls out new encryption standards to prepare:

"On Tuesday, NIST said it selected four candidate PQC algorithms to replace those that are expected to be felled by quantum computing. They are: CRYSTALS-Kyber, CRYSTALS-Dilithium, FALCON, and SPHINCS+.

CRYSTALS-Kyber and CRYSTALS-Dilithium are likely to be the two most widely used replacements. CRYSTALS-Kyber is used for establishing digital keys that two computers that have never interacted with each other can use to encrypt data. The remaining three, meanwhile, are used for digitally signing encrypted data to establish who sent it."

Alas, these standards don't address the problem outlined in this post. Events, however, have greatly reduced the prize, which now stands around a mere $20B.