Consensus

In distributed computing, consensus is the overall system reliability in the presence of a number of faulty processes.

Consensus requires agreement among a number of processes or agents for a single data value. Some of these might fail or be unreliable in other ways, so consensus protocols must be fault-tolerant. The processes must put forth their candidate values, communicate with one another, and agree on a single value.

A consensus protocol tolerating halting failures must satisfy the following properties:

• Termination: A liveness property in which every correct (non-faulty) process eventually decides some value.
• Integrity: The ability to recover from the failure of a participating node.
• Agreement: A safety property, in which every correct process must agree on the same value.

Failures can refer to either a fail-stop, when a process stops communicating or a Byzantine fault, where a process send faulty or malicious data. The term Byzantine is taken from a simile by Leslie Lamport about a group of generals of the Byzantine army camped with their troops around an enemy city. Communicating only by messenger, the generals must agree upon a common battle plan. However, one or more of them may be traitors who will try to confuse the others. An algorithm resilient to such failures is called Byzantine fault-tolerant.

In the case of cryptocurrencies such as Bitcoin, nodes in the network must agree upon a common order of transactions. They do so by timestamping transactions into blocks, which are hashed and linked into a chain. Miners produce computational work into finding nonce which would produce a block hash under a certain size, called the target. If the block is valid under the protocol rules, nodes accept the block as canonical, reaching a consensus.

In the case that multiple blocks are valid, the longest chain –carrying the most proof-of-work– is accepted as canonical. This is the essence of Nakamoto consensus.