Difference between revisions of "The Byzantine Generals Problem"
m
 
(10 intermediate revisions by 2 users not shown)
Line 1: Line 1:
−
The Byzantine Generals Problem was first proposed by Leslie Lamport, Robert Shostak, and Marshall Pease as part of research being conducted at NASA. The problem deals with how to define how to direct a network of disconnected units in a leaderless situation.
+
The Byzantine Generals Problem was first proposed by Leslie Lamport, Robert Shostak, and Marshall Pease as part of research being conducted at NASA. The problem deals with, how to define, how to direct a network of disconnected units in a leaderless situation. It has been somewhat adapted to the problem of Bitcoin for this description, however the original paper can be found [https://people.eecs.berkeley.edu/~luca/cs174/byzantine.pdf here].
  
−
umber 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, lest they be discovered. They only have enough CPU power to crack it fast enough if a majority of them attack at the same time.
+
The problem defines how Generals can issue commands without a centralised communication structure, while remaining robust in the face of bad actors who might try to issue malicious commands to the army.
  
−
They don't particularly care when the attack will be, just that they agree. It has been decided that anyone who feels like it will announce an attack time, which we'll call the "plan", and whatever plan is heard first will be the official plan. The problem is that the network is not instantaneous, and if two generals announce different plans at close to the same time, some may hear one first and others hear the other first.
+
The Byzantine army is encamped outside a city broken into divisions, each controlled by a General. Generals have no means to communicate other than through messengers. There are traitorous Generals in the army who will try to issue commands that prevent the loyal Generals from reaching agreement on a reasonable plan forward, so the messaging protocol must ensure that message receivers can know that they are from a loyal General.
  
−
They use a [[Proof of Work]] chain to solve the problem. Once each general receives whatever plan he hears first, he sets his computer to solve a difficult hash-based proof-of-work problem that includes the plan in its hash. The proof-of-work is difficult enough that with all of them working at once, it's expected to take 10 minutes before one of them finds a solution and broadcasts it to the network. Once received, everyone adjusts the hash in their proof-of-work computation to include the first solution, so that when they find the next proof-of-work, it chains after the first one. If anyone was working on a different plan, they switch to this one, because its proof-of-work chain is now longer.
+
Anyone can present a message to a General claiming it to be from another General, so the protocol must have a means for Generals to know with certainty, that any proposed moves are from another General. A cipher that demonstrates the message is from a real General is needed. In Bitcoin, [[Proof of Work]] demonstrates a node's authority to write blocks to the ledger. This is a core element of [[Nakamoto Consensus]].  
  
−
After about two hours, the plan 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 in the allotted time. At the least, most of them had to have seen the plan, since the proof-of-work is proof that they worked on it. If the CPU power exhibited by the proof-of-work is sufficient to crack the password, they can safely attack at the agreed time.<ref>https://bitcointalk.org/oldSiteFiles/byzantine.html</ref>
+
The army sometimes becomes divided when two Generals find valid moves at around the same time. It takes a short period of time for orders to be propagated so the Generals may end up following divergent moves.
  
 +
If the army starts moving apart, Generals in the group that falls behind the front will stop what they are doing and catch up. This is what happens in a network [[Re-org]], with the abandoned move creating an [[Orphan Block]].
  
−
== Links ==
+
The need for Generals to always be at the front of the army incentivises the best Generals to form direct lines of communication with each other, leading to much faster communication. In Bitcoin, this incentive drives Miners to find the best way to connect to each other, driving the [[Bitcoin Core Network]] members into forming a [[Small World Network]] with large highly connected systems. This core trends towards a [[Nearly Complete Graph]] where all nodes are connected to almost all other nodes.
−
[http://expectedpayoff.com/blog/2013/03/22/bitcoin-and-the-byzantine-generals-problem/ Bitcoin & the Byzantine Generals Problem]
+
 
 +
Finding valid solutions to proof of work, is generally limited to 6 nodes an hour, so the centre of the mandala trends towards a size maxima constrained by [[wikipedia:Metcalfe's law|Metcalfes law]]. As more nodes join the competition, it becomes more expensive to maintain connections, so Miners will instinctively cut ties with non-performing Miners to connect with newer, more powerful nodes. This element of constant building to maintain position can be described as a [[wikipedia:Red_Queen's race|Red Queen's race]] where participants must continuously accelerate in order to maintain their position in the field.

Latest revision as of 02:00, 18 November 2020

The Byzantine Generals Problem was first proposed by Leslie Lamport, Robert Shostak, and Marshall Pease as part of research being conducted at NASA. The problem deals with, how to define, how to direct a network of disconnected units in a leaderless situation. It has been somewhat adapted to the problem of Bitcoin for this description, however the original paper can be found here.

The problem defines how Generals can issue commands without a centralised communication structure, while remaining robust in the face of bad actors who might try to issue malicious commands to the army.

The Byzantine army is encamped outside a city broken into divisions, each controlled by a General. Generals have no means to communicate other than through messengers. There are traitorous Generals in the army who will try to issue commands that prevent the loyal Generals from reaching agreement on a reasonable plan forward, so the messaging protocol must ensure that message receivers can know that they are from a loyal General.

Anyone can present a message to a General claiming it to be from another General, so the protocol must have a means for Generals to know with certainty, that any proposed moves are from another General. A cipher that demonstrates the message is from a real General is needed. In Bitcoin, Proof of Work demonstrates a node's authority to write blocks to the ledger. This is a core element of Nakamoto Consensus.

The army sometimes becomes divided when two Generals find valid moves at around the same time. It takes a short period of time for orders to be propagated so the Generals may end up following divergent moves.

If the army starts moving apart, Generals in the group that falls behind the front will stop what they are doing and catch up. This is what happens in a network Re-org, with the abandoned move creating an Orphan Block.

The need for Generals to always be at the front of the army incentivises the best Generals to form direct lines of communication with each other, leading to much faster communication. In Bitcoin, this incentive drives Miners to find the best way to connect to each other, driving the Bitcoin Core Network members into forming a Small World Network with large highly connected systems. This core trends towards a Nearly Complete Graph where all nodes are connected to almost all other nodes.

Finding valid solutions to proof of work, is generally limited to 6 nodes an hour, so the centre of the mandala trends towards a size maxima constrained by Metcalfes law. As more nodes join the competition, it becomes more expensive to maintain connections, so Miners will instinctively cut ties with non-performing Miners to connect with newer, more powerful nodes. This element of constant building to maintain position can be described as a Red Queen's race where participants must continuously accelerate in order to maintain their position in the field.

Retrieved from "https://wiki.bitcoinsv.io/index.php?title=The_Byzantine_Generals_Problem&oldid=2654"