Snowman is the consensus protocol used by blockchains on Avalanche and is part of the Snow family of protocols, first introduced in the Avalanche whitepaper [28]. 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: In this paper, we address the two issues above. We consider a Byzantine adversary that controls at most $$f