Bitcoin's Academic Pedigree

Bitcoin's Academic Pedigree (also here) by Arvind Narayanan and Jeremy Clark starts:

If you've read about bitcoin in the press and have some familiarity with academic research in the field of cryptography, you might reasonably come away with the following impression: Several decades' worth of research on digital cash, beginning with David Chaum, did not lead to commercial success because it required a centralized, banklike server controlling the system, and no banks wanted to sign on. Along came bitcoin, a radically different proposal for a decentralized cryptocurrency that didn't need the banks, and digital cash finally succeeded. Its inventor, the mysterious Satoshi Nakamoto, was an academic outsider, and bitcoin bears no resemblance to earlier academic proposals.

They comprehensively debunk this view, showing that each of the techniques Nakamoto used had been developed over the preceding three decades of academic research, and that Nakamoto's brilliant contribution was:

the specific, complex way in which the underlying components are put together.

Below the fold, details on the specific techniques.

The idea of a cryptocurrency originates in David Chaum's 1983 Blind signatures for untraceable payments. Narayanan and Clark trace it through several successors leading up to Bitcoin in 2008. The techniques Nakamoto used were:

1. Public keys as pseudonymous identities, introduced in 1981's Untraceable electronic mail, return addresses, and digital pseudonyms by David Chaum.
2. Fault and attack resilience through voting among peers, introduced in 1982's The Byzantine Generals Problem by Leslie Lamport, Robert Shostak and Marshall Pease.
3. An integrity-protected, append-only log, introduced in 1991's How to timestamp a digital document by Stuart Haber and W. Scott Stornetta, based in turn on Merkle trees, introduced in 1980's Protocols for public key cryptosystems by Ralph Merkle.
4. Proof-of-work, introduced in 1992's Pricing via Processing or Combatting Junk Mail by Cynthia Dwork and Moni Naor.

In 2003, nearly five years before Nakamoto's magnum opus, my co-authors and I won a "best paper" award at the prestigious SOSP workshop for Preserving Peer Replicas By Rate-Limited Sampled Voting. It described a decentralized consensus system using voting among peers and proof-of-work, the protocol underlying the LOCKSS system. It doesn't rate a mention from Narayanan and Clark because its innovations weren't relevant to cryptocurrencies, but it illustrates the way these techniques were well-known in the computer science field.

Narayanan and Clark's detailed exposition of each of the techniques and the way Bitcoin combines them makes a fascinating read. It illuminates the gap between academia and practice, and they advocate better communication:

Practitioners would benefit from being able to identify overhyped technology. Some indicators of hype: difficulty identifying the technical innovation; difficulty pinning down the meaning of supposedly technical terms, because of companies eager to attach their own products to the bandwagon; difficulty identifying the problem that is being solved; and finally, claims of technology solving social problems or creating economic/political upheaval.

In contrast, academia has difficulty selling its inventions. For example, it's unfortunate that the original proof-of-work researchers get no credit for bitcoin, possibly because the work wasn't well known outside academic circles. Activities such as releasing code and working with practitioners are not adequately rewarded in academia. In fact, the original branch of the academic proof-of-work literature continues today without acknowledging the existence of bitcoin! Engaging with the real world not only helps get credit, but will also reduce reinvention and is a source of fresh ideas.

Amen!