Bitcoin Box

A magazine dedicated to all things Bitcoin

Bitcoin is Worse is Better

author: gwern
published: 2011-05-28 03:50:38 UTC

Some wonder who is the real man under the Satoshi Nakamoto mask; a hard question - how many libertarian cryptographers are there? But the interesting thing is, Satoshi could be anybody. Bitcoin involves no major intellectual breakthroughs, so Satoshi need have no credentials in cryptography or be anything but a self-taught programmer! Satoshi registered bitcoin.org in August 2008 and published his whitepaper May 2009, but if you look at the cryptography that makes up Bitcoin, they can basically be divided into:

Public key cryptography
Cryptographic signatures
Cryptographic hash functions
Hash chain used for proof-of-work
- Hash tree
- Bit gold
cryptographic time-stamps

Pre-requisites

The interesting thing is that by even the most generous accounting, all the pieces were in place for at least 8 years before Satoshi's publication, which was followed more than half a year later by the first public prototype (Satoshi claims that before he write the whitepaper, he wrote a prototype). If we look at the citations in the whitepaper and others, and then order the relevant technologies by year in descending order:

2001-2005: Nick Szabo, Bit Gold
2001: SHA-256 finalized
1998: Wei Dai, B-money
1997: HashCash
1992-1993: Proof-of-work for spam ("Pricing via Processing, Or, Combating Junk Mail, Advances in Cryptology", Dwork 1993, published in CRYPTO'92)
1991: cryptographic timestamps
1980: public key cryptography. (This is Satoshi's citation date; Diffie-Hellman, the first published system, was in 1976, not 1980.)
1979: Hash tree

I've guessed a bit with the first item: it's hard to figure out when exactly Szabo devised bit gold; his post claims to be from December 2008 but the URL indicates 2005 and it is linked in November 2008 emails. Szabo has long been interested in proof-of-work systems, writing on them in ~1998. A paper started in 2001 motivates the existence of bit gold and describes, but that may be material from the 2004 or 2005 revisions. Hal Finney mentioned bit gold in 2008 (in the context of a bitcoin discussion) describing Szabo's proposal as 'many years ago', and inasmuch as Hal has been active in cryptography circles since the '80s (was a member of the Cypherpunks mailing list etc.), it seems unlikely Hal was speaking of something then just 3 years ago.

This lack of novelty is part of the appeal - the fewer new parts of a cryptosystem, the less danger. All that was lacking was a Satoshi to start a Bitcoin.

Delay

But why this delay? If the idea is easy to understand and uses basic ideas, if it is very far from the cutting-edge of cryptography - one thinks of the formidable mathematical difficulties surrounding the area of homomorphic encryption where one would expect any breakthrough to be from a bona fide genius, or at least a credentialed expert - then there's no obvious reason it would not be seriously tried. I am only a layman with an interest in cryptography, but I am not alone in seeing this lack of really novel primitives or ideas in the Bitcoin scheme; Ben Laurie expresses exactly this idea in an aside in a blog post attacking Bitcoin:

"A friend alerted to me to a sudden wave of excitement about Bitcoin. I have to ask: why? What has changed in the last 10 years to make this work when it didn't in, say, 1999, when many other related systems (including one of my own) were causing similar excitement? Or in the 20 years since the wave before that, in 1990? As far as I can see, nothing."

Certainly the cypherpunks of the '90s were wildly creative, inventing everything from Cypherpunk/Mixmaster to MojoNation to assassination markets to data havens (memorably depicted in Cryptonomicon). We have already seen 2 of their proposed cryptocurrencies, and proof-of-work was one of the most common proposals to deal with the rising tsunami of spam. (Although ironically, proof-of-work never seemed to go into widespread use because of general inertia and because to deter large amounts of spam, proof-of-work would deter legitimate users under some models; spam seems to have been kept in check by better filtering techniques (eg. Paul Graham's "A Plan for Spam" using Bayesian spam filtering) and legal action against botnets & spammers.) Why did Bitcoin take a decade to be born? The problem nags at me - similar to the historical question of why England experienced the Industrial Revolution and grew to empire, and not China, which seems better equipped in every respect. There must be an answer.

