# Frosty: Bringing strong liveness guarantees to the Snow family of consensus protocols

arXiv: https://arxiv.org/abs/2404.14250 · HTML: https://mlsanity.com/paper/2404.14250/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Apr 2024.

## Built on by (most cited first, 1 of 1)

- [Snowveil: A Framework for Decentralised Preference Discovery](https://mlsanity.com/paper/2512.18444/) (2025)

## Abstract (arXiv)

Snowman is the consensus protocol implemented by the Avalanche blockchain and is part of the Snow family of protocols, first introduced through the original Avalanche leaderless consensus protocol. A major advantage of Snowman is that each consensus decision only requires an expected constant communication overhead per processor in the `common' case that the protocol is not under substantial Byzantine attack, i.e. it provides a solution to the scalability problem which ensures that the expected communication overhead per processor is independent of the total number of processors n during normal operation. This is the key property that would enable a consensus protocol to scale to 10,000 or more independent validators (i.e. processors). On the other hand, the two following concerns have remained: (1) Providing formal proofs of consistency for Snowman has presented a formidable challenge. (2) Liveness attacks exist in the case that a Byzantine adversary controls more than O(√n) processors, slowing termination to more than a logarithmic number of steps. In this paper, we address the two issues above. We consider a Byzantine adversary that controls at most f<n/5 processors. First, we provide a simple proof of consistency for Snowman. Then we supplement Snowman with a `liveness module' that can be triggered in the case that a substantial adversary launches a liveness attack, and which guarantees liveness in this event by temporarily forgoing the communication complexity advantages of Snowman, but without sacrificing these low communication complexity advantages during normal operation.