Bitcoin s Academic Pedigree – ACM Queue

The concept of cryptocurrencies is built from forgotten ideas ter research literature.

Arvind Narayanan and Jeremy Clark

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

This article challenges that view by demonstrating that almost all of the technical components of bitcoin originated ter the academic literature of the 1980s and ’90s (see figure 1). This is not to diminish Nakamoto’s achievement but to point out that he stood on the shoulders of giants. Indeed, by tracing the origins of the ideas ter bitcoin, wij can zero te on Nakamoto’s true leap of insight&mdash,the specific, ingewikkeld way te which the underlying components are waterput together. This helps explain why bitcoin took so long to be invented. Readers already familiar with how bitcoin works may build up a deeper understanding from this historical presentation. (For an introduction, see Bitcoin and Cryptocurrency Technologies by Arvind Narayanan et hoewel. 36 ) Bitcoin’s intellectual history also serves spil a case explore demonstrating the relationships among academia, outside researchers, and practitioners, and offers lessons on how thesis groups can benefit from one another.

The Ledger

If you have a secure ledger, the process to leverage it into a digital payment system is straightforward. For example, if Alice sends Bob $100 by PayPal, then PayPal debits $100 from Alice’s account and credits $100 to Bob’s account. This is also toughly what happens te traditional banking, albeit the absence of a single ledger collective inbetween banks complicates things.

This idea of a ledger is the beginning point for understanding bitcoin. It is a place to record all transactions that toebijten ter the system, and it is open to and trusted by all system participants. Bitcoin converts this system for recording payments into a currency. Whereas te banking, an account balance represents metselspecie that can be demanded from the bankgebouw, what does a unit of bitcoin represent? For now, assume that what is being transacted holds value inherently.

How can you build a ledger for use te an environment like the Internet where participants may not trust each other? Let’s embark with the effortless part: the choice of gegevens structure. There are a few desirable properties. The ledger should be immutable or, more precisely, append only: you should be able to add fresh transactions but not eliminate, modify, or reorder existing ones. There should also be a way to obtain a succinct cryptographic digest of the state of the ledger at any time. A digest is a brief string that makes it possible to avoid storing the entire ledger, knowing that if the ledger were tampered with ter any way, the resulting digest would switch, and thus the tampering would be detected. The reason for thesis properties is that unlike a regular gegevens structure that’s stored on a single machine, the ledger is a global gegevens structure collectively maintained by a mutually untrusting set of participants. This contrasts with another treatment to decentralizing digital ledgers, 7,13,21 te which many participants maintain local ledgers and it is up to the user querying this set of ledgers to resolve any conflicts.

Linked timestamping

Bitcoin’s ledger gegevens structure is borrowed, with minimal modifications, from a series of papers by Stuart Haber and Scott Stornetta written inbetween 1990 and 1997 (their 1991 paper had another co-author, Dave Bayer). Five,22,23 Wij know this because Nakamoto says so te his bitcoin white paper. 34 Haber and Stornetta’s work addressed the problem of document timestamping&mdash,they aimed to build a ",digital notary", service. For patents, business contracts, and other documents, one may want to establish that the document wasgoed created at a certain point ter time, and no zometeen. Their notion of document is fairly general and could be any type of gegevens. They do mention, te passing, financial transactions spil a potential application, but it wasn’t their concentrate.

Ter a simplified version of Haber and Stornetta’s proposal, documents are permanently being created and broadcast. The creator of each document asserts a time of creation and signs the document, its timestamp, and the previously broadcast document. This previous document has signed its own predecessor, so the documents form a long chain with pointers rearwards ter time. An outside user cannot alter a timestamped message since it is signed by the creator, and the creator cannot alter the message without also altering the entire chain of messages that goes after. Thus, if you are given a single voorwerp te the chain by a trusted source (e.g., another user or a specialized timestamping service), the entire chain up to that point is locked ter, immutable, and temporally ordered. Further, if you assume that the system rejects documents with incorrect creation times, you can be reasonably assured that documents are at least spil old spil they voorkeur to be. At any rate, bitcoin borrows only the gegevens structure from Haber and Stornetta’s work and reengineers its security properties with the addition of the proof-of-work scheme described straks ter this article.

Ter their follow-up papers, Haber and Stornetta introduced other ideas that make this gegevens structure more effective and efficient (some of which were hinted at te their very first paper). Very first, linksom inbetween documents can be created using hashes rather than signatures, hashes are simpler and quicker to compute. Such linksaf are called hash pointers. 2nd, instead of threading documents individually&mdash,which might be inefficient if many documents are created at approximately the same time&mdash,they can be grouped into batches or blocks, with documents ter each block having essentially the same timestamp. Third, within each block, documents can be linked together with a binary tree of hash pointers, called a Merkle tree, rather than a linear chain. Incidentally, Josh Benaloh and Michael den Mare independently introduced all three of thesis ideas te 1991, 6 soon after Haber and Stornetta’s very first paper.

