PaperlayerView exact revision on arXiv

Source-linked AI summary

Algorand

Jing Chen, Silvio Micali

arXiv:1607.01341v9cs.CRcs.DC

TL;DR

Without a universally trusted central authority, decentralized public ledgers face inefficiencies and weaknesses. Algorand selects verifiers through algorithmic randomness and uses Byzantine agreement to construct blocks; its transaction history forks only with very small probability.

  • Problem

    Without a universally trusted central authority, decentralized ledgers rely on shared transaction records, while current implementations have inefficiencies and weaknesses.

    Source: §1 · pp. 1–2

  • Method

    Algorand uses algorithmic randomness and cryptographic sortition to select verifiers who construct and agree on each block through Byzantine agreement.

    Source: §1 · p. 2, §1.2 · pp. 5–6

  • Results

    Algorand’s transaction history forks only with very small probability, such as one in a trillion or even 10^-18.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Algorand may address some legal and political concerns.

    Source: §1 · p. 2

    In a remote possibility that a round exceeds µ steps, a user may be unable to sign their message.

    Source: §6.2 · p. 59

Abstract

from arXiv · show

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

This section introduces Algorand’s efficient ledger design, including its selection and agreement mechanisms and aim to avoid forks. It also situates the protocol among related work by comparing fork behavior and honesty assumptions.

1.1 Bitcoin’s Assumption and Technical Problems

  • Proof-of-work Bitcoin assumes no adversary controls a computational majority, yet its computation is wasteful, mining pools concentrate block production, and competing chains make recent payments ambiguous.The top 500 supercomputers can supply only 12.8% of the total computational power required from Bitcoin players.Source: §1.1 · pp. 2–3

1.2 Algorand, in a Nutshell

  • Algorand supports permissionless participation and lazy-honest users who are offline most of the time, remaining secure even when most participating players are malicious if honest users are available when needed.In permissionless settings, the adversary may corrupt users provided that two-thirds of the money belongs to honest users.Source: §1.2 · pp. 3, 4, 6
  • Each of fifteen hundred users performs at most a few seconds of computation; block generation takes less than 10 minutes, with the first embodiment averaging less than Λ + 12.4λ.The second embodiment was reported to generate a block in less than 40 seconds.Source: §1.2 · p. 4
  • Algorand’s blockchain forks with probability less than one in a trillion, allowing immediate reliance on new-block payments; power resides with users, and the method applies to tamperproof block sequences beyond blockchains.The paper also characterizes Algorand as an alternative to blockchains that may be of independent interest.Source: §1 · p. 2, §1.2 · p. 4
  • Algorand builds blocks with BA⋆, a fast message-passing Byzantine-agreement protocol; player replaceability lets each step use a new random set, limiting the threat of corruption of small committees.The binary protocol uses a three-step loop and, in a synchronous network with more than two-thirds honest players, ends in agreement with probability greater than one-third after each loop.Source: §1.2 · pp. 4, 6
  • Cryptographic sortition uses an adversary-uninfluenced seed to select leaders and verifiers automatically and secretly, so adaptive corruption after a leader’s proposal cannot alter the block choice.The prior block alone could let an adversary influence the next leader, motivating the separate seed and secret credentials.Source: §1.2 · p. 5

1.3 Closely Related work

  • Against Pass and Shi’s Sleepy Consensus, Algorand is permissionless, avoids frequent forks and deep-wait reliance, and can provide Byzantine agreement on a single value.Algorand is also related to proof of stake because users’ block-building power is proportional to the money they own in the system.Source: §1.3 · p. 7
  • A protocol with a majority of lazy-but-honest players can work even when most online users are malicious.Sufficient honest players who expect to be crucial at a rare moment can stay online, and the Adversary cannot force them offline because it does not know who they are.Source: §1.3 · p. 7
  • A related protocol requires a simple honest majority, whereas the current Algorand version requires a 2/3 honest majority.Source: §1.3 · p. 8
  • Against Ouroboros, Algorand is overwhelmingly likely fork-free and avoids the four assumptions listed for Ouroboros.Ouroboros uses cryptographic sortition to avoid proof of work but remains a Nakamoto-style protocol with frequent, unavoidable forks. Its assumptions include high synchrony, stakeholder availability, limits on offline periods, and delayed adaptive corruption; Algorand permits instantaneous corruption.Source: §1.3 · p. 8

2 Preliminaries

The preliminaries establish the cryptographic, ledger, and communication framework for Algorand, formalizing rounds, blocks, and an acceptable probability of forks. They also specify the adversary model and assumptions on honest users, money, and timely message propagation.

