If bitcoin blockchain solves byzantine general problem, can you give an example of how it solves it?
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
Each miner will starts to solve a puzzle just after he received his first transaction message. Some will receive
tr1 first, others will receive
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.
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.
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.
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.