Merkle trees

Bitcoin uses essentially the gegevens structure te Haber and Stornetta’s 1991 and 1997 papers, shown ter simplified form te figure Two (Nakamoto wasgoed presumably unaware of Benaloh and den Mare’s work). Of course, ter bitcoin, transactions take the place of documents. Te each block’s Merkle tree, the leaf knots are transactions, and each internal knot essentially consists of two pointers. This gegevens structure has two significant properties. Very first, the hash of the latest block acts spil a digest. A switch to any of the transactions (leaf knots) will necessitate switches propagating all the way to the root of the block, and the roots of all following blocks. Thus, if you know the latest hash, you can download the surplus of the ledger from an untrusted source and verify that it hasn’t switched. A similar argument establishes another significant property of the gegevens structure&mdash,that is, someone can efficiently prove to you that a particular transaction is included te the ledger. This user would have to send you only a petite number of knots ter that transaction’s block (this is the point of the Merkle tree), spil well spil a petite amount of information for every following block. The capability to efficiently prove inclusion of transactions is very desirable for voorstelling and scalability.

Merkle trees, by the way, are named for Ralph Merkle, a pioneer of asymmetric cryptography who proposed the idea ter his 1980 paper. 33 His intended application wasgoed to produce a digest for a public directory of digital certificates. When a webstek, for example, presents you with a certificate, it could also present a brief proof that the certificate emerges ter the global directory. You could efficiently verify the proof spil long spil you know the root hash of the Merkle tree of the certificates ter the directory. This idea is ancient by cryptographic standards, but its power has bot appreciated only of late. It is at the core of the recently implemented Certificate Transparency system. 30 A 2015 paper proposes CONIKS, which applies the idea to directories of public keys for end-to-end encrypted emails. 32 Efficient verification of parts of the global state is one of the key functionalities provided by the ledger ter Ethereum, a fresh cryptocurrency.

Bitcoin may be the most well-known real-world instantiation of Haber and Stornetta’s gegevens structures, but it is not the very first. At least two companies&mdash,Surety embarking ter the mid-’90s and Guardtime kicking off te 2007&mdash,suggest document timestamping services. An interesting twist present te both of thesis services is an idea mentioned by Bayer, Haber, and Stornetta, Five which is to publish Merkle roots periodically te a newspaper by taking out an ad. Figure Three shows a Merkle root published by Guardtime.

Byzantine fault tolerance

Of course, the requirements for an Internet currency without a central authority are more stringent. A distributed ledger will inevitably have forks, which means that some knots will think block A is the latest block, while other knots will think it is block B. This could be because of an adversary attempting to disrupt the ledger’s operation or simply because of network latency, resulting te blocks from time to time being generated near-simultaneously by different knots unaware of each other’s blocks. Linked timestamping alone is not enough to resolve forks, spil wasgoed shown by Mike Just te 1998. 26

A different research field, fault-tolerant distributed computing, has studied this problem, where it goes by different names, including state replication. A solution to this problem is one that enables a set of knots to apply the same state transitions ter the same order&mdash,typically, the precise order does not matter, only that all knots are consistent. For a digital currency, the state to be replicated is the set of balances, and transactions are state transitions. Early solutions, including Paxos, proposed by Turing Award winner Leslie Lamport te 1989, 28,29 consider state replication when communication channels are unreliable and when a minority of knots may exhibit certain ",realistic", faults, such spil going offline forever or rebooting and sending outdated messages from when it very first went offline. A prolific literature followed with more adverse settings and efficiency tradeoffs.

A related line of work studied the situation where the network is mostly reliable (messages are delivered with bounded delay), but where the definition of ",fault", wasgoed expanded to treat any deviation from the protocol. Such Byzantine faults include both naturally occurring faults spil well spil maliciously crafted behaviors. They were very first studied ter a paper also by Lamport, cowritten with Robert Shostak and Marshall Pease, spil early spil 1982. 27 Much straks, ter 1999, a landmark paper by Miguel Castro and Barbara Liskov introduced PBFT (practical Byzantine fault tolerance), which accommodated both Byzantine faults and an unreliable network. 8 Compared with linked timestamping, the fault-tolerance literature is enormous and includes hundreds of variants and optimizations of Paxos, PBFT, and other seminal protocols.