2.1 Cryptographic Primitives

  • Unique signatures let Algorand construct a verifiable random function by hashing a signer’s unique signature, with correctness provable from the signature.The paper also defines a retrievable signature form that includes the signer and message alongside the signature.Source: §2.1 · p. 9

2.2 The Idealized Public Ledger

  • The ideal ledger records signed payments in tamper-proof, time-ordered blocks; public keys and amounts are visible, while sensitive information is represented by its hash.The current status of key balances can be deduced from the ledger, but active users must store and update it or reconstruct it themselves.Source: §2.2 · pp. 10–11

2.3 Basic Notions and Notations

  • Each round’s official payset determines the next status, while valid payments cannot exceed the payer’s balance or already appear in an earlier official payset.A payset is valid when each user’s included payments are collectively within that user’s balance.Source: §2.3 · pp. 12–13

2.4 Blocks and Proven Blocks

  • Algorand’s blocks are authenticated by certificates, and each block is safely final on entry, with minimal computation and overwhelmingly high probability of no fork.A certificate contains signatures on the block hash from a majority of the verifier set, plus proofs that the signers belong to that set.Source: §2.4 · p. 13

2.5 Acceptable Failure Probability

  • With F = 10^-12 and one-minute rounds, a fork is expected roughly once in 1.9 million years; with F = 10^-18 and one-second blocks, roughly once in the age of the Universe.F is the tolerated probability of a blockchain fork, not of forging an honest user’s digitally signed payment.Source: §2.5 · p. 14

2.6 The Adversarial Model

  • The adversary can efficiently and dynamically corrupt users, coordinate and control malicious users’ actions, and even isolate them from messages.Users may be corrupted at any time, subject to the stated upper bound on corruptions; the model assumes the adversary perfectly coordinates malicious users.Source: §2.6 · p. 14
  • The adversary cannot forge honest users’ signatures except with negligible probability or interfere with messages exchanged among honest users.The adversary is computationally bounded.Source: §2.6 · pp. 14–15
  • HMM_k > h requires honest users to own more than fraction h of the money at round r−k, for each round r, with h > 1/2.At one minute per round, k = 120 means the majority remains in honest hands for at least two hours, while k = 10,000 means at least one week; the assumption is presented as a continuum of choices.Source: §2.6 · p. 15

2.7 The Communication Model

  • The communication model assumes peer-to-peer gossip and, temporarily, timely delivery to almost all honest users; the MP assumption formalizes delivery of messages propagated before a time bound.Timely delivery of current-round messages alone cannot ensure verifiers know the previous blockchain needed to validate payments, so MP requires delivery of older messages as well; the paper later removes the entire-network assumption for partitions, retaining timely delivery within each connected component.Source: §2.7 · pp. 15–16
  • The strengthened MP assumption guarantees delivery of n messages of size µ to at least fraction ρ of honest users within a bound λ_n,ρ,µ.The assumption is stronger than needed; the model also lets the adversary control message delivery arbitrarily, provided it does not violate MP.Source: §2.7 · p. 16

3 The BA Protocol BA⋆in a Traditional Setting

Algorand requires Byzantine agreement that is efficient and player-replaceable; this section presents BA⋆ for synchronous complete networks while setting player replaceability aside. BA⋆ combines graded consensus and binary agreement to achieve arbitrary-value Byzantine agreement with soundness 1 when n ≥ 3t + 1.

3 The BA Protocol BA⋆in a Traditional Setting

  • BA⋆ is presented for synchronous complete networks without player replaceability, and is described as the most efficient cryptographic Byzantine agreement protocol then known for that setting.The paper says BA⋆ can also work in gossiping networks and satisfy player replaceability; a majority-honest extension is also identified as usable in Algorand.Source: §3 · pp. 16–17, §3.6 · pp. 21–22

3.1 Synchronous Complete Networks and Matching Adversaries

  • In the synchronous complete-network model, an adversary controls malicious players, may corrupt honest players at odd ticks, and can rush same-round messages; gossip adaptation uses digital signatures for authentication.The model assumes private, authenticated communication, whereas gossip provides no privacy and requires signed messages.Source: §3.1 · p. 17

3.2 The Notion of a Byzantine Agreement

  • A Byzantine agreement protocol must make every honest player halt with probability 1 and, with probability at least its soundness, satisfy agreement and consistency when at most t players are malicious and n ≥ 2t + 1.Consistency requires the common output to match the honest players’ common initial value.Source: §3.2 · p. 18

3.3 The BA Notation #

  • The BA notation #i(v) counts the players from whom i received value v in a given step; each player receives exactly one message from each player.Source: §3.3 · p. 18

