Friday, June 03, 2011

Bitcoin explained

As me, you might have recently heared about "Bitcoin", the internet currency that tries to be safe without a central authority like a bank or a credit card company that say which transactions are legitimate. So far, all mentions in blogs, podcasts or the press that I have seen had in common that they did not say how it works, what are the mechanisms that make sure Bitcoins operate like money. So I looked it up and this is what I found:

Bitcoin uses to cryptographic primitives: hashes and public key encryption. I case you don't know what these are: A hash is a function that reads in a string (or file or number, those are technically all the same) and produces some sort of checksum. The important properties are that everybody can do this computation (with some small amount of effort) and produce the same checksum. On the other hand, it is "random" in the sense that you cannot work backwards, i.e. if you only know the checksum you effectively have no idea about the original string. It is computationally hard to find a string for a given checksum (more or less the best you can do is guess random strings, compute their checksums until you succeed). A related hard problem is to find such a string with prescribed first $N$ characters.

This can be used as a proof of effort: You can pose the problem to find a string (possibly with prescribed first characters) such that the first $M$ digits of the checksum have a prescribed value. In binary notation you could for example you could ask for $M$ zeros. Then on the average you have to make $2^M$ guesses for the string until you succeed. Presenting such a string then proves you have invested an effort of $O(2^M)$. The nice thing is that this effort is additive: You can start your string with the characters "The message '....' has checksum 000000xxxxxxxxxxx" and continue it such that the checksum of the total string starts with many zeros. That proves that in addition to the zeros your new string has, somebody has already spent some work on the string I wrote as dots. Common hash functions are SHA-1 (and older and not as reliable: MD5).

The second cryptographic primitive is public key encryption. Here you have two keys $A$, the public key which you tell everybody about and $B$ your secret key (you tell nobody about). These have the properties that you can use one of the keys to "encrypt" a string and then the other key can be used to recover the original string. In particular, you need to know the private key to produce a message that can be decrypted with the public key. This is called a "signature": You have a message $M$ and encrypt it using $B$. Let us call the result $B(M)$. Then you can show $A$ and $M$ and $B(M)$ to somebody to prove that you are in possession of $B$ without revealing $B$ since that person can verify that $B(M)$ can be decrypted using $A$. Here, an example is the RSA algorithm.

Now to Bitcoin. Let's go through the list of features that you want your money to have. The first is that you want to be able to prove that your coins belong to you. This is done by making coins files that contain the public key $A$ of their owner. Then, as explained in the previous paragraph you can prove that you are the legitimate owner of the private key belonging to that coin and thus you are its owner. Note that you can have as many public-private key pairs as you like possibly one for every coin. It is just there to equate knowing of a secret (key) to owning the coin.

Second you want to be able to transfer ownership of the coin. Let us assume that the recipient has the public key $A'$. Then you transfer the coin (which already contains your public key $A$) by appending the string "This coin is transfered to the owner of the secrete key to the public key $A'$". Then you sign the whole thing with your private key $B$. The recipient can now prove that the coin was transferred to him as the coin contains both your public key (from before) and your statement of the transfer (which only you, knowing $B$ can have authorized. This can be checked by everybody by checking the signature). So the recipient can prove you owned the coin and agreed to transfer it to him.

The last property is that once you transfered the coin to somebody else you cannot give it to a third person as you do not own it anymore. Or put differently: If you try to transfer a coin a second time that should not work and the recipient should not accept it or at least it should be illegitimate.

But what happens if two people claim they own the same coin, how can we resolve this conflict? This is done via a public time-line that is kept collaboratively between all participants. Once you receive a coin you want to be able to prove later that you already owned it at a specific time (in particular at the time when somebody else claims he received it).

This is done as follows: You compute the hash function of the transfer (or the coin after transfer, see a,bove including the signature of the previous owner of the coin that he has given it to you) and add it to the time line. This means you take the hash value of the time line so far, at the hash of the transfer and compute new hash. This whole package you then send to your network peers and ask them to also include your transfer in their version of the time line.

So the time line is a record of all the transfers that have happened in the past and each participant in the network keeps his own copy of it.

There could still be a conflict when two incompatible time lines are around. Which is the correct one that should be trusted? One could have a majority vote amongst the participants but (as everybody knows from internet discussions) nothing is easier than to come up with a large number of sock puppets that swing any poll. Here comes the proof of work that I mentioned above in relation to hash functions: There is a field in the time line that can be filled with anything in the attempt to construct something that has a hash with as many zeros as possible. Remember, producing $N$ leading zeros amounts to $O(2^N)$ work. Having a time line with many zeros demonstrates that were willing to put a lot of effort into this time line. But as explained above, this proof of effort is additive and all the participants in the network continuously try to add zeros to their time line hashes. But if they share and combine their time lines often enough such that they stay coherent they are (due to additivity) all working on fining zeros on the same time line. So rather than everybody working for themselves everybody works together as long as their time lines stay coherent. And going back through a time line it is easy to see how much zero finding work has been but in. Thus in the case of conflicting time lines one simply takes that that contains more zero finding work. If you wanted to establish an alternative time line (possibly one where at some point in time you did not transfer a coin but rather kept it to yourself so you could give it to somebody else later) to establish it you would have to outperform all other computers in the network that are all busy working on computing zeros for the other, correct, time line.

Of course, if you want to receive a bitcoin you should make sure that in the generally accepted time line that same coin has not already been given to somebody else. This is why the transfers take some time: You want to wait for a bit that the information that the coin has been transferred to you has been significantly spread on the network and included in the collective time line that it cannot be reversed anymore.

There are some finer points like how subdividing coins (currently worth about 13 dollars) is done and how new coins can be created (again with a lot CPU work) but I think they are not as essential in case you want to understand the technical basis of bitcoin before you but real money in.

BTW, if you liked this exposition (or some other here) feel free to transfer me some bitcoins (or fractions of it). My receiving address is