Consensus mechanisms

The proof-of-work chain is a solution to the Byzantine Generals' Problem. by Satoshi Nakamoto

Specifically

The key property of blockchain is that it is tamper proof. That implies two elements: 1. the validity of blockchain is easy to verify, 2. creation of a valid blockchain is beyond computational/financial capability of any individual entity.

Since all network participants must agree on the validity of blockchain, the mechanism that leads to its creation is called Consensus.

The most reliable, computationally intensive, and thus in most cases wasteful, is Proof-of-Work.
The underlying mathematical structure is a sequence of concatenated hashes, where output of one hash feeds as one of the inputs to the subsequent hash.The other input has to be computed based on the target output of the hash function, which can only be done by trial and error. The discoverer of the needed input validates the block and reaps reward in the form of transaction fees, and possibly, newly minted cryptocurrency.

Less wasteful alternatives are being actively sought after, Proof of Stake being one of the candidates. However, unlike Proof of Work, it is not clear if this approach, which relies in part on the validator having sufficient assets, is equally robust.

Generalities

The main purpose of blockchain, and similar technologies is to provide a medium for creation and preservation of consensus. That is, it is crucial that essentially all market participant agree on the shared record (ledger). Formation of consensus has features of a "phase transition", familiar from physics: each individual follows some simple dynamical rules, but the collective behavior emerges nevertheless. Transitions can be dynamical (swarm of locust, or flock of birds), or statistical (freezing, spin glass or magnetism). In either case, a critical ingredient is the local reduction of entropy, that requires work.

Reviews

A Quick Classification of Cryptocurrency Consensus Algorithms