Proof-of-Work (PoW)

Proof-of-Work (PoW) was part of the first successful decentralized blockchain consensus algorithm. PoW is still used by Bitcoin and other cryptocurrencies, like Ethereum (Ethereum plans to move to Proof-of-Stake, more details there), Litecoin, ZCash, Monero, and many more. PoW requires participants to perform work that is computationally intensive but easy to verify by others in the network. In the case of Bitcoin, “miners” compete to add a collection of transactions, known as a block, to the global blockchain maintained by the network. To do this, a miner must be the first to correctly figure out the “nonce”, a number appended to the end of a string to create a hash that starts with a required number of zeroes (this is an abstraction of details; this piece provides a more detailed overview).

Basics

From this post: "The concept of PoW was invented in 1997 by Adam Back (now CEO of Blockstream) for Hashcash, a system that aimed to prevent Denial of Service (DoS) attacks and e-mail spam. However, it wasn’t until it was combined with the Bitcoin’s incentive structure until it became a success."
How miners participate in governance and how they can revolt can be read in this article (1-2-2021).

How it works

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)."

From this post by FlatOutCrypto (26-4-2018):

"Miners run a computer program which gives each miner an equal chance proportional to their computing power to discover the solution to the next block. They compete to find the answer (known as hash) to the set PoW parameters for that block. This hash is a 64-character long answer, and is based upon the inputs to the block, such as the transactions it contains.

Miners search for this hash by combining this input with a random number known as a nonce, until someone finds the correct answer. This solution is then broadcast to, and verified by, other miners. Once confirmed, it is added to the blockchain by the other miners, which then use this new block as the input for the hash needed for the next correct block. This chain forms a canonical ledger of all of transactions from Bitcoin’s inception.

As a result, PoW solves the Byzantine Generals Problem as it achieves a majority agreement without any central authority, in spite of the presence of unknown/potentially untrustworthy parties and despite the network not being instantaneous. It empowers the distributed and un-coordinated Generals to come to an agreement:

The Generals agree the first plan received by all Generals will be accepted as the plan
A General solves the PoW problem, creating a block that is broadcast to the network so that all Generals receive it
Following receipt of this block, each General verifies and works on solving the next PoW problem, incorporating the prior solution into it, so that their plan adds on to the previous resolution
Each time a General solves a PoW problem, a block is generated and the chain begins to grow. In time, any General working on a different solution will switch over to the longest chain. This is the one most Generals are contributing to and therefore has the greatest chance of success
As the Generals know roughly how long a PoW solution takes to solve, after a set amount of time they will know if enough of the other Generals are also working on the same chain

Through this process, the Generals can arrive at a consensus of when to attack, can estimate their chances of successfully doing so, and can prevent multiple different signals to attack being sent simultaneously.

PoW also prevents malicious actors, such as a traitorous General, from sabotaging the network by tampering with historic messages. Bitcoin, for example, stores the hash signature of the previous block in every new block. Any change to an earlier block would therefore require all successive blocks to also be changed. This would take an excessively large amount of computing power, and therefore the ledger is secure from alterations."

A piece of data that requires significant computation to find. In bitcoin, miners must find a numeric solution to the SHA-256 algorithm that meets a network-wide target, the difficulty target.
A proof of work is a piece of data which is difficult (costly, time-consuming) to produce but easy for others to verify and which satisfies certain requirements. Producing a proof of work can be a random process with low probability so that a lot of trial and error is required on average before a valid proof of work is generated. Bitcoin uses the Hashcash proof of work system.
One application of this idea is using Hashcash as a method to preventing email spam, requiring a proof of work on the email's contents (including the To address), on every email. Legitimate emails will be able to do the work to generate the proof easily (not much work is required for a single email), but mass spam emailers will have difficulty generating the required proofs (which would require huge computational resources).
Hashcash proofs of work are used in Bitcoin for block generation. In order for a block to be accepted by network participants, miners must complete a proof of work which covers all of the data in the block. The difficulty of this work is adjusted so as to limit the rate at which new blocks can be generated by the network to one every 10 minutes. Due to the very low probability of successful generation, this makes it unpredictable which worker computer in the network will be able to generate the next block.
For a block to be valid it must hash to a value less than the current target; this means that each block indicates that work has been done generating it. Each block contains the hash of the preceding block, thus each block has a chain of blocks that together contain a large amount of work. Changing a block (which can only be done by making a new block containing the same predecessor) requires regenerating all successors and redoing the work they contain. This protects the block chain from tampering.
The most widely used proof-of-work scheme is based on SHA-256 and was introduced as a part of Bitcoin. Some other hashing algorithms that are used for proof-of-work include Scrypt, Blake-256, CryptoNight, HEFTY1, Quark, SHA-3, scrypt-jane, scrypt-n, and combinations thereof.

Pro's and Con's

The most significant positive attribute of PoW is that is has been proven to work over a period of a few years, which is more than can be said for many other consensus algorithms. PoW is not without its shortcomings, however, which include high power consumption for the mining process and low transaction throughput.
From this post by FlatOutCrypto (26-4-2018):

"Mining Bitcoin is now a multi-billion dollar industry and, while all users still have an equal chance of mining a Bitcoin proportional to their computing power, the emergence of industrial scale mining operations means the ordinary individual has a very small chance of successfully mining one Bitcoin. As mining cartels continue to increase in size, the network becomes more centralized – the cartels control more of the hash power and so can mine more of the Bitcoin. This in turn means they can afford to expand operations and assume a greater proportion of computing power.

Critics also point to the waste of the processing power which is essentially only used to secure the network – the calculations have no application to other fields. This energy and financial burden is the cost of securing the network."

More Downsides of PoW:

"As long as it can attract enough honest participants that make it difficult for attackers to control the majority hash power, PoW has proven to be secure. Nonetheless, there are (potential) downsides to PoW, for example:

The intensive use of computing power consumes a lot of energy. However, the efficiency of mining equipment continues to improve, miners tend to seek cheap (often renewable) energy sources and you can argue that Bitcoin’s added value to society warrant its high energy consumption. Either way, a system that can achieve similar security with less energy consumption would be favorable from an environmental perspective.
In PoW cryptocurrencies with a capped supply (e.g. Bitcoin), the number of new coins that can be mined diminishes over time, and at some point only fees are available as block rewards. It remains to be seen if block rewards based on fees will be valuable enough to cover miners’ costs and keep incentivizing them to participate in the (distant) future.
In PoW, coin holders without a (mining) node cannot directly participate in network governance (besides ‘voting with their feet’ when choosing which fork to support or opting-out by selling their coins), while their interests do not necessarily align to those of developers and miners."