Te his original white paper, Nakamoto does not cite this literature or use its language. He uses some concepts, referring to his protocol spil a overeenstemming mechanism and considering faults both ter the form of attackers, spil well spil knots joining and leaving the network. This is te tegenstelling to his explicit reliance on the literature te linked timestamping (and proof of work, discussed next). When asked ter a mailing-list discussion about bitcoin’s relation to the Byzantine Generals’ Problem (a thought proefneming requiring BFT to solve), Nakamoto asserts that the proof-of-work chain solves this problem. 35

Te the following years, other academics have studied Nakamoto overeenstemming from the perspective of distributed systems. This is still a work ter progress. Some display that bitcoin’s properties are fairly feeble, 43 while others argue that the BFT perspective doesn’t do justice to bitcoin’s consistency properties. 40 Another treatment is to define variants of well-studied properties and prove that bitcoin sates them. Nineteen Recently thesis definitions were substantially sharpened to provide a more standard consistency definition that holds under more realistic assumptions about message delivery. 37 All of this work, however, makes assumptions about ",fair,", i.e., procotol-compliant, behavior among a subset of participants, whereas Nakamoto suggests that fair behavior need not be blindly assumed, because it is incentivized. A richer analysis of Nakamoto overeenstemming accounting for the role of incentives doesn’t gezond cleanly into past models of fault-tolerant systems.

Proof of Work

Virtually all fault-tolerant systems assume that a rigorous majority or supermajority (e.g., more than half or two-thirds) of knots ter the system are both fair and reliable. Te an open peer-to-peer network, there is no registration of knots, and they loosely join and leave. Thus an adversary can create enough Sybils, or sockpuppet knots, to overcome the overeenstemming ensures of the system. The Sybil attack wasgoed formalized te 2002 by John Douceur, 14 who turned to a cryptographic construction called proof of work to mitigate it.

The origins

To understand proof of work, let’s turn to its origins. The very first proposal that would be called proof of work today wasgoed created ter 1992 by Cynthia Dwork and Moni Naor. 15 Their purpose wasgoed to deter spam. Note that spam, Sybil attacks, and denial of service are all harshly similar problems ter which the adversary amplifies its influence ter the network compared to regular users, proof of work is applicable spil a defense against all three. Ter Dwork and Naor’s vormgeving, email recipients would process only those emails that were accompanied by proof that the sender had performed a moderate amount of computational work&mdash,hence, ",proof of work.", Computing the proof would take perhaps a few seconds on a regular rekentuig. Thus, it would pose no difficulty for regular users, but a spammer wishing to send a million emails would require several weeks, using omschrijving hardware.

Note that the proof-of-work example (also called a puzzle) has to be specific to the email, spil well spil to the recipient. Otherwise, a spammer would be able to send numerous messages to the same recipient (or the same message to numerous recipients) for the cost of one message to one recipient. The 2nd crucial property is that it should pose minimal computational cargo on the recipient, puzzle solutions should be trivial to verify, regardless of how hard they are to compute. Additionally, Dwork and Naor considered functions with a trapdoor, a secret known to a central authority that would permit the authority to solve the puzzles without doing the work. One possible application of a trapdoor would be for the authority to approve posting to mailing lists without incurring a cost. Dwork and Naor’s proposal consisted of three candidate puzzles meeting their properties, and it kicked off a entire research field, to which wij’ll terugwedstrijd.

Hashcash

A very similar idea called hashcash wasgoed independently invented ter 1997 by Adam Back, a postdoctoral researcher at the time who wasgoed part of the cypherpunk community. Cypherpunks were activists who opposed the power of governments and centralized institutions, and sought to create social and political switch through cryptography. Back wasgoed practically oriented: he released hashcash very first spil software, Two and five years straks ter 2002 released an Internet draft (a standardization document) and a paper. Four

Hashcash is much simpler than Dwork and Naor’s idea: it has no trapdoor and no central authority, and it uses only hash functions instead of digital signatures. It is based on a elementary principle: a hash function behaves spil a random function for some practical purposes, which means that the only way to find an input that hashes to a particular output is to attempt various inputs until one produces the desired output. Further, the only way to find an input that hashes into an arbitrary set of outputs is again to attempt hashing different inputs one by one. So, if I challenged you to find an input whose (binary) hash value embarks with Ten zeros, you would have to attempt numerous inputs, and you would find that each output had a 1/Two Ten chance of beginning with Ten zeros, which means that you would have to attempt on the order of Two Ten inputs, or approximately 1,000 hash computations.

Spil the name suggests, ter hashcash Back viewed proof of work spil a form of metselspecie. On his web pagina he placed it spil an alternative to David Chaum’s DigiCash, which wasgoed a system that issued untraceable digital contant from a bankgebouw to a user. Three He even made compromises to the technical vormgeving to make it emerge more cashlike. Zometeen, Back made comments suggesting that bitcoin wasgoed a straightforward extension of hashcash. Hashcash is simply not specie, however, because it has no protection against dual spending. Hashcash tokens cannot be exchanged among peers.

