See also: consensus
Primarily studied in the synchronous system model. Three forms:
Pseudocode properties (all implementations should satisfy these!):
- Initialize a hard-coded “genesis block” so everyone knows where the chain starts
- In each round
- One node is chosen as a leader. This leader can prove itself as leader to other nodes, non-leaders cannot pretend to be a leader or manipulate their chances of becoming a leader.
- Leader can create a set of round- blocks where all of there predecessors are strictly created in some previous round, each with a predecessor block. Blocks form an in-tree rooted at the genesis block.
- Form block using all known pending pending transactions
- Set the predecessor of to be the current longest chain, break ties arbitrarily
- Immediately broadcast to all other nodes
We define a sequence as -balanced if in every window where and a strict majority of leaders in that sequence are honest.
On finality: if , we can consider all but the last blocks in the chain finalized. is up to the user to determine what parts of the chain they want to consider finalized.
If we assume that the rate of block production is slow relative to the maximum message delay then inadvertent honest forks rarely occur.
We define as the last blocks of the longest chain where is the current tree of all transactions known. is potentially ill-defined if there are multiple longest chains.
Theorem: if a leader sequence is -balanced, then for every possible sequence has
- The common prefix property: is well defined
- Finality: one a block is confirmed, it is always confirmed,
- Liveness: if a transaction is known to all honest nodes, it will eventually be included in
In the case that we chose completely random leaders:
- we can expect randomly chosen leaders to be reasonably balanced
- on average, expect nodes to be honest
- bigger window length means that we are less likely to see Byzantine nodes
- Probability of a given length window being Byzantine is where is some constant (exponential is good!)
- Probability of a given length window being Byzantine is where is the length of the sequence we’re considering
- Thus we get a failure probability less than some if
- however, there is a small but non-zero chance of balancing failure