(For more on the history of industrialization, see Wikipedia on Industrial Revolution#Causes for occurrence in Europe, Chinese industrialization, the Great Divergence; I strongly recommend Gregory Clark's A Farewell to Alms.)

Impractical?

Is the problem one of resources? In the whitepaper, Satoshi remarks:

A block header with no transactions would be about 80 bytes. If we suppose blocks are generated every 10 minutes, 80 bytes * 6 * 24 * 365 = 4.2MB per year. With computer systems typically selling with 2GB of RAM as of 2008, and Moore's Law predicting current growth of 1.2GB per year, storage should not be a problem even if the block headers must be kept in memory.

That's fine to say in 2008, after many doublings. Would memory be a problem in the 1990s? It doesn't have to be. The difficulty of bitcoin mining is obviously adjustable, so the problem boils down to:

disk usage
- Use a smaller hash like SHA1; SHA-1, as of 2011, has not been cracked in practice.
- 10 minutes is not graven in stone; why not 20 minutes? Right there we have halved the hash tree
- the hash tree can be 'garbage collected' and shrunk. (My understanding is that simply no one has bothered to program this functionality since 400MB is not that much space.)
- it is only necessary to maintain a full hash tree if one is paranoid.
  
  In practice, like many programs of the era such as mail or Usenet clients, the default could simply be to hold onto the last n blocks/hashes (Satoshi estimates 12kb/day); this would consume a limited amount of disk space.
network connectivity is solvable by solutions to #1
1. A function of the existing hash tree size
2. And frequency of new transactions

It's worth pointing out that it's generally expected that at some point ordinary desktop users like you or me are expected to stop being full-fledged nodes and bitcoin miners and will instead make use of some specialist service running powerful servers of its own; in a counterfactual universe where Bitcoin was begun in the early 1990s, the changeover would simply have occurred sooner. (And with all the investment money desperately investing in the first Internet bubble, it would be quite easy to start such a service regardless of the technical demands.)

Contemporary objections

As well, few of the objections to cryptocurrencies seem to have been "computers which can run it are fantastically expensive". When there were performance objections, the objections were that cryptocurrencies had to be mobile - usable on the contemporary PDAs and cellphones, with the computing power of a watch. In computing, applications and techniques are often invented many decades before Moore's law makes them practically useful. (Garbage collection and most of artificial intelligence (or machine learning in particular) seem to have waited decades for sufficiently fast hardware. Indeed, I sometimes feel that Alan Kay's entire career has essentially been sketching out what he could do if only he had some decent cheap hardware.], but this does not seem to have happened with Bitcoin. A similar objection obtains with patents or published papers; if Bitcoin was a known idea, where are they? I have yet to see anybody point out what patents might have deterred cryptography researchers & implementers; the obvious answer is that there were none. Because there was no investor interest? Not that Satoshi needed investors, but there were a tremendous number of online payment services started in the '90s, each searching for the secret sauce that would let them win 'mindshare' and ride 'network effects' to victory; DigiCash again comes to mind.

So if the basic idea is accessible, and it's useful on consumer-grade hardware for the last 20 years or so, then what's the problem?

Cryptographers' objections

I think it's instructive to look at Satoshi's ANN thread on the Cryptography newsgroup/mailing list; particularly the various early criticisms:

disk/bandwidth won't scale
proposal is underspecified (omitting all the possible race conditions and scenarios in a distributed system) and details available only in code
conflating transactions with bitcoin creation requires constant inflation
it is very difficult to achieve consensus on large amounts of distributed data even without incentives to corrupt it or attacks
domination of the hash tree by fast nodes and starvation of transactions
pseudonymity & linkable transactions (irreversible transactions also implies double-spend must be very quickly detectable); Nick Szabo, discussing Chaumian ecash, comments (with almost palpable distaste) of a hypothetical system akin to Bitcoin in this respect:

"A use-once-address communications mix plus foreswearing any reputation gain from keeping accounts, in theory also buys us unlinkability, but a communications mix is weak and very expensive."

As well, let's toss in some recent blog posts on Bitcoin by the cryptographer Ben Laurie

What's the common thread? Is there any particular fatal flaw of Bitcoin that explains why no one but Satoshi came up with it?