3.4 The Binary BA Protocol BBA⋆

  • For n ≥ 3t + 1, BBA⋆ is a binary Byzantine agreement protocol with soundness 1, and each main-loop execution brings players into agreement with probability 1/3.The loop uses digital signatures to generate a sufficiently common random bit and requires a common random string independent of players’ keys.Source: §3.4 · pp. 18–19

3.5 Graded Consensus and the Protocol GC

  • GC outputs value-grade pairs: honest players with positive grades agree on the value, and unanimous initial values yield that value at grade 2; for n ≥ 3t + 1, GC satisfies graded consensus.The two-step protocol is formed from the last two steps of gradecast.Source: §3.5 · p. 20

3.6 The Protocol BA⋆

  • When n ≥ 3t + 1, BA⋆ achieves arbitrary-value Byzantine agreement with soundness 1 by combining graded consensus with binary agreement to decide whether to output a value or ⊥.Players first run GC on their initial values, then run BBA⋆ with an input determined by their grade; they output the GC value only if BBA⋆ outputs 0.Source: §3.6 · p. 21

4 Two Embodiments of Algorand

Section 4 outlines Algorand’s round workflow and presents two embodiments that share a common core but differ in their Byzantine-agreement assumptions and stopping behavior.

4 Two Embodiments of Algorand

  • Each round selects a leader to propose a block, selects committees for Byzantine agreement, then circulates threshold signatures and signer credentials so everyone learns the agreed block.Each BA step uses a separately selected committee; signatures authenticate the block’s hash.Source: §4 · p. 22
  • Both embodiments assume a majority of honest users; Section 8 adapts them to an honest-majority-of-money assumption, and Algorand′1 can be modified to allow arbitrary BA steps.The paper notes that many variants of the basic embodiments are easy to derive.Source: §4 · p. 22
  • Algorand′1 assumes >2/3 of committee members are honest and caps BA steps, falling back to the empty block if agreement is not reached; Algorand′2 requires at least tH honest members and permits arbitrary steps.Algorand′1 reaches agreement with overwhelming probability within a fixed number of steps; Algorand′2’s tH threshold guarantees, with overwhelming probability, at least 2/3 honest committee members.Source: §4 · p. 22

4.1 A Common Core

  • The stated ideal correctness objective is that, in each round, all honest users agree on the same block Br.Source: §4.1 · p. 22

2. Completeness 1. With probability 1, the payset of Br, PAY r, is maximal.10

This section presents Algorand’s correctness and completeness goals for h > 2/3 and its leader-based approach to achieving them when the leader is honest. It also describes leader selection, the look-back rule, and ephemeral keys, and states that honest leaders produce non-empty blocks with overwhelming probability.

Completeness

  • A maximal payset contains the currently outstanding payments of all honest users, since paysets contain valid payments and honest users make only valid payments.Source: §2 · p. 22
  • For h > 2/3, Algorand targets overwhelming-probability perfect correctness and completeness close to h, with both guaranteed when the selected leader is honest.The leader is honest with probability close to h.Source: §2 · p. 23
  • Agreement on users’ separate candidate blocks can lack completeness, even yielding the empty block; instead, Algorand′ agrees on the selected leader’s candidate, which is maximal when that leader is honest.The protocol prioritizes correctness because omitted payments can be processed in a later round, whereas a fork should be avoided if possible.Source: §2 · p. 23

Leader Selection

  • Leader selection uses hashed credentials and a prior-round quantity Q; eligible users’ hash-derived values support secret potential-leader selection, with the smallest revealed value identifying the leader.Potential leaders must have belonged to the system for at least k rounds.Source: §2 · pp. 23–24

Verifier Selection

  • Verifier-selection thresholds ensure, with sufficiently high probability, enough honest signatures for a new block, at most one block with enough signatures, and the required 2/3 honest majority at each Byzantine-agreement step.The thresholds differ between Algorand′ 1 and Algorand′ 2.Source: §2 · p. 24

Leader Selection

  • At h=80%, the honest-leader probability satisfies h′ > .7424; if Q were independently random, that probability would be exactly h.The paper’s bound is for its actual, sufficiently non-manipulatable Q; the exact-h statement is the ideal independent-randomness case.Source: §2 · pp. 25–26

The Seed Qr and the Look-Back Parameter k

  • Algorand inductively defines Q to resist adversarial manipulation: it hashes the leader’s credential with Q from the prior round for a nonempty block, and hashes the prior Q with the round number otherwise.The fallback supports continued leader selection when a malicious leader can cause the agreement protocol to output its default empty block.Source: §2 · p. 27

