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
19cFYVExc2ZS4p7ZARGyENFijnV43y6ts1
.

11 comments:

Jacques Distler said...

"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)."

Obviously, that doesn't scale.

"There are some finer points like ... how new coins can be created (again with a lot CPU work)"

Another thing which is completely wrong-headed, and is only explicable when you read the Rand Paul-ish nonsense, spouted by its proponents, vis-a-vis monetary policy and "conventional" currencies.

Robert said...

Jacques,

of course you are right that the idea that basically everybody must have a record of each transaction does not scale at all. Still, in the paper linked, they claim that the amount of storage needed can still handled.

I have to admit I had to google "Rand Paul" not being to familiar with US political figures.

It is also totally true that if it worked, the bitcoin system opens a possibility for all sorts of money laundering, tax evasion and threatens the applicability of monetary policy. In addition, it is not clear if at this point the current value shows signs of a fast growing bubble that makes it in effect a Ponzi scheme paying out to early adopters.

Still, I was interested in it so so much as a real currency with substancial volume to be any sort of threat to the real economy but more because I believe that the internet is still lacking a reliable, small friction system to transfer small amounts of money. Something that everybody can use both as sender and recipient. The currently existing ways do not fulfill this requirement: Sending cheques has far too much overhead and is too slow, online bank transfer works reasonably well only in the Euro region and is too much of a hassle for small amount, Paypal has too high transaction costs and there is always the threat that you cannot get your money out and credit cards do not work both ways (plus transaction costs). Here in Germany, flattr is becoming popular but has its own restrictions being designed for a different purpose.

Jacques Distler said...

"[T]he internet is still lacking a reliable, small friction system to transfer small amounts of money. ... Paypal has too high transaction costs ..."

For that, you don't need to invent a whole new electronic currency; what you need is a cheaper version of Paypal.

So ... why doesn't Paypal have more, cheaper, competition?

One reason is that it's expensive to deal with fraudulent/disputed transactions. And if you haven't established a good reputation for dealing with such, nobody is going to want to use your service.

Bitcoin ignores the hard part of online monetary transactions, while triumphantly solving the easy part (enabling party A to transfer funds to party B).

Unknown said...
This comment has been removed by a blog administrator.
Robert said...

I tend to disagree here: In my understanding one central idea of bitcoin is to use cryptography to eliminate fraudulent/disputed transactions. And that was what my post was about, how this is supposed to work.

Paypal does not have a lot of cheaper competition as with a centralized system where all funds are routed through a central entity you want the central entity to be so rich/strong that it can buffer all this traffic and has no incentive to at some point in time just take the money and run. So setting up a global, centralized money transfer system is not something a small start-up can handle IMHO not even a single although big bank.

And this is the second point (besides taking algorithmic measures to stop fraud) where bitcoin differs: They can do without the central entity that would need to be of a size of the order of the whole market. Thus it has a chance to grow without being established full size at day one.

I don't care if you call it a 'currentcy' (that's probably a misnomer). What I think it is interesting for is that it establishes a commodity that can be transferred electronically and which hopefully is stable enough that people are willing to assign a real value to it (i.e. that people are willing to give me real money or even better real goods in exchange).

[I had initially posted this reply while my wife was still logged in to google, so it appeared under her name]

Jacques Distler said...

"In my understanding one central idea of bitcoin is to use cryptography to eliminate fraudulent/disputed transactions."

It does absolutely nothing of the kind. To the contrary, it says you are completely on your own, in dealing with such matters. If you pay a merchant in bitcoin, and he fails to deliver the desired merchandise? Tough luck, you're on your own. If you laptop is stolen, or if a computer virus steals the bitcoins stored on your computer? Tough luck, you're on your own.

The only thing that all that cryptography achieves is the part that is absolutely trivial on a centralized system: securely transferring an amount X from the account of party A to the account of party B.

"Paypal does not have a lot of cheaper competition as with a centralized system where all funds are routed through a central entity you want the central entity to be so rich/strong that it can buffer all this traffic..."

Any such system could (and surely would) start small, and grow larger as it gains acceptance. In any case, as I said, the expensive part of the operation is not provisioning the network of servers.

