This paper assumes the reader is familiar with strong consistency as well as the basic design principles of block chains like Bitcoin. Brief reminders are provided below to refresh rusty memories.

Whenever CA and CB want to read/write to a shared state they will send all their reads and all their writes to S.

This approach is great because CA can be absolutely sure that once it’s write is accepted by S then any future reads from CB will see CA’s write.

But what happens if S fails? Or what happens if network connectivity between CA or CB and S is lost?

The system may be easy to reason about but it’s not terribly robust.

Now imagine that we replace server S with three servers, SA, SB and SC.

One can think of strong consistency as guaranteeing that for a pool of machines (in this case SA, SB and SC) their collective behavior will be indistinguishable to clients (in this case CA and CB) from having only a single server (our original server, S).

So in a strongly consistent system one gets the benefit of the robustness of having multiple servers while still having the same data model as if there was only one server. So the clients don’t care that they are talking to a group of machines. To them the experience will be the same as if all requests went to a single machine.

It’s worth pointing out that strong consistency doesn’t guarantee that the whole system can’t fail. Just like server S could go down and now nobody can read/write anything, so it is the case in distributed systems that if enough machines go down then the system will stop being able to handle read/writes in a strongly consistent manner. Strong consistency just guarantees equivalent behavior to a single server, that is, if enough machines are available the system is functional and if enough aren’t available then the system will visibly fail.

The way this all works is that Paxos depends upon having a known membership list of the machines in its quorum (where the quorum is how we refer to the group of machines, the servers if you will, that are trying to maintain the shared state). [A]  [A] It is possible to correctly implement Paxos in a multicast system where the exact identities of all members isn’t known but you do need to know the number of members and membership can’t change without going through Paxos itself. So the multicasting point is really just nit picking.

Paxos works by ensuring that a write will only be accepted if a majority of the quorum confirm they have accepted it. Reads work the same way, that is, a reader would only accept a value as being correct if that value was returned by a majority of the quorum members.

There are entire mountains of paper written about optimizations to Paxos but the above is the core idea.

The reason Paxos is interesting is that it was the first consensus protocol that was provably correct. As long as the members of the system follow the protocol (and ignoring attacks), one is guaranteed that the system will always have strong consistency.

In block chains there is a competition (at least in proof of work systems, proof of stake works differently) to create new blocks. Typically different groups of what are called miners are all racing to solve a proof of work problem off the current consensus chain [B]  [B] Systems like Bitcoin have what are called checkpoints that identify specific chain histories as being canonical. These checkpoints are published through a centralized mechanism (the reference client). This is effectively strong consistency by fiat. Which is legal but doesn’t exactly prove out the Bitcoin contention that it is a fully distributed system. So the issues discussed in this article just deal with what happens between checkpoints. Note however that as cheating goes this isn’t particularly bad. One shouldn’t let theory get in the way of a billion dollar working system.. A problem is that it’s possible for two different groups of miners to both solve the proof of work for the next block at the same time. This creates two alternate versions of the block chain.

Typically the rule is that a miner will accept whatever chains they know about that are the longest [C]  [C] And the hardest. We’ll talk more about this later. But if the miner finds out about multiple equally long but different chains then we are in an indeterminate situation.

The way this situation is resolved is where probabilities come in.

The proof of work problems involve solving problems (typically something with hashing) that are known to take serious computational resources. In general the probability of solving the problem is a function of the computational resources that one has. So in general if one controls say 30% of the computational resources of all members of the block chain ecosystem then one should, on average, “win” solving the proof of work 30% of the time. But this is not necessarily so. It is possible to get lucky and solve the problem faster than others regardless of the percentage of computational power one has. Equally one can get unlucky and take much longer.

Let’s take a situation where there are only two miners and each controls exactly 50% of the computational resources. Each one is trying to mine the next block and they both end up mining a block at the same time. This creates a fork since there is no way to decide which of their forks is authoritative. In theory, since their resources are identical, they could keep on each mining blocks at the same time and the fork could go on forever. But the probability of this is very low. Thanks to luck it is inevitable that one miner will produce a block before the other, successfully communicate this fact to the other miner and thus have the longest chain and thus become authoritative.

Thanks to probabilities, eventually someone gets a new block soon enough and communicates it far enough to become the longest chain and everyone will then switch to mining on their chain.

The probabilistic nature of the proof of work means that eventually someone is going to win and have the longest chain. But how do you define “win”?

Remember, we don’t know who all the miners are and what they have seen. Furthermore due to communication and other issues it’s quite possible for forks that are 3 or more blocks deep to happen. So how does one know when it’s safe to say “My transaction is official”?

According to this paper the rough probability of a fork n blocks long existing is O(2^− n). That is, each block added exponentially reduces the probability of another forked chain of that size existing.

So in a deterministic system like Paxos one knows one’s value is right (for either reading or writing) once a majority of the known quorum of members have agreed.

In a block chain one treats a value as being right (again, for reading or writing) only once it is enough blocks in that the probability of a fork existing that doesn’t include that block is acceptably small.

So we are to ignore the last X blocks at the tail of the chain where X is set to whatever our threshold of comfort is. Any transaction that isn’t X+1 blocks in or higher is ignored.

In the original Bitcoin reference client apparently the number of blocks to wait was set at 6. Looking here one can see that there is only one recorded instance on 7/3/2015 of a 7 block fork. Which would rather put paid to the traditional limit of 6. But I’ve had trouble finding any more data on this orphan. So what should X be? Beats me.

The answer is - probably not (there is that probability thing again).

Block chains are supposed to adjust the difficulty of their proof of work based on a rough measure of how much computational power is in the system. If that adjustment is accurate and if an attacker has a relatively small amount of processing power compared to the rest of the ecosystem then the attacker won’t be able to complete the proof of work at the appropriate level of difficulty faster than the legitimate miners.

This defense however assumes that the user trying to validate their transaction has a reasonable idea of what the level of difficulty is supposed to be. This is bootstrapped in Bitcoin by putting checkpoints (already mentioned) directly into the reference client.

But it’s worth taking a moment to talk about how block chains deal with changes in computational power and how it affects the difficulty level of the proof of work. As a block chain gets more popular it will attract more miners thus increasing the computational power available and thus increasing the probability of blocks being found and long forks happening.

Bitcoin deals with this via an algorithm built into its design which every 2016 blocks calculates the average rate at which blocks are being generated and then automatically calculates a new level of difficulty for the proof of work problem that will keep the rate at which blocks are found to roughly one every 10 minutes. This means that the rate adjustment should happen every 10 minutes * 2016 blocks / 60 minutes/hour / 24 hours/day / 7 days/week = 2 weeks.

As can be seen here the rate at which the difficulty changes isn’t smooth. Some periods have a lot of new mining power, some have smaller increases.

Of course there are attacks. Just to give a single example, if someone was willing to build a huge pool of potential mining power but keep it offline then they would have at least two weeks to really screw with the world. But this would be expensive and self defeating since it would likely crash the whole system. Of course that could be the point (aka a Goldfinger attack).