Scalable and Probabilistic Leaderless BFT Consensus through Metastability

Team Rocket; Maofan Yin; Kevin Sekniqi; Robbert van Renesse; Emin Gün Sirer

Source-linked AI summary

Scalable and Probabilistic Leaderless BFT Consensus through Metastability

Team Rocket, Maofan Yin, Kevin Sekniqi, Robbert van Renesse, Emin Gün Sirer

arXiv:1906.08936v2Jun 21, 2019cs.DC

TL;DR

The paper addresses scalable Byzantine consensus without the communication, energy, and membership-knowledge costs of classical and proof-of-work systems. It introduces Snow’s randomized, metastable protocols and applies them to Avalanche, concluding that the resulting systems scale well, achieve high throughput and quick finality, and degrade gracefully under adversarial attacks.

Problem
Classical consensus requires quadratic communication and accurate membership knowledge, while Nakamoto protocols are costly, wasteful, and non-quiescent.
Method
Snow repeatedly samples the network and uses metastable decisions to steer correct nodes toward a common irreversible outcome, with Avalanche applying Snowball instances through a DAG.
Results
The paper concludes that the protocols scale well, achieve high throughput and quick finality, work without precise membership knowledge, and degrade gracefully under catastrophic adversarial attacks.
Takeaways & Limitations
Snow provides a consensus design that combines probabilistic safety with quiescent operation, efficient communication, and tolerance for imperfect membership knowledge.
Takeaways & Limitations
The analysis fixes message delays to an exponential distribution, limiting the modeled asynchronous network setting.

Abstract

from arXiv · show

This paper introduces a family of leaderless Byzantine fault tolerance protocols, built around a metastable mechanism via network subsampling. These protocols provide a strong probabilistic safety guarantee in the presence of Byzantine adversaries while their concurrent and leaderless nature enables them to achieve high throughput and scalability. Unlike blockchains that rely on proof-of-work, they are quiescent and green. Unlike traditional consensus protocols where one or more nodes typically process linear bits in the number of total nodes per decision, no node processes more than logarithmic bits. It does not require accurate knowledge of all participants and exposes new possible tradeoffs and improvements in safety and liveness for building consensus protocols. The paper describes the Snow protocol family, analyzes its guarantees, and describes how it can be used to construct the core of an internet-scale electronic payment system called Avalanche, which is evaluated in a large scale deployment. Experiments demonstrate that the system can achieve high throughput (3400 tps), provide low confirmation latency (1.35 sec), and scale well compared to existing systems that deliver similar functionality. For our implementation and setup, the bottleneck of the system is in transaction verification.

1 Introduction

The paper introduces Snow, a leaderless consensus family that uses randomized network sampling and metastable decisions to provide probabilistic safety, efficiency, and scalability. It applies Snowball within a DAG to build Avalanche, a peer-to-peer payment system.

1 Introduction: Snow provides tunable probabilistic safety while avoiding proof-of-work, remaining quiescent, and requiring only O(1) communication per round and O(logn) rounds in expectation.The family also tolerates discrepancies in participants’ membership knowledge, unlike classical protocols that require accurate knowledge of n.
1 Introduction: Snow’s safety degrades smoothly beyond the Byzantine threshold f and exposes safety–liveness tradeoffs, including parameterizations tolerating more than one-third Byzantine nodes by sacrificing liveness.Efficiency is higher when the Byzantine fraction is small.
1 Introduction: Avalanche executes multiple Snowball instances over a DAG, reducing per-node cost from O(logn) to O(1) by piggybacking decisions and streamlining non-conflicting transactions.The paper presents this construction as a practical peer-to-peer payment system.
1 Introduction: Snow introduces randomized sampling and metastable decision-making as a new consensus design paradigm.The protocol repeatedly samples the network and steers correct nodes toward a common, effectively irreversible outcome.
1 Introduction: The paper’s central contribution is a family of efficient, probabilistically safe consensus protocols based on randomized sampling and metastable decisions.The approach targets scalable consensus without the costs and continuous participation required by Nakamoto-style proof-of-work systems.

2 Model and Goals