Aesthetics

No! What's wrong with Bitcoin is that it's ugly. It is not elegant. It's clever to define your bitcoin balance as whatever hash tree is longer, has won more races to find a new block, but it's ugly to make your network's security depend solely on having more brute-force computing power than your opponents, ugly to need at least half the processing power just to avoid double-spending. It's clever to have a P2P network distributing updated blocks which can be cheaply & independently checked, but there are tons of ugly edge cases which Satoshi has not proven (in the sense that most cryptosystems have security proofs) to be safe and he himself says that what happens will be a 'coin flip' at some points. It's ugly to have a hash tree that just keeps growing and is going to be gigabytes and gigabytes in not terribly many years. It's ugly to have a system which can't be used offline without proxies and workarounds, unlike Chaum's elegant. It's ugly to have a system that has to track all transactions, publicly; even if one can use bitcoins pseudonymously, that doesn't count for much, a cryptographer has learned from incidents like anon.penet.fi and decades of successful attacks on pseudonymity (for example, see some of the most recent research I linked in Death Note: L, Anonymity & Eluding Entropy). And what's with that arbitrary looking 21 million bitcoin limit? Couldn't it have been a rounder number or at least a power of 2? (Not that the bitcoin mining is much better, as it's a massive give-away to early adopters. Coase's theorem may say it doesn't matter how bitcoins are allocated in the long run, but such a blatant bribe to early adopters rubs against the grain. Again, ugly and inelegant.) Bitcoins can simply disappear if you send them to an invalid address.

How Worse is Better

In short, Bitcoin is a perfect example of Worse is Better (original essay). You can see the tradeoffs that Richard P. Gabriel enumerates: Bitcoin has many edge cases; it lacks many properties one would desire for a cryptocurrency; the whitepaper is badly underspecified; much of the behavior is socially determined by what the miners and clients collectively agree to accept, not by the protocol; etc.

But it seems to work. Just like Unix, there were countless ways to destroy your data or crash the system, which didn't exist on more 'proper' OSs like OpenVMS, and there were countless lacking features compared to systems like ITS or the Lisp machine OSs. But like the proverbial cockroaches, Unix spread, networked, survived - and the rest did not. The UNIX-HATERS Handbook, which contains many entertaining and often still-applicable descriptions of the fecklessness and sharp edges of Unixes, also contains an extremely funny 'Anti-Foreword' by Dennis Ritchie:

"To the contributors to this book: I have succumbed to the temptation you offered in your preface: I do write you off as envious malcontents and romantic keepers of memories. The systems you remember so fondly (TOPS-20, ITS, Multics, Lisp Machine, Cedar/Mesa, the Dorado) are not just out to pasture, they are fertilizing it from below...You claim to seek progress, but you succeed mainly in whining. Here is my metaphor: your book is a pudding stuffed with apposite observations, many well-conceived. Like excrement, it contains enough undigested nuggets of nutrition to sustain life for some. But it is not a tasty pie: it reeks too much of contempt and of envy. Bon appetit!"

A cryptographer would have difficulty coming up with Bitcoin because it is so ugly and there are so many elegant features he wants in it. Programmers and mathematicians often speak of 'taste', and how they lead one to better solutions. A cryptographer's taste is for cryptosystems optimized for efficiency and theorems; it is not for systems optimized for virulence, for their sociological appeal ("Bitcoin, like the recent commercial phenomenon Groupon, tends to turn people into marketers because they feel they have something to gain, however small it might be in the end; I think that partly accounts for its temporary success."). Centralized systems are natural solutions because they are easy, like the integers are easy; but like the integers are but a vanishingly small subset of the reals, so too are centralized systems a tiny subset of decentralized ones. DigiCash and all the other cryptocurrency startups may have had many nifty features, may have been far more efficient, and all that jazz, but they died anyway. They had no communities, and their centralization meant that they fell with their corporate patrons. They had to win in their compressed timeframe or die out completely. But "that is not dead which can eternal lie".

It may be that Bitcoin's greatest virtue is not its deflation, nor its microtransactions, but its viral distributed nature; it can wait for its opportunity. "If you sit by the bank of the river long enough, you can watch the bodies of your enemies float by."