[6009805681b416f34dcae012\_Avalanche%20Consensus%20Whitepaper.pdf](https://assets.website-files.com/5d80307810123f5ffbb34d6e/6009805681b416f34dcae012_Avalanche%20Consensus%20Whitepaper.pdf) [[Avalanche]] consensus mechanism TODO: Figure out how revertable transactions are # Abstract Introduces the Snow family of leaderless BFT protocols Build around metastable mechanism via network sampling Provide strong *==probabilistic==* (figure out what this means) safety guarantee Does not require accurate knowledge of all participants # Introduction Traditional consensus rely on all-to-all comms - difficult to scale Nakamoto consensus provide probabilistic safety guarantee and may revert with some probability $\epsilon$ Snow are inspired by gossip algorithms Repeatedly samples the network at random and steer correct nodes toward a common outcome Irreversibility implies a sufficiently large portion of the network has accepted a proposal and a conflict proposal will not be accepted with any higher than negligible ($\epsilon$) probability Snow is more efficient when fraction of Byzantine nodes is small, and can be parameterized to tolerate more than a third of Byzantine nodes by trading off liveness # Model and Goals ### Key Guarantees #### Safety Adopts $\epsilon$-safety guarantee, which is probabilistic but strong enough #### Liveness Non-zero guarantee of termination within a bounded amount of time, similar to longest-chain protocols For [[Nakamoto Consensus]], the number of required blocks for a transaction increases exponentially with the number of adversarial nodes, with an asymptote at f = n/2 wherein the number is infinte *Formal Guarantees* Lets the system be parametrized for an $\epsilon$ safety failure probability under a maximum expected f of adversarial nodes Snow provides the following guarantees **P1: Safety** - When decisions are made by any two correct nodes, they decide on conflicting transactions with negligible probability <= $\epsilon$ **P2: Liveness (Upper Bound)** - Snow protocols terminate with a strictly positive probability within $t_{max}$ rounds **P3: Liveness (Strong Form)** - If $f \leq O(\sqrt{ n })$, then Snow protocols terminate with high probability ($\geq 1-\epsilon$) in O(log n) rounds #### Network Fix the distribution of message delay to the exponential distribution #### Achieving Liveness Classic consensus that works with asynchrony doesn't get stuck in a voting phase Because vote initiator always polls votes from all known participants and waits for n-f responses In Snow, subsampling is used, so a single sample could select a majority of adversarial nodes and get stuck waiting for responses Protocols are synchronous to guarantee liveness [[Nakamoto Consensus]] is synchronous, where the required difficulty of PoW is dependent on max network delay #### Adversary Computationally bounded but knows all state and can modify strategy at any given time #### Additional Assumptions No assumption that all members of network are known to all participants Rather there may temporarily be some discrepancies in network view. # Protocol Design Start with non-BFT protocol called Slush, and build up to Snowflake and Snowball All based on same majority-based metastable voting mechanism ## Slush: Introducing Metastability Not tolerant to BFs, only crash faults Operation described using two conflicting colors, red and blue - Node starts in uncolored state - When it receives a tx from a client, it updates its color to the one carried in the tx and initates a query - This means it chooses a small, constant-sized sample of the network - When receiving a query, an uncolored node adopts the color in the query, responds with that color, and initiates its own query - Colored node responds with its current color - When querying node collects k responses, it checks if a fraction $\geq \alpha$ are for the same protocol, where $\alpha > floor\left( \frac{k}{2} \right)$ is a protocol param - If threshold is met and sampled color differs from node's color, node flips to that color - It then goes back to the query and does another round for a total of m rounds - Node decides on color it ends up with at time m Properties of interest: 1. almost memoryless 2. Every round involves sampling a small slice of network instead of every participant 3. Makes progress under any network configuration since random perturbations in sampling will cause on color to gain a slight edge that will grow 4. If m is chosen high enough, Slush ensures all nodes will have a high probability of being colored identically Does not provide strong safety in presence of Byzantine nodes An adversary can attempt to flip nodes to opposite and keep the network in balance to prevent a decision This is addressed in following BFT protocol by introducing more state storage ## Snowflake: BFT Augments Slush with a counter that captures the strength of a node's conviction in its current color Per-node counter stores how mnay consecutive samples of the network by that node have yielded the same color Node accepts the current color when its counter reaches $\beta$, a new security parameter Upon every color change, node resets counter to 0 Upon every successful query that yields more than alpha responses for the same color as the node, the node increments the count There exists an irreversible state after which a decision is irreversible ![[Pasted image 20230909163325.png]] ## Snowball: Adding Confidence Snowflake's notion of state is ephemeral: the counter gets reset with every color flip Snowball adds *confidence counters* that capture the number of quieries that have yielded a threshold result for their corresponding color Node decides if it gets $\beta$ consecutive chits for a color It only changes preference based on total accrued confidence To summarize, the differences are: 1. Upon every successful query, the node increments its confidence counter for that color 2. A node switches colors when the confidence in its current color becomes lower than the confidence value of the new color # Analysis Generally accept the validity of the arguments given for safety and liveness Every correct node implements a decision function that outputs 1 when the node detects that the network has reached an irreversibility state at time t for an output Probabilistic, so it can fail, but negligible in theory # Peer-to-Peer Payment System Liveness and safety guaranteed for virtuous transactions Rogue transactions that conflict with one another don't have the same guarantees and may stall in the network ## Avalanche: Adding a DAG [[Avalanche]] consists of multiple single-decree Snowball instances instantiated as a multi-decree protocol that maintains a dynamic, append-only DAG of all known transactions DAG has a single sink - genesis vertex Maintaining a DAG improves efficiency and security (rendering past decisions difficult to undo without approval of correct nodes) Conflict set is set of transactions that spend the same funds, out of which only one can be accepted A snowball instance is instantiated for each conflict set and nodes are queried to see which one they prefer If more than a threshold of responders vote positively, the tx is said to collect a chit Nodes then computer teh confidence as the total number of chits in the progeny of that transaction ## Avalanche: Specification Each correct node keeps track of all txs it has learned about in set $T_{u}$, partitioned into mutually exclusive conflict sets. Conflicting transactions have the equivalence relation because they are equivocations spending the same funds Each node implements an event-driven state machine centered aroudn a query that seves both to solicit votes on each tx and notify other nodes of the existence of newly discovered transactiosn Leaves determining the acceptance point of a transaction to the application ## Multi-Input UTXO Transactions An unspent transaction output graph that captures spending dependency is used to realize the ledger for the payment system Inherit the transaction and address mechanisms from Bitcoin Txs consist of multiple inputs and outputs with corresponding redeem scripts # Evaluation ## Comparison to Other Systems Comparing to algorand and conflux Others only present a sketch of protocols and don't offer practical implementation or evaluation results [[Algorand]] committee-scale consensus algo is quorum-based Byzantine agreement Avalanche performs much better in both throughput and latency since Algorand uses a VERF to elect committees and maintains a fully ordered log while Avalanche establishes only a partial order # RELATED WORK SECTION IS GREAT