Difference between revisions of "The Byzantine Generals Problem"
m
 
(7 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. It has been somewhat adapted to the problem of Bitcoin for this description however the original paper can be found here: https://people.eecs.berkeley.edu/~luca/cs174/byzantine.pdf
+
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].
  
−
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 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.
+
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 general has authority from soldiers in the army to propose a move is needed. This is what Proof of Work resolves for Bitcoin by creating a means for a general to attach the authority of troops they are providing to the army to a proposed maneuver. A block represents a potential move for the whole army as a collective so a general needs to be able to show he has troops. This is done through a troop lottery. Troops have an endless supply of fortune cookies which they open as fast as possible. If a troop finds a winning number their general gets to send a message to all other generals. Through this lottery system, generals can know that the person who sent a message has troops. They cannot tell how many troops or where they are. If the other generals also agree their maneuver is valid they will try to calculate a next move to follow that move. The army sometimes becomes divided when two troops find lotteries at around the same time. It takes a short period of time for orders to be propagated so the generals may end up following different moves. Generals always want to be at the very front of the army. If the army splits and some generals move forward with a new set of moves, generals who are still searching for a solution that is one move behind the front will stop what they are doing and catch up.
+
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]].  
  
−
Generals will follow the first valid command they receive which is encoded with an appropriate cipher. If competing generals discover a move at the same time, other generals will follow what they hear from the first general who's message they can decipher. This incentivizes strong generals to form direct lines of communication with other strong generals in the army leading to much faster communication between the command tents of the larger divisions. In Bitcoin, this incentive drives miners to find the best way to connect to each other, leading the network into forming a small world network with large highly connected nodes at the center of a [[Mandala Network]]. These nodes will form a [[Nearly Complete Graph]] where all nodes are connected to almost all other nodes. Finding valid solutions to proof of work is limited to 6 nodes an hour so the center 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 nodes and form new connections with more powerful nodes.  
+
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.
  
−
As new generals enter the field, the army becomes larger. New troops bring billions more fortune cookies into play making it much harder to find a winning lottery ticket. Generals must be in a constant fight to add more soldiers to their division lest they fall too far behind the most powerful generals. Simply in order to maintain their ranking in the army, generals must constantly work to add more troops. This element of constant building to maintain position can be described as a [[Red Queen game]] as told by the Red Queen in Alice in Wonderland.
+
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]].
  
−
All generals want to find the next move as there is a substantial reward for doing so. The generals are also the administrators of their army and the lands they control. These lands are fertile and trade is open and free. Since the army was formed, every move has rewarded the general who made it with an amount of coin. In the beginning, there were no coins and just two generals however now Byzantium has minted almost over 90% of it's currency. Eventually, these new coin issuances will go to zero and generals must find a new means of supporting their army. This is the how all Bitcoins are created through the network's fixed issuance protocol.
+
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.
  
−
Messages can be passed between hands so the person delivering the message may not the person who wrote it. For this we can assume that the Byzantines used a complex system of wax chops to manage signatures and identity. In Bitcoin this is much more simply resolved through third party oracles and ECDSA to manage identity and using encryption to manage message security.
+
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.
−
 
 
−
The message that notifies other generals that a valid next move has been found also contains a full history of all the trade that happened in Byzantium. All generals keep a copy of the most up to date ledger containing all ownership rights in the kingdom. These rights include exchanges in Byzantium's own currency and tokens for rights to all other goods and services. Similarly, in Bitcoin, anything can be tokenized including national currencies. These tokens are managed on the Bitcoin ledger and so take advantage of the security and speed of Bitcoin. For a tiny amount of money, the citizens of Byzantium can pass a transaction record to any one of the generals and it will be transmitted to all generals. Most generals will add your transaction to the message they draft to determine the next move however if you don't attach enough money, they might only look at it and pass it around, or just throw it away. It's up to each general to determine what price they will add transactions to the ledger for if they successfully find the next move. By keeping order in the kingdom through honestly and truthfully recording all financial interactions, the Byzantine generals grow their power and influence, causing people to start using their ledger for all manner of things...
 

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"