2. Completeness 1. With probability 1, the payset of Br, PAY r, is maximal.10

  • Without user injection, the adversary cannot reduce the probability of an honest leader at round r + 40 much below h; potential leaders are drawn from users already present at round r − k.Users added from rounds r − k through r are ineligible to lead round r, making the look-back parameter a security parameter.Source: §2 · p. 28
  • After a legitimate block is generated, an adversary may corrupt its verifiers and certify a syntactically correct alternate block, but single-use ephemeral keys prevent later signing of messages they did not originally sign.Verifiers destroy each ephemeral secret key after use.Source: §2 · p. 28

4.2 Common Summary of Notations, Notions, and Parameters

  • When the potential-leader set is non-empty, uniform credential hashes select a leader who is honest with probability at least h; n1 is chosen to make the set non-empty with overwhelming probability.Potential leaders are selected from users in PKr−k.Source: §4.2 · p. 30
  • If the leader is honest, the protocol guarantees that the block is non-empty with overwhelming probability.A non-empty block includes the leader’s identity, credential, and signature; its payset may still be empty.Source: §4.2 · p. 30

5 Algorand ′1 · 5.1 Additional Notations and Parameters · 5.2 Implementing Ephemeral Keys in Algorand ′1

Algorand′ is constructed under an honest-majority-of-users assumption for each PKr, with a later section replacing it with an honest-majority-of-money assumption. Its ephemeral signing keys use identity-based signatures, with parameters chosen to bound protocol steps and block-generation time.

5 Algorand ′1

  • Algorand′ assumes more than 2/3 of users in each PKr are honest; Section 8 replaces this with the honest-majority-of-money assumption.Source: §5 · p. 31

5.1 Additional Notations and Parameters

  • m is a multiple of 3 bounding binary BA steps, while Lr bounds block-generation time and m is chosen so Lr < m/3 with overwhelming probability.Lr counts Bernoulli trials to see a 1, capped at m/3; if all trials fail, Lr = m/3.Source: §5.1 · p. 31
  • For each step s > 1, n is chosen so the verifier-set inequalities hold with overwhelming probability, using Chernoff-bound variants; n can be smaller as h approaches 1.Source: §5.1 · p. 31

5.2 Implementing Ephemeral Keys in Algorand ′1

  • The protocol uses identity-based signatures in a novel way: each user acts as an authority for round-step identities, enabling public-key verification after master-secret destruction.In identity-based signatures, the user’s identity itself serves as the public key.Source: §5.2 · p. 32
  • Each user’s master public key supports immediate verification, with overwhelming probability, of ephemeral signatures for the first million rounds after the specified starting round.Source: §5.2 · p. 32
  • A user publishes PMK, derives and stores per-step secret keys, destroys SMK, then signs with and destroys each used ephemeral key.Source: §5.2 · p. 32
  • 180M ephemeral secret keys can be computed in under one hour with 32B elliptic-curve keys, and the stash lasts almost two years when m + 3 = 180 and rounds take a minute.The passage reports both the computation time and stash duration under these conditions.Source: §5.2 · p. 32

5.3 Matching the Steps of Algorand ′ 1 with those of BA⋆

Algorand ′ maps its round steps onto BA⋆, GC, and BBA⋆ while allowing verifiers to stop or adapt their actions when they learn that the block has already been chosen. The section also describes how ephemeral-key signatures are authenticated through a Merkle tree.

5.3 Matching the Steps of Algorand ′ 1 with those of BA⋆

  • A potential leader proposes a candidate block and sends a BA⋆-style initial message so participants can agree on its hash rather than the block itself.The leader also propagates a signature of the block hash under an ephemeral key and a credential.Source: §5.3 · p. 33
  • Step 2 corresponds to GC’s first step, while Steps 3 and 4 correspond to GC’s second step and BA⋆’s third step, respectively.At Step 4, verifiers use GC’s output to choose initial bit 0 if gi = 2 and 1 otherwise.Source: §5.3 · p. 33
  • Steps 5 through m + 2 correspond to later BA⋆ steps, but a verifier stops the current round and starts the next if it learns the block was already chosen.Because propagation is asynchronous, the verifier also checks whether BBA⋆ halted in a prior step and otherwise sends the corresponding BBA⋆ message.Source: §5.3 · pp. 33–34
  • Verifiers authenticate ephemeral public keys by providing a signature and a Merkle-tree path to the key’s leaf under a publicized root.The keys are canonically ordered and stored in the corresponding leaves of the tree.Source: §5.3 · p. 33
  • At Step m + 3, if the block was not generated earlier, the verifier computes the block and its certificate; when it is non-empty, the block and certificate must be properly reconstructed.If the block is empty, the verifier sets it to the specified empty-block value and computes its certificate.Source: §5.3 · p. 34

5.4 The Actual Protocol

