bitcoin is worse is better

[Eugen Leitl]

http://www.gwern.net/Bitcoin%20is%20Worse%20is%20Better

Bitcoin is Worse is Better

Home Site Me
26 Jan 2012

Bitcoin's long gestation indicates it is an example of the 'Worse is Better'
paradigm

    Pre-requisites
    Delay
        Impractical?
    Contemporary objections
        Cryptographers' objections
            Aesthetics
            How Worse is Better
    External links

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 published his whitepaper May
20091, 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

    "So the first answer to Why Now? is simply 'Because it's time.' I can't
tell you why it took as long for weblogs to happen as it did, except to say it
had absolutely nothing to do with technology. We had every bit of technology
we needed to do weblogs the day Mosaic launched the first forms-capable
browser. Every single piece of it was right there. Instead, we got Geocities.
Why did we get Geocities and not weblogs? We didn't know what we were
doing."2

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 later3 by the first public4 prototype. If
we look at the citations in the whitepaper and others, and then order the
relevant technologies by year in descending order:

    2001-20055: Nick Szabo, Bit Gold
    2001: SHA-256 finalized
    1998: Wei Dai, B-money6
    1997: HashCash
    1992-1993: Proof-of-work for spam7
    1991: cryptographic timestamps
    1980: public key cryptography8
    1979: Hash tree

This lack of novelty is part of the appeal - the fewer new parts of a
cryptosystem, the less danger9. 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 ideas10,
if it is very far from the cutting-edge of cryptography11, then there's no
obvious reason it would not be seriously tried. 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 spam12. 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 respect13. There must be an answer.
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
        With a smaller hash like SHA114, the 80 bytes can be shrunk
        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 shrunk15

        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
        A function of the existing hash tree size
        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"16. In computing,
applications and techniques are often invented many decades before Moore's law
makes them practically useful17, 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 scale18
    proposal is underspecified (omitting all the possible race conditions and
desynchronization attacks and scenarios in a distributed system) and details
available only in ad hoc code19
    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 transactions20 (irreversible transactions also
implies double-spend must be very quickly detectable)

As well, let's toss in some recent blog posts on Bitcoin by the cryptographer
Ben Laurie and Victor Grischchenko; Laurie particularly criticizes21 the
hash-contest which guarantees heavy resource consumption:

    "Bitcoin"
    "Bitcoin 2"
    "Bitcoin is Slow Motion"
    "Decentralised Currencies Are Probably Impossible: But Letbs At Least
Make Them Efficient"
    "Bitcoin?"

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 elegant22. 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 now and in perpetuity at least half the processing power just to
avoid double-spending23. 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 solution24. It's ugly
to have a system that has to track all transactions, publicly; even if one can
use bitcoins anonymously with effort, that doesn't count for much - a
cryptographer has learned from incidents like anon.penet.fi and decades of
successful attacks on pseudonymity25. 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. And so on.
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.26

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 appeal27. 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 ones28. 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."
External links

    Silk Road -(using the Silk Road marketplace)

    Original essay published on Bitcoin Weekly (7 comments)
        Reddit discussion
        Hacker News discussion

    Nick Szabo's reply/rebuttal, "Bitcoin, what took ye so long?"

    bitcoin.org was registered 18 August 2008, so presumably Satoshi had been
developing the bitcoin idea at least as early as 2008.b)

    "A Group Is Its Own Worst Enemy", by Clay Shirky, published July 1, 2003
on the "Networks, Economics, and Culture" MLb)

    The first revision in the Github repository is dated August 2009 by
'sirius-m'.b)

    Satoshi claims that before he write the whitepaper, he wrote a
prototypeb)

    It's hard to figure out when 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.b)

    In the same vein of 'the network is a third party which keeps a copy of
all signed transactions', you could include Ian Grigg's 2005 paper "Triple
Entry Accounting".b)

    "Pricing via Processing, Or, Combating Junk Mail", , Dwork 1993, published
in CRYPTO'92.b)

    This is Satoshi's citation date; Diffie-Hellman, the first published
system, was in 1976, not 1980.b)

    In cryptography, new parts are guilty until proven innocent. Hundreds of
past systems have been broken, sometimes after decades of study & use.b)

    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."

    b)

    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.b)

    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.b)

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

    SHA-1, as of 2011, has not been cracked in practice.b)

    My understanding is that simply no one has bothered to program this
functionality since 400MB is not that much space.b)

    Or rather, the objections were that cryptocurrencies had to be mobile -
usable on the contemporary PDAs and cellphones, with the computing power of a
watch.b)

    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.b)

    It probably will. Some informal projections have been made of what it
would take to run millions of transactions worth trillions of dollars, and
they tend to come in at comparable to the existing resource use of companies
like Google (which fund their own power plants or monopolize convenient
hydroelectric dams to run their datacenters).b)

    Recent criticism, too, sometimes focuses on the quality of the C++
