Have you ever wondered how proof of work (the mechanism by which new blocks are added to Bitcoin – a.k.a ‘mining’) solves the Byzantine Generals Problem?
Well, who better to try to explain this than the creator of Bitcoin himself: Satoshi Nakamoto.
Interestingly, everything Satoshi Nakamoto wrote is recorded for posterity on a website called the Satoshi Nakamoto Institute (note: there’s also an excellent book, published in 2019, called “Kicking The Hornet’s Nest“, by Mill Hill Books, that does exactly the same thing, but in a handy chronological order).
In an email response to the anonymous cypherpunk James A Donald dated November 13th 2008 (here’s the reference page from the Satoshi Nakamoto Institute for those interested – or on page 30 of the book if you happen to have it), Satoshi explains how the concept of proof of work solves the Byzantine Generals Problem:
Here’s what Satoshi wrote:
“The proof-of-work chain is a solution to the Byzantine Generals’ Problem…
…A number of Byzantine Generals each have a computer and want to attack the King’s wi-fi by brute forcing the password, which they’ve learned is a certain number of characters in length. Once they stimulate the network to generate a packet, they must crack the password within a limited time to break in and erase the logs, otherwise they will be discovered and get in trouble. They only have enough CPU power to crack it fast enough if a majority of them attack at the same time.
They don’t particularly care when the attack will be, just that they all agree. It has been decided that anyone who feels like it will announce a time, and whatever time is heard first will be the official attack time. The problem is that the network is not instantaneous, and if two generals announce different attack times at close to the same time, some may hear one first and others hear the other first.
They use a proof-of-work chain to solve the problem. Once each general receives whatever attack time he hears first, he sets his computer to solve an extremely difficult proof-of-work problem that includes the attack time in its hash. The proof-of-work is so difficult, it’s expected to take 10 minutes of them all working at once before one of them finds a solution. Once one of the generals finds a proof-of-work, he broadcasts it to the network, and everyone changes their current proof-of-work computation to include that proof-of-work in the hash they’re working on. If anyone was working on a different attack time, they switch to this one, because its proof-of-work chain is now longer.
After two hours, one attack time should be hashed by a chain of 12 proofs-of-work. Every general, just by verifying the difficulty of the proof-of-work chain, can estimate how much parallel CPU power per hour was expended on it and see that it must have required the majority of the computers to produce that much proof-of-work in the allotted time. They had to all have seen it because the proof-of-work is proof that they worked on it. If the CPU power exhibited by the proof-of-work chain is sufficient to crack the password, they can safely attack at the agreed time.
The proof-of-work chain is how all the synchronisation, distributed database and global view problems you’ve asked about are solved.”
-Reference: https://satoshi.nakamotoinstitute.org/
emails/cryptography/11/
It’s not necesarily the easiest explanation to follow if you’re a newbie to Bitcoin, but it’s definitely an invaluable insight into how Satoshi thought about a few of the absolutely fundamental concepts of the system.