This section describes how the protocol advances a round through verifier-selected proposals, graded consensus, and binary agreement with timed voting and ending conditions. It also specifies timed BBA⋆ steps and how users reconstruct the round’s block from messages, including a final step for completeness.

Step 1

  • A Step 1 verifier who is a potential leader builds a maximal payset from propagated payments, forms a candidate block, destroys its ephemeral key, and propagates its message.In practice, users selectively propagate verified Step 1 messages, favoring credentials with the smallest hashes; potential leaders can also propagate their credentials separately.Source: §5.4 · p. 34

Step 2

  • After waiting t2 = λ + Λ, a Step 2 verifier processes valid Step 1 messages and, when it receives a valid proposal, destroys its ephemeral key and propagates a Step 2 message.The verifier privately decides which user leads round r based on the proposal it accepts.Source: §5.4 · p. 35

Step 3

  • After t3 = 3λ + Λ, a Step 3 verifier adopts a non-bottom value if more than 2/3 of valid Step 2 messages support it without contradiction; otherwise it computes the alternate message.The protocol counts contradictory messages from a sender as invalid.Source: §5.4 · p. 36

Step 4

  • At Step 4, a participant computes GC outputs v_i and g_i from valid received Step 3 messages using more-than-2/3 and more-than-1/3 support conditions, then sets BBA* input b_i to 0 iff g_i = 2, and 1 otherwise.Source: §5.4 · p. 37

Later steps

  • When Ending Condition 0 is met during a Coin-Fixed-To-0 step, a user stops the round, adopts the received proposal as B_r, and sets its certificate from the condition’s messages.The condition applies to an eligible earlier step and a valid Step 1 message.Source: §5.4 · p. 38
  • When Ending Condition 1 is met during a Coin-Fixed-To-1 step, a user stops the round, sets B_r to empty, and sets its certificate from the condition’s messages.Otherwise, later steps wait for t_s = (2s − 3)λ + Λ, use majority votes for v_i, and derive b_i from signed bits in received messages.Source: §5.4 · p. 38

Coin-genuinely-flipped steps

  • Selected users start each BBA⋆ step after learning Br−1; nonselected users stop, while selected users wait for the step’s scheduled time.In steps s, the wait is ts ≜ (2s − 3)λ + Λ.Source: §5.4 · p. 40
  • After the wait, a user takes the majority of received valid messages’ votes and sets bi to 0 or 1 according to the messages’ ESIG value.The passages specify bi = 0 for messages of the form (ESIGj(0), ESIGj(vj), …) and bi = 1 for messages of the form (ESIGj(1), ESIGj(vj), …).Source: §5.4 · p. 40

Step m + 3

  • Step m + 3 is specified for completeness because BBA⋆ has overwhelmingly likely ended before it; selected users wait, then compute and propagate a message.Nonselected users stop, and the step’s certificate uses a uniform format even though ESIGi(outi) is not required.Source: §5.4 · p. 41

Reconstruction of the Round-r Block by Non-Verifiers

  • During round-r reconstruction, users stop on specified message conditions and set Br and their certificate from the received messages.The visible conditions include a qualifying string and step, a step in the specified range and congruence class, or receipt of at least tH valid messages.Source: §5.4 · p. 42

5.5 Analysis of Algorand ′1

The analysis defines round-level timing and trial-count notation for Algorand ′1. It treats computation as negligible relative to message propagation and states that most claims hold with overwhelming probability.

5.5 Analysis of Algorand ′1

  • T_r is when the first honest user knows B_{r−1}, and I_{r+1} spans [T_{r+1}, T_{r+1}+λ].The analysis sets T_0=0 by protocol initialization.Source: §5.5 · p. 42
  • For each step s, αᵢʳ,ₛ and αᵢʳ,ₛ mark player i’s starting and ending times; t_s=(2s−3)λ+Λ for 2≤s≤m+3.The analysis also sets I_0={0} and t_1=0.Source: §5.5 · p. 42
  • L_r counts Bernoulli trials until a 1 occurs, capped at m/3 trials, with each trial succeeding with probability p_h^2.If all trials fail, L_r=m/3.Source: §5.5 · p. 42
  • The analysis ignores computation time as negligible relative to message propagation; slightly larger λ and Λ can incorporate it, and most statements hold with overwhelming probability.Source: §5.5 · p. 42

5.6 Main Theorem

With overwhelming probability in every round, all honest users agree on the same block. Theorem 5.1 bounds block-generation time according to whether the leader is honest or malicious and gives a lower bound on the probability of an honest leader.

