Difference between revisions of "The Byzantine Generals Problem"

m
 
(8 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 that proposed moves are from another general. This is what Proof of Work resolves for Bitcoin by creating a means for a general to attach authority to a proposed maneuver. If all other generals agree their maneuver is valid and has the correct authority they will try to calculate a new move to follow the winning move.
+
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 obey the first valid message they receive that is encoded with an appropriate cipher. The messaging system must ensure that
+
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.
  
Messages can be passed between hands so the person delivering the message may not the person who wrote it. In Bitcoin this is resolved through parties using ECDSA and other encryption schemes to manage identity.
+
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.
 
 
In Bitcoin these generals are represented by the nodes who manage the network, and the plan is represented by their agreement on which blocks they use to build the ledger. The messaging protocol is the Bitcoin Peer to Peer protocol which nodes use to transmit transaction and block data to each other.
 
 
 
 
 
 
 
The messaging protocol must ensure that a small number of traitors cannot cause the loyal generals to move forward with a bad plan.
 
 
 
 
 
Generals are rewarded for issuing a successful command if the other generals follow all 100 subsequent commands on top of it. Commands are in one historical order and must be issued one after the other. Where two generals issue successful commands at or near the same time, other generals will always follow the general from whom they heard the next valid command first. In Bitcoin, when nodes find blocks simultaneously, only the block that the next valid 100 blocks are built upon receives a reward. This ensures that one of the blocks will be abandoned.
 
 
 
Generals in the Byzantine army compete with each other using either soldiers they pay directly or allied soldiers to calculate the next right move. Generals are rewarded for calculating the correct move and use this money to pay their soldiers. In Bitcoin, the soldiers are the voting hashpower being applied to any given node. A node can have hashpower that is paid for directly by the node's owner, or operates as a mining pool to offer a share of any block rewards to hashpower that contributes proof of work.
 
 
 
Generals can reject another general's command for any reason however if the remaining generals agree to it and make their next moves on top of it, this cause any rejecting generals' soldiers to split from the non-rejecting generals'. This is what caused the BTC and BCH forks to separate their own ledgers from Bitcoin as their generals wanted to work with commands considered invalid.
 
 
 
Generals with allied soldiers show proof that they are good at formulating moves and pay out fairly. Pool mining nodes compete for hash by demonstrating an ability to find valid block solutions reliably and paying out fairly to contributors. Pool mining groups represent a large proportion of network hash (get figures) and with pools competing for customer hash. These pools represent an easy way for small players to participate without the cost of running a node. Many of the large pools (and mining groups) run several nodes as part of their operations however only one node can find a block so in instances where the nodes of a single operator each find a different valid solution simultaneously, one of those blocks becomes an orphan.
 
 
 
Any person could try to be a general in the Byzantine army, but only someone who found a correct next move could be recognized by the other generals. A correct next move contained a history of things that happened in Byzantium and a valid codex. All generals had to agree that things that happened were true, and each thing that happened could only be written down once. In Bitcoin, these things are the transactions that take place on the BitcoinSV network. The codex is the proof of work applied to the block header.
 
The generals regulate the army's activities by agreeing how difficult the codex will be to solve ensuring that only a general with enough soldiers could possibly find a solution.
 

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.