[Algorand | Proceedings of the 26th Symposium on Operating Systems Principles](https://dl.acm.org/doi/10.1145/3132747.3132757) Confirms transactions in about a minute Users never have divergent views (no temporary forks) Uses a consensus mechanism based on VRF # Introduction Current blockchains suffer from a trade-off between latency and confidence in a transaction In [[Bitcoin]], users repeatedly compute hashes to grow the blockchain and the longest chain is considered authoritative Allows possibility of forks, with two mitigation methods: time to grow the chain (block time) must be reasonably high, and applications must wait several blocks to ensure their transaction remains on the authoritative chain Algorand faces 3 challnges: 1. Avoid Sybil attacks 1. Accomplished by assigned a weight to each user based on the money in their account 2. Their new Byzantine Agreement protocol BA(star) must scale to millions of users 1. Consensus by committee, with members chosen randomly based on users' weights 3. Resilient to adversary disconnecting users 1. Committee members picked in a private and non-interactive way by using a VRF that can be inputted with a private key and blockchain info 2. Committee members also speak once, then is transitioned out and is not used in any more consensus # Related Work **Byzantine Consensus** - BA protocols have been used to replicate a service across a small group of servers, like [[PBFT]] Most of these rely on a fixed set of servers determined ahead of time [[Algorand]] does not rely on a fixed set of servers **(does this mean dynamic participation? unsure)** [[HoneyBadger]] shows how BFT can built a crypto by using a set of servers to be in charge of reaching consensus on set of approved transactions Not decentralized, set of servers is fixed from the start [[Stellar]] uses trust quorums that create a trust hierarchy. Consistency ensured as long as all transactions share at least one transitively trusted quorum of users, with sufficiently many being honest With the leader selection in the way it is, meaning non-existent, as long as an attacker controls less than 1/3 of ALGO, the probability of forks is negligible **CHECK THIS** # Goals and Assumptions Algorand allows users to agree on an ordered log of transactions and achieves two goals: 1. **Safety:** All users agree on the same transactions with overwhelming probability 1. If one honest user accepts transaction A, then any future transactions accepted by honest users will appear in a log that already contains A 2. **Liveness:** Makes progress under additional assumptions about network reachability **Assumptions** Fraction of money held by honest users above 2/3 *Strong synchrony assumption for liveness*: Most honest users (95%) can send messages that will be received by most other honest users within a known time bound *Weak synchrony assumption for safety:* In every period of length b, there must be a strongly synchronous period of length s<b (b can be a day or week, s can be a few hours) Assumes loosely synchronized clocks across all users to recover liveness after weak synchrony # Overview Each user has a public key Algorand maintains a log of transactions - the blockchain Blockchain grown in asynchronous rounds, similar to Bitcoin Every round sees a new block appended to the chain Algorand nodes/users communicate through a gossip protocol Each user collects a block of pending transactions they hear about in case they are chosen to propose the next block BA(star) used to reach consensus on each of the pending blocks BA* executes in steps, communicates over the same gossip protocol, and produces a new agreed-upon block Can produce both *final* consensus and *tentative* consensus If one user reaches *final consensus*, any other user that reaches either type of consensus in the same round must agree on the same block value, regardless of synchrony assumption Ensures safety, since all future tx will be chained to this final block. *Thus*, a transaction is confirmed when its block reaches final consensus *Tentative consensus* means other users may have reached tentative consensus on a different block, as long as no user reached final consensus User will confirm transaction from tentative block only if and when a successor block reaches final consensus Tentative consensus produced in two cases: 1. If the network is strongly synchronous, there's a small chance an adversary can cause BA* to reach tentative consensus on a block 1. In this case BA* will not reach consensus on two different blocks but is unable to confirm strong synchrony. In a few rounds, Algorand will reach final consensus on a successor block and confirm earlier transactions 2. In weakly synchronous network, BA* can reach tentative consensus on two blocks, creating multiple forks 1. To recover liveness, Algorand periodically invokes BA* to reach consensus on which fork should be used going forward. 2. Once strong synchrony regained, Algorand will choose one of the forks and reach final consensus on a subsequent block **Gossip Protocol** Each user selects a small random set of peers to gossip messages to **Block Proposal** All users execute cryptographic sortition to determine if they're selected to propose a block in a given round Sortition ensures a small fraction of users are randomly selected, weighted by account balance, and provides each user with a priority There could be multiple users selected to propose a block, so the priority determines which block everyone should adopt Selected users distribute their block of pending transactions through the gossip protocol with their priority and proof **Agreement using BA**** Block proposal does not guarantee that all users received the same block, so BA* is used to reach consensus on a single block Each user initializes BA* with the highest-priority block they received It is then executed in repeated steps, beginning with sortition where all users check if they have been selected as committee members in that step Committee members then broadcast a message including their proof of selection These steps repeat until in some step enough users in the committee reach consensus **Efficiency** When the network is strongly synchronous, BA* guarantees that if all honest users start with the same initial block, then BA* establishes final consensus over that block and terminates precisely in 4 interactive steps between users. If there's a particularly lucky adversary, all users reach consensus on next block within expected 13 steps # Cryptographic Sortition Algorithm for choosing a random subset of users according to per-user weights Given a set of weights $w_{i}$ and the weights of all users W, the probability that user i is selected is proportional to $w_{i}$/W Randomness comes from a publicly known seed ## Selection Procedure Requires role parameter and number of role holders that tells if the user could be a block proposer or part of the committee at a certain step of BA* ![[Pasted image 20230827090032.png]] Since it uses user's private key, an adversary does not know if a user was chosen or how many times ## Choosing the Seed Each round requires a seed that is publicly known but not controlled by adversary Seed for r determined using VRFs with seed of r-1 If a block doesn't contain a valid seed, users treat the entire proposed block as if it were empty and use a cryptographic hash function to compute the associated seed as the hash of last round's seed with the round number ![[Pasted image 20230827090521.png]] ## Choosing $sk_{u}$ well in advance of the seed Computing r's seed requires that every user's secret key is chosen well in advance of the selection seed used in that round When network is not strongly synchronous, attacker can drop proposals and force users to agree on empty blocks This is why we need weak synchrony assumption - to ensure sufficiently many blocks to be created to ensure that at least one was honest. Algorand looks back b-time for keys and weights Only issue is that it doesn't have up to date balances for users # Block Proposal 26 proposers are chosen in the sortition to ensure a block gets proposed in each round **Minimizing unnecessary block transmissions** Risk of choosing several proposers is that each will gossip their own proposed block, creating a significant communication cost Users can learn about the highest priority proposer and discard other proposed blocks **Waiting for block proposals** Each user must wait a certain amount of time to receive block proposals via the gossip network Uses a timeout on the order of a minute, after which the user will propose an empty block **Malicious Proposers** If some block proposers are malicious, worst-case is they get different users to initialize BA* with different blocks, which could cause Algorand to reach consensus on an empty block Only really happens when malicious proposer is highest priority, and they can only propose an empty block # BA⋆ Consists of two phases 1. Reduces the problem of agreeing on a block to agreement on one of two options 2. Reaches agreement on one of these options: either agreeing on a proposed or empty block Each phase has several interactive steps First phase always takes two steps Second phase takes two if the highest-priority block proposer was honest and 11 if malicious and colluding 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) In common case, when the network is strongly synchronous and the highest-priority block proposer was honest, BA* reaches final consensus by using its final step to confirm that there cannot be any other agreed-upon block in teh same round - Otherwise, BA* may declare tentative consensus if it cannot confirm the absence of other blocks due to possible network asynchrony ## Main procedure of BA* 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. context has the seed for sortition, user weights, and last agreed-upon block ![[Pasted image 20230827093554.png]] ## Voting Algo 4 shows the CommitteeVote() function, checking if a user is selected for the committee in a given round and step ![[Pasted image 20230827093654.png]] **Counting Votes (Algos 5 and 6)** CountingVotes() (Algo 5) reads messages that belong to the current round and step from the incomingMsgs ![[Pasted image 20230827093937.png]] Processes votes by calling ProcessMsg() for every message (Algo 6) Ensures the vote is valid and returns the number of votes associated with the value contained in the message ![[Pasted image 20230827093957.png]] As soon as one value has more than T * $\tau$ votes, where tau is the expected number of users that Sortition() selects for the committee and T is a fraction of that expected committee size (>2/3) that defines BA*'s voting threshold Threshold ensures that if one honest user's CountVotes() returns a particular value, then all other honest users will return either the same value or TIMEOUT, even under weak synchrony assumption. ## Reduction Converts the problem of reaching consensus on an arbitrary value (block hash) to reaching consensus on one of two values: Either a specific proposed block hash, or the hash of an empty block In the first step, each committee member votes for teh hash of the block passed to the function by BA*. - In the second step, committee members vote for the hash that received at least T * $\tau$ votes in the first step, or the hash of the empty block if no hash received enough votes Reduction() ensures that there is at most one non-empty block that can be returned by Reduction() for all honest users ![[Pasted image 20230827101632.png]] ## Binary Agreement BinaryBA*() reaches consensus on either the ash passed to it or the hash of an empty block Replies on reduction() to ensure that at most one non-empty block hash is passed to BinaryBA*() by all honest users **Safety with strong synchrony** In each step of the function, a user who has seen more than T * $\tau$ votes for some value will vote for that same value in the next step, if selected If not value receives enough votes, the function chooses teh next vote in a way that ensures consensus in a strongly synchronous network - Specifically, a user may receive votes from an adversary that push the votes observed by A past the threshold, but the adversary may not send the same votes to other users. - Consequently, A returns consensus on a block, but other users timed out in that step - Crucial that BinaryBA* chooses the votes for the next step in a way that will match the block already returned by A - To accomplish, every return statement is coupled with a check for timeout that sets the next-step vote to the same value that could've been returned - Also crucial that BinaryBA is able to collect enough votes in the next step to carry forward the value that A has already reached consensus on - If there are many users like A that have already returned consensus, the function may not have enough users to push CountVotes in the next step past the threshold - To avoid this problem, whenever a user returns consensus, that user votes in the next three steps with the value they reached consensus on - In common case, when network is strongly synch and proposer is honest, BinaryBA*() will start with the same block hash for most users, and will reach consensus in the first step. ![[Pasted image 20230827102451.png]] **Safety with weak synchrony** If the network is not strongly synchronous, BinaryBA*() may return consensus on two different blocks Ex. suppose that in step 1 of BinaryBA*(), all users vote for a block hash, but only one honest user receives those votes. In this case, A will return consensus, but all other users will move to the next step Now, the other users vote for the hash again, since CountVotes returned a timeout. Assume the network drops all of these votes Finally, users vote for empty_hash in the third step and all votes are delivered. Users will keep voting for empty_hash until next iteration of the loop, at which point they reach consensus on empty_hash Undesirable outcome: returned consensus on two different hashes to different honest users Final and tentative consensus solves this problem Final consensus means BA*() will not reach consensus on any other block for that round Tentative consensus means that BA*() was unable to guarantee safety, either because of network asynchrony or due to a malicious block proposer BA*() designates consensus on V as final if binaryBA*() reached consensus on V in the very first step, and if enough users observed this consensus being reached. Specifically, BinaryBA*() sends out a vote for the special final step to indicate that a user reached consensus on some value in the very first step, and BA*() collects these votes to determine whether final consensus was achieved. In a strong synch network with an honest block proposer, BinaryBA*() will reach consensus in the first step, most committee members will vote for the consensus block in the special FINAL step in BinaryBA*(), and will receive more than a threshold of such votes in BA*(), thus declaring the block as final. FINAL step analogous to final confirmation in other Byzantine protocols Guarantees safety because a large threhold of users have already declared consensus on a certain value and will note vote for any other value in the same round. **Getting unstuck** Consensus could get stuck if two groups are voting for different values Third step of BinaryBA accounts ofr this by pushing towards accepting either block hash or empty hash based on a random value that's predominantly the same for all users. ## Committee Size BA* has two parameters to get a sufficiently honest committee: 1. $\tau$, controls the expected committee size 2. T, which controls the number of votes needed to reach consensus We want T to be as small as possible for liveness, but that means $\tau$ needs to be larger to ensure an adversary does not obtain enough votes by chance Choose a T and $\tau$ for FINAL step, ensuring an overwhelming probability of safety regardless of strong synchrony, and values for all other steps, achieving a reasonable trade-off between liveness, safety, and performance For $T_{step}, \tau_{step}$, BA* requires 1/2g+b $\leq T_{STEP}*\tau_{STEP}$ and g > $T_{STEP}*\tau_{STEP}$ , where g are honest committee members and b are malicious tStep = 2000, Tstep = .685 tFinal = 10000, Tfinal = .74 # ALGORAND Built on top of previously discussed primitives and addresses some higher-level issues ## Block Format Blocks consist of a list of txs along with the metadata needed by BA* ## Safety and Liveness Algorand confirms transactions only when the appear in a final block and relies on BA* to reach consensus on blocks in the ledger Final blocks guarantee safety, since no other block can have reached consensus in the same round If network isn't strongly synch, BA* may create forks, which impact liveness Algorand periodically proposes a fork that all users should agree on and uses BA* to reach consensus on whether all users should switch to this fork. Algorand users passively monitor all BA* votes and keep track of all forks Recovery protocol runs hourly to propose one of the forks that everyone should agree on Users propose a fork using block proposal mechanism Fork proposer proposes an empty block as part of the longest fork. Longest fork ensures it will include all final blocks For BA* to reach consensus, all Algorand users must use the same seed and user weights, so before any fork occurred. This is where the weak synchrony assumption comes into play. In every period of length b, there must be a strongly synchronous period of length s < b, where s is a few hours or so. Using block timestamps, Algorand quantizes time into b-long periods and finds the most recent block from the next-to-last complete b-long period. Algorand uses the seed from this block and weights from the last block that was agreed upon at least b-long time before it ## Bootstrapping Common genesis with initial sortition seed is given to all users New users that join have to get caught up to current state, defined to be the result of a chain of BA* consensus outcomes Algorand generates a *certificate* for every block that was agreed upon by BA* (including empty blocks) that is an aggregate of the votes from the last step of BinaryBA*() (not including final step) that would be sufficient to allow any user to reach the same conclusion by processing these votes Users validate prior blocks in order ## Communication Gossip protocol and message relaying is a little slower than theorhetical, but still sufficient to prevent DoS **Scalability** Dissemination time grows logarithmically in the number of users