codebase and ad hoc nature of many of the choices; from an anonymous Facebook
comment:

        "The protocol is not well-defined and clearly designed by an amateur
(that is, not someone who has done much protocol implementation work). It's a
binary protocol with a smattering of length-prefixing, null terminated
strings, etc. The messages look reasonable, just a horrible encoding. The
rules of the protocol are poorly defined and tightly coupled to
implementation; the implementation is done by someone who feels it's good and
well to have only 5 major source files for 17 KLOC. Due to lack of a
well-specified protocol, there is also a bit of client monoculture going on.

        It's worth noting that the whole system assumes SHA-256 -- the bitcoin
community says that rolling over to something else is just a matter of
introducing a new algo, but in actuality it's not nearly that simple. The
protocol has no concept of upgrading to different algos, so it would
necessitate a complete overhaul of the protocol (since there's a lot of
32-byte fields in there) AND a re-computation/rollover of the entire
transaction history. ...The protocol also has had no thought put into it re:
network architecture -- there are peers and that's it. Due to the
cryptographic nature of transactions, it's simply not possible to have
realtime transactions with bitcoin as the network scales (it already take 5-10
mins on average for the network to see a single transaction). Thus, there will
need to be some concept of a node in the network that can facilitate
interactions between two peers in a faster fashion, with the assumption of a
measure of trust. You shouldn't require it, of course, but it should be
defined, I think."

    Security expert Dan Kaminsky is similarly appalled at the bandwidth
requirements to scale (":0" was his emoticon) and predicts that the Bitcoin
network will eventually turn into a quasi-bank-like oligarchy of supernodes
(which changes the system and "offers a host of ugly semantics" since the
supernodes "don't need 50% -- just need to inconvenience 50% to accept your
opinion"). He comments that while "Normal Code" seems good but "Scratch the
surface, it's actually really bad", the Bitcoin codebase "Looks really bad up
front" and "Scratch the surface, it's actually surprisingly good". New Yorker
article's "The Crypto-currency: Bitcoin and its mysterious inventor":

        "'When I first looked at the code, I was sure I was going to be able
to break it', Kaminsky said, noting that the programming style was dense and
inscrutable. 'The way the whole thing was formatted was insane. Only the most
paranoid, painstaking coder in the world could avoid making mistakes.'...He
quickly identified nine ways to compromise the system...when he found the
right spot, there was a message waiting for him. 'Attack Removed', it said.
The same thing happened over and over, infuriating Kaminsky. 'I came up with
beautiful bugs', he said. 'But every time I went after the code there was a
line that addressed the problem.'...'I've never seen anything like it',
Kaminsky said, still in awe...'Either there's a team of people who worked on
this', Kaminsky said, 'or this guy is a genius.'"

    On a technical basis, he dislikes the use of SHA-256 as opposed to slower
time-lock crypto functions like bcrypt, because SHA-256 "can be accelerated
massively with GPUs" leading to GPU shortages and massive hashing disparities
between peers, and his slides conclude "BitCoin is actually well designed, if
you accept that anonymity and scaling forces the entire present model to be
shifted into something that effectively looks like banking"b)

    Nick Szabo, discussing Chaumian ecash ("the greatest simple equation since
e=mc2"), comments with almost palpable distaste of a hypothetical system akin
to Bitcoin in this respect:

        "A use-once-address communications mix plus forswearing any reputation
gain from keeping accounts, in theory also buys us unlinkability, but a
communications mix [BTC: "mixing service"; not necessarily easy] is weak and
very expensive."

    The most widely known, popular, and secure communications mix is probably
Tor; a number of flaws have been found in it over time, and Tor will never be
very secure - it's fundamentally difficult to impossible to have a anonymizing
communications mix which is also near real-time. Some flaws can't be removed
by the Tor network, like the ability of exit nodes to snoop on traffic (as has
been done many times, most memorably during the startup of Wikileaks).
Communications mixes are usually expensive in resources, so typically only
make up a part of an overall network - and the rest of the network leaks
considerable information, including in Bitcoin.b)

    Perry Metzger summarizes Laurie's approach:

        "I think people have missed the more subtle point that Ben Laurie made
here. Bitcoin requires the use of an unusual sort of secure consensus protocol
to work reliably, and such protocols are not known to exist in this context.
In the presence of such a protocol, however, there is no longer any need for
mining -- the system can simply elect a member to acquire a new coin every N
seconds via a secure election protocol (and those are known given the rest).
Thus, Ben's point that if you're going to have a system like bitcoin, one
could at least have an efficient system of this sort rather than a stupid one
based on an electrical potlatch."

    b)

    Not everyone agrees with me or those initial posters, though; "Bitcoins
