Abstract—Bitcoin has emerged as the most successful crypto- graphic currency in history. Within two years of its quiet launch in 2009, Bitcoin grew to comprise billions of dollars of economic value despite only cursory analysis of the system’s design. Since then a growing literature has identified hidden-but-important properties of the system, discovered attacks, proposed promis- ing alternatives, and singled out difficult future challenges. Meanwhile a large and vibrant open-source community has proposed and deployed numerous modifications and extensions.
We provide the first systematic exposition Bitcoin and the many related cryptocurrencies or ‘altcoins.’ Drawing from a scattered body of knowledge, we identify three key components of Bitcoin’s design that can be decoupled. This enables a more insightful analysis of Bitcoin’s properties and future stability. We map the design space for numerous proposed modifica- tions, providing comparative analyses for alternative consensus mechanisms, currency allocation mechanisms, computational puzzles, and key management tools. We survey anonymity issues in Bitcoin and provide an evaluation framework for analyzing a variety of privacy-enhancing proposals. Finally we provide new insights on what we term disintermediation protocols, which absolve the need for trusted intermediaries in an interesting set of applications. We identify three general disintermediation strategies and provide a detailed comparison.
I. WHY BITCOIN IS WORTHY OF RESEARCH
Consider two opposing viewpoints on Bitcoin in straw- man form. The first is that “Bitcoin works in practice, but not in theory.” At times devoted members of the Bitcoin community espouse this philosophy and criticize the security research community for failing to discover Bitcoin, not im- mediately recognizing its novelty, and still today dismissing it due to the lack of a rigorous theoretical foundation.
Copyright By PowCoder代写 加微信 powcoder
A second viewpoint is that Bitcoin’s stability relies on an unknown combination of socioeconomic factors which is hopelessly intractable to model with sufficient precision, failing to yield a convincing argument for the system’s soundness. Given these difficulties, experienced security re- searchers may avoid Bitcoin as a topic of study, considering it prudent security engineering to only design systems with precise threat models that admit formal security proofs.
We intend to show where each of these simplistic view- points fail. To the first, we contend that while Bitcoin has worked surprisingly well in practice so far, there is an im- portant role for research to play in identifying precisely why this has been possible, moving beyond a blind acceptance of the informal arguments presented with the system’s initial
© 2015, . Under license to IEEE. DOI 10.1109/SP.2015.14
proposal. Furthermore, it is crucial to understand whether Bitcoin will still “work in practice” as practices change. We expect external political and economic factors to evolve, the system must change if and when transaction volume scales, and the nature of the monetary rewards for Bitcoin miners will change over time as part of the system design. It is not enough to argue that Bitcoin has worked from 2009– 2014 and will therefore continue likewise. We do not yet have sufficient understanding to conclude with confidence that Bitcoin will continue to work well in practice, which is a crucial research challenge that requires insight from computer science theory.
To the second viewpoint, we contend that Bitcoin is filling an important niche by providing a virtual currency system without any trusted parties and without pre-assumed identities among the participants. Within these constraints, the general problem of consensus in a distributed system is impossible [7], [93] without further assumptions like Bitcoin’s premise that rational (greedy) behavior can be modeled and incentives can be aligned to ensure secure operation of the consensus algorithm. Yet these constraints matter in practice, both philosophically and technically, and Bitcoin’s approach to consensus within this model is deeply surprising and a fundamental contribution. Bitcoin’s core consensus protocol also has profound implications for many other computer security problems beyond currency1 such as distributed naming, secure timestamping and commitment, generation of public randomness, as well as many finan- cial problems such as self-enforcing (“smart”) contracts, decentralized markets and order books, and distributed au- tonomous agents. In short, even though Bitcoin is not easy to model, it is worthy of considerable research attention as it may form the basis for practical solutions to exceedingly difficult and important problems.
With this dichotomy in mind, we set out to synthesize the collective knowledge from the first six years of Bitcoin’s operation and development, as well as from its many derived cryptocurrencies. Our goal is both to highlight the many areas where significant innovation has already occurred, ranging from novel payment protocols to user-friendly key management, and also highlight the most important open research challenges for Bitcoin and future cryptocurrencies.
1As we shall see, it may not be possible to remove the currency functionality and still have a working consensus system.
2015 IEEE Symposium on Security and Privacy
SoK: Research Perspectives and Challenges for Bitcoin and Cryptocurrencies
∗†‡, §, ¶, ∗, . Kroll∗, . Felten∗ ∗Princeton University, †Stanford University, ‡Electronic Frontier Foundation, §University of Maryland, ¶Concordia University
Authorized licensed use limited to: IEEE Xplore. Downloaded on February 28,2022 at 07:19:35 UTC from IEEE Xplore. Restrictions apply.
II. OVERVIEW OF BITCOIN
A. A Contextualized History
We refer the interested reader to existing surveys on the “first wave” of cryptocurrency research [15], [95]. In short, cryptographic currencies date back to Chaum’s proposal for “untraceable payments” in 1983 [28], a system involving bank-issued cash in the form of blindly signed coins. Un- blinded coins are transferred between users and merchants, and redeemable after the bank verifies they have not been previously redeemed. Blind signatures prevent the bank from linking users to coins, providing unlinkability akin to cash.
Throughout the 1990s, many variations and extensions of this scheme were proposed. Significant contributions include removing the need for the bank to be online at purchase time [29], allowing coins to be divided into smaller units [92] and improving efficiency [27]. Several startup companies including DigiCash [107] and Peppercoin [99] attempted to bring electronic cash protocols into practice but ultimately failed in the market. No schemes from this “first wave” of cryptocurrency research achieved significant deployment.
A key building block of Bitcoin, moderately hard “proof- of-work” puzzles, was proposed in the early 1990s for combating email spam [42] although it was never widely deployed for this purpose [71]. Many other applications followed, including proposals for a fair lottery [51], mint- ing coins for micropayments [100], and preventing vari- ous forms of denial-of-service and abuse in anonymous networks [10]. The latter, Hashcash, was an alternative to using digital micropayments (e.g., NetBill [110] and Karma [121]). Proof-of-work was also used to detect sybil nodes in distributed peer-to-peer consensus protocols [7], similar to its current use in Bitcoin consensus.
Another essential element of Bitcoin is the public ledger, which makes double-spending detectable. In auditable e- cash [105], [106], proposed in the late 1990s, the bank maintains a public database to detect double-spending and ensure the validity of coins, however the notion of publishing the entire set of valid coins was dismissed as impractical (only a Merkle root was published instead). B-money [36], proposed in 1998, appears to be the first system where all transactions are publicly (though anonymously) broadcast. Proposed on the Cypherpunks mailing list, b-money received minimal attention from the academic research community.
Smart contracts [114], proposed in the early 1990s, enable parties to formally specify a cryptographically enforceable agreement, portending Bitcoin’s scripting capabilities.
In 2008, Bitcoin was announced and a white paper penned under the pseudonym was posted to the Cypherpunks mailing list [90], followed quickly by the source code of the original reference client. Bitcoin’s genesis block was mined on or around January 3, 2009.2 The first
2Famously, the first block contains the string “The Times 03/Jan/2009 Chancellor on brink of second bailout for banks.”
use of Bitcoin as a currency is thought to be a transaction in May 2010, where one user ordered pizza delivery for another in exchange for 10,000 bitcoins. Since then, an increasing number of merchants and services have adopted Bitcoin and the price has generally risen, reaching a peak of approximately US$1200 per bitcoin in late 2013.
Bitcoin’s history has also been colored by its association with crime. The popular black market website Silk Road [30] operated from Feb. 2011 until Oct. 2013 when it was seized and shut down by the FBI. Botnets have found Bitcoin mining to be a supplemental source of income [57]. A current US federal court case involves a large Bitcoin- based Ponzi scheme [109]. In 2014, a computer virus called CryptoLocker extorted millions of dollars from victims by encrypting their files and demanding a Bitcoin ransom to release the decryption key [47]. Many users’ Bitcoins have been lost due to theft [41] and collapsed exchanges [86].
B. A Technical Overview
We present Bitcoin’s three main technical components: transactions (including scripts), the consensus protocol, and the communication network. Bitcoin is exceedingly complex—our goal is to present the system with sufficient technical depth that the literature on Bitcoin and be reviewed and evaluated in later sections of this paper. In particular, a key benefit of our three-component breakdown is that it makes evaluating and systematizing proposed changes (Sections VI & VIII) insightful by “decoupling” concepts that may be changed independently.
Sources of information on Bitcoin. Bitcoin can be difficult to define as there is no authoritative formal speci- fication. The original Bitcoin white paper [90] provides a good overview of Bitcoin’s design philosophy but many important technical details are omitted or outdated. The reference implementation bitcoind is considered a de facto specification, with further knowledge scattered across a series of “Bitcoin Improvement Proposals” (BIPs), forum postings, online wiki articles, the developer mailing list, and logged IRC discussions.3 We systematize these sources into a precise technical introduction, putting forward the components of the system we consider to be independent design decisions.
1) Transactions & Scripts: The state of the world in Bitcoin is represented by a series of messages called trans- actions. Among other possibilities, transactions are foremost published to transfer currency from one user to another. It is important to note that the large (and growing) list of transactions is the only state in Bitcoin. There is no built- in notion of higher-level concepts such as users, account
3Which can be found, respectively, at: https://github.com/bitcoin/bitcoin/ bips, https://bitcointalk.org/, https://bitcoin.it/,
Authorized licensed use limited to: IEEE Xplore. Downloaded on February 28,2022 at 07:19:35 UTC from IEEE Xplore. Restrictions apply.
sourceforge.net, #bitcoin- wizards
irc://freenode.net/#bitcoin- dev, and
irc://freenode.net/
balances or identities—these all exist only to the extent that they can be imputed from the list of published transactions. Transaction format. A transaction contains an array of inputs and an array of outputs. The entire transaction is hashed using SHA-2564 and this hash eventually5 serves as its globally unique transaction ID. Transactions are rep- resented using an ad hoc binary format; this is an early example of an important detail for which bitcoind is the
de facto specification.
Each output contains an integer value representing a
quantity of the Bitcoin currency. The precision of this value limits the extent to which units of the currency can be sub- divided; the smallest unit is called a satoshi. By convention, 108 satoshis is considered the primary unit of currency, called one “bitcoin”6 and denoted B, BTC or XBT.
Each output also has a short code snippet (in a special scripting language) called the scriptPubKey representing the conditions under which that transaction output can be redeemed, that is, included as an input in a later transaction.
Transaction scripts. Typically, the scriptPubKey specifies the hash of an ECDSA public key and a signature validation routine. This is called a “pay-to-pub-key-hash” transaction and the entire redeeming transaction must be signed using a key with the the specified hash. The vast majority of Bitcoin transactions are pay-to-pub-key-hash and the system is often described with this being the only possibility, although other transaction types are possible. The scripting language is an ad hoc, non-Turing-complete stack language with fewer than 200 commands called opcodes. They include support for cryptographic operations—e.g., hashing data and verifying signatures. Like the transaction format, the scripting lan- guage is only specified by its implementation in bitcoind.
Transaction inputs refer to previous transactions by their transaction hash and the index of the output within that transaction’s output array. They must also contain a code snippet which “redeems” that transaction output called the scriptSig. To successfully redeem a previous transaction, the scriptSig and scriptPubKey, must both execute successfully, one after the other, using the same stack. For pay-to-pub- key-hash transactions, the scriptSig is simply a complete public key (with the correct hash) and a signature.
Conservation of value. In addition to the requirements that each transaction input matches a previous transaction output and that the two scripts execute successfully, transac- tions are only valid if they satisfy the fundamental constraint that the sum of the values of all transaction outputs is less than or equal to the sum of the values of all inputs. We discuss the one exception in Section II-B2: coinbase
4In fact, whenever Bitcoin uses SHA-256, the hash function is actually applied twice. This could be denoted SHA-2562, but we omit this notation. 5Prior to publication in a block, a transaction’s hash is not a unique ID
due to transaction malleability [6].
6When capitalized “Bitcoin” refers to the entire system whereas lower-
case “bitcoin” refers to one unit of currency.
transactions used to create new units of currency.
From transactions to ownership. By themselves, this format of transaction implies several interesting properties. There is no inherent notion of identities or individual accounts which “own” bitcoins. Ownership simply means knowing a private key which is able to make a signature that redeems certain outputs—an individual owns as many bitcoins as they can redeem. Public key hashes, as specified in pay-to-pub-key-hash transactions, effectively function as pseudonymous identities within the system and are referred to as addresses. No real-world name or identifying informa-
tion are required.
Arguably, there is little that is deeply innovative about
Bitcoin’s transaction format. However, the use of a scripting language to specify redemption criteria and the realization that transactions can specify the entire state of the system are non-obvious design choices given prior cryptocurrency systems, both of which have been standard in essentially all subsequent designs. Some proposals extend the semantics of Bitcoin transactions (often by enhancing the scripting language) without changes to any other components.
2) Consensus and Mining: A transaction-based currency system would be insecure if transactions were sent directly between users to transfer funds. While the signatures would limit only the valid recipient of a previous transaction from referencing it in valid follow-up transactions, there is nothing in the transactions themselves to limit Alice from redeeming some transaction input twice in separate transactions sent to Bob and Carol, both of which would appear valid in isolation. Bitcoin takes a simple approach to solving this double spending attack: all transactions must be published in a global, permanent transaction log and any individual transaction output may only be redeemed in one subsequent transaction. Verifying a transaction now requires verifying the transaction’s scripts as well as ensuring that it is success- fully published to the log. In Bitcoin, the log is implemented as a series of blocks of transactions, each containing the hash of the previous block, committing this block as its sole antecedent. It is referred to as the blockchain.
Note that this design still requires global consensus on the contents of the blockchain. If Bob and Carol see two divergent blockchains, they will be vulnerable to double- spending attacks. One solution is to use a trusted central authority to collect transactions and publish them in signed blocks. However, this is undesirable as this authority might refuse to publish certain transactions (effectively freezing a user’s assets), might go offline completely, or might intentionally fork the blockchain to double-spend coins.
Nakamoto consensus. Bitcoin instead establishes consen- sus on the blockchain through a decentralized, pseudony- mous protocol dubbed Nakamoto consensus. This can be considered Bitcoin’s core innovation and perhaps the most crucial ingredient to its success. Any party can attempt to add to the chain by collecting a set of valid pending transac-
Authorized licensed use limited to: IEEE Xplore. Downloaded on February 28,2022 at 07:19:35 UTC from IEEE Xplore. Restrictions apply.
tions and forming them into a block. The core ingredient is the use of a challenging computational puzzle (usually given the slight misnomer proof of work7) to determine which party’s block will be considered the next block in the chain.
The process for choosing a new block is simple: the first announced valid block containing a solution to the computational puzzle is considered correct. Upon hearing of it, other participants are meant to begin working to find a followup block. If an announced block contains invalid transactions or is otherwise malformed, all other participants are meant to reject it and continue working until they have found a solution for a valid block. At any given time, the consensus blockchain is the “longest” version. Typically this is simply the branch with the most blocks, but because the mining difficulty can vary between long forks the longest chain must be defined as the one with the greatest expected difficulty to produce.8
It is also possible for two valid solutions to be found at approximately the same time (depending on network latency), which leads to a temporary fork during which there are two equal-length chains. Miners can choose either fork in this scenario. Due to the random nature of the computational puzzle, one blockchain will eventually be extended further than the other at which point all miners should adopt it.
While Bitcoin’s original specification provided only an in- formal argument that eventual consensus would emerge [90], followup work has proved that, assuming an effective and timely broadcast channel and that miners controlling a ma- jority of computational power follow the protocol faithfully, the protoc
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com