Notes

Blockchain is a Distributed System Blockchain consists of different actors. Each actor acts depending on personal incentives and on available information. When a new transaction is broadcasted to the network, nodes can decide if they want to include it as a copy in their ledger or to ignore it. When the majority of the actors decides on a single defined state, the consensus is achieved.

What is the Consensus? The consensus is simply the common agreement on something. It is a fundamental problem in distributed computing. The problem is: how can we reach a consensus through computers? Well, we need an algorithm. Definition: a consensus algorithm is a process used to achieve agreement on a single data value among distributed processes or systems. Let's try to improve our definition ... more formally.

Distributed Consensus Protocol: There are n nodes that each have an input value. Some of these nodes are faulty or malicious. A distributed consensus protocol has the following two properties:

• It must terminate with all honest nodes in agreement on the value.
• The value must have been generated by an honest node.

The context of Bitcoin Let's focus for a second on Bitcoin: a peer-to-peer system. What happens when Princess Leia wants to send the money that Han Solo deserves? Princess Leia has to broadcast the transaction to all the nodes within the network.

Ian's node might be in the network (not a requirement). Actually, he is running one of the nodes. He wants to be notified when the transaction did happen.

Distributed Consensus Several users are broadcasting this transaction. The nodes must agree on two things:

• All the nodes in the P2P network have a ledger consisting of a sequence of blocks, each containing a list of transactions, that they've reached consensus on.
• This leads to a single and global ledger.

Also, some of the nodes might have not being informed ---> the network is not perfect.

How exactly do nodes come to consensus on a block? At regular intervals, say every 10 minutes, every node in the system proposes its own outstanding transaction pool to be the next block. Then the nodes execute some consensus protocol, where each node's input is its own proposed block. If the consensus protocol succeeds, a valid block will be selected as the output. There are a number of technical problems with this approach.

Issues with Distributed Consensus First: consensus in general is a hard problem

• Nodes can crash
• Nodes can be malicious

Second: the network is imperfect

• Not all pairs of nodes are connected to each other
• Poor internet connectivity

Third: for real cases, latency is a real problem

• No global time so there is no common ordering of events based on timestamps.

Request: Fault Tolerance The goal is to achieved overall system reliability in the presence of a number of faulty processes. So, this requires to agree on some data value needed during computation. What happens when an actor decides to not follow the rules and to tamper with the state of the ledger? What happens when these actors are a large part of the network, but not the majority? In order to create a secure consensus protocol it must be fault tolerant.

Unsolvable Problems Focus on two well-known problems:

• The Two Generals Problem
• The Byzantine Generals' Problem Plus:
• Byzantine Fault Tolerance

The Two Generals Problem (Akkoyunlu te al. 1975) The scenario: two generals are attacking a common enemy. General 1 is the leader, while General 2 should obey General 1's orders. Each general's army has not enough power to defeat the enemy. They need to cooperate and coordinate the attack. There is one big caveat though. Since they have to agree on the attack time, General 1 sends out a messenger to General 2's camp. There is a chance that the messenger can get caught by enemy. If the messenger does not get caught, then General 2 has to acknowledge the message by sending the messenger back to General 1's camp. Again, there is a chance that the messenger can get caught by enemy. There is no way to guarantee that each general be sure the other has agreed to the attack plan! Both generals will always be left wondering whether their last messenger got through.

The Byzantine Generals' Problem (Lamport et al. 1982) In this scenario, the authors generalize the Two Generals Problem. So, we have manifold of Generals who need to agree on the time to attack the enemy camp. There is a twist! One or more generals can be a traitor. A traitor is a liar, and he can lie about his choice. Each general has a certain number of lieutenants. To achieve consensus, both the general and all his lieutenants must agree on the same choice. For simplicity, the choice is binary: attack or retreat.

Even if the General is a traitor, consensus must be achieved anyway. Thus, all lieutenants take a majority vote. For any m, OM(m) (Oral Message) reaches the consensus if there are more than 3m generals and at most m traitors.

