A Note On Blockchains

Blockchains have three components, a data structure, a set of replicas, and a consensus mechanism:

• The data structure is often said to provide immutability or to be tamper-proof, but this is wrong. It is made out of bits, and bits can be changed or destroyed. What it actually provides is tamper-evidence, revealing that the data structure has changed.
• If an unauthorized change to the data structure is detected the damage must be repaired. So there must be multiple replicas of the data structure to allow an undamaged replica to be copied to the damaged replica.
• The role of the consensus mechanism is to authorize changes to the data structure, and prevent unauthorized changes. A change is authorized if the consensus of the replicas agrees to it.
  

Below the fold, some details.

Data Structure

The data structure used for blockchains is a form of Merkle or hash tree, published by Ralph Merkle in 1980. In the blockchain application it is a linear chain to which fixed-size blocks are added at regular intervals. Each block contains the hash of its predecessor; a chain of blocks. Hash algorithms have a limited lifetime, but while the hash algorithm remains unbroken it is extremely difficult to change blocks in the chain but maintain the same hash values. A change that does not maintain the same hash values is easy to detect.

Replicas

The set of replicas can be either closed, composed of only replicas approved by some authority, or open, in which case no approval is required for participation. In blockchain jargon, closed replica sets correspond to permissioned blockchains, and open replicas sets to permissionless blockchains.

Consensus Mechanism

1

4

2

7

3

10

4

13

5

16

6

19

An important result in theoretical computer science was published in The Byzantine Generals Problem by Lamport et al in 1982. They showed that the minimum size of a replica set to survive f simultaneous failures was 3f+1. Thus Byzantine Fault Tolerance (BFT) is the most efficient possible consensus mechanism in terms of number of replicas. BFT requires a closed replica set, and synchronized operation of the replicas, so can be used only in permissioned blockchains.

If joining the replica set of a permissionless blockchain is free, it will be vulnerable to Sybil attacks, in which an attacker creates many apparently independent replicas which are actually under his sole control. If creating and maintaining a replica is free, anyone can authorize any change they choose simply by creating enough Sybil replicas.

Defending against Sybil attacks requires that membership in a replica set be expensive. The cost of an attack is at least the membership cost of half the replica set, so that the attacker controls a majority of the replicas. Permissionless blockchains have implemented a number of ways to make it expensive to take part, including:

• Proof of Work (PoW), a concept originated by Cynthia Dwork and Moni Naor in 1992, in which the expensive resource is CPU cycles. This is the "mining" technique used by Bitcoin, and is the only technique that has been demonstrated to work well at scale. But at scale the cost and environmental damage is unsustainable; the top 5 cryptocurrencies are estimated to use as much energy as The Netherlands. At smaller scales it doesn't work well because renting 51% of the mining power is cheap enough to motivate attacks. 51% attacks have become endemic among the smaller alt-coins. For example, there were three successful attacks on Ethereum Classic in a single month.
• Proof of Stake (PoS) in which the expensive resource is capital tied up, or staked. Participants stand to lose their stake in case of detected misbehavior. The Ethereum blockchain has been trying to implement PoS for 5 years, so far without success. The technique has similar economic linits and vulnerabilities as PoW.
• Proofs of Time & Space (PoTS), advocated by Bram Cohen, in which the expensive resource is disk storage.

Conclusion

Eric Budish points out the fundamental problem with expensive defenses in The Economic Limits of Bitcoin and the Blockchain:

From a computer security perspective, the key thing to note ... is that the security of the blockchain is linear in the amount of expenditure on mining power, ... In contrast, in many other contexts investments in computer security yield convex returns (e.g., traditional uses of cryptography) ... analogously to how a lock on a door increases the security of a house by more than the cost of the lock.

The difference between permissioned and permissionless blockchains is the presence or absence of a trusted authority controlling the replica set. A decision not to trust such an authority imposes enormous additional costs and performance penalties on the system because the permissionless consensus mechanism has to be expensive.

Decentralization in Bitcoin and Ethereum Networks by Adem Efe Gencer et al compares the cost of a permissioned system using BFT to the actual Bitcoin PoW blockchain:

a Byzantine quorum system of size 20 could achieve better decentralization than proof-of-work mining at a much lower resource cost.

As an Englishman I appreciate understatement. By "much lower", they mean around 5 orders of magnitude lower.