In this article I argue that depending on how one programs one’s client, one can build a Consistent and Partition Tolerant or Available and Partition Tolerant system on top of Bitcoin or really any block chain. And no, that isn’t a contradiction and no this doesn’t violate the CAP theorem.
[Note: Lots of updates in response to feedback]
1 Thanks
Thank you to Ashok Misra, Marc Walter & Yorke Rhodes who provided feedback on this article. Please note that they did not officially review or sign off on it in anyway and are in no way responsible for its content. It really and truly is all my fault.
2 Who cares?
So who cares about CAP and Bitcoin in particular or a block chain in general? It’s mostly just me and a few other people. I’m only curious because forcing myself to go through the arguments of how CAP applies to a block chain helps me understand how a block chain works. But if you aren’t a distributed systems geek feel free to find another article to read.
Now, it’s just us distributed systems geeks. BTW, if you could use a quick refresh on CAP feel free to head over here.
But I’m also looking for block chain geeks. I’m going to assume my dear reader is pretty familiar with how block chains work, especially Bitcoin.
3 Disclaimers
The purpose of this article is just to show conceptually how block chains, using Bitcoin as an example, can be configured to provide either CP or AP functionality. This is not intended as an exhaustive catalog of all the possibilities of how this can be achieved. Rather I’m using a single example, in this case Bitcoin, just to illustrate the point that depending on how one configures one’s use of Bitcoin in particular and block chains in general, one can get either CP or AP behavior.
4 A note on terminology
It seems like there is a consensus that the proper phrase is “blockchain” and not “block chain”. I don’t care. It’s my blog and I’m calling it “block chain”. I know I will lose this battle but I’m allowed my eccentricities.
A more interesting (to me anyway) question is if the correct phrasing is “the block chain” or “a block chain”. Given that there are numerous independent and/or forked implementations of block chains using “the block chain” does seem misleading so I try to use “a block chain”.
Also note that I’ve tried to adopt the convention that “Bitcoin” refers to the entire Bitcoin ecosystem, software, hardware, etc. While “bitcoin” refers to an actual coin that one can use on the Bitcoin block chain.
5 Available and Partition Tolerant (e.g. eventually consistent)
For those who want a system that can take a licking and keep on ticking the CAP selection is available and partition tolerant. This means we are giving up consistency. By consistency we mean that multiple people could write to the same value and some readers might see one write and other readers might see the other write and eventually the system might coalesce into a single agreed value but until then the system will authoritatively return potentially conflicting responses. If we had kept consistency then once we get a write accepted by the system we know all readers will either see that value or get an error.
Traditionally those who come down on A and P in CAP choose to build a system that is eventually consistent. This isn’t strictly necessary but it would be sort of perverse not to.
Let’s walk through an eventually consistent scenario on a block chain.
There exists on the consensus chain transaction T1 in which a large amount of bitcoin is moved to an output assigned to public key P1 which belongs to user U1.
User U1 now publishes a transaction, T2, which moves the bitcoin from T1 to the control of public key P2. P2 belonging to user U2. T2 is part of an agreement between U1 and U2 where U1 moves bitcoin to U2 and U2 executes a money transfer (outside of Bitcoin) to U1.
So, once U2 sees T2 and thus can see that U1 has kept up their side of the bargain, then U2 executes the money transfer (again, outside of Bitcoin) of money to U1.
After the money has been transferred, U2 tries to spend the bitcoin from T2 and finds out that T2 has disappeared! Since the money transfer can’t be reversed U1 has U2’s money but U2 doesn’t have U1’s bitcoin.
5.1 A completely unrealistic scenario only intended to illustrate a point
In this section I’m going to demonstrate how the above situation might have occurred. That is, how U2 thought that U1 had moved the bitcoins to U2’s control but in fact did not. The attack I describe below is not feasible in the real world as described. But my goal here isn’t to get into a deep dive discussion of the various security implications of gossip protocols, tactical network partitioning attacks and colluding miners. Rather the goal is to give the reader a very general sense of why eventual consistency isn’t ideal in a monetary system like Bitcoin and how it can be abused.
In this case U1 knows that U2 always gets data from miner M1. So what U1 does is submit T2 to M1. At the same time U1 studies the transfer of data in the Bitcoin network and figures out which miners are “far away” in network terms from M1. U1 then creates a new transaction, T3 that just moves the bitcoin in the output of T1 to key P3, which is actually owned by U1. But U1 puts a high transaction fee on T3.
While this is happening M1 mints a block that contains T1. U2 sees that block, gets excited and moves the money. But at the same time all the other miners in the world are minting blocks with T3. Eventually M1 is going to find out about T3. What happens next depends on how M1 finds out about T3.
If M1 finds out about T3 as a stand alone transaction that isn’t in a block yet then M1 will realize that T3 conflicts with T2. If the tip of M1’s chain contains T2 and if the transaction fee in T3 is high enough then M1 might abandon its fork and create a new one that contains T3. Alternatively M1 might decide to hold to its current block with T2 and hope it beats any other forks with T3. A bet its likely to lose for the reasons explained below.
If M1 finds out about T3 as part of another forked chain and if T3 is in the tip of that chain then M1 has to make a bet as in the previous paragraph. Does M1 think its chain will get bigger faster than the other fork? If it does then it might hold on to its fork (and T2). Alternatively, M1 might decide that the other chain is going to win and switch (thus abandoning T2).
If M1 finds out about T3 as part of another forked chain that is longer than M1’s chain then we are done. The rules are that the longer chain wins. So M1 would abandon its fork and adopt the longer chain. Note that this isn’t necessarily true. In some cases M1 might actually hold on to its fork if the other longer chain isn’t too much longer and M1 has some reason to believe it can eventually win.
But in our scenario U1 flooded T3 to lots and lots of people. So more miners are going to be working with T3 than T2 and therefore T3 is all but certain to win. Eventually some fork with T3 will get so much longer than M1’s fork that M1 will be forced to give up on its fork (and T2).
So unless M1 by itself has so much processing power that it can mine blocks faster than all the people U1 sent T3 to (which is unlikely) then all roads lead to a situation where M1 abandons its fork and adopts a chain that contains T3, not T2.
The end result is that the consensus chain will contain T3 and not T2 and hence U2 won’t get the money sent in T2 since T2 won’t be in the consensus chain. T3 will.
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.
6 Consistent and Partition Tolerant
Even the theoretical ability to launch an attack like the previous one isn’t something one wants to be possible in what amounts to a currency system. What one really wants is strong consistency. In fact what we really, really want is ACID semantics but I’ll get to that in another article. For now let’s just focus on consistency in the CAP sense. Which in this case means that when U2 sees T2 then U2 knows that T2 is the system consensus and can’t disappear or be changed.
So in a CAP sense we want to build a system that is consistent and partition tolerant. To do this we need to follow the algorithm I described in fairly painful detail here. Which can be briefly summarized as “don’t treat anything as existing until it’s at least X blocks in.”
So now let’s replay our previous scenario and see how things change.
Again, there exists transaction T1 on the consensus chain and again it moves a large mount of bitcoin to an output assigned to public key P1 which belongs to user U1.
User U1 still publishes a transaction, T2, which moves the bitcoin from T1 to the control of public key P2. But User U1 is still up to its old tricks and publishes T3 which takes the same output as T2 did but moves it to a public key that U1 controls. And, as before, U1 puts a high transaction fee on T3 and tells lots of miners about it who are “far away” from miner M1 that U2 uses.
But it turns out that U2 never sees T2 and so never executes the money transfer and so U2 at least is quite happy (U1, less so).
6.1 A still completely unrealistic scenario only intended to illustrate a point
Nothing has changed from the disclaimers I made about this attack in the previous section. This attack is still completely unrealistic. But I believe it illustrates the salient points about what changes in a block chain system like Bitcoin when one uses CP rather than AP.
Again, as in the previous section, U1 knows that U2 always get data from miner M1 (no, this isn’t how it actually works, it’s just a hypothetical to illustrate a point). So U1 submits T2 to M1 and at the same time U1 creates T3 (the transaction that moves the bitcoin out of T1 and back to a different key controlled by U1) and gives it to all the miners far away from M1 and puts in a high transaction fee.
Now as soon as M1 gets T2, it publishes it in a block. That block is seen by U2 but unlike in the previous section U2 doesn’t actually accept a transaction until it is X blocks in (and X is certainly higher than 1). Right now the transaction is only one block in on M1’s fork. So U2 ignores it.
Eventually the same process as described previously occurs and M1 will abandon its fork with T2 and adopt a fork with T3. So long as U2 sets X high enough then the probability that M1 will abandon its fork with T2 before T2 shows up at least X blocks in is so tiny that it’s not going to happen. So T2 will never get X blocks in and hence U2 will never acknowledge T2. U2 will just see T3 and so never make the money transfer.
7 Conclusion – Wait… didn’t we just disprove CAP?
Spoiler alert No, we didn’t.
I realize that the above examples can be a bit confusing. After all, we just showed Bitcoin being both AP and CP and CAP says you have to choose.
The problem here is one of terminology. What is “Bitcoin”?
If Bitcoin is just the miners then what we have shown is that if one changes how one interacts with the mining infrastructure then one gets different behaviors. That shouldn’t be surprising. It’s like saying that if you put a 6 ALV 335 Franklin helicopter engine in a helicopter then you get a helicopter but if you put the same engine into a Tucker 48 you get a car. The engine is still the same. It’s the system surrounding it that changed and those changes are very meaningful [A] [A] Unless you think that helicopters and cars are really just modes of transportation and hence basically equivalent. Which I suppose is true but really misses the point..
CAP captures trade offs regarding the behavior of an entire system including all of its parts and clients are one of those parts. So to speak of “Bitcoin” and to leave out the clients is to not describe the entire behavior of the system.
The way to think about the examples above is that we are really describing two different version of Bitcoin. In one version the clients trust transactions they see on the chain as soon as they are in a block and in the other version clients only trust transactions that are at least X blocks deep. By changing the client’s behavior we make different trade offs and so we fundamentally change Bitcoin.
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.
There is really nothing new here. For example, in Cassandra, one can do a single read (e.g. read a value from a local machine) or a quorum read in which Cassandra won’t return an answer until it has read from a majority of nodes in the quorum. Clients who only do quorum reads and quorum writes will get strong consistency while clients that do non-quorum reads and writes get eventual consistency. The core Cassandra system didn’t change, but the client’s behavior did and that behavior is part of the system and determines what guarantees the system provides.
So the fact that Bitcoin or Cassandra can be made AP or CP depending on the behavior of the clients doesn’t violate CAP. CAP covers everything and clients are part of everything. No one should be surprised that if you change a key part of the system’s behavior (in this case, how the clients work) then the system’s qualities will change as well.
To me the real point is that depending on how one configures one’s clients one can choose in Bitcoin in particular and block chains in general if the entire system will be AP or CP.
And just for the record I’m not Microsoft’s Chief Architect. In the article this was taken from I am called (correctly) principal architect at Microsoft. I wonder, did Google and Bing translate (tried both) mis-translate the Chinese for ‘principal architect at Microsoft’ into ‘Microsoft Chief Architect’? Or is the error in the Chinese?
Hey bro, I’m a student studying blockchain and distributed system right now, just read this article and I just want to thank you for giving me a better understanding of CAP theory and the concept of “defining a system”. Really Appreciate it.
BTW, love the tone you start your blog, I’m a geek lol!
Happy to help!