The model provides probabilistic safety and bounded-probability liveness under Byzantine, asynchronous, and partially known-network conditions. Its guarantees include negligible conflicting decisions and high-probability termination in O(logn) rounds when f ≤ O(√n).

2 Model and Goals: Snow’s probabilistic safety degrades smoothly as Byzantine participation exceeds f, unlike classical quorum safety, which fails once its threshold is exceeded.The supplied Figure 1 compares this behavior with classical BFT and Bitcoin’s six-block finality choice.
2 Model and Goals: Snow protocols ensure that two correct nodes decide conflicting transactions only with negligible probability.The system is parameterized by a target ε safety failure probability and an expected maximum of f adversarial nodes.
2 Model and Goals: Snow protocols terminate with strictly positive probability within the bounded execution limit tmax.The formal model requires O(logn) < tmax < ∞.
2 Model and Goals: If f ≤ O(√n), Snow protocols terminate with probability at least 1−ε in O(logn) rounds.This is the strong liveness guarantee under the stated adversarial bound.
2 Model and Goals: The model uses exponentially distributed message delays rather than unrestricted asynchronous scheduling.Correct-node scheduling can still delay a local round arbitrarily, while adversarial nodes may execute arbitrarily fast.
2 Model and Goals: The system permits temporary discrepancies in network views and relies on safe bootstrapping to obtain a statistically unbiased view with sufficiently many correct nodes.It does not assume that every participant knows the complete membership list or that a PKI exists.

3 Protocol Design

The Snow family progressively strengthens gossip-based metastable consensus from non-Byzantine Slush to Snowflake and Snowball, using random subsampling and increasingly persistent state. These protocols trade communication efficiency, safety, and liveness through tunable parameters and provide probabilistic guarantees under Byzantine faults.

3 Protocol Design: Snow builds a family of single-decree protocols from Slush through Snowflake and Snowball, increasing robustness while retaining a common majority-based metastable voting mechanism.Slush is non-BFT, while later protocols add state to address Byzantine behavior.
3.1 Slush: Introducing Metastability: Each Slush round samples a small constant-sized random peer set, flips color when at least α responses agree, and repeats for m rounds before deciding.The threshold satisfies α > ⌊k/2⌋, where k is the sample size.
3.2 Snowflake: BFT: Slush lacks strong Byzantine safety because adversaries can flip nodes between colors and keep the network balanced, motivating additional node state.Snowflake adds a counter that records consecutive successful samples and accepts a color after β successes.
3.2 Snowflake: BFT: Correctly parameterized Snowflake can provide safety and liveness guarantees, with an irreversible state after which correct nodes adopt the same color with high probability.Snowflake resets its conviction counter whenever the node changes color.
3.3 Snowball: Adding Confidence: Snowball adds persistent confidence counters to Snowflake, changing preference according to accumulated confidence while deciding after β consecutive successful chits.Unlike Snowflake’s ephemeral counter, Snowball accumulates query support for each color.

4 Analysis

The analysis models Snow as a continuous-time stochastic process and identifies metastable irreversibility as the basis for probabilistic safety and liveness. Results show that majority drift rapidly suppresses reversal, while parameter choices and adversarial presence determine termination behavior.

Safety: Snow’s continuous-time analysis identifies an irreversibility state from which the network is unlikely to return to the minority outcome.The state-space reduction tracks the number of blue nodes and uses absorbing all-red and all-blue states.
Safety: As majority drift δ increases, the probability of moving toward the minority decreases exponentially fast for fixed α and k.The same trend holds when α increases with k fixed.
Safety: Snowflake detects irreversibility probabilistically, whereas Snowball adds confidence history to reduce random-sample perturbations and improve security.Snowball’s proof sketch uses martingale concentration to show majority confidence continues to grow after irreversibility.
Liveness: With positive buffer zone ψ, termination is finite with probability one and has positive probability within any bounded time when a proposal has at least α support.If ψ approaches zero or becomes negative, an adversary can stall termination by withholding responses, although safety may still hold.
Liveness: Non-conflicting transactions decide in O(logn) mixing time, while fully bivalent configurations achieve O(logn) rounds when Byzantine nodes are at most O(√n).The worst-case number of rounds increases when the adversary surpasses O(√n) nodes.