5.6 Main Theorem

  • With overwhelming probability, all honest users agree on the same block B_r in each round r ≥ 0.This is Property 1 of Theorem 5.1.Source: §5.6 · p. 43
  • With an honest leader, B_r is generated by that leader, contains a maximal payset it received by α_r,1, and is known to all honest users in I_r+1 within 8λ + Λ.The round satisfies T_r+1 ≤ T_r + 8λ + Λ, with overwhelming probability.Source: §5.6 · p. 43
  • With a malicious leader, all honest users agree on B_r and know it in I_r+1, with T_r+1 ≤ T_r + (6L_r + 10)λ + Λ, with overwhelming probability.Source: §5.6 · p. 43
  • The leader is honest with probability at least p_h, where p_h = h2(1 + h − h2) for L_r.Source: §5.6 · p. 43
  • At h = 80%, expected block-generation time is at most 12.7λ + Λ, and expected duration depends on the precise value of h.Source: §5.6 · p. 43
  • As the number of users grows, λ should remain stable while Λ grows because blocks must accommodate more transactions at a fixed transaction rate.Source: §5.6 · p. 43

5.7 The Completeness Lemma

Assuming Properties 1–3 hold for round r−1 and the round-r leader is honest, the completeness lemma states that, with overwhelming probability, honest users agree on the leader’s block and learn it within the next-round interval. The lemma also bounds the round’s timing and gives an expected step count under a stated condition.

5.7 The Completeness Lemma

  • With overwhelming probability, honest users agree on the leader’s block containing a maximal payset received by αr,1, and T r+1 ≤ T r + 8λ + Λ.All honest users know the block in interval Ir+1; for r = 0, T 1 ≤ 6λ + Λ.Source: §5.7 · pp. 46, 48
  • An honest user reconstructs the block after receiving tH valid round-r messages for the leader’s block hash, including the leader’s message with its proper certificate.At least one of the threshold messages comes from an honest verifier and is sent after T r + t4.Source: §5.7 · p. 47

5.8 The Soundness Lemma

This section establishes agreement and timing guarantees by analyzing the GC and BBA⋆ phases and bounding binary agreement’s final step through genuinely flipped coin steps.

5.8 The Soundness Lemma

  • With overwhelming probability, all honest users agree on block Br by time T r+1 ≤ T r + (6Lr + 10)λ + Λ and know it in interval Ir+1.This soundness claim assumes Properties 1–3 hold for round r −1 and that the round-r leader is malicious.Source: §5.8 · p. 48
  • If no honest step-4 verifier sets gi = 2, honest verifiers begin binary agreement on bit 1 and ultimately stop with the empty block Br ε.The proof shows no honest verifier can obtain the required bit-0 messages; after step 5 propagates bit 1, step 6 stops with Br ε, which all honest users learn in interval Ir+1.Source: §5.8 · pp. 48–49
  • When a step-4 verifier sets gi = 2, the honest verifiers agree on its value v′, and the proof establishes that a valid leader message exists.The verifier has seen more than a 2/3 majority for v′; the proof uses this to show other honest verifiers cannot settle on a different value and that honest earlier verifiers received a valid leader message.Source: §5.8 · pp. 48–49
  • A malicious leader cannot selectively delay its round-1 message to verifiers without exposing it to non-verifiers; for enormous blocks, steps 3 and 4 can wait λ′/2 if 4λ < λ′.The proof notes that a good constant fraction of honest users see the message after waiting t2, leaving less than Λ for it to reach the rest.Source: §5.8 · p. 51
  • When an honest verifier stops in event E.a at the fixed-to-0 step, honest verifiers align on H(Br ℓ), propagate bit 0, and later stop with Br ℓ.Even if the first stopper is malicious and its certificate may not reach honest users in time, the subsequent honest propagation leads to a fixed-to-0 stop at step s∗+3 and user knowledge within Ir+1.Source: §5.8 · pp. 52–53

The Soundness Lemma

  • All honest users know B_r within I_{r+1}; T_{r+1} ≤ T_r + λ + t_{s*} in Cases 2.1.a/b and ≤ T_r + λ + t_{s*+3} in Cases 2.2.a/b.Source: §5.8 · p. 53
  • Combining the probability for ℓ′ ∈ HSV r,s′−1, the honest verifiers in HSV r,s′ reach agreement on a bit b ∈ {0, 1} with probability at least ph.If such a verifier exists, all honest verifiers in HSV r,s′ agree on b with probability 1/2; if no such verifier exists, they agree on lsb(H(σr,s′−1ℓ′)) with probability 1.Source: §5.8 · p. 54
  • After agreement at a genuinely flipped step, no later such step is executed; the last one is s' = 4 + 3L_r, and the adversary's other placements of s* yield no greater delay.For s* before the second-last genuinely flipped step, T_{r+1} < T_r + λ + t_{s'}; for s* = s' - 2 or s' - 1, T_{r+1} ≤ T_r + λ + t_{s'+2}.Source: §5.8 · p. 54
  • T_{r+1} ≤ T_r + λ + t_{3L_r+6} = T_r + λ + (2(3L_r+6) - 3)λ + Λ; the worst case is s* = s' - 1 in Case 2.2.b.The last genuinely flipped step is s' = 4 + 3L_r.Source: §5.8 · pp. 54–55