Meantime, ter the academic toneel, researchers found many applications for proof of work besides spam, such spil preventing denial-of-service attacks, 25 ensuring the integrity of web analytics, 17 and rate-limiting password guessing online. 38 Incidentally, the term proof of work wasgoed coined only te 1999 te a paper by Markus Jakobsson and Ari Juels, which also includes a nice survey of the work up until that point. 24 It is worth noting that thesis researchers seem to have bot unaware of hashcash but independently began to converge on hash-based proof of work, which wasgoed introduced te papers by Eran Gabber et hoewel. Eighteen and by Juels and Brainard. 25 (Many of the terms used across this paragraph didn’t become standard terminology until long after the papers ter question were published.)

Proof of work and digital metselspecie: A catch-22

You may know that proof of work did not succeed ter its original application spil an anti-spam measure. One possible reason is the dramatic difference te the puzzle-solving speed of different devices. That means spammers will be able to make a petite investment te custom-built hardware to increase their spam rate by orders of magnitude. Te economics, the natural response to an asymmetry te the cost of production is trade&mdash,that is, a market for proof-of-work solutions. But this presents a catch-22, because that would require a working digital currency. Indeed, the lack of such a currency is a major part of the motivation for proof of work ter the very first place. One crude solution to this problem is to announce puzzle solutions to be metselspecie, spil hashcash attempts to do.

More samenhangend approaches to treating puzzle solutions spil contant are found ter two essays that preceded bitcoin, describing ideas called b-money 13 and bit gold 42 respectively. Thesis proposals offerande timestamping services that sign off on the creation (through proof of work) of money, and once money is created, they sign off on transfers. If disagreement about the ledger occurs among the servers or knots, however, there isn’t a clear way to resolve it. Letting the majority determine seems to be implicit ter both authors’ writings, but because of the Sybil problem, thesis mechanisms aren’t very secure, unless there is a gatekeeper who controls entry into the network or Sybil resistance is itself achieved with proof of work.

Putting it all together

Understanding all thesis predecessors that contain lumps of bitcoin’s vormgeving leads to an appreciation of the true genius of Nakamoto’s innovation. Te bitcoin, for the very first time, puzzle solutions don’t constitute contant by themselves. Instead, they are merely used to secure the ledger. Solving proof of work is performed by specialized entities called miners (albeit Nakamoto underestimated just how specialized mining would become).

Miners are permanently ter a wedloop with each other to find the next puzzle solution, each miner solves a slightly different variant of the puzzle so that the chance of success is proportional to the fraction of global mining power that the miner controls. A miner who solves a puzzle gets to contribute the next batch, or block, of transactions to the ledger, which is based on linked timestamping. Te exchange for the service of maintaining the ledger, a miner who contributes a block is rewarded with freshly minted units of the currency. With high likelihood, if a miner contributes an invalid transaction or block, it will be rejected by the majority of other miners who contribute the following blocks, and this will also invalidate the block prize for the bad block. Te this way, because of the monetary incentives, miners ensure each other’s compliance with the protocol.

Bitcoin neatly avoids the double-spending problem plaguing proof-of-work-as-cash schemes because it eschews puzzle solutions themselves having value. Te fact, puzzle solutions are twice decoupled from economic value: the amount of work required to produce a block is a floating parameter (proportional to the global mining power), and further, the number of bitcoins issued vanaf block is not immobilized either. The block prize (which is how fresh bitcoins are minted) is set to halve every four years (ter 2018, the prize is 12.Five bitcoins/block, down from 50 bitcoins/block). Bitcoin incorporates an extra prize scheme&mdash,namely, senders of transactions paying miners for the service of including the transaction te their blocks. It is expected that the market will determine transaction fees and miners’ prizes.

Nakamoto’s genius, then, wasn’t any of the individual components of bitcoin, but rather the intricate way ter which they getraind together to breathe life into the system. The timestamping and Byzantine agreement researchers didn’t kasstuk upon the idea of incentivizing knots to be fair, strafgevangenis, until 2005, of using proof of work to do away with identities. Conversely, the authors of hashcash, b-money, and bit gold didn’t incorporate the idea of a overeenstemming algorithm to prevent dual spending. Te bitcoin, a secure ledger is necessary to prevent dual spending and thus ensure that the currency has value. A valuable currency is necessary to prize miners. Ter turn, strength of mining power is necessary to secure the ledger. Without it, an adversary could amass more than 50 procent of the global mining power and thereby be able to generate blocks swifter than the surplus of the network, double-spend transactions, and effectively rewrite history, overrunning the system. Thus, bitcoin is bootstrapped, with a circular dependence among thesis three components. Nakamoto’s challenge wasgoed not just the vormgeving, but also coaxing the initial community of users and miners to take a leap together into the unknown&mdash,back when a pizza cost Ten,000 bitcoins and the network’s mining power wasgoed less than a trillionth of what it is today.

