Threats to Consensus
The consensus algorithm must result in nodes reaching agreement even when some nodes fail or behave unreliably (including maliciously). Two types of threat are usually considered, a crash failure, which occurs when a process abruptly stops and does not resume and a Byzantine failure which refers to any failure that is not a Crash failure. Importantly, this includes the malicious actions of an adversary. For example, the failed node might generate arbitrary data, pretending that this is correct data. Or a given node may send contradictory or conflicting data to other nodes, or it may sleep and then resume activity after a lengthy delay.
Of the two types of failure, Byzantine failures are far more disruptive for reaching consensus. A consensus protocol tolerating Byzantine failures must be resilient to every possible error that can occur.
Addressing Byzantine Failure
Consensus algorithms that address arbitrary network faults (i.e. ‘Byzantine failures’) usually implement some form of randomized node selection across the broadest possible population of participants; a node is elected - in some transparently verifiable and random manner - to choose the next block on behalf of the network. By randomizing node selection, the network ensures no node can have fore knowledge it will be next to define a block; therefore, no node can undertake ‘double spend’ transactions with the certainty that the blockchain can then be manipulated to cover its tracks.
Two alternative approaches to randomized node selection are often used, firstly, Nakamoto consensus is where a node is elected through a ‘lottery’ (i.e. through some randomized process, e.g. Bitcoin, where the elected node is the winner of a cryptographic puzzle so computationally difficult that it can be solved only by trying answers randomly). The elected node then proposes the next block to add to the chain of previously committed blocks, and then broadcasts the new block to the rest of the nodes, who implicitly accept the block by adding it to a chain of accepted blocks and proposing subsequent transaction blocks that build on that chain. And through voting, consensus is achieved through multiple rounds of explicit votes.