How is the Two Generals Problem solved with proof of work?

Question

Here is an email where Satoshi Nakamoto explains how PoW solves the Byzantine Generals' problem http://satoshi.nakamotoinstitute.org/emails/cryptography/11/

The proof-of-work chain is a solution to the Byzantine Generals' Problem. I'll try to rephrase it in that context...

On Wikipedia, however, it's said that this problem is proved to be unsolvable https://en.wikipedia.org/wiki/Two_Generals%27_Problem

The Two Generals Problem was the first computer communication problem to be proved to be unsolvable. An important consequence of this proof is that generalizations like the Byzantine Generals problem are also unsolvable in the face of arbitrary communication failures

What did PoW actually solve and with what assumptions?

Answer 1

Proof of Work like proposed by Satoshi doesn't solve the Two Generals Problem or the more generic Byzantine Generals Problem. It's a probabilistic solution to the Byzantine Generals Problem, which means the confidence that a consensus is reached is growing with every block added to the chain, but it never reaches 100%.

https://medium.com/loom-network/understanding-blockchain-fundamentals-part-1-byzantine-fault-tolerance-245f46fe8419

Practical Byzantine Fault Tolerance (PBFT) for instance will guarantee consistency (no forks -> 100% finality) in a system with 3*k+1 nodes only if the number of traitors does not exceed k. Hence, you‘ll need at least 2*k+1 votes for a block. The reason you need 2*k+1 is that for every number smaller than that, you can not be sure that traitors are not in majority for this subset. See Liskov/Castro Paper on PBFT for details.

Answer 2

PoW (or in fact any consensus algorithm) can't solve the Two Generals/Byzantine Generals Problem. It can only provide a very high and easily verifiable certainty of a transaction being correct.

A few assumptions are made:

1. Most miners and node operators act either altruistic (true to the code no matter what comes) or economically egoistic (try to make as much money as possible). Purely destructive miners are a minority because it would not serve them a purpose.
2. Network lag is negligible. It is assumed that no node will ever fall behind the chain, it will have received a block before the next one is mined.

Under these circumstances, the problem can be solved because all nodes agree on a common truth and nothing ever goes wrong. Here is why those assumptions are not necessarily always true:

1. There might be an economic incentive for some miners to behave destructive and perform a 51% attack. Governments, big companies or investors who shorted a given cryptocurrency might have a benefit out of destroying it.
2. Network lag is not negligible! The shorter the block time is, the higher the probability of two blocks being mined at the same time and therefore forking the chain. It is then the next block that makes on of the chains longer and therefore causes all of the non-destructive nodes to switch to the longer chain and therefore agreeing on a common truth again. That is why a transaction is not confirmed after only one block, there might always be a longer chain that your node doesn't know about yet. After a few blocks have been mined, it is highly likely that a transaction is correct and will never be changed.

The Two Generals problem can't be formally solved by modern consensus algorithms, but it can tremendously increase the likelihood of reaching consensus after a short time.