Frosty: Bringing Strong Liveness Guarantees to the Snow Family of Consensus Protocols

Summary. Snowman is the consensus protocol run by blockchains on Avalanche and is part of the Snow family of protocols. A major advantage of Snowman is the low communication overhead: each consensus decision only requires an expected constant communication overhead per validator in the “common” case that the protocol is not under substantial attack. This low overhead is the key property that would enable a consensus protocol to scale to n = 10000 or more independent validators. On the other hand, the two following concerns have remained: 

  1. Providing formal proofs of consistency for Snowman has presented a serious challenge.
  2. Liveness attacks exist in the case that a Byzantine adversary controls a sufficiently large proportion (more than O(sqrt(n)) of the validators, slowing termination to more than a logarithmic number of steps.

In this post, we briefly discuss a recent paper that addresses the two issues above by providing a formal consistency proof for Snowman (showing that finalized transactions will not be reverted) and then describing how to augment Snowman with a “liveness module” that can be triggered in the case that a substantial adversary launches a liveness attack. 

Background. Since Bitcoin was announced to the world in 2008, there has been a race to develop consensus protocols that work efficiently ‘at scale’. In concrete terms, this means looking to minimize the latency and communication complexity per consensus decision as a function of the number of validators (sometimes called ‘miners’ in the context of proof-of-work protocols). Unfortunately, a classic result of Dolev and Reischuk from 1985 presents a fundamental barrier in this regard. The  Dolev-Reischuk bound asserts that deterministic protocols that can tolerate a Byzantine (i.e. arbitrary) adversary of size O(n) must necessarily suffer a quadratic blow-up in communication cost as the size of the network grows. It is precisely this relationship that makes these protocols susceptible to considerable slowdown when the number of validators is large.

Probabilistic sortition. One approach to dealing with this quadratic blow-up in communication cost, as employed by protocols such as Algorand, is to utilize probabilistic sortition. Rather than have all validators participate in every consensus decision, the basic idea is to sample a committee of sufficient size that the proportion of adversarial committee members is almost certainly close to the proportion of all validators that are adversarial.  Sampled committees of constant bounded size can then be used to implement consensus, thereby limiting the communication cost. In practical terms, however, avoiding adversarial control of committees requires each committee to have a number of members sufficient that the quadratic communication cost for the committee is already substantial, e.g. Algorand requires committees with k members, where k is of the order of one thousand, meaning that k^2 is already large.

The Snow family of consensus protocols. The original Avalanche whitepaper described a family of consensus protocols that provide an alternative approach to limiting communication costs. These protocols are all based on a common approach that is best described by considering a binary decision game. For the sake of simplicity, consider the Snowflake protocol which uses three parameters: k, alpha > k/2, and beta (in the whitepaper, other variants such as the Slush and Snowball protocols are also described). For the sake of concreteness, think of k as being a small number, less than 100.  Suppose that each validator begins with an initial color, either red or blue. Each validator, p say, then proceeds in rounds. In each round, p randomly samples p validators from the total population and asks those validators to report their present color. If at least alpha of the reported values are the opposite of p’s present color, then p adopts that opposite color.  If p sees beta consecutive rounds in which at least alpha of the reported values are red, then p decides red (and similarly for blue). 

The outcome of this dynamic sampling process can be informally described as follows when the adversary is sufficiently bounded. Once the proportion of the population who are red, say, passes a certain tipping point, it holds with high probability that the remainder of the (non-adversarial) population will quickly become red (and symmetrically so for blue). If beta is set appropriately, then the chance that any honest (non-adversarial) validator decides on red before this tipping point is reached can be made negligible, meaning that once any honest validator decides on red (or blue), they can be sure that all other honest validators will quickly decide the same way. The chance that honest validators decide differently can thus be made negligible through an appropriate choice of parameter values. If honest validators begin heavily weighted in favor of one color, then convergence on a decision value  will happen very quickly, while variance in random sampling is required to tip the population in one direction in the case that initial inputs are evenly distributed. 

While the discussion above considers a single binary decision game, the “Snowman” protocol shows that similar techniques can be used to efficiently solve State Machine Replication (SMR) (i.e. to build a full blockchain that continuously finalizes transactions). The transition from simple consensus (Byzantine Agreement) to an efficient SMR protocol is non-trivial, and is described in detail in the paper.  A major benefit of the approach is that it avoids the need for all-to-all communication. In an analysis establishing that there is only a small chance of consistency failure (i.e. that honest processors will finalize the same transactions except with small probability), the value of k can be specified independent of the number of validators n, and each round requires each validator to collect reported values from only k others. 

The new results in the paper. The Snowman protocol is presently used by the Avalanche blockchain to implement SMR. However, the two following concerns have remained: 

  1. Providing formal proofs of consistency for Snowman has presented a serious challenge. 
  2. Liveness attacks exist in the case that a Byzantine adversary controls a sufficiently large proportion (more than O(sqrt(n)) of the validators, slowing termination to more than a logarithmic number of steps.

The new paper addresses the two issues above. With respect to issue (1), the paper: 

  • Describes a variant of Snowflake, called Snowflake+.
  • Gives a complete specification of a version of Snowman that builds on Snowflake+. 
  • For appropriate parameter values, gives a simple proof of consistency for the resulting Snowman protocol.
  • Describes a variant of Snowflake+ called Error-driven Snowflake+, that can be used to give very low latency in the “common case” that there is no substantial attack. 

With regard to issue (2), it is worth noting that malicious liveness attacks on Avalanche have not been observed to date. It is certainly desirable, however, to have strong guarantees in the case that a large adversary launches an attack on liveness.  The approach taken in the paper is therefore to strike a practical balance. More specifically, the aim is to specify a protocol that is optimized to work efficiently in the “common case” that there is no substantial Byzantine attacker, but which also provides a “fallback” mechanism in the worst case of a substantial attack on liveness.

With that aim in mind, the paper describes how to supplement Snowman with a “liveness module”. The basic idea is that one can use Snowman to reach fast consensus under normal operation, and can then trigger an “epoch change” that temporarily implements some standard quorum-based protocol to achieve liveness in the case that a substantial adversary attacks liveness. In the (presumably rare) event that a substantial adversary attacks liveness, liveness is thus ensured by temporarily forgoing the communication complexity advantages of Snowman during normal operation. The difficulty in implementing such a module is to ensure that interactions between the different modes of operation do not impact consistency. The paper gives a formal proof that the resulting protocol, called Frosty, is consistent and live, except with small error probability. 

The full paper can be found at https://arxiv.org/abs/2404.14250 and is a collaboration between Andrew Lewis-Pye (London School of Economics) and Aaron Buchwald, Stephen Buttolph, Patrick O’Grady and Kevin Sekniqi (Ava Labs). 

SHARE //
NEXT UP//
Gaming

Elixir Games Announces Acquisition of RoboKiden and Strategic Partnership with Ava Labs

NFT

Artist Spotlight: Ed Balloon Blending Web2 and Web3 at Avalanche Park

Gaming

Gamestarter introduces ‘GameChain’ powered by Avalanche

Institutions

Wine Capital Fund Leverages Oasis Pro and Avalanche to Make Fine Wine an Investable Asset Class

Gaming

LiveDuel Brings Web3 Sports Betting to Avalanche

Community

Introducing Core’s Airdrop Tool: A Free Way to Distribute Tokens and Reward Your Community on Avalanche

NFT

Salvor Secures Avalanche Rush with a $1M Incentive Grant to Build Out Avalanche’s Prime NFT Lending Platform

Gaming

Avalanche & Funtico: Revolutionizing Gaming on the Blockchain

Avalanche Watch: April 2024

DEFI

The Avalanche Foundation Announces Memecoin Rush

Institutions

Homium Issues First Home Equity Loans on Avalanche

Enterprise

Feature.io Uses Avalanche-Powered API to Bring Web3 to Any Streaming Platform or Media File

Enterprise

stc Bahrain and Avalanche forge partnership to drive Web3 progress in the Middle East

Enterprise

Avalanche x Seedhe Maut: Revolutionizing the Fan Engagement Economy with Metasky

Enterprise

Really Launches Avalanche Subnet to Expand Reach of On-Chain Movies

Developers

Frosty: Bringing Strong Liveness Guarantees to the Snow Family of Consensus Protocols

Platform

BitNote Launches Encrypted Notes on Avalanche

Platform

Avalanche Integrates with Stripe for Crypto Onramping

Avalanche Watch: March 2024

Platform

The Avalanche Foundation Unveils the Icebreaker Program

Community

The Avalanche Foundation Launches Ambassador DAO to Usher in the Next Wave of Users

The Avalanche Foundation Announces a New Board

Community

The Avalanche Foundation Discloses Community Coin Holdings

Platform

Avalanche Foundation Launches Community Grants Program with Gitcoin

Institutions

Clearpool Expands to Avalanche with Exclusive Launch of Credit Vaults

Enterprise

Coachella to Gamify the Festival Experience and Distribute New Rewards Using Avalanche

Developers

Startup Incubator Codebase Names First Cohort

Institutions

Diamond Standard Leverages Oasis Pro and Avalanche to Make Diamonds an Investable Asset Class

Institutions

Tokenization 101: The Tokenized Collateral Ecosystem

Enterprise

Avalanche Powers Web3-Enabled Voucher Program on Alipay+ D-store

Institutions

Avalanche and Chainlink Leveraged in Tokenized Asset Settlement Project

Developers

The Graph Expands Data Tools for Avalanche Developers

Community

Avalanche Foundation: Eligibility Criteria Framework for Community Coins

Platform

Avalanche Watch: February 2024

NFT

Best Dish Ever Launches NFTs on Avalanche, Pioneering the Future of Culinary Exploration

Gaming

Legendary MMORPG MapleStory Comes to Avalanche

Platform

Teleporter Makes Avalanche a Fully Interoperable L0 Network

Enterprise

Loyalty+ to Receive Multiverse Incentives to Spur AI-Enhanced Loyalty Programs

DEFI

SteakHut V2 Introduces New Liquidity Features on Avalanche

Enterprise

Avalanche to Power SI Tickets’ NFT Platform, Box Office

NFT

Looty and Inspect Launch Loyalty Platform with Loot Crate Rewards, Boosting Avalanche NFT Season

Platform

Durango: Avalanche Warp Messaging Comes to the EVM

Community

Avalanche DeFi Saga with Rep3

Institutions

Citi Tests Benefits of Private Markets Tokenization With Avalanche Evergreen Subnet ‘Spruce’

Enterprise

Avalanche Named Exclusive Sponsor of Collider on the Lot Startup Accelerator

Platform

Cortina: X-Chain Linearization

Avalanche Watch: January 2024

Gaming

Owned Blends SocialFi and Gaming on Avalanche with Battle Tech

Enterprise

The Empire State Building Launches NFT Loyalty Program on Avalanche Using Uptop

Institutions

Intain Launches Avalanche Subnet to Usher in New Era for Multi-Trillion Dollar Securitized Finance Market

Institutions

How Avalanche Uses Account Abstraction to Improve the Web3 Experience for Institutions

Institutions

Institutional Products, Pilots Signal Growing Interest in Tokenization

Enterprise

Edgevana to Provide Infrastructure to Avalanche Network, Expanding Validator Decentralization

Institutions

South Korean Digital Asset Custodian BDACS to Support Avalanche

DEFI

Struct Finance Joins Avalanche Rush with an Incentive Program of up to $1M

DEFI

Fonbnk Builds Avalanche On-Ramp for Cross-Border Payments in Emerging Markets

Platform

Avalanche Wallet Phase-Out Guide

Platform

Avalanche Watch: December Edition

Institutions

What is Asset Tokenization: Why & Why Now?

DEFI

Sub-Saharan Africa: A Land Of DeFi Opportunity

NFT

NFT-TiX Migrates to Avalanche and Announces Global Festival Partnerships

Enterprise

AR Platform Really to Upgrade Entertainment Using Avalanche

Gaming

Tiltyard Gives Web3 Games Tournaments and Fantasy Sports Features

DEFI

Hubble Exchange Launches Order Book DEX Built on a Custom Avalanche Subnet

Platform

Avalanche Watch: November Edition

Developers

NodeKit Raises a $1.2M Pre-Seed Round to Build a Shared Sequencer L1 with HyperSDK

Gaming

Mirai Labs Blends SocialFi and Web3 Gaming, Migrates to an Avalanche Subnet

Institutions

Republic Selects Avalanche for its Profit-Sharing Note, Gains Vista Support

Platform

Avalanche Watch: October Edition

Institutions

Avalanche Supports Citi FX Solution Under Project Guardian

Institutions

Onyx by J.P. Morgan Leverages Avalanche To Explore a New Paradigm for Portfolio Management

Platform

Avalanche Foundation Mission Statement and Reminder About System Unlocks

Developers

Web2 and Web3 Leaders Launch Codebase by Avalanche, an Accelerator Supporting Early-Stage Avalanche Projects

DEFI

Avalanche Expands Forex Market in Africa With Canza Finance’s Baki Launch

Platform

Avalanche Powers Metaverse Experience at Hong Kong FinTech Week

Gaming

5 Great Web3 Games Coming Soon

Institutions

Beneath the Surface: The Infrastructure Driving Tokenization Forward

Developers

Avalanche is Advancing Off-Chain Computation Services for Developers

Enterprise

Neal Stephenson’s LAMINA1 to Reimagine the Open Metaverse with New Layer 1 Built on Avalanche

Ava Labs Accelerates Push in India with Key Senior Hires

Platform

CCRI Finds Avalanche Emits 12x Less CO2 Than Ethereum, 300,000x Less CO2 Than Bitcoin

DEFI

The Tangible Benefits of Bringing Non-USD Stablecoins and FX On-Chain

Institutions

On-Chain Cash Management: Thematic Takeaways From Partner Discussions

Platform

7 Avalanche Use Cases

NFT

Builder Spotlight: Zeroone is Rethinking How NFT Enjoyers Create and Collect

Institutions

Navigating Tokenized Asset Investments for Institutional Buyers

NFT

Blockticity Mints $275M in Hemp and Other Product Certifications on Avalanche, Disrupting a $4.5T Industry

Developers

Introducing Firewood: A Next-Generation Database Built for High-Throughput Blockchains

Community

Builder Spotlight: Steven Gates Wants to Bring Subnets to the World

Community

Avalanche Foundation Launches Ted Yin Grant Program to Expand Open Source Technology Development

Enterprise

Korean Entertainment Giant Powers Ticketing Platform with Avalanche

Developers

Developer Spotlight: NodeKit’s Cofounder on Why Avalanche is “Unrivaled”

Platform

New Avalanche C-Chain Explorer Launches

Developers

Time to Finality (TTF): The Ultimate Metric for Blockchain Speed

Platform

Avalanche Watch: August Edition

Developers

Movement Labs Raises Pre-Seed Round, Launches Movement SDK To Reignite Web3’s Interoperable Future

Gaming

Builder Spotlight: Kam Punia’s Quest to Level Up Web3 RPGs

DEFI

Multiswap Launches with Plan to Unlock Swaps of 300+ Assets in a Single Transaction on Avalanche

Gaming

Korean Game Publisher Neowiz and Ava Labs Form Partnership

NFT

NFT Marketplace Hyperspace Makes EVM Debut on Avalanche