Source-linked AI summary
Algorand
Jing Chen, Silvio Micali
TL;DR
Existing decentralized financial systems rely on shared ledgers but face inefficiencies and weaknesses. Algorand uses cryptographic sortition and message-passing Byzantine agreement to construct blocks, with transaction histories that fork only with very small probability.
Problem
Decentralized cryptocurrencies and smart-contract systems need shared ledgers, while current decentralized implementations have inefficiencies and weaknesses.
Method
Algorand uses cryptographic sortition to select verifiers and secretly selected leaders, who propose blocks certified through Byzantine agreement.
Results
One in a trillion, or even 10−18: Algorand’s transaction history may fork only with very small probability.
Takeaways & Limitations
Algorand aims to provide the convenience and efficiency of a trusted centralized system without the inefficiencies and weaknesses of current decentralized implementations.
Takeaways & Limitations
A remote possibility remains that a round exceeds µ steps, preventing a player from signing its message.
Abstract
from arXiv · showhide
A public ledger is a tamperproof sequence of data that can be read and augmented by everyone. Public ledgers have innumerable and compelling uses. They can secure, in plain sight, all kinds of transactions ---such as titles, sales, and payments--- in the exact order in which they occur. Public ledgers not only curb corruption, but also enable very sophisticated applications ---such as cryptocurrencies and smart contracts. They stand to revolutionize the way a democratic society operates. As currently implemented, however, they scale poorly and cannot achieve their potential. Algorand is a truly democratic and efficient way to implement a public ledger. Unlike prior implementations based on proof of work, it requires a negligible amount of computation, and generates a transaction history that will not "fork" with overwhelmingly high probability. Algorand is based on (a novel and super fast) message-passing Byzantine agreement. For concreteness, we shall describe Algorand only as a money platform.
1 Introduction
Algorand proposes a democratic public-ledger method designed to avoid proof-of-work inefficiency, power concentration, and blockchain forks. It combines fast Byzantine agreement with cryptographic selection and replaceable verifier sets.
- 1 Introduction: Algorand addresses proof-of-work ledgers’ computational inefficiency, poor scalability, and concentration of power.Bitcoin’s proof-of-work approach requires extraordinary computation, while ordinary users cannot profitably generate blocks.
- 1 Introduction: Algorand selects block verifiers algorithmically and unpredictably, keeping selection manipulation-resistant while distributing authority among users.Its approach uses cryptographic sortition and a seed Qr that is provably unpredictable and not influentiable by the adversary.
- 1.2 Algorand, in a Nutshell: A new block is generated in less than 10 minutes, while an experimentally tested embodiment generates blocks in less than 40 seconds.The first embodiment’s expected generation time is less than Λ + 12.4λ.
- 1 Introduction: Algorand’s blockchain forks only with negligible probability, allowing users to rely on payments in a new block immediately.The stated example gives a fork probability of less than one in a trillion.
- 1.2 Algorand, in a Nutshell: Algorand’s new message-passing Byzantine agreement protocol reaches agreement quickly and certifies each agreed block through verifier signatures.In a synchronous network with more than 2/3 honest players, BA⋆ ends in agreement with probability > 1/3 after each 3-step loop.
- 1.2 Algorand, in a Nutshell: Player-replaceable Byzantine agreement lets independently selected verifier sets execute successive protocol steps securely despite a dynamic adversary.With millions of users, each small set associated with one step most probably has empty intersection with the next.
2 Preliminaries
The preliminaries define the cryptographic primitives and idealized payment ledger underlying Algorand. They also contrast Algorand’s minimally computational, overwhelmingly likely fork-free blockchain with Bitcoin’s computationally intensive and frequently forking design.
- Digital signatures: Digital signatures let users authenticate messages using a secret signing key, while anyone can verify them with the corresponding public key.The scheme uses key generation, signing, and verification algorithms; signatures are assumed hard to forge.
- Digital signatures: Unique digital signatures prevent finding two distinct signatures that both verify for the same message and public key.This uniqueness property also applies to public-key strings that were not legitimately generated.
- Cryptographic hashing: Hashing a unique signature yields a unique randomly selected 256-bit string whose correctness can be publicly proved, providing an elementary verifiable-random-function construction.The paper models hashing as a random oracle and uses 256-bit outputs.
- The idealized public ledger: The idealized ledger associates money with public keys and represents each valid payment as a signed transfer between keys, with additional information that may include sensitive data.Sensitive information is hidden through its hash, while the payer can later reveal it for verification.
- Algorand versus Bitcoin: Bitcoin makes block generation computationally intensive and forks frequent, whereas Algorand uses minimal computation and makes each block safely final upon entry with overwhelmingly high probability.Algorand’s transaction history is designed not to fork with overwhelmingly high probability.
3 The BA Protocol BA⋆in a Traditional Setting
BA⋆ is introduced as an efficient Byzantine agreement protocol for synchronous complete networks, then adapted for Algorand’s communication model and player-replaceability requirements.
- BA is central to Algorand because it prevents forks, but the protocol must also satisfy player-replaceability and efficiency requirements.
- BA⋆ is introduced for synchronous complete networks while initially ignoring player replaceability.The paper describes BA⋆ as the most efficient cryptographic BA protocol for such networks known at the time.
- The synchronous complete-network model uses a common clock and simultaneous message exchange, with messages received at the next time click.
- The communication model permits malicious users to coordinate, adaptively corrupt honest users, and choose messages after observing honest messages sent simultaneously.
- BBA⋆ reaches agreement with probability 1/3 per main-loop execution and is a binary BA protocol with soundness 1 when n ≥3t + 1.
- BA⋆ is adapted for gossiping networks and Algorand, where player replaceability is required; related variants can operate with a simple majority of honest players.
4 Two Embodiments of Algorand
Algorand is presented through two embodiments that select leaders and verifier committees to propose blocks and reach Byzantine agreement, under different honesty and timing assumptions.
- Each Algorand round selects a leader to propose a block, followed by a randomly selected committee reaching Byzantine agreement on that proposal.
- The embodiments initially operate under a majority-of-honest-users assumption and can be adapted to a majority-of-honest-money assumption.
- Algorand′1: Algorand′1 assumes more than 2/3 of committee members are honest and caps agreement steps to achieve overwhelming-probability termination within a fixed bound.If agreement is not reached by the final step, the committee agrees on the always-valid empty block.
- Both embodiments share a common core, notations, notions, and parameters.
- The ideal correctness objective is that all honest users agree on the same block Br in every round.
2. Completeness 1. With probability 1, the payset of Br, PAY r, is maximal.10
Algorand combines leader selection with Byzantine agreement to preserve perfect correctness while achieving completeness close to the honest-user fraction. Its look-back parameter and non-manipulatable selection quantity protect the probability of honest leadership.
- Algorand targets perfect correctness and completeness close to h when the honest-user fraction satisfies h > 2/3.The system prioritizes correctness because delayed payments can be processed later, whereas forks should be avoided.
- A naive Byzantine-agreement approach can preserve correctness but has no completeness guarantees because honest users may propose different candidate blocks.The agreed block could therefore have a non-maximal payset, including the empty block.
- Algorand first selects a leader, who propagates a candidate block so verifiers can agree on the leader’s proposal rather than unrelated candidates.When the leader is honest, perfect correctness and Completeness 1 both hold.
- The leader is chosen by comparing hashed credentials derived from Qr−1, with eligibility and credential revelation designed to make selection unpredictable and non-manipulatable.Potential leaders and verifiers are selected from users already in the system k rounds earlier.
- The look-back parameter k limits adversarial influence on future leader probabilities, keeping honest leadership probability close to h when new users cannot be injected.The analysis gives h′ > h2(1 + h − h2); for h = 80%, h′ > .7424.
- If the leader is honest, the protocol produces a non-empty block with overwhelming probability, while a malicious leader may cause an empty payset.A maximal PAY r contains the currently outstanding payments of all honest users.
5 Algorand ′1
Algorand′ operates under an honest-majority assumption and uses ephemeral keys, identity-based signatures, and randomly selected verifiers. The key-management design supports long-lived participation with modest computation.
- Algorand′ initially assumes that more than 2/3 of the users in each PKr are honest, with a later construction replacing this by an honest-majority-of-money assumption.
- A verifier set is sampled from users present k rounds earlier, with parameters chosen so the set has the required honest-majority relationships with overwhelming probability.Chernoff-bound variants are used to ensure the desired conditions.
- Each verifier uses ephemeral keys for round-step messages, and the protocol requires verifiers to destroy the corresponding secret keys after signing.Identity-based signatures provide an efficient way to verify which ephemeral public key belongs to each round-step pair.
- Identity-based signatures let each user act as the authority generating round-step signing keys from a master key, which is then destroyed after key generation.The public key of a round-step identity is the identity itself in this scheme.
- A stash covering one million rounds can last almost two years when rounds take one minute, and 180M 32B secret keys can be computed in less than one hour.
5.3 Matching the Steps of Algorand ′ 1 with those of BA⋆
Algorand′ maps its round steps onto the stages of the BA⋆ protocol, adding leader-block handling, ephemeral authentication, and termination logic. Verifiers may stop early when a block has already been established.
- Step 1 has potential leaders compute and propagate candidate blocks together with credentials identifying their roles.
- Verifiers use credentials and ephemeral signatures so other participants can authenticate round-step messages and associated values.
- The later Algorand′ steps correspond to BA⋆ and its graded-consensus and binary-agreement stages, with verifiers sending ephemerally signed messages.
- During later steps, verifiers detect whether agreement has already halted and either reconstruct a certified block or set the block to the empty value.
- The protocol is bounded by m + 3 steps per round, with the final step computing the block and its certificate if no earlier termination occurred.
5.4 The Actual Protocol
The actual protocol has eligible users derive verifier membership, while selected verifiers process candidate blocks through timed, authenticated steps. Majority thresholds and ending conditions determine whether a certified block or the empty block is adopted.
- Potential leaders collect propagated payments, compute maximal paysets and candidate blocks, destroy their ephemeral keys, and propagate authenticated messages.
- Eligible users compute Qr−1 and locally determine whether they belong to the verifier set for each round-step.
- At Step 3, verifiers accept a value when more than 2/3 of valid messages support it without contradiction; otherwise they continue with the fallback case.
- At Step 4, graded-consensus outputs determine the binary-agreement input, using bi = 0 when gi = 2 and bi = 1 otherwise.
- Ending conditions let verifiers adopt an already generated block and certificate, or adopt the empty block when the protocol reaches the corresponding fixed-coin outcome.
5.5 Analysis of Algorand ′1
The analysis introduces round-based timing notation and models the random number of additional Byzantine-agreement trials. Computation is treated as negligible relative to message propagation.
- Round notation: T_r denotes when the first honest user learns B_r−1, while I_{r+1} spans the following λ-time dissemination interval.The interval is [T_{r+1}, T_{r+1}+λ].
- Round notation: For steps s≥2, t_s=(2s−3)λ+Λ, with I_0={0} and t_1=0.These definitions establish the waiting schedule used in each round.
- Randomized analysis: L_r counts Bernoulli trials needed to observe a 1, is bounded by m/3, and equals m/3 if all trials fail.Each trial succeeds with probability p_h^2.
- Timing assumptions: The analysis ignores computation time because it is negligible relative to message propagation; larger λ and Λ could incorporate it.Most statements hold with overwhelming probability.
5.6 Main Theorem
The main theorem establishes that each round produces a common block known to all honest users, with overwhelming probability, under the protocol’s assumptions. It also bounds generation time and the probability of an honest leader.
- Agreement: With overwhelming probability, all honest users agree on the same block B_r in every round.This is stated as a theorem property and follows from the completeness and soundness lemmas.
- Honest leader: When the leader is honest, B_r contains a maximal payset received by the leader, and all honest users know it by T_r+8λ+Λ.The block is generated by the honest leader.
- Malicious leader: When the leader is malicious, T_{r+1}≤T_r+(6L_r+10)λ+Λ, and all honest users learn B_r within I_{r+1}.The soundness bound holds with overwhelming probability.
- Leader selection: The leader is honest with probability at least p_h=h^2(1+h−h^2), where h is the honest-user fraction.This probability is used to derive expected round duration.
- Performance: For h=80%, the expected time between successive learned blocks is at most 12.7λ+Λ.The general expected-time expression depends on h through p_h.
5.7 The Completeness Lemma
The completeness lemma shows that an honest leader causes honest users to agree on the leader’s block and its maximal available payset. The block is disseminated within a bounded interval.
- Completeness: When the leader ℓ_r is honest, all honest users agree on the same block B_r generated by ℓ_r.The block contains a maximal payset received by the leader by α_{r,1}.
- Payset construction: The honest leader’s block contains a maximal payset among payments received by ℓ_r by time α_{r,1}.A maximal payset includes the currently outstanding payments of honest users.
- Dissemination: All honest users know B_r within I_{r+1}, with T_{r+1}≤T_r+8λ+Λ.The first user who learns the block helps propagate its certificate.
- Leader security: The leader’s credential and ephemeral-key destruction prevent later corruption from changing the already disseminated proposal.The adversary may corrupt the leader after observing the credential, but the proposal has already been propagated.
- Probability condition: For h=80%, at least t_H honest verifiers appear in step 4 with probability 1−10^-8; otherwise the protocol continues for additional steps.This affects running time but not correctness.
5.8 The Soundness Lemma
The soundness lemma shows that even with a malicious leader, honest users agree on a common block and learn it within a bounded time interval. The proof relies on Byzantine agreement, honest-verifier majorities, and ephemeral signatures.
- Soundness: When the leader is malicious, all honest users agree on the same block B_r with overwhelming probability.They also learn it within I_{r+1}.
- Soundness: A malicious leader yields the bound T_{r+1}≤T_r+(6L_r+10)λ+Λ for block generation.The bound accounts for the random number L_r of coin-flip steps.
- Block reconstruction: If a verifier stops without propagating, the protocol assigns the block consistently and subsequent honest users reconstruct it from the certificate.The same block is carried forward by later verifiers and honest users.
- Byzantine agreement: The binary agreement analysis ensures that honest verifiers converge on a single value and block, even across differing observed majorities.Ephemeral-key destruction prevents forged contradictory signatures after verifier identities become known.
- Termination analysis: The number of genuinely coin-flipped steps before termination is distributed according to L_r, while later fixed-coin steps add bounded delay.The worst case produces the stated soundness time bound.
5.9 Security of the Seed Qr and Probability of An Honest Leader
Algorand protects the seed Qr−1 from adversarial prediction by looking back k rounds, making the selected verifier process effectively unpredictable. This yields an honest leader with probability at least ph = h2(1 + h −h2).
- Seed security: The look-back parameter k prevents the Adversary from predicting Qr−1 when malicious users are added to PKr−k.Qr−1 is a random-oracle input used to select verifiers for round r.
- Adversarial analysis: k = O(log1/2 F) suffices for the Adversary to fail to predict Qr−1 with overwhelming probability.For h ∈(2/3, 1], a more complex analysis gives k = O(logC F) for a constant C slightly larger than 1/2.
- Seed security: A malicious leader sequence is the only case that lets the Adversary predict Qr−1 with good probability.If any leader in rounds r−k through r−1 is honest, the resulting seed remains random from the Adversary’s perspective.
- Adversarial analysis: The Adversary’s prediction process is modeled as a Markov chain whose unique absorbing state represents failure to predict Qr−1.Every other state has a positive probability of transitioning to state 0.
- Honest-leader probability: The leader ℓr is honest with probability at least ph = h2(1 + h −h2).The same lower bound applies to the leader of each Coin-Genuinely-Flipped step.
6 Algorand ′2
Algorand′2 operates under an honest-majority-of-users assumption and uses ephemeral keys, selective propagation, and graded consensus to generate and agree on blocks. With overwhelming probability, honest users agree on the same block, while leaders are honest with probability at least ph.
- Assumptions: Algorand′2 assumes that more than 2/3 of the users in each PKr are honest.The paper later explains how to replace this assumption with an honest-majority-of-money assumption.
- Ephemeral keys: Users prepare ephemeral keys for possible protocol steps and destroy each secret key after signing its corresponding message.The implementation uses chained master and ephemeral keys when additional steps are needed.
- Round execution: Potential leaders privately learn their roles, construct candidate blocks, and disseminate credentials with their proposed blocks.Credentials allow users to prove their selected roles without revealing them in advance.
- Round execution: Selective propagation forwards the first valid message and thereafter favors credentials with the smallest hash values.Messages from the same malicious player are discarded after the first verified message.
- Graded consensus: Step 2 uses graded consensus after CERT r−1, with selected verifiers propagating signed messages and non-verifiers stopping.Users compute Qr−1, check verifier membership, and only selected Step 2 verifiers transmit messages.
- Results: With overwhelming probability, all honest users agree on the same block Br, and the leader is honest with probability at least ph = h2(1 + h −h2).The stated result is derived for Algorand′2 from the corresponding properties of Algorand′1.
7 Handling Offline Honest users
Algorand can accommodate honest users who are frequently offline by selecting verifiers from an earlier participant set and giving them advance notice. This removes the need for continual participation while preserving a practical participation burden.
- Practical operation: With 95% honest players, setting parameters for h = 80% allows Algorand to continue working when at most half of honest players go offline.At least 80% of online players remain honest under this example.
- Lazy honesty: Choosing verifiers from users already present in a much earlier round removes the continual participation requirement.The look-back interval can match the users’ offline schedule.
- Lazy honesty: Lazy-but-honest users follow protocol instructions when asked but participate only rarely, potentially with advance notice and rewards.The model allows users to remain offline between assigned participation periods.
- Practical operation: A user checking possible verifier assignments for the next 2,000 rounds needs about 1 minute of computation if each signature takes a millisecond.If unselected, the user can go offline; if selected, the user prepares to participate.
- Practical operation: Lazy-but-honest verifiers mainly miss message propagation, which is described as typically robust because recent payment participants are expected to remain online.Payers and payees can therefore participate in propagating messages when honest.
8 Protocol Algorand ′ with Honest Majority of Money
Algorand′ replaces an honest-majority-of-users assumption with an honest-majority-of-money model by weighting verifier selection according to users’ monetary holdings. The paper describes implementations using money-linked copies and randomized selection.
- Honest majority of money: Verifier selection gives users decision power proportional to the amount of money they own.This is the basic proof-of-stake-style replacement for the honest-majority-of-users assumption.
- Honest majority of money: The money used for weighting can be measured at round r or at an earlier round when continual participation is removed.The earlier-round choice is associated with the look-back approach.
- Implementations: A capped-money implementation limits each public key to M units so repeated selection within k rounds has negligible probability.A user is selected according to its owned amount a(r)i relative to the system’s total money.
- Implementations: An alternative represents each user as K + 1 independently selectable copies, with K determined by the user’s money holdings.Each copy has its own ephemeral key and can be selected as a verifier.
- Implementations: For copies v = 1, ..., K, verifier membership is automatic, while the remaining copy is selected by a money-dependent biased coin.For example, with i = 3.7M and Ar = 1B, three of four copies are automatic and the fourth is selected with probability 0.7.
9 Handling Forks
Algorand makes forks practically negligible and provides deterministic procedures for resolving the rare cases when multiple chains appear.
- 10^-12 or 10^-18 fork probability makes it practically unnecessary to handle forks routinely.
- Users can follow the longest chain when multiple chains are visible.
- If longest chains tie, users prefer one ending in a non-empty block, then compare earlier blocks if needed.
- Among tied longest chains with non-empty endings, users select the leader with the smallest credential.
- Remaining ties are resolved by the smallest block hash and then lexicographic block order.
10 Handling Network Partitions
Network partitions can cause a short-lived fork, but Algorand’s threshold-based certification prevents competing branches from persisting beyond one round with high probability.
- 10.1 Physical Partitions: A partition can make the honest verifier count fall below tH, allowing the Adversary to force a fork with non-negligible probability.
- 10.1 Physical Partitions: Even when a fork occurs, only one branch can grow in the following round with overwhelming probability.
- 10.1 Physical Partitions: At most one branch has enough proper signatures to certify a block in the next round with high probability under bounded partition duration.For F = 10^-18 and up to 10^4 steps, the stated probability is 1−10^-10.
- 10.2 Adversarial Partitions: For roughly equal partition parts, at most one of four branches may grow in round r + 1.
- 10.3 Network Partitions in Sum: A partition-induced fork lasts at most one round, so ambiguity does not persist across the network.
- 10.3 Network Partitions in Sum: In all but at most one partition part, users cannot generate a new block and therefore do not rely on blocks that later vanish.