Thread by @iamlevelhead

Thread: Byzantine Generals Problem
I think Blockchain is extremely cool. It's very cool because at the core of all the buzzwords, a blockchain solves a very difficult problem in computing, Byzantine Fault Tolerance.

1.) Before I get into Byzantine stuff I'm going to talk about another important problem called the Two Generals Problem. This is an experiment that represents the issues of computer networking over an unreliable link. In this problem we will call these 2 nodes “Generals”

2.) In this situation, the generals and their armies have come upon a city they wish to attack. Each general’s army on its own is not enough to defeat the enemy army successfully, thus they need to cooperate and attack at the same time

3.) The problem arises because the 2 generals are separated by significant distance, think of it as they are on opposite sides of the city. General 1 is considered the leader and the other is considered the follower.

4.) In order for them to communicate and decide on a time of attack, General 1 has to send a messenger across the enemy’s camp that will deliver the time of the attack to General 2. But that could mean that the messenger could get captured and the message would be lost

5.) This will result in General 1 attacking while General 2 and his army hold their grounds. Assuming the first message goes through, General 2 still must acknowledge that he received the message, so he sends a messenger back, thus repeating the previous scenario where the...

6.) ...messenger can get caught. This opens up an infinite loop where both parties are sending acknowledgments back and forth with neither general knowing whether or not the message was received.

7.) If general 1 receives a message, how will the general 2 know that the message was received without an additional acknowledgment message from General 1?

Well, you can't because the 2 generals problem is currently unsolvable (yay).

8.) Buuut a new problem was iterated off this one and it stuck its roots in the blockchain space. The Byzantine Generals Problem :)

9.) Similar to the 2 Generals problem, the Byzantine Generals Problem deals with reliable computer systems handling malfunctioning components that give conflicting information to different parts of the system to ensure consensus within a distributed computing system.

10.) The difference now, is more than two generals need to agree on a time to attack their common enemy. The leader-follower paradigm described in the Two Generals Problem is transformed to a commander-lieutenant setup.

11.) To achieve consensus here, the commander and every lieutenant must agree on the same decision but a problem is that one or more of the generals can be a traitor, they can lie about their choice. So if 2 generals agree to attack, one could lie about attacking and retreat.

12.)

13.) In this Illustration, we can see that Lieutenant 3 is a malicious actor. Looking at the interaction between the honest counterparts, we can see that the decision is “v” while Lieutenant 3 is trying to tell Lieutenant 2 “x”.

14.) The final result is a majority vote by Lieutenant 1-3 is majority(v,v,x) = v therefore consensus is reached by the honest majority while there being a malicious actor in the system.

15.) In this illustration the commander has sent different input to the 3 lieutenants. So there’s no possible way they could come out with the same answer right? Not quite, remember there are two outputs, (Attack & Retreat) The inputs are different times of attack.

16.) Using the majority vote we find all lieutenants have found the same inputs which are x,y,z

L1(x,y,z)
L2(x,y,z)
L3(x,y,z)

Therefore the majority is majority(x,y,z) = x,y,z

17.) Because the Lieutenants have realized that the commander is sending out conflicting information, they can reach consensus on Retreat, because it is clear that the commander is peddling malicious information on the time of attack.

18.) The Byzantine Generals problem leads us to the notion of Byzantine Fault Tolerance. This is the characteristic of a system that tolerates the byzantine failures brought about in the byzantine generals problem.

19.) So how does this relate to blockchain? A blockchain is a distributed ledger that is not in control of any one party. It’s not news to anyone that these distributed ledgers hold massive amounts of value.

20.) It would be in the best interests of a hacker to cause faults in the system that could benefit them monetarily. In that case, a byzantine fault tolerance is necessary for a blockchain to operate effectively in a trustless environment.

21.) Take Bitcoin for example: in the absence of byzantine fault tolerance, a malicious actor could execute double spends or alter transactions which would pretty much eliminate the bitcoin blockchain’s reliability, and render the currency worthless.

22.) In November 2008 Satoshi explained the concept in a simple way, demonstrating general byzantine fault tolerance enabled by Proof of Work. Providing an example of Byzantine Generals brute forcing a wifi password, akin to the original problem of generals attacking a city.

23.) Here's the link to it. A good little informative read from the G.O.A.T
mail-archive.com/cryptography@m…

24.) What Satoshi’s idea enabled, was guaranteeing a way for an honest majority to come to consensus over something. She/he/they said “They don't particularly care when the attack will be, just that they all agree”

25.) By being able to calculate the expended cpu power on finding the proof-or-works, it can be seen whether or not the majority had come to consensus over the move.

The end. Honestly threads are a bit annoying to write. Would anyone prefer medium or should I stick to twitter threads?

Oh lol if anyone wants to look at the original Byzantine Generals Problem research paper its right here people.eecs.berkeley.edu/~luca/cs174/by…