Public keys spil identities

This article began with the understanding that a secure ledger makes creating digital currency straightforward. Let’s revisit this optie. When Alice wishes to pay Bob, she broadcasts the transaction to all bitcoin knots. A transaction is simply a string: a statement encoding Alice’s wish to pay Bob some value, signed by hier. The eventual inclusion of this signed statement into the ledger by miners is what makes the transaction real. Note that this doesn’t require Bob’s participation ter any way. But let’s concentrate on what’s not ter the transaction: conspicuously absent are Alice and Bob’s identities, instead, the transaction contains only their respective public keys. This is an significant concept ter bitcoin: public keys are the only kinds of identities ter the system. Transactions transfer value from and to public keys, which are called addresses.

Ter order to ",speak for", an identity, you voorwaarde know the corresponding secret key. You can create a fresh identity at any time by generating a fresh key pair, with no central authority or registry. You don’t need to obtain a user name or inform others that you have picked a particular name. This is the notion of decentralized identity management. Bitcoin doesn’t specify how Alice tells Bob what hier pseudonym is&mdash,that is outer to the system.

Albeit radically different from most other payment systems today, thesis ideas are fairly old, dating back to David Chaum, the father of digital specie. Te fact, Chaum also made seminal contributions to anonymity networks, and it is te this setting that he invented this idea. Te his 1981 paper, ",Untraceable Electronic Mail, Terugwedstrijd Addresses, and Digital Pseudonyms,", 9 he states: ",A digital pseudonym’ is a public key used to verify signatures made by the anonymous holder of the corresponding private key.",

Now, having message recipients be known only by a public key presents an evident problem: there is no way to route the message to the right pc. This leads to a massive inefficiency ter Chaum’s proposal, which can be traded off against the level of anonymity but not eliminated. Bitcoin is similarly exceedingly inefficient compared with centralized payment systems: the ledger containing every transaction is maintained by every knot ter the system. Bitcoin incurs this inefficiency for security reasons anyway, and thus achieves pseudonymity (i.e, public keys spil identities) ",for free.", Chaum took thesis ideas much further te a 1985 paper, 11 where he presents a vision of privacy-preserving e-commerce based on pervasive pseudonyms, spil well spil ",vensterluik signatures,", the key technical idea behind his digital metselspecie.

The public-keys-as-identities idea is also seen ter b-money and bit gold, the two precursor essays to bitcoin discussed earlier. However, much of the work that built on Chaum’s foundation, spil well spil Chaum’s own straks work on ecash, moved away from this idea. The cypherpunks were keenly interested te privacy-preserving communication and commerce, and they embraced pseudonyms, which they called nyms. But to them, nyms weren’t mere cryptographic identities (i.e., public keys), but rather, usually email addresses that were linked to public keys. Similarly, Ian Goldberg’s dissertation, which became the ondergrond of much future work on anonymous communication, recognizes Chaum’s idea but suggests that nyms should be human-memorable nicknames with certificates to tie them. 20 Thus Bitcoin proved to be the most successful instantiation of Chaum’s idea.

The Blockchain

So far, this article has not addressed the blockchain, which, if you believe the hype, is bitcoin’s main invention. It might come spil a verrassing to you that Nakamoto doesn’t mention that term at all. Te fact, the term blockchain has no standard technical definition but is a liberate umbrella term used by various parties to refer to systems that bear varying levels of resemblance to bitcoin and its ledger.

Discussing example applications that benefit from a blockchain will help clarify the different uses of the term. Very first, consider a database backend for transactions among a consortium of banks, where transactions are netted at the end of each day and accounts are lodged by the central canap. Such a system has a petite number of well-identified parties, so Nakamoto overeenstemming would be overkill. An on-blockchain currency is not needed either, spil the accounts are denominated te traditional currency. Linked timestamping, on the other arm, would clearly be useful, at least to ensure a consistent global ordering of transactions ter the face of network latency. State replication would also be useful: a bankgebouw would know that its local copy of the gegevens is identical to what the central bankgebouw will use to lodge its account. This slijper banks from the expensive reconciliation process they vereiste presently perform.

2nd, consider an asset-management application such spil a registry of documents that tracks ownership of financial securities, or real estate, or any other asset. Using a blockchain would increase interoperability and decrease barriers to entry. Wij want a secure, global registry of documents, and ideally one that permits public participation. This is essentially what the timestamping services of the 1990s and 2000s sought to provide. Public blockchains suggest a particularly effective way to achieve this today (the gegevens itself may be stored off-chain, with only the metadata stored on-chain). Other applications also benefit from a timestamping or ",public bulletin houtvezelplaat", abstraction, most notably electronic voting.

