Byzantine generals problem bitcoin wiki
It is related to the more general Byzantine Generals Problem though published long before that later generalization and appears often in introductory classes about computer networking particularly with regard to the Transmission Control Protocol where it shows that TCP can't guarantee state consistency between endpoints and why , though it applies to any type of two party communication where failures of communication are possible.
A key concept in epistemic logic , this problem highlights the importance of common knowledge. An important consequence of this proof is that generalizations like the Byzantine Generals problem are also unsolvable in the face of arbitrary communication failures, thus providing a base of realistic expectations for any distributed consistency protocols.
Two armies , each led by a different general , are preparing to attack a fortified city. The armies are encamped near the city, each in its own valley. A third valley separates the two hills, and the only way for the two generals to communicate is by sending messengers through the valley. Unfortunately, the valley is occupied by the city's defenders and there's a chance that any given messenger sent through the valley will be captured.
While the two generals have agreed that they will attack, they haven't agreed upon a time for attack. It is required that the two generals have their armies attack the city at the same time in order to succeed, else the lone attacker army will die trying. They must thus communicate with each other to decide on a time to attack and to agree to attack at that time, and each general must know that the other general knows that they have agreed to the attack plan.
Because acknowledgement of message receipt can be lost as easily as the original message, a potentially infinite series of messages is required to come to consensus. The thought experiment involves considering how they might go about coming to consensus. In its simplest form one general is known to be the leader, decides on the time of attack, and must communicate this time to the other general. The problem is to come up with algorithms that the generals can use, including sending messages and processing received messages, that can allow them to correctly conclude:.
Allowing that it is quite simple for the generals to come to an agreement on the time to attack i. The first general may start by sending a message "Attack at on August 4. This uncertainty may lead the first general to hesitate to attack due to the risk of being the sole attacker. To be sure, the second general may send a confirmation back to the first: Further confirmations may seem like a solution—let the first general send a second confirmation: Thus it quickly becomes evident that no matter how many rounds of confirmation are made, there is no way to guarantee the second requirement that each general be sure the other has agreed to the attack plan.
Both generals will always be left wondering whether their last messenger got through. Because this protocol is deterministic , suppose there is a sequence of a fixed number of messages, one or more successfully delivered and one or more not.
The assumption is that there should be a shared certainty for both generals to attack. Consider the last such message that was successfully delivered. If that last message had not been successfully delivered, then one general at least presumably the receiver would decide not to attack. Since the protocol is deterministic , the general sending that last message will still decide to attack.
We've now created a situation where the suggested protocol leads one general to attack and the other not to attack—contradicting the assumption that the protocol was a solution to the problem. A nondeterministic protocol with a variable message count can be compared to a finite tree , where each leaf or branch node in the tree represents an explored example up to a specified point. The roots of this tree are labeled with the possible starting messages, and the branch nodes stemming from these roots are labeled with the possible next messages.
Leaf nodes represent examples which end after sending the last message. A protocol that terminates before sending any messages is represented by a null tree. Suppose there exists a nondeterministic protocol which solves the problem. Byzantine errors were observed infrequently and at irregular points during endurance testing for the newly constructed Virginia class submarines , at least through when the issues were publicly reported.
A similar problem faces honeybee swarms. They have to find a new home, and the many scouts and wider participants have to reach consensus about which of perhaps several candidate homes to fly to. And then they all have to fly there, with their queen. Several solutions were described by Lamport, Shostak, and Pease in Several system architectures were designed c. In , Miguel Castro and Barbara Liskov introduced the "Practical Byzantine Fault Tolerance" PBFT algorithm, [15] which provides high-performance Byzantine state machine replication, processing thousands of requests per second with sub-millisecond increases in latency.
Furthermore, Adapt [22] tried to make use of existing BFT protocols, through switching between them in an adaptive way, to improve system robustness and performance as the underlying conditions change. Furthermore, BFT protocols were introduced that leverage trusted components to reduce the number of replicas, e. UpRight [25] is an open source library for constructing services that tolerate both crashes "up" and Byzantine behaviors "right" that incorporates many of these protocols' innovations.
This library implements a protocol very similar to PBFT's, plus complementary protocols which offer state transfer and on-the-fly reconfiguration of hosts. BFT-SMaRt is the most recent effort to implement state machine replication, still being actively maintained.
Archistar [27] utilizes a slim BFT layer [28] for communication. Focus lies on simplicity and readability, it aims to be the foundation for further research projects. Askemos [29] is a concurrent, garbage-collected, persistent programming platform atop of replicated state machines which tolerates Byzantine faults. It prototypes an execution environment facilitating Smart contracts. Tendermint [30] is general purpose software for BFT state machine replication.
Using a socket protocol, it enables state machines to be written in any programming language, and provides means for the state machine to influence elements of the consensus, such as the list of active processes. Tendermint is implemented in the style of a blockchain , which amortizes the overhead of BFT and allows for faster recovery from failure.
One example of BFT in use is bitcoin , a peer-to-peer digital currency system. The bitcoin network works in parallel to generate a chain of Hashcash style proof-of-work known as mining.
The proof-of-work chain is the key to overcome Byzantine failures and to reach a coherent global view of the system state.
Because these are real-time systems, their Byzantine fault tolerance solutions must have very low latency. For example, SAFEbus can achieve Byzantine fault tolerance within the order of a microsecond of added latency. Some spacecraft such as the SpaceX Dragon flight system [34] consider Byzantine fault tolerance in their design. Byzantine fault tolerance mechanisms use components that repeat an incoming message or just its signature to other recipients of that incoming message. All these mechanisms make the assumption that the act of repeating a message blocks the propagation of Byzantine symptoms.
For systems that have a high degree of safety or security criticality, these assumptions must be proven to be true to an acceptable level of fault coverage. When providing proof through testing, one difficulty is creating a sufficiently wide range of signals with Byzantine symptoms. From Wikipedia, the free encyclopedia.
For military generals of the Byzantine empire, see Category: Atomic commit Brooks—Iyengar algorithm List of mathematical concepts named after places List of terms relating to algorithms and data structures Byzantine Paxos Quantum Byzantine agreement Two Armies Problem. Archived from the original PDF on 7 February Association for Computing Machinery.
Speculative Byzantine Fault Tolerance". Proceedings of the 5th European conference on Computer systems. Symposium on Networked Systems Design and Implementation. Redundant Byzantine Fault Tolerance. International Conference on Distributed Computing Systems.