The algorithm can reach consensus as long as 2/3 of the actors are honest. If the traitors are more than 1/3, consensus is not reached, the armies do not coordinate their attack and the enemy wins.

Case 1

• The commander sends v to all lieutenants.
• L1 sends v to L2 && L3 sends x to L2.
• L2 <--- majority(v, v, x) := v.
• L3 is the traitor!
• The final decision is the majority vote from L1, L2, L3.
• The goal is for the majority of all the L* to pick the same decision not a specific one.

Case 2

• The commander sends x, y, z to L1, L2, L3, respectively.
• L1 sends x to L2, L3 && L2 sends y to L1, L3 && L3 sends z to L1, L2.
• L1 <--- majority(x, y, z) | L2 <--- majority(x, y, z) | L3 <--- majority(x, y, z).
• Commander is the traitor!
• They all have the same value.
• If x, y, z are different commands, a default option would be to retreat.

A tree with n = 7 and m = 2:

Byzantine Fault Tolerance (BFT) Byzantine Fault Tolerance is the characteristic which defines a system that tolerates the class of failures that belong to the Byzantine Generals' Problem. Byzantine Failures are the most difficult class of failures. There are no restrictions and no assumptions on the kind of behavior and data a node can inject in the network. BFT is required in airplanes, nuclear power plants and even SpaceX. SpaceX requires it to handle situations where the computers do not agree (e.g., changing values in memory/registry due to radiation). In the context of Byzantine Generals Problem, this is indeed BFT as long as the number of traitors do not exceed 1/3 of the generals. Blockchains are distributed systems with no central authority. What is stored in the ledgers could be of high value so there are relevant economic incentives by malicious nodes to cause faults. With not BTF, a malicious node can transmit false transactions. This would then impede the achievement of integrity.

Proof-of-Work (PoW) Bitcoin solves the Byzantine Generals Problem... Under a probabilistic flavor. Here, the leader is the responsible for transmitting the block to the network so that the other peers can verify it. To be elected as a leader and choose the next block, the network has to solve a mathematical puzzle.

Given data X, find a number n such that the hash of n appended to X is a number less than Y.

Since hash() is a cryptographic hash function, we must use brute force to find a solution. In probability, the node that will solve the problem first is probably the one with more computing power. These nodes are called miners. It is a very popular algorithm, for which is very hard to find a solution. When the solution is found, it is very easy to verify it. When a miner finds a solution, it gets rewarded ---> incentive!

An attack to the whole network would cost a lot. Energy, computational power, hardware, potential missed rewards.

Each block is mined every 10mins. For a safe transaction, it can take up to 1 hour. Miners are rewarded 6.25 Bitcoins for mining each block. Remember how computational power increases the chances of breaching algorithms? Mining difficulty increases with time. The mining difficulty is adjusted every 2016 blocks. The difficulty can even go down if the supply of computational power decreases.

Proof-of-Stake (PoS) Let's start with an analogy, a probabilistic analogy

• Think about a lottery
• If Alice has more tickets than Bob
• Then Alice is more likely to win the lottery.

Similarly, under PoW if Alice had more computational power than Alice, she is more likely to be able to mine the next block. Similarly, under PoS if Alice had more stake than Bob, she is more likely to be able to mine the next block.

The big difference between PoW and PoS is that the latter replaces the computational power with the stake. We refer to the stake as a given amount of currency that a given wallet is willing to lock up and freeze for a certain amount of time. In return, you get a chance of mining the next block proportional to the stake you froze. Issue: nothing-at-stake ---> nodes are not disincentivized in mining forked chains. Some hybrid consensus algorithms PoS-PoW have been developed.

Consensus Algorithms We need robust consensus algorithms! These algorithms verify the validity of transactions:

• Through them we reach the consensus.
• Through them we avoid the double-spending problem.