Consensus Problem in Blockchain

What:

How do all participants of a Distributed Ledger agree on a single, consistent version of history (aka the Byzantine Agreement Problem).

The solution?:
Come up with a Consensus Protocol that, even if there are some ($<50\%$) malicious actors, consensus can still be reached.

Impossibility Result:

Consensus is impossible if the majority ($\ge 50\%$)of participants are malicious.

Proof:

Setup:

Assumption:

• A perfect consensus protocol,
• Group 0 ($N/2$). Their input is ($0$)
• Group 1 ($N/2$). Their input is ($1$)
• Malicious actors can corrupt anyone, up to exactly $N/2$
• We split it into 3 scenarios

Scenario 1:

• Malicious corrupts nobody. Everyone is honest. The output will be a single, agreed-upon value. It could be either 0 or 1.

Scenario 2:

• Malicious affects all of Group 0. They all act as if their input was 0.
• Validity says that the output must be 1 (as it was just honest people saying 1)

Senario 3:

• Malicious affects all of Group 1. They all act as if their input was 1.
• Validity says that the output must be 0 (as it was just honest people saying 0)

Contradiction (Paradox):

• From the perspective of the honest party, World 2 is exactly the same as World 1. The vice versa is true for World 3.
• Thus, the 3 world are indistinguishable.
• Thus, the honest participants must behave in the same way.
• But, World 2 and World 3 have different outputs.
• Thus, they don’t all agree.
• Thus, the Agreement property is violated.
• 🫳🎤

Bitcoin’s Solution (Proof of Work):

• Let’s assume there’s a synchronous network (messages are guaranteed to arrive, even if delayed) with no setup (parties can join and leave at will).
• The majority is defined by the hash with the most computing power behind it