Blockchain Properties: CAP Theorem and Byzantine Fault

CAP Theorem

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 properties

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 k blocks "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 k blocks 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.

Byzantine Fault

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:

If A is honest, then all honest components agree on the value x.
In any case, all honest components agree on the same value y.