Difference between revisions of "The Byzantine Generals Problem"
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 here: https://people.eecs.berkeley.edu/~luca/cs174/byzantine.pdf
  
−
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 soldiers in the Byzantine army are led by a set of generals who have no set means to communicate a direction forward other than through agreeing as a group to enact a maneuver in unison. In Bitcoin, these generals are represented by the nodes who are constantly aggregating transactions into blocks and the soldiers are represented by the hashpower being applied to the network. A maneuver is a block being added to the ledger.
  
−
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.
+
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 has been abandoned and a new chaintip has formed. The protocol makes miners wait 100 blocks however in reality almost all orphan blocks are less than three blocks from the terminated chaintip.
  
−
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.
+
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.
  
−
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>
+
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.
  
−
== Links ==
+
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.
−
[http://expectedpayoff.com/blog/2013/03/22/bitcoin-and-the-byzantine-generals-problem/ Bitcoin & the Byzantine Generals Problem]
+
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.

Revision as of 12:56, 27 December 2019

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 soldiers in the Byzantine army are led by a set of generals who have no set means to communicate a direction forward other than through agreeing as a group to enact a maneuver in unison. In Bitcoin, these generals are represented by the nodes who are constantly aggregating transactions into blocks and the soldiers are represented by the hashpower being applied to the network. A maneuver is a block being added to the ledger.

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 has been abandoned and a new chaintip has formed. The protocol makes miners wait 100 blocks however in reality almost all orphan blocks are less than three blocks from the terminated chaintip.

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.

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