<p><strong>The Byzantine Generals' Problem</strong></p>

<p>Imagine a time during the dark ages, where a pirate ship is under attack. There are 200
pirates aboard the pirate ship surrounded by six army ships of 50 warriors each, who've
anchored, surrounding the pirate ship. Each army ship is commanded by a captain. The 300
warriors can easily overpower the 200 pirates aboard the pirate ship. However, if they don't
all attack simultaneously, there is a very real risk that the warriors will be outnumbered by
the pirates and they'll go on to lose the battle.</p>

<p>So, how can the captains all agree on the same time to attack the pirate ship? These days,
we'd simply need a quick group video-conference call, and the captains would have to
agree to attack at 22:00 hours (10 PM).
However, back in the dark ages, things were a little more complicated:
The 22:00 attack message could only be passed on by a sailor on a small boat. He
has to sail around each army ship, visiting each captain in turn to confirm.
Any captain may be a traitor and in league with the pirates in the pirate ship.</p>

<p><strong>Losing strategy</strong></p>

<p>Captain 1 decides to attack at 22:00. He sends his sailor out with the message (22:00 attack)
to deliver to Captain 2. Upon arrival, Captain 2 reads the message, notes the time of the
attack, and sends a message that also says 22:00 attack. He sends the sailor on to share the
message with Captain 3. However, we have a problem. Captain 3 is a traitor. He wants the
attack to fail. So, when he gets the message, he rips it up and replaces it with a new message
that says 21:00 attack (9 PM). The sailor continues unaware. Captain 4 now receives a
message saying 21:00 attack. He notes the time, signs the message saying 21:00 attack and
sends this on to Captain 5, who then sends the same message to Captain 6. Now, the
message has gone around everyone, but we have a problem. The dishonest captain has
disrupted the result. We now have three captains (4, 5, and 6) with 150 warriors attacking
the pirate ship at 21:00. Expecting others to join them, they instead get outnumbered and
overpowered by the 200 pirates. The victorious pirates now stream out of the pirate ship
and join forces with the treacherous Captain 3. Suddenly, the two remaining captains (1 and
2) have only 100 warriors and find themselves fighting 200 pirates plus 50 traitors.
Unfortunately, the pirates and traitors win.</p>

<p><strong>Winning strategy</strong></p>

<p>Captain 1 wants to send the same message (attack at 22:00). However, this time, there are
two new rules he must obey:
He must spend 10 minutes preparing any new message for it to be valid
He must include the history of every previous message in every new message
So, let's see what happens this time. As before, Captain 1 sends the message (22:00 attack)
with the sailor on the boat. This time, however, it is different for Captain 2, because he
knows two things for certain:
The message must have taken 10 minutes to prepare
There are no previous messages, so it must be the truth (even if Captain 1 is a
traitor and put in the wrong time, it doesn't matter; if the majority of captains
followed this suggestion and went with a 22:00 attack time, they would still
outnumber those in the pirate ship and win the battle)</p>

<p>So, now it is time for Captain 2 to send a message. As required, he spends 10 minutes
preparing the new message and he embeds Captain 1's message into his own. The sailor
then sets off with this message (now in fact, it is two messages chained together as the
second has the first embedded within it). Now it gets to Captain 3.
Remember, he's the traitor. So, what does he do? Last time, he changed the message to 21:00
attack so that captains 4, 5, and 6 would attack early and get overpowered. Now, however,
he can't because, under the new rules, he has only 10 minutes to prepare a message for
Captain 4. He has two options:
1. Cheat by changing the message to 21:00 attack. To do this, he needs to (a) spend
10 minutes creating his message and then (b) spend an extra 2 x 10 minutes
working to create replacement 21:00 attack messages from Captains 1 and 2 to
embed these into his message and carry out this 30 minutes of work within the
next 10 minutes to avoid the other captains knowing that he's a traitor.
2. Admit defeat and prepare the 22:00 attack message during those 10 minutes.
In other words, every captain has got no more than 10 minutes to provide the next captain
with something that would take more than 10 minutes to fake if they were trying to be
dishonest. If they can't deliver it within 10 minutes, everyone knows they're dishonest and
ignores them, rendering their attempts to mislead others useless.</p>