5 Peer-to-Peer Payment System

Avalanche turns repeated Snowball instances into a multi-decree payment protocol by maintaining an append-only DAG of transactions. The DAG batches voting, links transaction decisions, and introduces a tradeoff between faster progress and liveness risks from rogue parents.

5.1 Avalanche: Adding a DAG: Avalanche maintains a dynamic append-only DAG whose vertices instantiate multiple single-decree Snowball instances.A single vote on a DAG vertex implicitly votes for all transactions on its path to genesis.
5.1 Avalanche: Adding a DAG: The DAG improves efficiency and security by batching votes and intertwining transaction fates, but attaching transactions to undecided parents can risk liveness if those parents are rogue.Unlike direct graph-vertex voting, Avalanche builds confidence from chits, so rejected-side vertex flooding does not subvert the protocol.
5.1 Avalanche: Adding a DAG: Conflicting transactions form application-defined conflict sets, such as double-spends, from which only one transaction can be accepted.A virtuous transaction always has a singleton conflict set.
5.2 Avalanche: Specification: Avalanche batches queries through transaction progeny and requires positive responses for a transaction and its entire ancestry to be preferred.Each transaction is queried once, while confidence can grow as additional progeny chits accumulate.
5.2 Avalanche: Specification: Virtuous transactions can be accepted when they are the sole conflict-set member with confidence at least β1 or after β2 consecutive successful queries.Transactions blocked by problematic parents may be reissued with different parents.

6 Evaluation

Avalanche achieves high throughput and low latency in large-scale experiments, with throughput remaining nearly stable as the network grows. Signature verification is the main implementation bottleneck, while comparisons show competitive or better performance than existing systems.

6.2 Throughput: 6851 tps with batch size 20 and above 7002 tps with batch size 40 demonstrate high throughput using small batches.
6.3 Scalability: 1.34% throughput degradation occurs when the network grows 16× to n = 2000, reaching 6909 tps.
6.4 Bottlenecks: 2.6× higher throughput without signature verification identifies cryptographic verification as the current implementation bottleneck.
6.5 Latency: Most transactions confirm within approximately 0.3 seconds, with common latency around 206 ms and maximum observed latency around 0.4 seconds.
Over 3400 tps is sustained on up to 2000 nodes, while confirmation latency is 1.35 seconds.
6.7 Comparison: Avalanche exceeds 3400 tps without committees or proof-of-work and has lower latency than Bitcoin, Algorand, and Conflux in the reported comparison.

7 Related Work

Related consensus systems trade among scalability, communication cost, latency, leadership, membership assumptions, and energy use. The paper positions Avalanche against proof-of-work, quorum-based BFT, relaxed BFT, leader-based, and DAG-based approaches.

Bitcoin and other proof-of-work systems suffer low throughput, high latency, scalability bottlenecks, and substantial computational energy use.
Classical Byzantine agreement protocols commonly require precise membership knowledge and quorum communication, with PBFT requiring quadratic message exchanges.
Relaxed BFT proposals obtain probabilistic liveness or higher availability by changing failure assumptions or consistency guarantees.
Leader-based systems such as Tendermint and HotStuff retain leader-related limitations, while Ripple relies on collectively trusted sub-networks.
DAG-based systems including GHOST, SPECTRE, and PHANTOM use alternative chain or transaction-ordering rules, with some retaining proof-of-work.

8 Conclusion

The paper concludes that Snow protocols combine probabilistic consensus with high efficiency, scalability, and quick finality. It also identifies adversarial scheduling, realistic adversary models, and initialization as directions for further work.

Snow protocols are presented as efficient and robust, scaling without precise membership knowledge while providing high throughput, quick finality, and graceful degradation under adversarial attacks.
The work contributes a new consensus-protocol family together with mathematical tools for analyzing it.
Future work includes adversarial network scheduling, realistic bounded-adversary guarantees, and improved initialization for multi-value consensus.

A Analysis

The appendix analyzes Slush, Snowflake, and Snowball, providing the analysis context for the Snow protocol family.