Let’s build on the asset-management example. Suppose you want to execute trades of assets via the blockchain, and not merely record them there. This is possible if the asset is issued digitally on the blockchain itself, and if the blockchain supports brainy contracts. Ter this example, wise contracts solve the ",fair exchange", problem of ensuring that payment is made if and only if the asset is transferred. More generally, brainy contracts can encode ingewikkeld business logic, provided that all necessary input gegevens (assets, their prices, and so on) are represented on the blockchain.

This mapping of blockchain properties to applications permits us not only to appreciate their potential, but also to inject a much-needed dose of skepticism. Very first, many proposed applications of blockchains, especially te banking, don’t use Nakamoto overeenstemming. Rather, they use the ledger gegevens structure and Byzantine agreement, which, spil shown, date to the ’90s. This belies the voorkoop that blockchains are a fresh and revolutionary technology. Instead, the whirr around blockchains has helped banks initiate collective activity to deploy shared-ledger technology, like the parable of ",stone soup.", Bitcoin has also served spil a very visible proof of concept that the decentralized ledger works, and the Bitcoin Core project has provided a convenient code base that can be adapted spil necessary.

2nd, blockchains are frequently introduced spil more secure than traditional registries&mdash,a misleading voorkoop. To see why, the overall stability of the system or verhoging voorwaarde be separated from endpoint security&mdash,that is, the security of users and devices. True, the systemic risk of blockchains may be lower than that of many centralized institutions, but the endpoint-security risk of blockchains is far worse than the corresponding risk of traditional institutions. Blockchain transactions are near-instant, irreversible, and, te public blockchains, anonymous by vormgeving. With a blockchain-based stock registry, if a user (or broker or smeris) loses control of his or hier private keys&mdash,which takes nothing more than losing a phone or getting malware on a laptop&mdash,the user loses his or hier assets. The extreme history of bitcoin hacks, thefts, and scams doesn’t inspire much confidence&mdash,according to one estimate, at least six procent of bitcoins ter circulation have bot stolen at least once. 39

Concluding Lessons

The history described here offers rich (and complementary) lessons for practitioners and academics. Practitioners should be skeptical of claims of revolutionary technology. Spil shown here, most of the ideas ter bitcoin that have generated excitement ter the enterprise, such spil distributed ledgers and Byzantine agreement, actually date back 20 years or more. Recognize that your problem may not require any breakthroughs&mdash,there may be long-forgotten solutions ter research papers.

Academia seems to have the opposite problem, at least te this example: a resistance to radical, extrinsic ideas. The bitcoin white paper, despite the pedigree of many of its ideas, wasgoed more novel than most academic research. Moreover, Nakamoto didn’t care for academic peer review and didn’t fully connect it to its history. Spil a result, academics essentially overlooked bitcoin for several years. Many academic communities informally argued that Bitcoin couldn’t work, based on theoretical models or practices with past systems, despite the fact that it wasgoed working te practice.

Wij’ve seen repeatedly that ideas te the research literature can be little by little forgotten or lie unappreciated, especially if they are ahead of their time, even te popular areas of research. Both practitioners and academics would do well to revisit old ideas to glean insights for present systems. Bitcoin wasgoed unusual and successful not because it wasgoed on the cutting edge of research on any of its components, but because it combined old ideas from many previously unrelated fields. This is not effortless to do, spil it requires bridging disparate terminology, assumptions, etc., but it is a valuable blueprint for innovation.

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 impatient to fasten their own products to the bandwagon, difficulty identifying the problem that is being solved, and eventually, claims of technology solving social problems or creating economic/political upheaval.

Ter tegenstelling, 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 spil releasing code and working with practitioners are not adequately rewarded ter academia. Ter fact, the original branch of the academic proof-of-work literature resumes 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.

Sidebars

Sybil-resistant networks

Ter his paper on Sybil attacks, John Douceur proposed that all knots participating te a BFT protocol be required to solve hashcash puzzles. If a knot were masquerading spil N knots, it would be incapable to solve N puzzles te time, and the fake identities would be purged. A malicious knot, however, could still obtain a moderate advantage overheen an fair knot that claimed only a single identity. A follow-up paper te 2005 1 suggested that fair knots should instead mimic the behavior of malicious knots and eis spil many virtual identities spil they computationally can afford to voorkoop. With thesis virtual identities executing a BFT protocol, the assumption, ",At most a fraction f of knots are faulty", can be substituted with the assumption ",The fraction of total computational power managed by faulty knots is at most f.", Thus, it is no longer necessary to validate identities, and open peer-to-peer networks can run a BFT protocol. Bitcoin uses exactly this idea. But Nakamoto asks a further question: What motivates knots to perform computationally expensive proof of work? The response requires a further leap: digital currency.

