Nakamoto Consensus

Basics

• Nakamoto consensus is a name for Bitcoin’s decentralized, pseudonymous consensus protocol. It is considered as Bitcoin’s core innovation and its key to success. The consensus protocol doesn’t require any trusted parties or pre-assumed identities among the participants. Nakamoto consensus consists of the longest chain rule using proof of work as its sybil resistance mechanism and leader election.
• At any given point in time the network of peer parties has an established agreement about a global ledger of transactions which have happened so far. The ledger consists of blocks each of which comprises individual valid transactions as well as special transaction called block reward. There are special types of parties called miners which decide to compete each other to produce a new block and win the block reward as well as optionally collect transaction fee. The consensus protocol is needed in order to decide which next block to include into the ledger. The consensus protocol says that the first announced valid block containing solution to a computational puzzle is considered correct; and all other miners are to start searching for a followup block after that moment. This may occasionally lead to temporary forks due to several simultaneously found solutions. The longest fork in that case is considered valid. In case of equal-length forks miners can choose either one. Due to probabilistic nature of computational puzzle, one fork will eventually get longer than the other.
• The computational puzzle plays essential role in establishing the consensus. It is often referenced as proof-of-work in spite the fact that the process of finding the solution is rather probabilistic.
• From the Polkadot wiki (7-5-2021):

"Proof of Work (PoW) and Proof of Stake (PoS) have been inaccurately used as short hand to refer to consensus mechanisms of blockchains, but that does not capture the full picture. PoW is the method for agreeing on a block author and part of the fuller Nakamoto consensus that also encompasses a chain selection algorithm (longest chain rule in Bitcoin). Similarly, PoS is a set of rules for selecting the validator set and does not specify a chain selection rule or how a chain might reach finality. PoS algorithms have traditionally been paired with an algorithm for coming to Byzantine agreement between nodes."

Finality

• From the Polkadot wiki (7-5-2021):

"Nakamoto consensus only gives us probabilistic finality. Probabilistic finality states that a block in the past is only as safe as the number of confirmations it has, or the number of blocks that have been built on top of it. As more blocks are built on top of a specific block in a Proof of Work chain, more computational work has been expended behind this particular chain. However, it does not guarantee that the chain containing the block will always remain the agreed-upon chain, since an actor with unlimited resources could potentially build a competing chain and expend enough computational resources to create a chain that did not contain a specific block. In such a situation, the longest chain rule employed in Bitcoin and other proof of work chains would move to this new chain as the canonical one."