Security Analysis of Avalanche Consensus
Summary
Last week, Ignacio Amores-Sesar, Christian Cachin, and Enrico Tedeschi published a careful and insightful security analysis paper that provides a detailed formulation of Avalanche Consensus through pseudocode and analyzes its security guarantees. This work describes a liveness attack that takes advantage of the mapping of Avalanche Consensus to Snowball Consensus, as specified in one of the early papers, that could allow an adversary to delay transactions. The same vulnerability was identified by Ava Labs researchers in December 2018 and was addressed during the initial development of AvalancheGo. As a result, AvalancheGo is not, nor has it ever been vulnerable to this attack. Amores-Sesar et al. graciously acknowledge this in their publication:
Avalanche is well-known for its remarkable throughput and latency that are achieved through a metastable sampling technique. The pseudocode we introduce captures in a compact and relatively simple manner the intricacies of the system. We show that Avalanche, as originally introduced, possesses a vulnerability allowing an adversary to delay transactions arbitrarily. We also address such vulnerability with a modification of the protocol, Glacier, that allows Avalanche to satisfy both safety and liveness.
The developers of Avalanche have acknowledged the vulnerability, and the actual implementation does not suffer from it due to an alternative fix. Understanding this variant of Avalanche remains open and is subject of future work.
Before diving into a summary of the findings by Amores-Sesar et al. and an explanation of AvalancheGo’s fix, we’d like to extend a huge thanks to Ignacio Amores-Sesar, Christian Cachin, and Enrico Tedeschi for their work. The Avalanche Foundation is proud to sponsor their future research on Avalanche.
Tracking Consecutive Polls in Avalanche Consensus
Avalanche Consensus is a multi-decree consensus protocol, which relies on the Snowball consensus primitive. Snowball is a single-decree binary consensus protocol. Snowball works by repeatedly polling a random subset of participants. Correct participants will respond with their currently preferred choice. Faulty participants can act arbitrarily, which includes responding with an arbitrary preference or never responding. If a value is seen to be preferred by a threshold of peers, its sequence counter is incremented. If a value does not meet the threshold, its sequence counter is reset to 0.
Avalanche executes multiple Snowball instances concurrently. One reason Avalanche is highly performant is its ability to perform multiple Snowball polls within a single Avalanche poll. This can significantly reduce the total number of network polls required to finalize transactions, compared to the minimum β network polls per decision in Snowball. This is implemented by transitively voting for Snowball instances through parent dependencies.
In the attack described by Amores-Sesar et al., the Avalanche protocol could be made to reset the consecutive counters for all transactions that were referenced in the transitive closure of the queried vertex if a poll failed. This deviates from the Snowball protocol, which should have increased the consecutive count if a sufficient number of polled peers preferred the transaction.
Glacier: Proposed Fix from Amores-Sesar et al.
To fix this issue, Amores-Sesar et al. suggest that rather than resetting the consecutive counters for all transactions that were referenced in the transitive closure of the queried vertex, the votes should specify which transactions are not preferred in the transitive closure. This could then be used to ensure that all referenced transactions that were preferred by the threshold of peers would have their confidence values increased as expected.
Voting Over Preferred Frontiers: AvalancheGo’s Fix
The Ava Labs team solved this problem during the initial implementation of AvalancheGo in 2018 by developing a different approach: voting over preferred frontiers. Rather than returning the preferred-ness of only the requested vertex, a peer will respond with the set of vertices that describe all strongly preferred vertices. Additionally, a virtuous frontier, which is guaranteed to be a subset of the preferred frontier, is used to select parents for reissuance of non-conflicting transactions. This guarantees that all virtuous transactions will receive an affirmative vote for any poll that is initiated.
Conclusion
We are grateful to Ignacio Amores-Sesar, Christian Cachin, and Enrico Tedeschi for their deep and insightful work analyzing Avalanche’s security guarantees and for reporting a potential vulnerability responsibly before publication. The Avalanche Foundation welcomes and appreciates scrutiny from some of the world’s top distributed systems researchers and is proud to sponsor their future research on Avalanche.
As explained above, the implementation of Avalanche Consensus in AvalancheGo extends the original Avalanche Consensus specification and is not, nor has ever been, vulnerable to this attack.
If you are interested in performing research on Avalanche, we’d love to chat! Reach out to us at research@avalabs.org.
Security Analysis of Avalanche Consensus was originally published in Avalanche on Medium, where people are continuing the conversation by highlighting and responding to this story.