And, as should be obvious, there are plenty of existing financial institutions (banks, credit card companies, ...) with the required infrastructure already in place. The only reason they don't get int the business of undercutting Paypal is that there's no money in it. (In fact, I suspect that the only reason Paypal is still in business is that its owner, eBay, finds it a necessary and useful adjunct to its main line of business.)

" and has no incentive to at some point in time just take the money and run."

That's your worry?? That the service would abscond with all the users' money? Since that would result in civil and/or criminal proceedings, I think that scenario is pretty low down on the list of things to worry about.

"They can do without the central entity that would need to be of a size of the order of the whole market."

Nonsense. Bitcoin cannot possibly scale up even to the size of Paypal, let alone the banks and credit-card clearing houses, which handle several orders of magnitude more transactions than Paypal.

The decentralized nature of bitcoin is an ideological choice, not the result of any technical superiority.

"I don't care if you call it a 'currentcy' (that's probably a misnomer). What I think it is interesting for is that it establishes a commodity ..."

No. "Currency" is the right name. "Commodities" are things that have some intrinsic value in and of themselves. "Currencies" are valuable only to the extent that they can be exchanged for goods and services (that are of intrinsic value).

wolfgang said...

Just a practical point about bitcoins: Transactions are really slow (it can take hours) if one does not pay a fee.
In order to get transactions done within minutes one needs to set fees to 0.01 BTC or higher.
At the current exchange rate this is equivalent to 16 US cents.
Not really a good starting point for a micropayment system imho.

Also, one warning: We do not know how tax authorities treat the conversion from bitcoins to e.g. US$ (with traditional currencies conversion from one currency to the other is not a taxable income event) and some people who trade on bitcoin exchanges could have some explaining to do.

And one last point: BTC mining is not profitable unless somebody else pays for the electricity and hardware bill(s). Thus I predict that bitcoins will mostly be minted by those who control botnets - the first currency mostly coined by crooks and thieves.

The major use for bitcoins right now seems to be 1) speculative trading and 2) purchase of illegal drugs and since nobody enforces any transaction agreements (as Jacques explained) there will soon be a flood of bitcoins scams etc.

So I predict that somebody will have to invent a better mousetrap 8-)

Thomas Larsson said...

A good explanation why Bitcoin will not work can be found here.

Thomas Larsson said...

Somebody apparently stole a whole bunch of bitcoins at mtgox over the weekend. Or something like it. The bitcoin crashed from 30$ to 1 cent, which can be watched live at youtube.

mtgox claim that they will rollback all trades. But can they? I thought bitcoins were supposed to be untraceable.

Robert said...

That was Jacques point that you cannot roll back bitcoin transactions. I am still not convinced that that is a feature since once you received bitcoins you are sure you have them and the other party cannot claim them back (which is a major problem of paypal, it happens far too often that paypal freezes accounts).

On the other hand, this incident shows that all the macroeconomic discussions were orders of magnitude off target since a currency that can be brought down by selling worth a few thousand dollars cannot be a threat do anything (except those people's purses that own too much of it).

Even if the price at the other exchanges is not affected too much, it shows that currently bitcoin is still far too volatil to be really useful for anything except gambling. Which is too bad since I am convinced (as stated above) that the internet still lacks a good micropayment system.

The situation reminds me a bit of some sort of spam popular during the dotcom bubble: You would receive emails stating that some penny-stock is about to make a great announcement that will skyrocket its value (the idea being that the sender of the spam bought shares of that company before sending the spam). A number of people would than buy that share and since the market is so small the price would indeed go up (even without announcement). So the sender could make a profit by selling the shares that he bought before anybody else.

The curious thing is that upon receiving the email it is not 100% clear that one should not buy the share although the information in the mail is clearly wrong since one could still hope to be early enough to buy the share at a good price before more people react to the spam and bring up the price even further.

Rohitpal said...

Really-Really This is nice blog till i have been visited. Innocent photos are wonderful. I think this is the blog which i was search before. it so informative and i enjoyed very much from it . so thanks you very much to created such a nice blog & written article.