Theoretical Computer Science 777 (2019) 155–183
Contents lists available at ScienceDirect Theoretical Computer Science www.elsevier.com/locate/tcs
Algorand: A secure and efficient distributed ledger ✩ a,∗, b
a Computer Science Department, Stony Brook University, Stony Brook, NY 11794, USA b CSAIL, MIT, Cambridge, MA 02139, USA
Copyright By PowCoder代写 加微信 powcoder
article info
Article history:
Received 15 February 2018
Received in revised form 26 January 2019 Accepted 4 February 2019
Available online 7 February 2019
Public ledger
Blockchain
Byzantine agreement Distributed computation Cryptographic self-selection Permissionless system
1. Introduction
A distributed ledger is a tamperproof sequence of data that can be publicly accessed and augmented by everyone, without being maintained by a centralized party. Distributed ledgers stand to revolutionize the way a modern society operates. They can secure all kinds of traditional transactions, such as payments, asset transfers and titles, in the exact order in which the transactions occur; and enable totally new transactions, such as cryptocurrencies and smart contracts. They can remove intermediaries and usher in a new paradigm for trust. As currently implemented, however, distributed ledgers scale poorly and cannot achieve their enormous potential.
In this paper we propose Algorand, an alternative, secure and efficient distributed ledger. Algorand is permissionless and works in a highly asynchronous environment. Unlike prior implementations of distributed ledgers based on “proof of work,” Algorand dispenses with “miners” and requires only a negligible amount of computation. Moreover, its transaction history “forks” only with negligible probability: that is, Algorand guarantees the finality of a transaction the moment the transaction enters the ledger.
© 2019 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).
Money is becoming increasingly virtual. It has been estimated that about 80% of United States dollars today only exist as ledger entries [9]. In an ideal world, in which we could count on a universally trusted central entity, immune to all possible cyber attacks, money could be solely electronic. Unfortunately, we do not live in such a world. Accordingly, decentralized cryptocurrencies such as Bitcoin [36] and “smart contract” systems such as Ethereum [17] have been proposed. At the heart of these systems is a shared ledger that reliably records a sequence of transactions, as varied as payments and contracts, in a tamperproof way. The technology of choice to guarantee such tamperproofness is the blockchain. Blockchains are behind applications such as cryptocurrencies (most prominently, Bitcoin [36]), financial applications (e.g., [17]), and the Internet of Things (e.g., [42]). Several techniques to manage blockchain-based ledgers have been proposed: proof of work [36], proof of stake [41], practical Byzantine fault-tolerance [5], or some combinations of them.
✩ This paper is based on early versions of the arXiv paper by the second author [32], a paper itself based on [24]. Algorand’s technologies are the object of the following patent applications: US62/117,138 US62/120,916 US62/142,318 US62/218,817 US62/314,601 PCT/US2016/018300 US62/326,865 62/331,654 US62/333,340 US62/343,369 US62/344,667 US62/346,775 US62/351,011 US62/653,482 US62/352,195 US62/363,970 US62/369,447 US62/378,753 US62/383,299 US62/394,091 US62/400,361 US62/403,403 US62/410,721 US62/416,959 US62/422,883 US62/455,444 US62/458,746 US62/459,652 US62/460,928 US62/465,931.
* Corresponding author.
E-mail addresses: (J. Chen), (S. Micali).
https://doi.org/10.1016/j.tcs.2019.02.001
0304-3975/© 2019 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).
156 J. Chen, S. Micali / Theoretical Computer Science 777 (2019) 155–183
Currently, however, ledgers can be inefficient to manage. For example, Bitcoin’s proof-of-work approach (based on the original concept of [15]) requires a vast amount of computation, is wasteful and scales poorly. In addition, it de facto con- centrates power in few hands.
We therefore wish to put forward a new method to implement a distributed ledger that offers the convenience and efficiency of a centralized system run by a trusted and inviolable authority, without the inefficiencies and weaknesses of current decentralized implementations. We call our approach Algorand, because we crucially rely on algorithmic randomness for its efficiency.
For concreteness, in this paper we focus on Algorand as a payment system. Essentially, each user is identified with his public key. The system starts with an initial set of users, each owning a given amount of money. The initial status is assumed to be common knowledge. At any time, each public key can make a payment: that is, transfer all or part of the money it currently owns to another public key, by means of a digital signature. Roughly said, the goal of the system is to organize all payments into an ordered sequence of blocks, B1,B2,…, each containing a set of payments, so as to guarantee the following three properties in absence of any centralized authority: (P1) each block quickly becomes universally known; (P2) all payments in each block Br are valid, relative to the amount of money each payer owns according to the initial status and the payments in preceding blocks; and (P3) each valid payment quickly appears in a block.
Our model. In our system we assume the availability of a digital signature scheme secure in the sense of [23], such that each message has a unique valid signature (even when a public key is adversarially chosen); see [34] for an example. We also assume the availability of a random oracle [22]—or a hash function H modeled as a random oracle, as done in Bitcoin.
Our system is permissionless: any user can join at any time. The mechanism for a player to join Algorand is the same main mechanism for joining Bitcoin. Namely, a new user i joins the system when an already-existing user j makes a payment to i.1
The users have individual and asynchronous clocks, and all honest users’ clocks have the same speed. Colloquially,
“a minute is a minute for all of them.” Users communicate by propagating messages (i.e., via peer-to-peer gossiping) [11].2
We assume that each message m whose propagation is initiated by an honest user is received by (almost) all honest users
within a fixed amount of time that solely depends on m’s length.3 Specifically, as our system envisages only two classes
of messages—control messages which are several hundred bits long, and blocks which are (chosen to be) several mega-bytes
long, we let λ and be the time upper-bounds for the two classes, respectively. A similar communication model is consid-
ered by [37] for analyzing Bitcoin in asynchronous networks. Following [20], it is well known that consensus is impossible
to achieve in a totally asynchronous network by any deterministic protocol, where messages may arrive after arbitrarily
long delays, even with a fixed set of users and a single malicious user. Recently, [28] achieves consensus in the totally
asynchronous model with fixed users, with expected O(n3) communication and polynomial computation, when the number
of faulty users is less than n . 106
In this paper we consider a powerful but computationally bounded Adversary, which (1) instantaneously corrupts any user he wants, whenever he wants; (2) chooses the actions of all corrupted users; and (3) introduces new users into the system whenever he wants. At no time, however, can the corrupted users collectively own more than 1/3 of the total amount of money in the system. Also, the Adversary cannot forge signatures of honest users except with negligible probability. It is important to emphasize that the Adversary fully determines when each user receives a specific message, as long as it is within the corresponding time bound. Thus, messages may reach different users under different orders and at different times.
Algorand’s high-level structure. Algorand is an asynchronous distributed protocol organized in rounds. Conceptually, rounds are non-overlapping time intervals for a single user, but different users’ consecutive rounds may overlap due to asynchrony. Round r is devoted to construct the r-th block, Br. Each user i starts his own round r the moment he is sure about block Br−1.
At the highest level, round r starts by randomly selecting and publicizing (the identity of) a user, lr , the round leader. The leader constructs, digitally signs, and propagates a block B, which is his own candidate for the r-th block and includes a set of new and valid payments. Next, a small set of selected verifiers, S V r , referred to as the committee, is randomly chosen and publicized. The size of the committee is such that, with overwhelming probability it has at least a 2/3 honest majority. The committee reaches Byzantine agreement [40,19,13,30] on the block B proposed by lr . Upon termination, each honest verifier locally outputs his own block, whose hash value he digitally signs and propagates. Block Br is defined to be the block that has been signed by a given number of properly chosen verifiers. We now summarize the performance of our protocol.
1 Indeed, we focus on Algorand as a payment system. In principle, any user may join the system by publicizing his public key. However, a key with 0 balance cannot make payment to others or participate in block-building, thus we ignore their existence.
2 Essentially, when a message m is propagated, every user i receiving m for the first time randomly and independently selects a small number of active users, his “neighbors”, to whom he forwards m, possibly until he receives their acknowledgments. The propagation terminates when no user receives m for the first time.
3 Our protocol works if m is received by a sufficiently high fraction, say 95%, of the honest users, within a fixed amount of time. To simplify the discussions, we will not deal with this scenario in the analysis.
J. Chen, S. Micali / Theoretical Computer Science 777 (2019) 155–183 157 Theorem 1. (informally stated) The following properties hold with overwhelming probability for each round r ≥ 0:
• All honest users agree on the same block Br, and all payments in Br are valid.
• Let h > 2/3 be the fraction of money in the system collectively owned by honest users, and ph = h2(1 + h − h2). The leader lr is
honest with probability at least ph.
• When lr is honest, the block Br is generated by lr and round r takes at most 4λ + time.
• When lr is malicious, round r takes in expectation at most ( 12 + 8)λ + time. ph
• All honest users become sure about Br within time λ of each other.
Indeed, different from all other existing blockchains, Algorand essentially never “forks”. A user of Algorand can rely on a
new block Br as soon as his own round r terminates, and all honest users quickly learn about the agreement on Br.
Forthcoming work. In this paper we present and analyze Algorand under widely-adopted network assumptions for distributed ledgers, where messages propagated by honest users reach all honest users within a bounded amount of time. In a forth- coming paper, we strengthen our protocol by allowing the Adversary to arbitrarily partition the network for an arbitrarily long time. Essentially, for a large interval of time, the Adversary is allowed to complete control the delivery of messages: fully determining which message is delivered to which user and at what time, without any bounded time guarantee.
In other forthcoming papers we will also discuss quite different concerns, such as how to properly distribute initial money so as to accelerate the adoption of the system, and incentive mechanisms. Note that traditional cryptocurrencies require incentives. For example, in Bitcoin, since miners have to consume and pay for a lot of electricity, incentives are necessary to reimburse them for their large expenses. By contrast, in Algorand, the required amount of computation is trivial, thus there is little to reimburse. This said, it is possible to introduce incentives in Algorand. However, in line with Algorand’s mathematically rigorous approach, these incentives are engineered so as to be able to prove that they do not interfere with our stated liveness and soundness properties. (For instance, in the case of Bitcoin, the rise of mining pools can be attributed to a set of poorly engineered incentives.) It is thus to be expected that incentive engineering in Algorand is a separate project.
2. Main challenges and overview of algorand
Implementing the high-level structure of Algorand to achieve the desired properties of a blockchain requires meeting notable challenges. We now briefly discuss the challenges and our techniques.
From honest majority of users to honest majority of money. In Algorand a real person may own arbitrarily many public keys. To avoid Sybil attacks [14], each public key is selected to be a leader or a verifier with probability proportional to the amount of money owned by it. In particular, our protocol works under the honest-majority-of-money (HMM) assumption. To highlight our main techniques, however, we start by assuming that each user owns only one public key, and present the system in Sections 4 and 5 under the simpler honest-majority-of-user (HMU) assumption. In Section 6, we show how to modify our protocol to work under the HMM assumption.
Cryptographicself-selection. It is easy to randomly and publicly select lr and SVr from the set of users, based on r or H(Br−1). However, even though the latter is random, the identities of the selected users become public right away, and our powerful Adversary could immediately corrupt them before they could honestly take any action. In addition, since our system is permissionless, the Adversary could bring in any user i he wants, once he realizes that i will be lr or in SVr.
Instead, we introduce cryptographic self-selection. Assume for a moment that at the very beginning of round r, a quantity Q r is, by magic, randomly selected and made universally available. Then, each current user i is able to privately compute the (256-bit) string xri = H ( S I G i ( Q r )): that is, digitally sign Q r and then hash it. Note that xri is not only random, but also unique to i and r. This is because Q r is uniquely and publicly associated to r, and because the adopted signature scheme guarantees that at most one string can be i’s digital signature of Q r . The string xri is interpreted to be the binary expansion of a (256-bit) number between 0 and 1. If this number is less than a given threshold pv ∈(0,1), then i is a member of SVr and σir SIGi(Qr) is his committee credential. If xri is smaller than another threshold pl