Frosty: Bringing strong liveness guarantees to the Snow family of consensus protocols
<|reference_start|>Frosty: Bringing strong liveness guarantees to the Snow family of consensus protocols: 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(\sqrt{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.<|reference_end|>
@article{buchwald2024frosty:,
    title={Frosty: Bringing strong liveness guarantees to the Snow family of
  consensus protocols},
    author={Aaron Buchwald, Stephen Buttolph, Andrew Lewis-Pye, Patrick O'Grady,
  Kevin Sekniqi},
    journal={arXiv preprint arXiv:2404.14250},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.14250},
    primaryClass={cs.DC}
}