[Ethereum] How is the Two Generals Problem solved with proof of work


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?

Best Answer

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%.


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.

Related Topic