what is the Byzantine generals problem?


And how does it relate to bitcoin?

Reward: 1000 sats

The Byzantine generals problem is an analogy to illustrate problems in distributed systems with unreliable communications, if I'm not mistaken it was first described by Robert Shostak at NASA while investingating how to program controllers that would work reliably even in the presence of malfunctions, but I believe the analogy was only introuced later. In the story several generals are splitting up into factions, and are attempting to communicate with one another to determine their allegiances, but can only do this by sending messengers who may be captured or coerced. From the point of view of a single general (which corresponds to a node in a distributed system) there is never absolute certainty about whether or not their messages he sent were delivered intact. By analogy, a byzantine fault in computer science is when a message is arbitrarily modified or discarded by an adversary, so the byzantine setting is more challenging to work in than the setting where communication channels are merely unreliable, causing some messages to be lost. It relates to Bitcoin because Bitcoin is a distributed system: every node is only in contact with its direct peers, and those peers may be malicious. Messages in the protocol are transactions and blocks. It's a common to use digital signatures to protect the integrity of messages in a byzantine fault tolerant setting, and that is what is used for transactions (but see also transaction malleability), and the problem of reliable delivery is mitigated because the network is well connected and transactions can propagate to all peers over multiple paths. Blocks can't be signed in a similar way because miners' identities (and therefore any hypothetical signing keys) are not predetermined, so instead Bitcoin uses proof of work to ensure that miners can't flood the network with new blocks, allowing all peers in the network to validate blocks. This allows peers in the network to reach a distributed consensus about the last block, or more precisely Nakamoto consesnsus is probabilistic solution to the distributed consensus problem in the byzantine setting.