Blockchain Properties: CAP Theorem and Byzantine Fault
A network of P2P blockchain nodes is a good example of a distributed data store. The theorem says that such system can have 2 out of 3 guarantees:
- Consistency — all nodes have the most recent data simultaneusly
- Availability — every request receives a response from one of the nodes
- Partition tolerance — network can deal with breakups
The blockchain network is AP. Since the network propagates the updates in a peer-to-peer manner, nodes need different time to catch-up, so some of them can return the stale latest block for example. In principle the network is eventually consistent, meaning all nodes will catch-up sooner or later.
Blockchain network, being a public distributed ledger must be resistant to arbitrary adversarial behaviour and have a way to find consensus. These features are defined as following:
- Persistence — once a transaction goes more than
kblocks "deep" into the blockchain of one honest player, it will be included in every honest player's blockchain with overwhelming probability, and it will be assigned a permanent position in the ledger
- Liveness — all transactions originating from honest account holders will eventually end up at a depth more than
kblocks in an honest player's blockchain
Or, in more simple words, liveness ensures that a network is always available and does not get stuck and persistence is the ability to achieve an eventual consensus using PoW, PoS, PoA etc.
Speaking of dishonest parties within the network, it must achieve a Byzantine fault tolerance.
The system is said to resist Byzantine faults if a component
A can broadcast a value
x, and then:
Ais honest, then all honest components agree on the value
- In any case, all honest components agree on the same value