The appendix analyzes the Slush, Snowflake, and Snowball protocols.

A.1 Preliminaries

The preliminaries model subsampled voting with hypergeometric probabilities, concentration bounds, and sub-martingale tools for analyzing consensus dynamics.

A.1 Preliminaries: Hypergeometric sampling models the number of blue votes in a size-k sample from a network of n nodes, with threshold probability H(N,x,k,α).The sample is without replacement, and x denotes the population count of blue nodes.
A.1 Preliminaries: Hoeffding tail bounds and Kullback–Leibler divergence bound deviations of hypergeometric samples from their mean.
A.1 Preliminaries: The expected number of blue votes is kp when blue support has population ratio p = x/n.
A.1 Preliminaries: Sub-martingale concentration bounds constrain stochastic processes whose successive changes are almost surely bounded.

A.2 Slush

Slush is analyzed as a continuous-time stochastic voting process whose state is the number of blue nodes, with absorbing consensus states and exponentially small reversal probability after drift.

A.2 Slush: The process state records the total number of blue nodes, with birth and death rates determined by thresholded hypergeometric sampling.States 0 and c are absorbing, while λ_i governs transitions toward blue and μ_i toward red.
A.2 Slush: Once the network drifts from a balanced state, the probability of reverting is exponentially small.The paper derives a closed-form reversibility expression that is strictly below the earlier Chvátal bounds.
A.2 Slush: The expected convergence time is characterized as the mean time to reach either absorbing state.The analysis defines τ_z as the expected time to reach all-red or all-blue from state z.
A.2 Slush: Slush reaches an absorbing all-red or all-blue state in finite time almost surely.The result follows from every transient state having a nonzero probability of absorption.

A.3 Snowflake

Snowflake extends Slush to Byzantine sampling by tracking consecutive majority confidence and analyzing adversarial reversibility under a bounded-time interpretation.

A.3 Snowflake: Snowflake includes Byzantine nodes in samples and tracks β, the number of consecutive same-color majority samples, through its decision function D(∗).An adversarial strategy A(S_t) can modify node colors based on the network configuration and scheduled nodes.
A.3 Snowflake: Because an adversary with f ≥ α can reverse a converged system with positive probability, safety is interpreted over a bounded time horizon.If reversal from an all-blue state is exponentially unlikely, the expected attack time is correspondingly exponential as a lower bound.
A.3 Snowflake: The Snowflake analysis conditions reversibility on the first node deciding blue, after which the adversary continually votes red.The resulting probabilities account for additional blue commitments and the adversary’s fixed strategy.
A.3 Snowflake: For selected k and β, the analysis identifies the minimum α needed for strong irreversibility.
A.3 Snowflake: Snowflake terminates in O(logn) rounds with high probability when f < O(√n) and α = ⌊k/2⌋+1.The proof attributes the logarithmic bound to mixing time after sampling creates an expected O(√n) network bias.

A.4 Snowball

Snowball extends Snowflake with growing confidence, while Avalanche applies conflict-set voting and view-split analysis to early commitment, liveness, and churn.

A.4 Snowball: In Snowball, majority-value confidence grows faster than minority confidence with high probability, producing drift away from the minority as time advances.The paper models the protocol as a two-urn system whose urns are sub-martingales.
A.4 Snowball: Avalanche models each conflict set as a Snowball instance, where transactions vote along their ancestry paths.This structure can cause virtuous transactions depending on rogue transactions to inherit their fate.
A.4 Snowball: For n = 2000, α = 0.8k, and ε ≪ 10^-9, the birth-process analysis supplies a lower bound for β1 in the fast-decision branch.The resulting bound supports the β choice used in evaluation, with a small number of iterations sufficient for the safe early commitment predicate.
A.4 Snowball: A synchrony heuristic improves liveness by using O(logn) proposal-gossip rounds before deterministic selection and consensus.A second O(logn)-round phase helps correct nodes obtain approximately the same proposal set.
A.4 Snowball: With network-view splits, there is a maximal churn size τ below which equivocating finalizations occur with probability less than ε.As τ increases, the two views become more independent and adversarial influence increases.