5.9 Security of the Seed Qr and Probability of An Honest Leader

The section shows that a look-back parameter makes the seed Q unpredictable to the adversary with overwhelming probability, then uses this to bound the probability of an honest leader. Under the stated properties, that probability is at least h^2(1 + h − h^2).

5.9 Security of the Seed Qr and Probability of An Honest Leader

  • With k = O(log^(1/2) F), the adversary fails to predict Qr−1 at round r − k with overwhelming probability.The look-back prevents the adversary from querying Qr−1 to the random oracle when malicious users are added to PKr−k.Source: §5.9 · pp. 55, 57
  • The adversary’s prediction game is modeled as a Markov chain whose absorbing state means failure, with each other state having a positive probability of transitioning to it.The adversary’s best option each round maximizes the initial run of malicious users in the next round’s permutation, increasing its options for Q in the following round.Source: §5.9 · p. 56
  • Given Properties 1–3 for each round before r, leader ℓr is honest with probability at least h^2(1 + h − h^2); in each Coin-Genuinely-Flipped step s, the verifier is honest with the same lower bound.Source: §5.9 · pp. 57–58

6 Algorand ′2

Algorand ′2 develops and analyzes a protocol for honest users to agree on a block with overwhelming probability under an honest-user majority assumption. It uses parameterized verifier selection, renewable ephemeral keys, timed verifier steps, certificates, and block reconstruction to coordinate rounds.

6 Algorand ′2

  • Algorand ′2 assumes that more than 2/3 of users in each PKr are honest, an assumption Section 8 later replaces with an honest-majority-of-money assumption.Source: §6 · p. 58

6.1 Additional Notations and Parameters for Algorand ′2

  • The protocol chooses n so that, with overwhelming probability, selected verifiers satisfy |HSV r,s| > tH and |HSV r,s| + 2|MSV r,s| < 2tH, implying a 2/3 honest majority.Variants of Chernoff bounds ensure these conditions; a higher h allows a smaller n.Source: §6.1 · pp. 58–59

6.2 Implementing Ephemeral Keys in Algorand ′2

  • When a round exceeds its precomputed µ ephemeral keys, a user cannot sign later-step messages, so the protocol extends the stash by authenticating a new master public key with the last key.The extension can be repeated as needed if the round continues.Source: §6.2 · p. 59

6.3 The Actual Protocol Algorand ′2

  • In Step 1, a selected potential leader constructs a candidate block, while users selectively propagate the first valid message and thereafter favor messages with the smallest credential hash.A user discards a second message from the same sender.Source: §6.3 · pp. 60–61
  • The graded-consensus stages use messages from at least tH verifiers to adopt a value, then determine each user's value and grade before the protocol proceeds to binary agreement.Users select the value in Step 3 from an uncontradicted set of tH valid Step 2 messages; Step 4 computes the graded-consensus output.Source: §6.3 · pp. 63–64
  • Verifiers wait at most 2λ per step; reaching tH valid prior-step messages can set their bit, while specified ending conditions let them finish the round and establish its certificate.A verifier that has learned the block hash finishes the round and can proceed without initiating further verifier-message propagation.Source: §6.3 · p. 65
  • If a round runs beyond μ steps, a verifier exhausts pre-generated ephemeral keys and authenticates messages through a key cascade, causing λ to increase slightly until a new block starts.The parameter λ reverts to its original value when a new block is produced and a new round begins.Source: §6.3 · pp. 66–67
  • Non-verifiers follow the steps and relay messages, end the round with a certificate, then start the next round while awaiting the block pinned down by that certificate.If the certificate indicates an empty block, they know the block as soon as they have the certificate.Source: §6.3 · p. 67

6.4 Analysis of Algorand ′2

  • With overwhelming probability, all honest users agree on the same block, and a new-block leader is honest with probability at least p_h = h^2(1 + h - h^2).The passage gives the leader probability as p_h = h^2(1 + h - h^2).Source: §6.4 · p. 67

7 Handling Offline Honest users

Algorand can tolerate substantial honest-user absenteeism, and a larger look-back parameter can support lazy honesty instead of continual participation. Users can check in advance whether they will be selected, prepare if needed, and otherwise remain offline.

