A Beginner’s Guide to Bitcoin (Part 7): Being Consistent

Previous Article   –   Next Article   –   Table of Contents

The Problem

The next big problem with our distributed ledger is more subtle, and much harder to solve.  Indeed as we shall see it’s a problem that leads to the crazy genius at the heart of Bitcoin.

However, it’s in no way a new problem.  I worked on a system in 1997 that had exactly the same issue.

Network Latency

If we have a network of computers where data is being copied between all of them then inevitably it takes some time for the data to be copied.  This time may be very short.  With a peer-to-peer network of computers running on the internet the delay for them to all synchronize after a change is just a few seconds if the changed data is one megabyte  (1MB) in size. This is true even if there are a lot of computers scattered all over the world.  This delay isn’t much, but it does exist.  We’ll see why one megabyte is relevant later.

The time delay in copying data around a network of computers is called ‘network latency’.

Inconsistent Data

The problem that network latency gives rise to is that at any given time not all computers will have the same data.  Some computers in the network may have data that other computers may not have because it hasn’t yet been copied to them.  This makes it hard to know if new data received by one computer conflicts with data on other computers, and hence whether we should process it or not.

Double Spend

Network latency leads to one very specific problem in the Bitcoin network.

If I own a coin there’s nothing to stop me submitting a signed payment instruction to a computer in one location, and at the same time submitting a signed payment instruction for the same coin but to a different payee to a computer in a different location.  I might do this by mistake, or I might be trying to get two sets of goods in different locations for my one coin.

In either case Bitcoin needs to be able to deal with this in a sensible way.  It needs to resolve the conflict and prevent both payments being accepted by the network, even temporarily.

The original Bitcoin paper calls this the ‘double spend’ problem, because I’m trying to spend my coin twice.  However, it’s really a general problem of computing where updates to the same data can happen in more than one place in the presence of network latency: how do we reconcile those updates and get consensus on what the correct state of the data is?

Possible Solutions and Why They Don’t Work

The solution to the double spend problem may seem obvious to you for spending coins.  We just take the first payment and discard the second, right?  One of them has to be submitted before the other, even if only by milliseconds.

This would work if we could reliably determine that two conflicting payments had been attempted and then reliably decide which the first one was.  In general though this isn’t possible in a peer-to-peer network.  Remember that one computer has one payment and is trying to process it, and a second computer a long way away has another conflicting payment and is trying to process that.  Initially neither of them knows that there’s a conflicting payment in the system.  How can they check that, since neither payment has been processed?

Note that this problem only occurs if conflicting payments are sent to different computers in the network.  If two conflicting payments are sent to the same computer then that computer can easily see it has a conflict and discard one of the payments.  Bitcoin’s validation rules will ensure this happens.

Some solutions to the double spend problem could be:

  • Ensuring all updates to the ledger happen on one computer (a ‘write server’) and copying the results from there.
  • Only allowing certain updates to happen on certain computers.  In the case of Bitcoin maybe we could have a given coin always updated on a computer in one known location.
  • Having central timestamp servers.  When a computer receives a payment it reads the timestamp and adds it to the payment.  Now we know which one was received first.
  • Locking every known computer whilst any update takes place.

These approaches are all valid, but in the case of our distributed ledger none of them will work well.  In Bitcoin we don’t want central known and trusted computers, we want a network of anonymous peer computers any of which can handle any payment.  We want this both for ideological reasons and because we want a resilient peer-to-peer network.  Ideally we want to be able to turn any computer off and the network will carry on working, which is what happens in most peer-to-peer networks.  That isn’t going to happen if specific computers have specific tasks, or we’re trying to lock them all for an update.

Bitcoin’s Crazy Solution

So how does Bitcoin handle this?  We are now entering the crazy genius part of this discussion.

Multiple Versions of the Book

The answer is that Bitcoin allows both the conflicting ‘double spend’ payments to be processed on the two different computers.  It allows the resulting state from both computers to then be copied to all the other computers.

That is, there can be one version of the ledger with the first payment from the first computer, and simultaneously a second version of the ledger with the second conflicting payment from the second computer.  Any individual computer in the network may well have been sent both of these versions of the ledger, which conflict with each other.

Of course to do this means we need an efficient way of storing versions of the ledger where most of the historic data is the same but after a certain point the versions contain different payments.

