CAP Theorem and blockchain

In theoretical computer science, the CAP theorem states that it is impossible for a distributed data store (such as a blockchain network) to simultaneously provide more than two out of the three guarantees: Consistency, Availability & Partition tolerance.

CAP Theorem – the parts

  • C: Consistency – At any given time, all nodes in the network have exactly the same (most recent) value.
  • A: Availability – Every request to the network receives a response, though without any guarantee that returned data is the most recent.
  • P: Partition tolerance – The network continues to operate, even if an arbitrary number of nodes are failing.

Due to the nature of distributed data stores (such as blockchain), Partition tolerance is a given fact; there will always be failing/unreachable nodes in the network (not least because of the unstable nature of the internet). CAP Theorem states that one has to choose between C (Consistency) or A (Availability) when in the presence of P (Partition):

Availability over Consistency (A + P)

Every request to the network receives a response, even if the network cannot guarantee it is up to date due to network partitioning (failing nodes).

Choosing Availability over Consistency for a world-wide distributed system will make it highly available, but its data will be out of date for 99.99% of the time. Furthermore, no-one will be able to guarantee that the data returned is in fact the most recent. The best example is Facebook, as it's much more important to get into the network, than to see the latest updates of a particular person (depends who you ask, of course!).

Consistency over Availability (C + P)

The system will return an error or a time-out if particular information cannot be guaranteed to be up to date due to network partitioning (failing nodes). Choosing Consistency over Availability for a world-wide distributed system will make it highly accurate, but it will most likely be unavailable for 99.99% of the time.

Blockchain

As blockchain networks (such as Bitcoin) are distributed systems, they have to deal with Partition tolerance. Out of the two options that remain, they choose Availability over Consistency. If, for example, Bitcoin would instead choose consistency, it would mean that in the event of a connectivity problem, or any failing node/component (which happens all the time), you wouldn’t be able to use/send/receive Bitcoin. Blockchain networks in general use other means of becoming eventually consistent over time: through mining and blocks.

So, which one does Bitcoin sacrifice? Availability, consistency, or partition tolerance?

  • If Bitcoin sacrifices partition tolerance, this means that Bitcoin can only be run on networks that reliably deliver messages.
  • If Bitcoin sacrifices availability, this means that the Bitcoin network pauses when transactions can’t be committed. So, if there’s a connectivity problem, you can’t read or write Bitcoin data at all.
  • If Bitcoin sacrifices consistency, this means that new Bitcoin transactions aren’t guaranteed to be committed. So, you send a transaction and it may or may not be received by other parties.

So, what’s the verdict?

Well, Bitcoin is “eventually consistent,” which is a polite way to say that it is not consistent. That is, if you send a Bitcoin transaction, there’s no guarantee that it will be received. Sounds bad? Maybe.

First, remember that the CAP theorem applies to all financial systems just as it applies to Bitcoin. A credit card is a good example of an “eventually consistent” system: typically, you pay a bill only once a month. This makes it easy to violate the constraints of the system by spending more money than you have. Of course, this risk is (theoretically) mitigated because you know that the credit card companies will ruin your credit score if you do it.

Eric Brewer, the originator of the CAP theorem, pointed out in 2012 that the CAP theorem only prohibits a tiny fraction of the design space of distributed systems; it’s still possible to create many useful and robust distributed systems. Although Bitcoin doesn’t provide firm guarantees that your transactions have been committed, in practice it does a pretty good job. The longer you wait, the more confident you can be that a transaction has gone through successfully:

In a matter of seconds, the transaction will be relayed around the world. At this point, it will be difficult but possible to reverse.

After an average of five minutes, the transaction will be inserted into a block. About 999 in 1000 blocks make it into the blockchain, so you can feel pretty good at this point. 1 in 1000 blocks is an orphan block; if the transaction ends up in an orphan block, you just ignore it and wait until the transaction goes into a non-orphan block.

The longer you wait, the more blocks will pile up on top of the block containing your transaction, and the more certain you can be that your transaction won’t be rolled back. In practice, the longest ever fork in the blockchain was 24 blocks in length, and even this was a one-time event caused by a software bug. To date, no transaction more than five hours old has ever been rolled back.

To read about ways to intentionally exploit Bitcoin’s consistency guarantees, wait for the double spending article or find it on the Bitcoin Wiki.

Comments

Post a Comment

Popular posts from this blog

Length extension attack

Image
What is length extension? When a Merkle–Damgård based hash is misused as a message authentication code with construction H(secret ‖ message), and message and the length of secret is known, a length extension attack allows anyone to include extra information at the end of the message and produce a valid hash without knowing the secret. Quick sidebar, before you freak out: Since HMAC does not use this construction, HMAC hashes are not prone to length extension attacks. So, a length extension attack is a type of attack where an attacker can use Hash(message1) and the length of message1 to calculate Hash(message1 ‖ message2) for an attacker-controlled message2, without needing to know the content of message1. Algorithms like MD5, SHA-1 and most of SHA-2 that are based on the Merkle–Damgård construction are susceptible to this kind of attack. Truncated versions of SHA-2, including SHA-384 and SHA-512/256 are not susceptible, nor is the SHA-3 algorithm. A bit more details ...
Read more

Contract upgrade anti-patterns

Image
A popular trend in smart contract design is to promote the development of upgradable contracts . To be fair, existing techniques to upgrade contracts have flaws, increase the complexity of the contract significantly, and ultimately introduce bugs - even in the Zeppelin contract upgrade strategy. In this article, we are going to detail our analysis of existing smart contract upgrade strategies, describe the weaknesses we have observed in practice, and provide recommendations for contracts that require upgrades. In a follow-up blog post, we will detail a method, contract migration, that achieves the same benefits with few of the downsides. An overview of upgradable contracts Two ‘families’ of patterns have emerged for upgradable smart contracts: Data separation, where logic and data are kept in separate contracts. The logic contract owns and calls the data contract. Delegatecall-based proxies, where logic and data are kept in separate contracts, also, but the data contr...
Read more