Brainy contracts

A wise contract takes the idea of putting gegevens te a secure ledger and extends it to computation. Te other words, it is a overeenstemming protocol for the keurig execution of a publicly specified program. Users can invoke functions te thesis smart-contract programs, subject to any confinements specified by the program, and the function code is executed te tandem by the miners. Users can trust the output without having to redo the computation and can write their own programs to act on the output of other programs. Wise contracts are especially powerful when combined with a cryptocurrency verhoging, because the programs ter question can treat money&mdash,own it, transfer it, demolish it, and, ter some cases, even print it.

Bitcoin implements a limitary programming language for wise contracts. A ",standard", transaction (i.e., one that moves currency from one address to another) is specified spil a brief script te this language. Ethereum offers a more permissive and powerful language.

The idea of brainy contracts wasgoed proposed by Nick Szabo te 1994 41 and so named because he eyed them spil analogs of legal contracts, but with automated enforcement. (This view has bot critiqued by Karen Levy 31 and Ed Felten. 16 ) Presciently, Szabo introduced brainy contracts spil extensions of digital-cash protocols and recognized that Byzantine agreement and digital signatures (among others) could be used spil building blocks. The success of cryptocurrencies has made brainy contracts practical, and research on the topic has bloomed spil well. For example, programming languages researchers have adapted their methods and instruments to automatically detect bugs ter brainy contracts and to write verifiably onberispelijk ones.

Permissioned blockchains

While this article has emphasized that private or permissioned blockchains omit most of bitcoin’s innovations, this isn’t meant to diminish the interesting work happening ter this space. A permissioned blockchain places confinements on who can join the network, write transactions, or mine blocks. Ter particular, if miners are restricted to a list of trustworthy participants, the proof of work can be dropped te favor of a more traditional BFT treatment. Thus, much of the research is a rebirth of BFT that asks questions such spil: Can wij use hash trees to simplify overeenstemming algorithms? What if the network can fail only ter certain ways?

Further, there are significant considerations around identity and public-key infrastructure, access control, and confidentiality of the gegevens stored on the blockchain. Thesis issues largely don’t arise ter public blockchain settings, strafgevangenis are they studied ter the traditional BFT literature.

Ultimately, there is also the engineering work of scaling blockchains for high throughput and adapting them to various applications such spil supply-chain management and financial technology.

Acknowledgements

The authors are grateful to Adam Back, Andrew Miller, Edward Felten, Harry Kalodner, Ian Goldberg, Ian Grigg, Joseph Bonneau, Malte Mö,ser, Mike Just, Neha Narula, Steven Goldfeder, and Stuart Haber for valuable terugkoppeling on a draft.

References

1. Aspnes, J., et alhoewel. 2005. Exposing computationally challenged Byzantine imposters. Yale University Department of Pc Science, http://cs.yale.edu/publications/techreports/tr1332.pdf.

Two. Back, A. 1997. A partial hash collision based postage scheme, http://www.hashcash.org/papers/announce.txt.

Five. Bayer, D., Haber, S., Stornetta, W. S. Improving the efficiency and reliability of digital time-stamping. Proceedings of Sequences 1991, https://verbinding.springer.com/chapter/Ten.1007/978-1-4613-9323-8_24.

8. Castro, M., Liskov, B. 1999. Practical Byzantine fault tolerance. Proceedings of the Third Symposium on Operating Systems Vormgeving and Implementation, http://pmg.csail.mit.edu/papers/osdi99.pdf.

9. Chaum, D. 1981. Untraceable electronic mail, comeback addresses, and digital pseudonyms. Communications of the ACM 24(Two): 84-90, https://dl.acm.org/citation.cfm?id=358563.

Ten. Chaum, D. 1983. Vensterluik signatures for untraceable payments. Advances ter Cryptology: 199-203.

11. Chaum, D. 1985. Security without identification: transaction systems to make Big Brother obsolete. Communications of the ACM 28(Ten): 1030-1044, https://dl.acm.org/citation.cfm?id=4373.

12. Chaum, D., et hoewel. 1988. Untraceable electronic metselspecie. Advances ter Cryptology: 319-327, https://dl.acm.org/citation.cfm?id=88969.

15. Dwork, C., Naor, M. 1992. Pricing via processing or combatting junk mail, https://dl.acm.org/citation.cfm?id=705669.

17. Franklin, M. K., Malkhi, D. 1997. Auditable metering and lightweight security, http://www.hashcash.org/papers/auditable-metering.pdf.

