BT

Facilitating the Spread of Knowledge and Innovation in Professional Software Development

Write for InfoQ

Topics

Choose your language

InfoQ Homepage News The Blockchain and the CAP Theorem

The Blockchain and the CAP Theorem

This item in japanese

Lire ce contenu en français

Bookmarks

Yaron Goland, principal architect at Microsoft, has published an article describing how a blockchain client can be made AP or CP based on its implementation. This works by being able to configure how many blocks must come after a transaction until it is accepted. The more blocks which have occurred after the transaction, the more likely it is to have a system wide consensus, making it consistent.

A blockchain is a peer to peer, distributed database, with no central source of truth. Goland explains how this could be particularly problematic with digital currencies such as bitcoin. A user may believe they have received bitcoins, exchange real money for them, and then check their wallet at a later point in time only to find out that the bitcoins have disappeared.

Whilst the blockchain is an immutable series of blocks, it's still possible for each peer to build up a different set of transaction histories. This divergence is known as forking, and is the cause of the consistency problem in Golands example. He explains that the way the blockchain resolves this is with a consensus algorithm, where eventually there is a majority agreement on which forks should be dropped:

"This is a pretty classic example of eventual consistency. Two conflicting values were written, the system gossiped them around and eventually a conflict resolution protocol was used to pick a winner."

Goland explains that it's choosing whether or not to wait for the blockchain to become eventually consistent that makes a client AP or CP. In order to be AP, a client should accept a transaction as soon as it's added to the blockchain. This way, there is no dependency on the rest of the peers, making it available, but there is a risk that the remaining peers will reject the transaction, sacrificing consistency. In order to be CP, the client should accept the transaction once the block chain has come to a consensus on it. This has the inverse effect, where the data is consistent, but risks becoming unavailable if there's a network partition preventing a consensus.

In terms of how to wait for a system consensus on a transaction, Goland has published a detailed explanation which he summarises as: "Don’t treat anything as existing until it’s at least X blocks in." This means that a client will wait for X more blocks to occur after a transaction until it is accepted.

Yaron also emphasises that being able to configure a client in this way does not violate CAP theorem. This is because this type of configuration is a tradeoff between availability and consistency - both cannot be had at the same time:

"So what we did above is not show that Bitcoin can be both AP and CP. What we did above is show how one can build two completely different systems with completely different CAP trade offs by keeping all the parts of Bitcoin the same except the clients."

In summary, Goland has demonstrated that despite the blockchain being a peer to peer model, strong consistancy requirements can be met. This is particularly important with digital currencies such as bitcoin, as it's this type of tradeoff which means that users are able to trust transactions.

Rate this Article

Adoption
Style

BT