CC BY-SA 4.0
2020-02-29T02:06:47.547Z
This is an amazing analogy, +1
woojoo666
CC BY-SA 4.0
2018-06-08T06:26:09.413Z
2018-06-08T06:26:09.413Z
Chirag Maliwal
<p><strong>The Proof of Work algorithms is a probabilistic solution to the Byzantine General's problem</strong> in the case where traitorous generals represent strictly less than 50% of the generals.</p>

<p>To simplify, the main thing a solution to this problem has to guarantee is that all honest generals (honest miners) agree on the same thing. </p>

<p>Let's assume there are 10 miners in the Bitcoin blockchain and a new transaction comes in. This transaction (noted <code>tr1</code>) is broadcasted among all miners. 10 of those miners are traitorous and they broadcast another transaction (noted <code>tr2</code>) where they changed the recipient in <code>tr1</code>.
Each miner will starts to solve a puzzle just after he received his first transaction message. Some will receive <code>tr1</code> first, others will receive <code>tr2</code> first.</p>

<p>The puzzle is difficult enough that, on average, a solution will be found every 10 minutes. After 10 minutes, miner M solves the proof of work problem. He broadcasts his solution to the 9 other miners and includes in there the transaction he received first. Upon receiving this solution, each miner adjusts his transaction to the new one received. They then all work on the next puzzle. After 1 hour, the chain has 6 blocks (6 puzzles solved). Each general can evaluate how much CPU was necessary to get solve 6 puzzles in 10 minutes. Each general knows then if the majority of the general contributed to building this chain. If the answer is yes, then they agreed on the transaction inside the initial block of this chain.</p>

<p>Now an interesting point: what if the transaction in the initially mined block is <code>tr2</code>? The solution described here doesn't prevent from agreeing on a false transaction. <strong>In the context of the Byzantine Generals problem, it is sufficient for the generals to agree on a false plan as long as they agree.</strong></p>

CC BY-SA 4.0
2022-05-14T17:52:45.820Z
is there a reason you say POW algorithm'S' in plural? Maybe I'm mistaken in thinking of POW as a one single algorithm?
StatsScared
CC BY-SA 3.0
2018-02-28T10:07:46.373Z
2018-02-28T10:07:46.373Z
Aymen
<p>If bitcoin blockchain solves byzantine general problem, can you give an example of how it solves it?</p>

<p>Thanks</p>

<blockchain><ethereum>
Does Bitcoin Blockchain solves Byzantine General Problem?
Minisha
# Does Bitcoin Blockchain solves Byzantine General Problem?

(Asked by: username_0 on 2018-02-28)

If bitcoin blockchain solves byzantine general problem, can you give an example of how it solves it?

Thanks

**Tags:** blockchain, ethereum


---

## 2 answers

### Answer by username_3 on 2018-02-28. Score: 7 | Accepted answer

**The Proof of Work algorithms is a probabilistic solution to the Byzantine General's problem** in the case where traitorous generals represent strictly less than 50% of the generals.

To simplify, the main thing a solution to this problem has to guarantee is that all honest generals (honest miners) agree on the same thing.

Let's assume there are 10 miners in the Bitcoin blockchain and a new transaction comes in. This transaction (noted `tr1`) is broadcasted among all miners. 10 of those miners are traitorous and they broadcast another transaction (noted `tr2`) where they changed the recipient in `tr1`.
Each miner will starts to solve a puzzle just after he received his first transaction message. Some will receive `tr1` first, others will receive `tr2` first.

The puzzle is difficult enough that, on average, a solution will be found every 10 minutes. After 10 minutes, miner M solves the proof of work problem. He broadcasts his solution to the 9 other miners and includes in there the transaction he received first. Upon receiving this solution, each miner adjusts his transaction to the new one received. They then all work on the next puzzle. After 1 hour, the chain has 6 blocks (6 puzzles solved). Each general can evaluate how much CPU was necessary to get solve 6 puzzles in 10 minutes. Each general knows then if the majority of the general contributed to building this chain. If the answer is yes, then they agreed on the transaction inside the initial block of this chain.

Now an interesting point: what if the transaction in the initially mined block is `tr2`? The solution described here doesn't prevent from agreeing on a false transaction. **In the context of the Byzantine Generals problem, it is sufficient for the generals to agree on a false plan as long as they agree.**

