Understanding blockchain can be structured in these layers. Blockchain system is the result of orchestration of these layers.

In the next part, we will assume that internet layer is in its default state: simply running. Which is when multiple machines can talk to each other. This allow us to think in a wider abstraction.

Consensus layer

To fulfil consensus layer, we need a digital signature scheme. This scheme come with three component, key generation algorithm, signing algorithms, and verification algorithms. Those three algorithms need to be polynomial (computationally possible) but to reverse engineer the products or doing a wild guess require exponential computation complexity. This principles make sure the signature is ideal.

State machine replication (SMR) is coming in as an issue in replication of machines. Multiple state machine will need the same sequence of state transition history to make sure the state in a machine is the same as the state in other machine. This transaction history is saved in an append only data structure. To solve this issue, we need a protocol, which is event driven codes that need to be obeyed by the machine. In SMR problem, the protocol need to guarantee the consistency and the liveness of the system.

Consistency is when all nodes agree on the same history. Liveness is when all nodes eventually receive a new transaction.

The million dollar question is: Does there exist a protocol that can guarantee consistency and liveness in the same time?

To solve this problem we can start from defining assumptions, create protocol based on the assumption we defined, and then relax the assumption to improve the protocol quality.

• permissioned, known IP address
• public key infrastructure, each nodes have pk-sk system and every nodes know other nodes pk
• synchronous, all nodes share a global clock and all message sent at t will arrived at t + 1
• all honest nodes, all nodes run the intended protocol

Round Robin Leaders

• Nodes take turns as leader
• leader sends the ordered list of transactions it knows to all other nodes
• to satisfy consistency: nodes need to operate in lockstep. In t where t > 0, every nodes append the ordered list from leader in t - 1
• to satisfy liveness: nodes need to run in at least n (number of nodes) step. It will make sure that every transaction that happened in the system will be appended to every node local history

Faults

When a node is dishonest, we call the node as faulty. There are three type of faulty:

• Crash fault, happened when a node is crashed, liveness compromised
• Omission fault, happened when a node send different data from what it should send, consistency compromised
• Byzantine fault, happened when a node is generally dishonest

Based on the unavoidable faults, we will change the assumption of all honest nodes, to for f, there are less than f nodes which are byzantine and n-f node are honest.

Byzantine Broadcast

To resolve byzantine failure, a round robin leaders can be improved by adding byzantine broadcast protocol. There is a sender which has a private input. A subroutine need to comply with:

• termination, each nodes will eventually halts and have the data
• agreement, all honest nodes hold the same history
• validity, if sender node is honest, then private input same as the data received by all nodes

The Dolev Strong Protocol

This protocol runs in a core assumption that the number of byzantine nodes is known. Let's say that the number of byzantine nodes is f. Then,

• in t = 0, sender send value v with its signature
• in t = {1, 2, 3, ...., f + 1}, if node i convinced of value v, then send the value v to other nodes with its signature
• if any node i, receive 0 or more than 2 different value, then don't append the value to the node's array.

Nodes can only be convinced in time t if it received message such that:

• references value v
• signed by the sender
• signed by >= t - 1 other node

These are notes from Foundations of Blockchain