create truly democratic policy, followers say", Canada.com:

        '"It's like the Mona Lisa." said Bruce Wagner, an IT consultant who
discovered bitcoin in October and now hosts an online TV show about it. "It's
a masterpiece of technology."'

    b)

    "Decentralised Currencies Are Probably Impossible: But Letbs At Least
Make Them Efficient", Ben Laurie:

        "Now that we understand the core problem, namely that of agreement, we
can quite easily understand Bitcoinbs solution to the problem. Bitcoin
defines the consensus group as ball the computing power in existenceb, and
requires participants to prove their possession of whatever fraction of this
power they care to spend on Bitcoin by using it to produce proof-of-work
tokens. And once we state the problem like this, we can quite clearly see the
flaw. Until at least half of the computing power in existence is actually used
to produce Bitcoins, we cannot know that we have consensus! If, for example,
1% of the total power availableStrictly, I mean energy rather than power,
since Bitcoin actually, in effect, sums power over time. is used to produce
Bitcoins at present (in fact, the amount is far less than that), then at any
point someone could come along with a further 1.1% of the total power and use
this to define their own consensusBy forking history right back to the first
block, and producing a hash chain that is longer than the current consensus.,
thus invalidating all the work, and all the money, of the initial group, and
instead take possession of the entire currency for themselves.

        ...Even worse, it is clear that arriving at the equilibrium state for
Bitcoin is incredibly expensive: half of all the computing power in existence
must be burnt, in perpetuity, maintaining agreement about the current state of
the currency. It also unknowable: we can never be sure that we actually are
burning half of all the power in existence, because we do not know how much
power exists."

    Laurie points out that in practice, the Bitcoin community does depend on a
centralized authority which periodically passes down 'blessed' block-chains -
the Bitcoin developers periodically hardwire known-good states of the
block-chain into the clients (which of course is a theoretical weakness).b)

    Chaum pays a price for his systems' ability to work offline. Don't take my
word for it; see Tim May in section 12.6.6 of his early '90s Cyphernomicon
(not to be confused with Stephenson's novel drawing heavily on it):

        "...Chaum went to great lengths to develop system which preserve
anonymity for single-spending instances, but which break anonymity and thus
reveal identity for double-spending instances. I'm not sure what market forces
caused him to think about this as being so important, but it creates many
headaches. Besides being clumsy, it require physical ID, it invokes a legal
system to try to collect from "double spenders", and it admits the extremely
serious breach of privacy by enabling stings. For example, Alice pays Bob a
unit of money, then quickly Alice spends that money before Bob can...Bob is
then revealed as a "double spender," and his identity revealed to whomever
wanted it...Alice, IRS, Gestapo, etc. A very broken idea. Acceptable mainly
for small transactions.

            Multi-spending vs. on-line clearing
                I favor on-line clearing. Simply put: the first spending is
the only spending. The guy who gets to the train locker where the cash is
stored is the guy who gets it. This ensure that the burden of maintaining the
secret is on the secret holder.
                When Alice and Bob transfer money, Alice makes the transfer,
Bob confirms it as valid (or verifies that his bank has received the deposit),
and the transaction is complete.
                With network speeds increasing dramatically, on-line clearing
should be feasible for most transactions. Off-line systems may of course be
useful, especially for small transactions, the ones now handled with coins and
small bills."

    b)

    For example, see some of the most recent research I linked in Death Note:
L, Anonymity & Eluding Entropy.b)

    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!"

    b)

    Many anonymous commenters point this out because it makes Bitcoin smell
like some sort of Ponzi scheme or multilevel marketing scheme:

        "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."

    Or "The Rise and Fall of Bitcoin", Wired:

        "Stefan Brands, a former ecash consultant and digital currency
pioneer, calls bitcoin bcleverb and is loath to bash it but believes
itbs fundamentally structured like ba pyramid schemeb that rewards early
adopters."

    John Robb, "More Thoughts on Bitcoin":

        "Lots of people are saying: "The deflation built into bitcoin was a
terrible idea. People are getting rich." In fact, it was a brilliant idea. It
brought in speculators (people that are buying/selling it as if in a game). It
created a bubble. The bubble put it on the map. The bubble has attracted
thousands of developers/participants. Think of how the Netscape IPO fueled the
Web/Internet."

    b)

    Decentralized systems are usually convertible into centralized systems
easily, while the converse is not true. (Much like parallel versus serial
programming - to make a parallel program serial, just insert a lot of
blocking.) For a simple example, consider cases where n=2: imagine a
BitTorrent swarm (a decentralized system) with one seed and one leech. Or take
Distributed Revision Control Systems like Darcs or Git; it's a commonplace to
point out that if a group really wants a 'centralized' workflow, they can just
designate one particular repository the 'master' canonical repository and
continue onwards with the DVCS as a more capable replacement for Apache
Subversion or CVS.b)