> **Comments:**
> **username_4**: is there a reason you say POW algorithm'S' in plural? Maybe I'm mistaken in thinking of POW as a one single algorithm?  

---

### Answer by username_1 on 2018-06-08. Score: 4

**The Byzantine Generals' Problem**

Imagine a time during the dark ages, where a pirate ship is under attack. There are 200
pirates aboard the pirate ship surrounded by six army ships of 50 warriors each, who've
anchored, surrounding the pirate ship. Each army ship is commanded by a captain. The 300
warriors can easily overpower the 200 pirates aboard the pirate ship. However, if they don't
all attack simultaneously, there is a very real risk that the warriors will be outnumbered by
the pirates and they'll go on to lose the battle.

So, how can the captains all agree on the same time to attack the pirate ship? These days,
we'd simply need a quick group video-conference call, and the captains would have to
agree to attack at 22:00 hours (10 PM).
However, back in the dark ages, things were a little more complicated:
The 22:00 attack message could only be passed on by a sailor on a small boat. He
has to sail around each army ship, visiting each captain in turn to confirm.
Any captain may be a traitor and in league with the pirates in the pirate ship.

**Losing strategy**

Captain 1 decides to attack at 22:00. He sends his sailor out with the message (22:00 attack)
to deliver to Captain 2. Upon arrival, Captain 2 reads the message, notes the time of the
attack, and sends a message that also says 22:00 attack. He sends the sailor on to share the
message with Captain 3. However, we have a problem. Captain 3 is a traitor. He wants the
attack to fail. So, when he gets the message, he rips it up and replaces it with a new message
that says 21:00 attack (9 PM). The sailor continues unaware. Captain 4 now receives a
message saying 21:00 attack. He notes the time, signs the message saying 21:00 attack and
sends this on to Captain 5, who then sends the same message to Captain 6. Now, the
message has gone around everyone, but we have a problem. The dishonest captain has
disrupted the result. We now have three captains (4, 5, and 6) with 150 warriors attacking
the pirate ship at 21:00. Expecting others to join them, they instead get outnumbered and
overpowered by the 200 pirates. The victorious pirates now stream out of the pirate ship
and join forces with the treacherous Captain 3. Suddenly, the two remaining captains (1 and
2) have only 100 warriors and find themselves fighting 200 pirates plus 50 traitors.
Unfortunately, the pirates and traitors win.

**Winning strategy**

Captain 1 wants to send the same message (attack at 22:00). However, this time, there are
two new rules he must obey:
He must spend 10 minutes preparing any new message for it to be valid
He must include the history of every previous message in every new message
So, let's see what happens this time. As before, Captain 1 sends the message (22:00 attack)
with the sailor on the boat. This time, however, it is different for Captain 2, because he
knows two things for certain:
The message must have taken 10 minutes to prepare
There are no previous messages, so it must be the truth (even if Captain 1 is a
traitor and put in the wrong time, it doesn't matter; if the majority of captains
followed this suggestion and went with a 22:00 attack time, they would still
outnumber those in the pirate ship and win the battle)

So, now it is time for Captain 2 to send a message. As required, he spends 10 minutes
preparing the new message and he embeds Captain 1's message into his own. The sailor
then sets off with this message (now in fact, it is two messages chained together as the
second has the first embedded within it). Now it gets to Captain 3.
Remember, he's the traitor. So, what does he do? Last time, he changed the message to 21:00
attack so that captains 4, 5, and 6 would attack early and get overpowered. Now, however,
he can't because, under the new rules, he has only 10 minutes to prepare a message for
Captain 4. He has two options:
1. Cheat by changing the message to 21:00 attack. To do this, he needs to (a) spend
10 minutes creating his message and then (b) spend an extra 2 x 10 minutes
working to create replacement 21:00 attack messages from Captains 1 and 2 to
embed these into his message and carry out this 30 minutes of work within the
next 10 minutes to avoid the other captains knowing that he's a traitor.
2. Admit defeat and prepare the 22:00 attack message during those 10 minutes.
In other words, every captain has got no more than 10 minutes to provide the next captain
with something that would take more than 10 minutes to fake if they were trying to be
dishonest. If they can't deliver it within 10 minutes, everyone knows they're dishonest and
ignores them, rendering their attempts to mislead others useless.

> **Comments:**
> **username_2**: This is an amazing analogy, +1  

---