Now we see one of the reasons why the blockchain is useful as it facilitates this.  In our example one payment processor has produced a block of processed payments.  A second payment processor has produced another block that conflicts with it.  Both of these blocks follow on from a valid block in the chain.  So all we need to store both versions of the ledger is the two blocks and the blocks in the chain up to that point.  Because we have no balance or other information this can be done reasonably efficiently.

Which Book Is The Right Book?

We have allowed multiple versions of the ledger to exist.  We need a rule to decide which version is the current valid ledger.  We do this simply by saying that the current valid version of the ledger is the one that has the most payment processing.  We can determine which this is by just counting the number of blocks of payments that are included in the ledger.  This number is called the ‘block height’.

Note that even with this rule it’s perfectly possible to have two different ledgers with the same block height in existence at any given time, and hence not be able to determine which the final valid ledger is.

How This Works in Practice

In our example above where there are just two double spend payments that have led to two conflicting versions of the ledger then initially both versions will have had the same amount of payment processing.  They are the same until one final block of payments is added.  The final blocks conflict.

Each payment-processing computer can now decide to add new payments to either version of the ledger (it may only see one), or both.  Remember that the payment processors get paid if they add payments to the ledger, but they only get paid if they contribute to the eventual valid version of the ledger.  So they are incentivized to pick the correct version if they can identify it.

So it’s likely that both versions of the ledger will have more blocks of payments added to them.  However, there’s an element of randomness about this so eventually one version of the ledger is likely to have had more blocks added than the other.  As soon as this happens the payment processors are all likely to switch to that version, as it’s probably the final valid version and they only get paid if they work on that.  So we aren’t likely to have conflicting versions for too long.  A valid version will emerge.  We call the version that gets discarded an ‘orphan’.  Orphans are bad for the payment processors as they’ve worked on something but not been paid for that work.

You may be beginning to see why it’s necessary to slow the payment processing down a little.  More on this below.

Did Our Solution Make Things Worse?

We’ve decided to allow any payment processor (miner) to generate a block of payments at any time.  Some alternatives were to restrict who could produce a given block or when they could produce one.  This is what we need for a decentralized system, but it actually gives rise to some new problems.

Remember that at this point we are discussing the rather artificial case of how Bitcoin would behave without mining.  We have to introduce mining to fix the problems below.

General Chaos

With Bitcoin as I’ve currently described it it will be very quick for a payment processor to create a new block of payments and add it to what they think is the valid ledger.  It will then be relatively slow for that new block of payments to be copied to all the other payment processors because of network latency.  It will also be relatively slow for new payments to be copied between the computers in the first place.

This means that all the payment processors are likely to be continually producing new versions of the ledger very quickly, with different valid sets of payments, and firing them at the other payment processors.  These versions of the ledger will be different from other payment processors’ versions, even if based on the same starting ledger and even if there are no conflicts.

In short, because we allow multiple versions of the ledger to exist and those versions are easy to create, Bitcoin as described here would get a little chaotic with lots of versions of the ledger continually being created and discarded.

This leads to some more specific problems.

We Can’t Tell If A Payment Is Processed

In my original example I submitted two conflicting payments.  For a period of time both of these payments could appear in different versions of the ledger on different computers, or even on the same computer.  At this stage we can’t tell if either payment has correctly been processed.  We have to wait a bit to see which version of the ledger gets worked on the most, and once we have a clear winner that should become the definitive version of our ledger.  However, even if one processing computer thinks that’s the valid ledger it’s still possible there’s another version of the ledger on another computer that has had more processing and that hasn’t been copied yet.  There’s an element of uncertainty.

Again, you may be seeing why slowing down the speed of payment processing relative to the network latency may help with this.

It May Be Possible To Manipulate The Ledger

There’s a second related but more fundamental problem with the design without mining as it stands.

An evil payment processor can attempt to manipulate the ledger.

For example they could deliberately create and publish a version of the ledger that excludes a previously accepted payment made by them and replaces it with a payment of the same coins to someone else.  They could make this ledger version much larger than the current version.  It’s possible this could subsequently be accepted as the valid ledger.  They can do this since it’s very quick for them to create versions of the ledger.  This is a version of the 51% attack that Bitcoin is subject to that we will look at in more detail later.

Previous Article   –   Next Article   –   Table of Contents

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s