第1页 / 共18页
第2页 / 共18页
第3页 / 共18页
第4页 / 共18页
第5页 / 共18页
第6页 / 共18页
第7页 / 共18页
第8页 / 共18页
Algorand算法: Scaling Byzantine Agreements for Cryptocurrencies.pdf
Algorand: Scaling Byzantine Agreements
for Cryptocurrencies
Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, Nickolai Zeldovich
MIT CSAIL
ABSTRACT
Algorand is a new cryptocurrency that confirms transactions
with latency on the order of a minute while scaling to many
users. Algorand ensures that users never have divergent
views of confirmed transactions, even if some of the users
are malicious and the network is temporarily partitioned.
In contrast, existing cryptocurrencies allow for temporary
forks and therefore require a long time, on the order of an
hour, to confirm transactions with high confidence.
Algorand uses a new Byzantine Agreement (BA) protocol
to reach consensus among users on the next set of trans-
actions. To scale the consensus to many users, Algorand
uses a novel mechanism based on Verifiable Random Func-
tions that allows users to privately check whether they are
selected to participate in the BA to agree on the next set
of transactions, and to include a proof of their selection in
their network messages. In Algorand’s BA protocol, users
do not keep any private state except for their private keys,
which allows Algorand to replace participants immediately
after they send a message. This mitigates targeted attacks
on chosen participants after their identity is revealed.
We implement Algorand and evaluate its performance on
1,000 EC2 virtual machines, simulating up to 500,000 users.
Experimental results show that Algorand confirms transac-
tions in under a minute, achieves 125× Bitcoin’s throughput,
and incurs almost no penalty for scaling to more users.
1 INTRODUCTION
Cryptographic currencies such as Bitcoin can enable new
applications, such as smart contracts [24, 50] and fair pro-
tocols [2], can simplify currency conversions [12], and can
avoid trusted centralized authorities that regulate transac-
tions. However, current proposals suffer from a trade-off
between latency and confidence in a transaction. For exam-
ple, achieving a high confidence that a transaction has been
Permission to make digital or hard copies of part or all of this work for
personal or classroom use is granted without fee provided that copies
are not made or distributed for profit or commercial advantage and that
copies bear this notice and the full citation on the first page. Copyrights for
third-party components of this work must be honored. For all other uses,
contact the owner/author(s).
SOSP’17, October 28–31, 2017, Shanghai, China.
© 2017 Copyright is held by the owner/author(s).
ACM ISBN 978-1-4503-5085-3/17/10.
https://doi.org/10.1145/3132747.3132757
1
confirmed in Bitcoin requires about an hour long wait [7].
On the other hand, applications that require low latency
cannot be certain that their transaction will be confirmed,
and must trust the payer to not double-spend [46].
Double-spending is the core problem faced by any cryp-
tocurrency, where an adversary holding $1 gives his $1 to two
different users. Cryptocurrencies prevent double-spending
by reaching consensus on an ordered log (“blockchain”) of
transactions. Reaching consensus is difficult because of the
open setting: since anyone can participate, an adversary can
create an arbitrary number of pseudonyms (“Sybils”) [21],
making it infeasible to rely on traditional consensus proto-
cols [15] that require a fraction of honest users.
Bitcoin [42] and other cryptocurrencies [23, 54] address
this problem using proof-of-work (PoW), where users must
repeatedly compute hashes to grow the blockchain, and
the longest chain is considered authoritative. PoW ensures
that an adversary does not gain any advantage by creating
pseudonyms. However, PoW allows the possibility of forks,
where two different blockchains have the same length, and
neither one supersedes the other. Mitigating forks requires
two unfortunate sacrifices: the time to grow the chain by one
block must be reasonably high (e.g., 10 minutes in Bitcoin),
and applications must wait for several blocks in order to
ensure their transaction remains on the authoritative chain
(6 blocks are recommended in Bitcoin [7]). The result is that
it takes about an hour to confirm a transaction in Bitcoin.
This paper presents Algorand, a new cryptocurrency de-
signed to confirm transactions on the order of one minute.
The core of Algorand uses a Byzantine agreement protocol
called BA⋆ that scales to many users, which allows Algo-
rand to reach consensus on a new block with low latency and
without the possibility of forks. A key technique that makes
BA⋆ suitable for Algorand is the use of verifiable random
functions (VRFs) [39] to randomly select users in a private
and non-interactive way. BA⋆ was previously presented at a
workshop at a high level [38], and a technical report by Chen
and Micali [16] described an earlier version of Algorand.
Algorand faces three challenges. First, Algorand must
avoid Sybil attacks, where an adversary creates many
pseudonyms to influence the Byzantine agreement protocol.
Second, BA⋆ must scale to millions of users, which is far
higher than the scale at which state-of-the-art Byzantine
agreement protocols operate. Finally, Algorand must be re-
silient to denial-of-service attacks, and continue to operate
even if an adversary disconnects some of the users [30, 52].
Algorand addresses these challenges using several tech-
niques, as follows.
Weighted users. To prevent Sybil attacks, Algorand as-
signs a weight to each user. BA⋆ is designed to guarantee
consensus as long as a weighted fraction (a constant greater
than 2/3) of the users are honest. In Algorand, we weigh
users based on the money in their account. Thus, as long as
more than some fraction (over 2/3) of the money is owned by
honest users, Algorand can avoid forks and double-spending.
Consensus by committee. BA⋆ achieves scalability by
choosing a committee—a small set of representatives ran-
domly selected from the total set of users—to run each step
of its protocol. All other users observe the protocol mes-
sages, which allows them to learn the agreed-upon block.
BA⋆ chooses committee members randomly among all users
based on the users’ weights. This allows Algorand to ensure
that a sufficient fraction of committee members are honest.
However, relying on a committee creates the possibility of
targeted attacks against the chosen committee members.
Cryptographic sortition. To prevent an adversary from
targeting committee members, BA⋆ selects committee mem-
bers in a private and non-interactive way. This means that
every user in the system can independently determine if they
are chosen to be on the committee, by computing a func-
tion (a VRF [39]) of their private key and public information
from the blockchain. If the function indicates that the user
is chosen, it returns a short string that proves this user’s
committee membership to other users, which the user can
include in his network messages. Since membership selec-
tion is non-interactive, an adversary does not know which
user to target until that user starts participating in BA⋆.
Participant replacement. Finally, an adversary may tar-
get a committee member once that member sends a message
in BA⋆. BA⋆ mitigates this attack by requiring committee
members to speak just once. Thus, once a committee member
sends his message (exposing his identity to an adversary),
the committee member becomes irrelevant to BA⋆. BA⋆
achieves this property by avoiding any private state (except
for the user’s private key), which makes all users equally
capable of participating, and by electing new committee
members for each step of the Byzantine agreement protocol.
We implement a prototype of Algorand and BA⋆, and use
it to empirically evaluate Algorand’s performance. Experi-
mental results running on 1,000 Amazon EC2 VMs demon-
strate that Algorand can confirm a 1 MByte block of transac-
tions in ∼22 seconds with 50,000 users, that Algorand’s la-
tency remains nearly constant when scaling to half a million
users, that Algorand achieves 125× the transaction through-
put of Bitcoin, and that Algorand achieves acceptable latency
even in the presence of actively malicious users.
2 RELATED WORK
Proof-of-work. Bitcoin [42], the predominant cryptocur-
rency, uses proof-of-work to ensure that everyone agrees
on the set of approved transactions; this approach is of-
ten called “Nakamoto consensus.” Bitcoin must balance the
length of time to compute a new block with the possibil-
ity of wasted work [42], and sets parameters to generate a
new block every 10 minutes on average. Nonetheless, due
to the possibility of forks, it is widely suggested that users
wait for the blockchain to grow by at least six blocks be-
fore considering their transaction to be confirmed [7]. This
means transactions in Bitcoin take on the order of an hour
to be confirmed. Many follow-on cryptocurrencies adopt
Bitcoin’s proof-of-work approach and inherit its limitations.
The possibility of forks also makes it difficult for new users
to bootstrap securely: an adversary that isolates the user’s
network can convince the user to use a particular fork of the
blockchain [29].
By relying on Byzantine agreement, Algorand eliminates
the possibility of forks, and avoids the need to reason about
mining strategies [8, 25, 47]. As a result, transactions are
confirmed on the order of a minute. To make the Byzan-
tine agreement robust to Sybil attacks, Algorand associates
weights with users according to the money they hold. Other
techniques have been proposed in the past to resist Sybil
attacks in Byzantine-agreement-based cryptocurrencies, in-
cluding having participants submit security deposits and
punishing those who deviate from the protocol [13].
Byzantine consensus. Byzantine agreement protocols
have been used to replicate a service across a small group
of servers, such as in PBFT [15]. Follow-on work has shown
how to make Byzantine fault tolerance perform well and
scale to dozens of servers [1, 17, 34]. One downside of Byzan-
tine fault tolerance protocols used in this setting is that they
require a fixed set of servers to be determined ahead of time;
allowing anyone to join the set of servers would open up the
protocols to Sybil attacks. These protocols also do not scale
to the large number of users targeted by Algorand. BA⋆ is a
Byzantine consensus protocol that does not rely on a fixed
set of servers, which avoids the possibility of targeted attacks
on well-known servers. By weighing users according to their
currency balance, BA⋆ allows users to join the cryptocur-
rency without risking Sybil attacks, as long as the fraction of
the money held by honest users is at least a constant greater
than 2/3. BA⋆’s design also allows it to scale to many users
(e.g., 500,000 shown in our evaluation) using VRFs to fairly
select a random committee.
Most Byzantine consensus protocols require more than
2/3 of servers to be honest, and Algorand’s BA⋆ inherits
this limitation (in the form of 2/3 of the money being held
by honest users). BFT2F [36] shows that it is possible to
achieve “fork∗-consensus” with just over half of the servers
being honest, but fork∗-consensus would allow an adver-
sary to double-spend on the two forked blockchains, which
Algorand avoids.
2
Honey Badger [40] demonstrated how Byzantine fault tol-
erance can be used to build a cryptocurrency. Specifically,
Honey Badger designates a set of servers to be in charge
of reaching consensus on the set of approved transactions.
This allows Honey Badger to reach consensus within 5 min-
utes and achieve a throughput of 200 KBytes/sec of data
appended to the ledger using 10 MByte blocks and 104 par-
ticipating servers. One downside of this design is that the
cryptocurrency is no longer decentralized; there are a fixed
set of servers chosen when the system is first configured.
Fixed servers are also problematic in terms of targeted at-
tacks that either compromise the servers or disconnect them
from the network. Algorand achieves better performance
(confirming transactions in about a minute, reaching similar
throughput) without having to choose a fixed set of servers
ahead of time.
Stellar [37] takes an alternative approach to using Byzan-
tine consensus in a cryptocurrency, where each user can trust
quorums of other users, forming a trust hierarchy. Consis-
tency is ensured as long as all transactions share at least one
transitively trusted quorum of users, and sufficiently many
of these users are honest. Algorand avoids this assumption,
which means that users do not have to make complex trust
decisions when configuring their client software.
Proof of stake. Algorand assigns weights to users propor-
tionally to the monetary value they have in the system, in-
spired by proof-of-stake approaches, suggested as an alter-
native or enhancement to proof-of-work [3, 10]. There is a
Bitcoin-NG [26] suggests using the Nakamoto consensus
to elect a leader, and then have that leader publish blocks
of transactions, resulting in an order of magnitude of im-
provement in latency of confirming transactions over Bitcoin.
Hybrid consensus [31, 33, 43] refines the approach of using
the Nakamoto consensus to periodically select a group of
participants (e.g., every day), and runs a Byzantine agree-
ment between selected participants to confirm transactions
until new servers are selected. This allows improving perfor-
mance over standard Nakamoto consensus (e.g., Bitcoin); for
example, ByzCoin [33] provides a latency of about 35 sec-
onds and a throughput of 230 KBytes/sec of data appended to
the ledger with an 8 MByte block size and 1000 participants
in the Byzantine agreement. Although Hybrid consensus
makes the set of Byzantine servers dynamic, it opens up the
possibility of forks, due to the use of proof-of-work consen-
sus to agree on the set of servers; this problem cannot arise
in Algorand.
Pass and Shi’s paper [43] acknowledges that the Hybrid
consensus design is secure only with respect to a “mildly
adaptive” adversary that cannot compromise the selected
servers within a day (the participant selection interval), and
explicitly calls out the open problem of handling fully adap-
tive adversaries. Algorand’s BA⋆ explicitly addresses this
open problem by immediately replacing any chosen com-
mittee members. As a result, Algorand is not susceptible to
either targeted compromises or targeted DoS attacks.
key difference, however, between Algorand using monetary
value as weights and many proof-of-stake cryptocurrencies.
In many proof-of-stake cryptocurrencies, a malicious leader
(who assembles a new block) can create a fork in the network,
but if caught (e.g., since two versions of the new block are
signed with his key), the leader loses his money. The weights
in Algorand, however, are only to ensure that the attacker
cannot amplify his power by using pseudonyms; as long as
the attacker controls less than 1/3 of the monetary value,
Algorand can guarantee that the probability for forks is neg-
ligible. Algorand may be extended to “detect and punish”
malicious users, but this is not required to prevent forks or
double spending.
Proof-of-stake avoids the computational overhead of
proof-of-work and therefore allows reducing transaction con-
firmation time. However, realizing proof-of-stake in practice
is challenging [4]. Since no work is involved in generating
blocks, a malicious leader can announce one block, and then
present some other block to isolated users. Attackers may
also split their credits among several “users”, who might
get selected as leaders, to minimize the penalty when a bad
leader is caught. Therefore some proof-of-stake cryptocur-
rencies require a master key to periodically sign the correct
branch of the ledger in order to mitigate forks [32]. This
raises significant trust concerns regarding the currency, and
has also caused accidental forks in the past [44]. Algorand
answers this challenge by avoiding forks, even if the leader
turns out to be malicious.
Ouroboros [31] is a recent proposal for realizing proof-of-
stake. For security, Ouroboros assumes that honest users can
communicate within some bounded delay (i.e., a strongly
synchronous network). Furthermore, it selects some users
to participate in a joint-coin-flipping protocol and assumes
that most of them are incorruptible by the adversary for
a significant epoch (such as a day). In contrast Algorand
assumes that the adversary may temporarily fully control the
network and immediately corrupt users in targeted attacks.
Trees and DAGs instead of chains. GHOST [48], SPEC-
TRE [49], and Meshcash [5] are recent proposals for increas-
ing Bitcoin’s throughput by replacing the underlying chain-
structured ledger with a tree or directed acyclic graph (DAG)
structures, and resolving conflicts in the forks of these data
structures. These protocols rely on the Nakamoto consensus
using proof-of-work. By carefully designing the selection
rule between branches of the trees/DAGs, they are able to
substantially increase the throughput. In contrast, Algorand
is focused on eliminating forks; in future work, it may be
interesting to explore whether tree or DAG structures can
similarly increase Algorand’s throughput.
3 GOALS AND ASSUMPTIONS
Algorand allows users to agree on an ordered log of transac-
tions, and achieves two goals with respect to the log:
Safety goal. With overwhelming probability, all users
agree on the same transactions. More precisely, if one honest
3
user accepts transaction A (i.e., it appears in the log), then
any future transactions accepted by other honest users will
appear in a log that already contains A. This holds even for
isolated users that are disconnected from the network—e.g.,
by Eclipse attacks [29].
Liveness goal. In addition to safety, Algorand also makes
progress (i.e., allows new transactions to be added to the log)
under additional assumptions about network reachability
that we describe below. Algorand aims to reach consensus
on a new set of transactions within roughly one minute.
Assumptions. Algorand makes standard cryptographic
assumptions such as public-key signatures and hash func-
tions. Algorand assumes that honest users run bug-free
software. As mentioned earlier, Algorand assumes that the
fraction of money held by honest users is above some thresh-
old h (a constant greater than 2/3), but that an adversary can
participate in Algorand and own some money. We believe
that this assumption is reasonable, since it means that in
order to successfully attack Algorand, the attacker must in-
vest substantial financial resources in it. Algorand assumes
that an adversary can corrupt targeted users, but that an
adversary cannot corrupt a large number of users that hold a
significant fraction of the money (i.e., the amount of money
held by honest, non-compromised users must remain over
the threshold).
To achieve liveness, Algorand makes a “strong synchrony”
assumption that most honest users (e.g., 95%) can send mes-
sages that will be received by most other honest users (e.g.,
95%) within a known time bound. This assumption allows
the adversary to control the network of a few honest users,
but does not allow the adversary to manipulate the network
at a large scale, and does not allow network partitions.
Algorand achieves safety with a “weak synchrony” as-
sumption: the network can be asynchronous (i.e., entirely
controlled by the adversary) for a long but bounded period
of time (e.g., at most 1 day or 1 week). After an asynchrony
period, the network must be strongly synchronous for a rea-
sonably long period again (e.g., a few hours or a day) for
Algorand to ensure safety. More formally, the weak syn-
chrony assumption is that in every period of length b (think
of b as a day or a week), there must be a strongly synchronous
period of length s < b (an s of a few hours suffices).
Finally, Algorand assumes loosely synchronized clocks
across all users (e.g., using NTP) in order to recover liveness
after weak synchrony. Specifically, the clocks must be close
enough in order for most honest users to kick off the recovery
protocol at approximately the same time. If the clocks are
out of sync, the recovery protocol does not succeed.
4 OVERVIEW
Algorand requires each user to have a public key. Algorand
maintains a log of transactions, called a blockchain. Each
transaction is a payment signed by one user’s public key
transferring money to another user’s public key. Algorand
grows the blockchain in asynchronous rounds, similar to
4
Bitcoin. In every round, a new block, containing a set of
transactions and a pointer to the previous block, is appended
to the blockchain. In the rest of this paper, we refer to Algo-
rand software running on a user’s computer as that user.
Algorand users communicate through a gossip protocol.
The gossip protocol is used by users to submit new transac-
tions. Each user collects a block of pending transactions that
they hear about, in case they are chosen to propose the next
block, as shown in Figure 1. Algorand uses BA⋆ to reach
consensus on one of these pending blocks.
BA⋆ executes in steps, communicates over the same gos-
sip protocol, and produces a new agreed-upon block. BA⋆
can produce two kinds of consensus: final consensus and
tentative consensus.
If one user reaches final consensus,
this means that any other user that reaches final or tenta-
tive consensus in the same round must agree on the same
block value (regardless of whether the strong synchrony
assumption held). This ensures Algorand’s safety, since this
means that all future transactions will be chained to this
final block (and, transitively, to its predecessors). Thus, Al-
gorand confirms a transaction when the transaction’s block
(or any successor block) reaches final consensus. On the
other hand, tentative consensus means that other users may
have reached tentative consensus on a different block (as
long as no user reached final consensus). A user will con-
firm a transaction from a tentative block only if and when a
successor block reaches final consensus.
BA⋆ produces tentative consensus in two cases. First,
if the network is strongly synchronous, an adversary may,
with small probability, be able to cause BA⋆ to reach tenta-
tive consensus on a block. In this case, BA⋆ will not reach
consensus on two different blocks, but is simply unable to
confirm that the network was strongly synchronous. Algo-
rand will eventually (in a few rounds) reach final consensus
on a successor block, with overwhelming probability, and
thus confirm these earlier transactions.
The second case is that the network was only weakly
synchronous (i.e., it was entirely controlled by the adversary,
with an upper bound on how long the adversary can keep
control). In this case, BA⋆ can reach tentative consensus
on two different blocks, forming multiple forks. This can in
turn prevent BA⋆ from reaching consensus again, because
the users are split into different groups that disagree about
previous blocks. To recover liveness, Algorand periodically
invokes BA⋆to reach consensus on which fork should be used
going forward. Once the network regains strong synchrony,
this will allow Algorand to choose one of the forks, and then
reach final consensus on a subsequent block on that fork.
We now describe how Algorand’s components fit together.
Gossip protocol. Algorand implements a gossip network
(similar to Bitcoin) where each user selects a small random
set of peers to gossip messages to. To ensure messages cannot
be forged, every message is signed by the private key of its
original sender; other users check that the signature is valid
before relaying it. To avoid forwarding loops, users do not
Figure 1: An overview of transaction flow in Algorand.
relay the same message twice. Algorand implements gossip
over TCP and weighs peer selection based on how much
money they have, so as to mitigate pollution attacks.
Block proposal (§6). All Algorand users execute crypto-
graphic sortition to determine if they are selected to propose
a block in a given round. We describe sortition in §5, but at
a high level, sortition ensures that a small fraction of users
are selected at random, weighed by their account balance,
and provides each selected user with a priority, which can be
compared between users, and a proof of the chosen user’s
priority. Since sortition is random, there may be multiple
users selected to propose a block, and the priority deter-
mines which block everyone should adopt. Selected users
distribute their block of pending transactions through the
gossip protocol, together with their priority and proof. To
ensure that users converge on one block with high probabil-
ity, block proposals are prioritized based on the proposing
user’s priority, and users wait for a certain amount of time
to receive the block.
Agreement using BA⋆ (§7). Block proposal does not guar-
antee that all users received the same block, and Algorand
does not rely on the block proposal protocol for safety. To
reach consensus on a single block, Algorand uses BA⋆. Each
user initializes BA⋆ with the highest-priority block that they
received. BA⋆ executes in repeated steps, illustrated in Fig-
ure 2. Each step begins with sortition (§5), where all users
check whether they have been selected as committee mem-
bers in that step. Committee members then broadcast a
message which includes their proof of selection. These steps
repeat until, in some step of BA⋆, enough users in the com-
mittee reach consensus. (Steps are not synchronized across
users; each user checks for selection as soon as he observes
the previous step had ended.) As discussed earlier, an impor-
tant feature of BA⋆ is that committee members do not keep
private state except their private keys, and so can be replaced
after every step, to mitigate targeted attacks on them.
Efficiency. When the network is strongly synchronous,
BA⋆ guarantees that if all honest users start with the same
initial block (i.e., the highest priority block proposer was hon-
est), then BA⋆ establishes final consensus over that block
5
Figure 2: An overview of one step of BA⋆. To simplify
the figure, each user is shown twice: once at the top of the
diagram and once at the bottom. Each arrow color indicates
a message from a particular user.
W =
and terminates precisely in 4 interactive steps between users.
Under the same network conditions, and in the worst case of
a particularly lucky adversary, all honest users reach consen-
sus on the next block within expected 13 steps, as analyzed
in Appendix C of the technical report [27].
5 CRYPTOGRAPHIC SORTITION
Cryptographic sortition is an algorithm for choosing a ran-
dom subset of users according to per-user weights; that
is, given a set of weights wi and the weight of all users
i wi, the probability that user i is selected is propor-
tional to wi/W . The randomness in the sortition algorithm
comes from a publicly known random seed; we describe
later how this seed is chosen. To allow a user to prove that
they were chosen, sortition requires each user i to have a
public/private key pair, (pki ,ski).
Sortition is implemented using verifiable random func-
tions (VRFs) [39]. Informally, on any input string x, VRFsk(x)
returns two values: a hash and a proof. The hash is a hashlen-
bit-long value that is uniquely determined by sk and x, but
is indistinguishable from random to anyone that does not
know sk. The proof π enables anyone that knows pk to check
that the hash indeed corresponds to x, without having to
know sk. For security, we require that the VRF provides
these properties even if pk and sk are chosen by an attacker.
5.1 Selection procedure
Using VRFs, Algorand implements cryptographic sortition
as shown in Algorithm 1. Sortition requires a role parameter
that distinguishes the different roles that a user may be se-
lected for; for example, the user may be selected to propose
a block in some round, or they may be selected to be the
member of the committee at a certain step of BA⋆. Algorand
specifies a threshold τ that determines the expected number
of users selected for that role.
It is important that sortition selects users in proportion to
their weight; otherwise, sortition would not defend against
Sybil attacks. One subtle implication is that users may be
chosen more than once by sortition (e.g., because they have
a high weight). Sortition addresses this by returning the j
parameter, which indicates how many times the user was
procedure Sortition(sk,seed,τ ,role,w,W ):
⟨hash, π⟩ ← VRFsk(seed||role)
p ← τ
j ← 0
while hash
k =0 B(k;w,p),j+1
2hashlen j
k =0 B(k;w,p) do
W
j++
return ⟨hash, π , j⟩
Algorithm 1: The cryptographic sortition algorithm.
procedure VerifySort(pk,hash, π ,seed,τ ,role,w,W ):
if ¬VerifyVRFpk(hash, π ,seed||role) then return 0;
p ← τ
j ← 0
while hash
k =0 B(k;w,p) do
k =0 B(k;w,p),j+1
2hashlen j
W
j++
return j
Algorithm 2: Pseudocode for verifying sortition of a user
with public key pk.
k
chosen. Being chosen j times means that the user gets to
participate as j different “sub-users.”
To select users in proportion to their money, we consider
each unit of Algorand as a different “sub-user.” If user i
owns wi (integral) units of Algorand, then simulated user
(i, j) with j ∈ {1, . . . ,wi} represents the jth unit of currency
i owns, and is selected with probability p = τ
, where W is
W
the total amount of currency units in Algorand.
As shown in Algorithm 1, a user performs sortition by
computing ⟨hash, π⟩ ← V RFsk(seed||role), where sk is the
user’s secret key. The pseudo-random hash determines
how many sub-users are selected, as follows. The prob-
ability that exactly k out of the w (the user’s weight)
sub-users are selected follows the binomial distribution,
k =0 B(k;w,p) = 1. Since
B(k1;n1,p) + B(k2;n2,p) = B(k1 + k2;n1 + n2,p), splitting a
user’s weight (currency) among Sybils does not affect the
number of selected sub-users under his/her control.
pk(1−p)w−k, wherew
B(k;w,p) =w
j
k =0 B(k;w,p),j+1
k =0 B(k;w,p) for j ∈ {0,1, . . . ,w}.
To determine how many of a user’s w sub-users
are selected, the sortition algorithm divides the inter-
val [0,1) into consecutive intervals of the form I j =
If
hash/2hashlen (where hashlen is the bit-length of hash) falls in
the interval I j, then the user has exactly j selected sub-users.
The number of selected sub-users is publicly verifiable using
the proof π (from the VRF output).
Sortition provides two important properties. First, given a
random seed, the VRF outputs a pseudo-random hash value,
which is essentially uniformly distributed between 0 and
2hashlen − 1. As a result, users are selected at random based
on their weights. Second, an adversary that does not know
ski cannot guess how many times user i is chosen, or if i was
chosen at all (more precisely, the adversary cannot guess any
better than just by randomly guessing based on the weights).
The pseudocode for verifying a sortition proof, shown in
Algorithm 2, follows the same structure to check if that user
was selected (the weight of the user’s public key is obtained
from the ledger). The function returns the number of selected
sub-users (or zero if the user was not selected at all).
5.2 Choosing the seed
Sortition requires a seed that is chosen at random and pub-
licly known. For Algorand, each round requires a seed that
is publicly known by everyone for that round, but cannot be
controlled by the adversary; otherwise, an adversary may
be able to choose a seed that favors selection of corrupted
users.
In each round of Algorand a new seed is published. The
seed published at Algorand’s round r is determined using
VRFs with the seed of the previous round r −1. More specifi-
cally, during the block proposal stage of round r − 1, every
user u selected for block proposal also computes a proposed
seed for round r as ⟨seedr , π⟩ ← VRFsku(seedr−1||r). Algo-
rand requires that sku be chosen by u well in advance of the
seed for that round being determined (§5.3). This ensures that
even if u is malicious, the resulting seedr is pseudo-random.
This seed (and the corresponding VRF proof π) is included
in every proposed block, so that once Algorand reaches agree-
ment on the block for round r − 1, everyone knows seedr at
the start of round r. If the block does not contain a valid seed
(e.g., because the block was proposed by a malicious user
and included invalid transactions), users treat the entire pro-
posed block as if it were empty, and use a cryptographic hash
function H (which we assume is a random oracle) to com-
pute the associated seed for round r as seedr = H(seedr−1||r).
The value of seed0, which bootstraps seed selection, can be
chosen at random at the start of Algorand by the initial partic-
ipants (after their public keys are declared) using distributed
random number generation [14].
To limit the adversary’s ability to manipulate sortition,
and thus manipulate the selection of users for different com-
mittees, the selection seed (passed to Algorithm 1 and Algo-
rithm 2) is refreshed once every R rounds. Namely, at round r
Algorand calls the sortition functions with seedr−1−(r mod R).
5.3 Choosing sku well in advance of the seed
Computing seedr requires that every user’s secret key sku
is chosen well in advance of the selection seed used in
that round, i.e., seedr−1−(r mod R). When the network is not
strongly synchronous, the attacker has complete control over
the links, and can therefore drop block proposals and force
users to agree on empty blocks, such that future selection
seeds can be computed. To mitigate such attacks Algorand
relies on the weak synchrony assumption (in every period
of length b, there must be a strongly synchronous period of
length s < b). Whenever Algorand performs cryptographic
sortition for round r, it checks the timestamp included in
the agreed-upon block for round r − 1−(r mod R), and uses
the keys (and associated weights) from the last block that
was created b-time before block r −1−(r mod R). The lower
6
bound s on the length of a strongly synchronous period
should allow for sufficiently many blocks to be created in
order to ensure with overwhelming probability that at least
one block was honest. This ensures that, as long as s is suit-
ably large, an adversary u choosing a key sku cannot predict
the seed for round r.
This look-back period b has the following trade-off: a large
b mitigates the risk that attackers are able break the weak
synchronicity assumption, yet it increases the chance that
users have transferred their currency to someone else and
therefore have nothing to lose if the system’s security breaks.
This is colloquially known as the “nothing at stake” problem;
one possible way to avoid this trade-off, which we do not
explore in Algorand, is to take the minimum of a user’s
current balance and the user’s balance from the look-back
block as the user’s weight.
Appendix A of the technical report [27] formally analyzes
the number of blocks that Algorand needs to be created in the
period s when the network is strongly connected. We show
that to ensure a small probability of failure F, the number of
blocks is logarithmic in 1
, which allows us to obtain high
F
security with a reasonably low number of required blocks.
6 BLOCK PROPOSAL
To ensure that some block is proposed in each round, Al-
gorand sets the sortition threshold for the block-proposal
role, τproposer, to be greater than 1 (although Algorand will
reach consensus on at most one of these proposed blocks).
Appendix B of the technical report [27] proves that choosing
τproposer = 26 ensures that a reasonable number of proposers
(at least one, and no more than 70, as a plausible upper bound)
are chosen with very high probability (e.g., 1− 10−11).
Minimizing unnecessary block transmissions. One
risk of choosing several proposers is that each will gossip
their own proposed block. For a large block (say, 1 MByte),
this can incur a significant communication cost. To reduce
this cost, the sortition hash is used to prioritize block propos-
als: For each selected sub-user 1, . . . , j of user i, the priority
for the block proposal is obtained by hashing the (verifiably
random) hash output of VRF concatenated with the sub-user
index. The highest priority of all the block proposer’s se-
lected sub-users is the priority of the block.
Algorand users discard messages about blocks that do not
have the highest priority seen by that user so far. Algorand
also gossips two kinds of messages: one contains just the
priorities and proofs of the chosen block proposers (from
sortition), and the other contains the entire block, which also
includes the proposer’s sortition hash, and proof. The first
kind of message is small (about 200 Bytes), and propagates
quickly through the gossip network. These messages enable
most users to learn who is the highest priority proposer, and
thus quickly discard other proposed blocks.
Waiting for block proposals. Each user must wait a cer-
tain amount of time to receive block proposals via the gossip
7
protocol. Choosing this time interval does not impact Algo-
rand’s safety guarantees but is important for performance.
Waiting a short amount of time will mean no received pro-
posals. If the user receives no block proposals, he or she
initializes BA⋆ with the empty block, and if many users do
so, Algorand will reach consensus on an empty block. On the
other hand, waiting too long will receive all block proposals
but also unnecessarily increase the confirmation latency.
To determine the appropriate amount of time to wait for
block proposals, we consider the plausible scenarios that a
user might find themselves in. When a user starts waiting for
block proposals for round r, they may be one of the first users
to reach consensus in round r −1. Since that user completed
round r − 1, sufficiently many users sent a message for the
last step of BA⋆ in that round, and therefore, most of the
network is at most one step behind this user. Thus, the user
must somehow wait for others to finish the last step of BA⋆
from round r − 1. At this point, some proposer in round r
that happens to have the highest priority will gossip their
priority and proof message, and the user must somehow wait
to receive that message. Then, the user can simply wait until
they receive the block corresponding to the highest priority
proof (with a timeout λblock, on the order of a minute, after
which the user will fall back to the empty block).
It is impossible for a user to wait exactly the correct
amount for the first two steps of the above scenario. Thus,
Algorand estimates these quantities (λstepvar, the variance
in how long it takes different users to finish the last step
of BA⋆, and λpriority, the time taken to gossip the priority
and proof message), and waits for λstepvar + λpriority time
to identify the highest priority. §10 experimentally shows
that these parameters are, conservatively, 5 seconds each.
As mentioned above, Algorand would remain safe even if
these estimates were inaccurate.
Malicious proposers. Even if some block proposers are
malicious, the worst-case scenario is that they trick different
Algorand users into initializing BA⋆ with different blocks.
This could in turn cause Algorand to reach consensus on
an empty block, and possibly take additional steps in doing
so. However, it turns out that even this scenario is relatively
unlikely. In particular, if the adversary is not the highest pri-
ority proposer in a round, then the highest priority proposer
will gossip a consistent version of their block to all users.
If the adversary is the highest priority proposer in a round,
they can propose the empty block, and thus prevent any real
transactions from being confirmed. However, this happens
with probability of at most 1−h, by Algorand’s assumption
that at least h > 2/3 of the weighted user are honest.
7 BA⋆
The execution of BA⋆ consists of two phases. In the first
phase, BA⋆ reduces the problem of agreeing on a block to
agreement on one of two options. In the second phase, BA⋆
reaches agreement on one of these options: either agreeing
on a proposed block, or agreeing on an empty block.
Each phase consists of several interactive steps; the first
phase always takes two steps, and the second phase takes
two steps if the highest-priority block proposer was honest
(sent the same block to all users), and as we show in our
analysis an expected 11 steps in the worst case of a malicious
highest-priority proposer colluding with a large fraction of
committee participants at every step.
In each step, every committee member casts a vote for
some value, and all users count the votes. Users that receive
more than a threshold of votes for some value will vote
for that value in the next step (if selected as a committee
member). If the users do not receive enough votes for any
value, they time out, and their choice of vote for the next
step is determined by the step number.
In the common case, when the network is strongly syn-
chronous and the highest-priority block proposer was hon-
est, BA⋆ reaches final consensus by using its final step to
confirm that there cannot be any other agreed-upon block
in the same round. Otherwise, BA⋆ may declare tentative
consensus if it cannot confirm the absence of other blocks
due to possible network asynchrony.
A key aspect of BA⋆’s design is that it keeps no secrets,
except for user private keys. This allows any user observing
the messages to “passively participate” in the protocol: verify
signatures, count votes, and reach the agreement decision.
7.1 Main procedure of BA⋆
The top-level procedure implementing BA⋆, as invoked by
Algorand, is shown in Algorithm 3. The procedure takes a
context ctx, which captures the current state of the ledger, a
round number, and a new proposed block, from the highest-
priority block proposer (§6). Algorand is responsible for
ensuring that the block is valid (by checking the proposed
block’s contents and using an empty block if it is invalid,
as described in §8). The context consists of the seed for
sortition, the user weights, and the last agreed-upon block.
For efficiency, BA⋆ votes for hashes of blocks, instead of
entire block contents. At the end of the BA⋆ algorithm, we
use the BlockOfHash() function to indicate that, if BA⋆ has
not yet received the pre-image of the agreed-upon hash, it
must obtain it from other users (and, since the block was
agreed upon, many of the honest users must have received
it during block proposal).
The BA⋆ algorithm also determines whether it established
final or tentative consensus. We will discuss this check in
detail when we discuss Algorithm 8.
7.2 Voting
Sending votes (Algorithm 4). Algorithm 4 shows the
pseudocode for CommitteeVote(), which checks if the user
is selected for the committee in a given round and step of
BA⋆. The CommitteeVote() procedure invokes Sortition()
from Algorithm 1 to check if the user is chosen to partici-
pate in the committee. If the user is chosen for this step, the
user gossips a signed message containing the value passed to
CommitteeVote(), which is typically the hash of some block.
procedure BA⋆(ctx,round,block):
hblock ← Reduction(ctx,round,H(block))
hblock⋆ ← BinaryBA⋆(ctx,round,hblock)
// Check if we reached “final” or “tentative” consensus
r ← CountVotes(ctx,round,final,Tfinal,τfinal,λstep)
if hblock⋆ = r then
return ⟨final,BlockOfHash(hblock⋆)⟩
return ⟨tentative,BlockOfHash(hblock⋆)⟩
else
Algorithm 3: Running BA⋆ for the next round, with a
proposed block. H is a cryptographic hash function.
procedure CommitteeVote(ctx,round,step,τ ,value):
// check if user is in committee using Sortition (Alg. 1)
role ← ⟨“committee”,round,step⟩
⟨sorthash, π , j⟩ ← Sortition(user.sk,ctx.seed,τ ,role,
ctx.weight[user.pk],ctx.W )
// only committee members originate a message
if j > 0 then
Gossip(⟨user.pk,Signeduser.sk(round,step,
sorthash, π ,H(ctx.last_block),value)⟩)
Algorithm 4: Voting for value by committee members.
user.sk and user.pk are the user’s private and public keys.
To bind the vote to the context, the signed message includes
the hash of the previous block.
Counting votes (Algorithm 5 and Algorithm 6). The
CountVotes() procedure (Algorithm 5) reads messages that
belong to the current round and step from the incomingMsgs
buffer. (For simplicity, our pseudocode assumes that a back-
ground procedure takes incoming votes and stores them into
that buffer, indexed by the messages’ round and step.) It pro-
cesses the votes by calling the ProcessMsg() procedure for
every message (Algorithm 6), which ensures that the vote is
valid. Note that no private state is required to process these
messages.
ProcessMsg() returns not just the value contained in the
message, but also the number of votes associated with that
value. If the message was not from a chosen committee
member, ProcessMsg() returns zero votes. If the committee
member was chosen several times (see §5), the number of
votes returned by ProcessMsg() reflects that as well. Pro-
cessMsg() also returns the sortition hash, which we will use
later in Algorithm 9.
As soon as one value has more than T · τ votes,
CountVotes() returns that value. τ is the expected num-
ber of users that Sortition() selects for the committee, and is
the same for each step (τstep) with the exception of the final
step (τfinal). T is a fraction of that expected committee size
2
(T >
3) that defines BA⋆’s voting threshold; this is also the
same for every step except the final step, and we analyze it in
§7.5. If not enough messages were received within the allo-
cated λ time window, then CountVotes() produces timeout.
8
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