7 Handling Offline Honest users

  • With 95% honest players, parameters set for h = 80% preserve operation even if up to half of honest players go offline, leaving at least 80% of online players honest.The passage describes this as a major case of absenteeism.Source: §7 · p. 67

From Continual Participation to Lazy Honesty

  • Choosing a sufficiently large look-back k lets Algorand replace continual participation with lazy honesty as an alternative way to ensure the underlying BBA⋆ protocol has an honest majority.Lazy-but-honest users follow instructions when asked to participate, but are asked only rarely, with advance notice and potentially significant rewards.Source: §7 · p. 67
  • For weekly planning, verifier selection shifts back 2,000 rounds, letting users determine upcoming duties in advance from values already included in the blockchain.The example assumes rounds average about 5 minutes and bases selections on Q values.Source: §7 · p. 68
  • About 1 minute of computation suffices to check 2,000 rounds of possible verifier selections; unselected users can go offline, while selected users prepare to act as honest verifiers.This estimate assumes each digital signature takes 1 millisecond.Source: §7 · p. 68
  • Lazy-but-honest potential verifiers miss only message propagation, which is typically robust, while honest payers and payees of recent payments are expected to be online and participate.The passage says these users watch what happens to their payments.Source: §7 · p. 68

8 Protocol Algorand ′ with Honest Majority of Money

Section 8 replaces an honest majority of users with an honest majority of money by selecting verifiers with decision power proportional to their holdings. Using balances at round r supports continual participation; using balances from round r−k−2,000 avoids that requirement.

8 Protocol Algorand ′ with Honest Majority of Money

  • Verifier selection gives users decision power proportional to their money, with the balance measured at round r or, to avoid continual participation, at round r−k−2,000.The section opts for round-r balances when continual participation is acceptable.Source: §8 · p. 68

The Next Simplest Implementation

  • A capped-key implementation limits each public key to M money, chosen so the probability of a key entering verifier sets in multiple steps within k rounds is negligible.The key’s verifier-selection probability is based on the money it owns in round r; execution then proceeds as before.Source: The Next Simplest Implementation · p. 69

A More Complex Implementation

  • An alternative represents a user with K + 1 copies, where K depends on the user’s money; the first K copies are automatic verifiers and the last is conditionally selected.The final copy’s selection is determined per step, with the user proving the result through a credential.Source: A More Complex Implementation · pp. 69–70
  • In the example, a user holding 3.7M of 1B has three automatic copies and a fourth selected with probability 0.7.The biased coin is implemented by hashing and signing so the user can prove the outcome; round execution otherwise follows the previously described protocol.Source: A More Complex Implementation · p. 70

9 Handling Forks

Algorand reduces the probability of forks to 10^-12 or 10^-18, making resolution practically unnecessary, but it can also use fork-resolution procedures with or without proof of work.

9 Handling Forks

  • The probability of forks is reduced to 10^-12 or 10^-18, making it practically unnecessary to handle them.Algorand can nevertheless employ fork-resolution procedures with or without proof of work.Source: §9 · p. 70
  • When users see multiple chains, they can resolve forks by following the longest chain.This is presented as one possible instruction for users.Source: §9 · p. 70
  • For tied longest chains, prefer a non-empty final block; resolve remaining ties by leader credential, block hash, then lexicographic order.If all tied chains end in empty blocks, compare their second-last blocks; the smallest credential and hash, then first lexicographic order, decide among chains with non-empty final blocks.Source: §9 · p. 70

10 Handling Network Partitions

Assuming bounded message propagation times, Algorand continues to work through occasional network partitions; the analysis covers two-part partitions and says the case of more parts is similar.

10.1 Physical Partitions

  • The authors treat the smaller part as offline because it lacks enough verifiers to generate tH signatures for a block; the cited probability is very low, e.g., 10^-16 when F = 10^-18.Source: §10.1 · p. 71
  • A physical partition can create a fork in round r, but with high probability only one of two branches grows in round r + 1; with roughly equal-sized parts, at most one of four branches grows.The stated 1 − 10^-10 bound applies when F = 10^-18 and the adversary cannot partition honest users for more than 10^4 steps.Source: §10.1 · p. 72

10.2 Adversarial Partition

  • Even if an adversary partitions honest users’ message paths while forwarding messages between parts, it may create a fork, but at most one branch grows.Once a forwarded message reaches an honest user in the other part, it is propagated there as usual.Source: §10.2 · p. 72

10.3 Network Partitions in Sum

  • A partition may cause a fork in one round, but it lasts at most one round: at most one branch grows, while users in other parts cannot generate new blocks or rely on blocks that vanish.This leaves no lingering ambiguity after the partition-induced fork.Source: §10.3 · p. 72
Loading 1607.01341v9…