Now we can get to the stuff about bitcoin that’s actually interesting. How does it work?

Before I start, one major caveat. I’m deliberately talking about this in vague terms – enough so that you an understand how and why it works, but not enough so that you could do something like implement it. Like anything else involving cryptography: if you’re thinking about implementing your own crpytosystem, don’t!

Cryptography is an area where even seasoned experts can easily make mistakes. A serious crpytosystem is built by a team of professionals, including people whose entire job is do everything in their power to break it. And even then, it’s all to easy to wind up with un-noticed bugs! When it comes to something like bitcoin, an inexperienced cryptographer trying to implement a new agent for the bitcoin network is insane: you’re dealing with money, and you’re risking losing a whole lot of it if you screw up. (That’s basically what appears to have happened to mtgox – and if the reports I’m reading are correct, they managed to lose hundreds of millions of dollars worth of bitcoins.

On to the fun part!

Basically, bitcoin is a protocol. That means that it’s really just a system that defines how to communicate information between a collection of computers. Everything about bitcoin is defined by that protocol.

At the heart of the protocol is the ledger. The ledger is a list of transactions that says, essentially A gave N bitcoins to B. The only way to get a bitcoin is by a transaction: there needs to be a transaction saying that someone or something gave you a bitcoin. Once you have one, you can transfer it to someone else, by adding a new transaction to the ledger.

That’s the basic idea of it. The beauty of bitcoin is that at the core, it’s incredibly simple – it’s just a list of transactions. What makes it interesting is the crpytographic magic that makes it work. In theory, the ledger could be simple text. Each line would contain a sender, a receiver, and a quantity. If you have that, it’s enough to manage transactions. But there are a bunch of problems with a simple ledger approach, which mostly involve making sure that transactions in the ledger are valid and that they can’t be changed.

In addition, there are problems that come about because of the fact that bitcoin wants to be completely decentralized. There is no authority in charge of bitcoin. That means that you need to have a consensus based system. Anyone can join the network of bitcoin managers at any time, and anyone in the network can drop out at any time – but the network as a whole must always have a consensus about what the current ledger is. There’s also the question of where the coins come from!

We’ll start with the question of authentication.

Suppose I own a bitcoin, and I want to use it to buy a loaf of bread from friendly baker, Barbera. I need to give Barbera my bitcoin. To do that, I need to add an entry to the ledger saying “MarkCC gave one bitcoin to Barbera”. The problem is, the ledger entry needs to contain something to prove that I’m really the owner of the bitcoin that I’m trying to transfer! If it doesn’t do that, then my arch-nemesis, Tony the thief, could just add a ledger entry saying “MarkCC gave one bitcoin to Tony”. Only I should be able to add a ledger entry transferring my bitcoin.

This one is simple: it’s a textbook use-case for public key crpytography. In a public key system, you have key-pairs. One member of the key pair is called the public key, and the other is the private key. Anything encrypted with the public key can only be decrypted using the private key; anything encrypted with the private key can only be decrypted with the public key. So you get a key pair, lock the private key away somewhere safe, and give away copies of the public key to anyone who wants it. Then if someone sees a message that can be decoded with your public key, it means that you must have been the one who sent it. No one else could encrypt a message using your private key!

In the bitcoin ledger, the lines are signed. Instead of directly saying “MarkCC gave one bitcoin to Barbera”, they say “One bitcoin was transferred from the owner of MarkCCs cryptokey to the owner of Barbera’s cryptokey”. The ledger entry for that transaction is signed using a signature generated from the ledger entry using MarkCC’s private key. Anyone can verify the validity of the transaction by checking the signature using MarkCC’s public key. Once that’s in the ledger, Barbera now own a bitcoin, and only Barbera (or whoever has access to Barbera’s private key) can do transfer that bitcoin to anyone else.

Now, on to the complicated part! There is no authoratative ledger in bitcoin. There are many copies – thousands of copies! – of the ledger, and they’re all equal. So how can you be sure that a transaction is real? Someone could write a transaction to a ledger, show you the ledger, and then you could find out that in every ledger except the one you looked at, the transaction doesn’t exist! If you there is no single place that you can check to be sure that a transaction is in the ledger, how can you be sure that a transaction is real?

The answer is a combination of a consensus protocol, and a bit of computational cleverness. When you want to add a ledger entry, you broadcast a message to the bitcoin network. Every 10 minutes or so, participants in the bitcoin network take whatever transactions were added to the current ledger, put them into a structure called a block, and perform a very difficult, semi-random computational task using the block. When they find a solution, they sign the block using the solution, and broadcast it to the network.

The first agent in the bitcoin network that completes a solution and broadcasts it to the network “wins” – their block becomes the new basis for the next block.

The blocks form a chain: block one contains some transactions; block 2 contains more transactions that happened after block1 was broadcast; block 3 contains transactions that happened after block 2 was broadcast, and so on.

At any time, the consensus ledger – that is the master, canonical ledger – is the one with the longest verifiable chain. So someone can broadcast a new solution to an old block, but it will be ignored, because there is already a longer chain in the consensus. You can be certain that your transaction can’t be revoked or lost once you see a new block issued that builds on the block containing your transaction.

This all relies on people finding solutions to computationally expensive problems. Why would anyone do it? That’s why this process of computing hashes for the blocks is called mining: because if you’re the first one who finds a solution for a block, then you get to add a transaction giving yourself 25 brand new bitcoins to yourself! Mining – the process of maintaining the ledger – becomes a sort of lottery, where the people doing the mining randomly get bonuses to motivate them to do it.

The computational side of it is clever in its simplicity. The bitcoiners want the problem to be hard enough to make it effectively impossible to cheat. But they also want to be sure that it’s easy enough that they get blocks frequently. If it takes an hour before anyone has a solution for a new block, that’s also a problem: if it takes that long to commit a transaction to the ledger, then people aren’t going to trust bitcoin for fast transactions. They can’t be sure that a bitcoin was transferred to them unless they know that the transaction was committed in an accepted block. But there’s a trick there: people want to get the mining rewards. That means that they’re constantly trying to push the limits of what they can get away with computationally. People started with bunches of PCs, and then discovered that the GPUs on their graphic cards could do it faster, and then started building custom PCs with tons of graphics cards to do bitcoin mining computations in parallel. And of course, there’s always Moore’s law: computers are constantly getting faster. That means that they can’t just pick a particular complexity for the problem and stick with it.

The solution is to make the problem variable. They start with a well known algorithm that’s a very good one-way problem (meaning that it’s relatively easy to compute a result given an input; but very, very hard to figure out the inverse – to get an input that produces a desired result. In slightly more mathematical terms, if , then computing is easy if you know , but it’s very hard to compute if you know .

There are a bunch of well known one-way computations. They just picked one, called SHA-256 computation. Now the clever part: they make SHA-256 computation into a variable complexity problem by picking a threshold , agreed on by consensus in the bitcoin ledger protocol. The solution for a block is a hashcode for the block plus a bit of extra data which is smaller than : for a ledger block , they need to find a value called a Nonce where .

Because SHA-256 is a one-way function, there’s no good way to predict what value of will give them a hashvalue that’s smaller than the threshold – the only way to do it is to just keep guessing new -values, and hoping that one of them will produce an acceptable result. By reducing the value of , you can make the problem harder; by increasing the value of , you can make it easier. The bitcoin protocol specifies a regular interval and an algorithm for selecting a new .

When a miner solves the problem, they publish the new ledger block to the bitcoin network, with the new ledger section and its values. Once a new block is issued, all of the future ledger entries can only get added to the next unsolved block in the ledger.

The reason that this is safe is a matter of computation. You can go back in time, and find an old transaction, remove an entry from it, and recalculate the block. But it takes time, and other people are still moving on, computing new blocks. For your change to be accepted by the bitcoin network, you would need to issue new version of the altered block, plus new versions of any other blocks issued since the one you altered, and you’d have to do it before anyone else could issue a new block. The consensus is the longest block-chain, so issuing blocks that aren’t longer than the longest chain in the network is a waste of time. Because the computation is hard, even being one block behind is enough to make it effectively impossible to be able to change the ledger: to become the new largest chain when you’re just one block behind means you’d need to compute solutions for three blocks before anyone could find a solution for just one more block!

That last bit isn’t so clear when you read it, so let’s work through an example.

1. Block B is issued
2. Block C is issued
3. You want to change block B.
4. The current longest blockchain is […, B, C].
5. To replace B with a new block B’, you need to issue a
   longer blockchain that the current consensus of […, B, C].
6. That means that you need to issue B’, C’, and a new block D’ before anyone else can just issue D.
7. By falling just one block behind, you need to issue 3 three new blocks before anyone else can issue just one.

And that, my friends, is effectively impossible.