Nineteen. Garay, J. A., et alreeds. 2015. The bitcoin backbone protocol: analysis and applications. Advances ter Cryptology: 281-310, https://eprint.iacr.org/2014/765.pdf.

20. Goldberg, I. 2000. A pseudonymous communications infrastructure for the Internet. Ph.D. dissertation, University of California Berkeley, http://moria.freehaven.netwerken/anonbib/cache/ian-thesis.pdf.

22. Haber, S., Stornetta, W. S. 1991. How to timestamp a digital document. Journal of Cryptology Three(Two): 99-111, https://verbinding.springer.com/chapter/Ten.1007/3-540-38424-3_32.

23. Haber, S., Stornetta, W. S. 1997. Secure names for bit-strings. Te Proceedings of the Four th ACM Conference on Rekentuig and Communications Security: 28-35, http://dl.acm.org/citation.cfm?id=266430.

24. Jakobsson, M., Juels, A. 1999. Proofs of work and bread vla protocols, http://www.hashcash.org/papers/bread-pudding.pdf.

25. Juels, A., Brainard, J. 1999. Client puzzles: a cryptographic countermeasure against connection completion attacks. Proceedings of Networks and Distributed Security Systems: 151-165, https://www.isoc.org/isoc/conferences/ndss/99/proceedings/papers/juels.pdf.

27. Lamport, L., et hoewel. 1982. The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems Four(Three): 382-401, https://dl.acm.org/citation.cfm?id=357176 .

31. Levy, K. E. C. 2018. Book-smart, not street-smart: blockchain-based wise contracts and the social workings of law. Engaging Science, Technology, and Society Three: 1-15, http://estsjournal.org/article/view/107.

32. Melara, M., et hoewel. 2015. CONIKS: bringing key transparency to end users. Proceedings of the 24 th Usenix Security Symposium, https://www.usenix.org/system/files/conference/usenixsecurity15/sec15-paper-melara.pdf.

33. Merkle, R. C. 1980. Protocols for public key cryptosystems. IEEE Symposium on Security and Privacy, http://www.merkle.com/papers/Protocols.pdf.

34. Nakamoto, S. 2008. Bitcoin: a peer-to-peer electronic metselspecie system, https://bitcoin.org/bitcoin.pdf.

36. Narayanan, A., et reeds. 2016. Bitcoin and Cryptocurrency Technologies: A Comprehensive Introduction. Princeton University Press, http://bitcoinbook.cs.princeton.edu/.

37. Pass, R., et reeds. 2018. Analysis of the blockchain protocol te asynchronous networks. Annual International Conference on the Theory and Applications of Cryptographic Technologies, https://verbinding.springer.com/chapter/Ten.1007/978-3-319-56614-6_22.

38. Pinkas, B., Sander, T. 2002. Securing passwords against dictionary attacks. Proceedings of the Ninth ACM Conference on Laptop and Communications Security: 161-170, https://dl.acm.org/citation.cfm?id=586133.

43. Wattenhofer, R. 2016. The Science of the Blockchain. Inverted Forest Publishing.

44. Rivest, R. L., Shamir, A. 1996. PayWord and MicroMint: Two ordinary micropayment schemes. International Workshop on Security Protocols.

Arvind Narayanan is an assistant professor of laptop science at Princeton. He leads the Princeton Web Transparency and Accountability Project to uncover how companies collect and use our private information. Narayanan also leads a research team investigating the security, anonymity, and stability of cryptocurrencies, spil well spil novel applications of blockchains. He co-created a massive open online course, and a textbook on bitcoin and cryptocurrency technologies. His doctoral research displayed the fundamental thresholds of de-identification, for which he received the Privacy Enhancing Technologies Award. Narayanan is an affiliated faculty member at the Center for Information Technology Policy at Princeton and an affiliate scholar at Stanford Law Schoolgebouw’s Center for Internet and Society. You can go after him on Twitter at @random_walker.

Jeremy Clark is an assistant professor at the Concordia Institute for Information Systems Engineering. He obtained his Ph.D. from the University of Waterloo, where his gold medal dissertation wasgoed on designing and deploying secure voting systems, including Scantegrity&mdash,the very first cryptographically verifiable system used ter a public-sector election. He wrote one of the earliest academic papers on bitcoin, ended several research projects te the area, and contributed to the very first textbook. Beyond research, he has worked with several municipalities on voting technology and testified to the Canadian Senate on bitcoin. You can go after him on Twitter at @PulpSpy.

Copyright ©, 2018 held by possessor/author. Publication rights licensed to ACM.

Related movie: 8 Card Vertical GPU Mining Equipment Cradle Framework Build


Leave a Reply

Your email address will not be published. Required fields are marked *