Paying With Bits

In the course of a friendly discussion with Dirk-Jan, I’ve been reading up on the miracles of digital cash.

And by digital cash, I do not mean lame stuff like Paypal, which is basically just an ordinary bank account to which you can send transfer orders. No, what I’m interested in is the real heavy stuff, whereby you have a digital wallet full of cryptographic “coins” which can be transfered from one party to another, without a single central entity keeping track of the contents of your wallet. Ideally, you want to be able to transfer such coins even off-line, without the central entity needing to be involved with every individual transfer.

There are a couple of basic problems with the idea of using bits as money, which any “crypto cash” system will need to find solutions for.

Probably the biggest one is non-technical: the fact that governments really hate it when you propose something like an untraceable, anonymous and decentralized currency which is not under their control. Ask Douglas Jackson, founder of E-Gold, who in this Wired article is painted as a naive but basically well-intentioned and idealistic guy who tried to create a currency for the twenty-first century but who ran afoul of a whole lot of government objections. But let’s ignore the political angle for now, and look into the technical obstacles.

The first technical problem is obvious: if my coins are just strings of bits, what is preventing me from spending a single coin multiple times, or minting my own coins?

And then there is an issue which is somewhere mid-way between technical and legal/practical: where does the money get its value from? Here in the real world, it used to be that money was backed by gold or silver: in theory, you could take your bank note to the bank and they would exchange it for a little sliver of precious metal. Nowadays, pretty much all money is fiat currency: it has value because the government says it has value, which works as long as we all believe that it does. The latter is a bit less intellectually satisfying than the former, but it does raise the interesting question of whether you could create a working fiat currency from scratch, without being backed by any government or central trusted organization.

When it comes to sophisticated cryptographic techniques for digital money, the work of David Chaum is the acknowledged gold standard (sorry). His digital money is a brilliant combination of pretty much all of the most advanced techniques in cryptography: blind signatures, commitment schemes, zero-knowledge proofs and lots more. Particularly brilliant is his solution to the “double spending problem” mentioned above. In his approach, people cryptographically sign digital money orders with their name when they receive them from the bank, but they sign them in such a way that the information can only be retrieved when a money order is spent twice. The spending (which can be done off-line) will succeed, but when the bank receives the same “coin” back through two different channels, it will not only know that cheating has occurred, but it can retrieve the name of the cheater! However, as long as you spend each coin only once, your anonymity is safe from the bank as well as from the people you exchange money with, even if they all work together!

Chaum’s work requires some seriously advanced crypto, though. In the book Future Imperfect from my favourite author David Friedman, there is an alternative scheme which is a lot less sophisticated, but just as elegant in its impressive simplicity. Here is the entire system:

  1. The bank gives out coins, which are simply large randomly-generated numbers.
  2. When you receive a coin, you immediately send an (anonymous, encrypted) message to the bank, requesting that the coin’s number be changed to a different random value generated by you. You include a transaction code which is another random number.
  3. If the bank can indeed find the original number in its database, it exchanges it for your new number, and publishes the transaction code in a public place so that you can verify that the coin you were given did indeed exist, and has been assigned the new number which only you know.
  4. When you walk into the bank and present them with the new number, they will exchange it for, say, an amount of gold matching the value of the coin.

That’s all!

It’s not quite as secure as Chaum’s system in all directions. The system can be used off-line, but only if the payee trusts the payer to give him a real coin. The bank cannot breach your anonymity, but it can cheat by refusing to honour a valid coin. Even in the case of an on-line transaction, if the payee claims that the payer did not give him a valid coin, there is no way for an outsider to determine which of the two is telling the truth. But within these limitations, the basic functionality works and it’s a rather impressive achievement for a system which is so trivially simple that you could explain it to your ten-year-old nephew.

If you’re looking for a nice little intellectual challenge, think about Friedman’s proposal a little further. Identify the various practical problems with it, and see if you can come up with a solution for each of them, using basic crypto techniques such as symmetric and asymmetric encryption, digital signatures and secure hash codes.

Now, in the above approaches, the assumption is that there is still a central bank, trusted by all parties, which gives out the money and which gives that money its value by pledging to exchange it for some real-world valuable material such as gold, or perhaps simply by linking it to an ordinary bank account containing ordinary government-backed euros or dollars.

Bitcoin goes even further: it proposes (there exists a technical implementation, but they’re not really pretending that it’s ready for real-world use) a form of digital money which is completely decentralized: there is no central entity, anybody can create money and then spend it. As the FAQ explains it:

What is Bitcoin’s value backed by? Bitcoin is valued for the things it can be exchanged to, just like all the traditional paper currencies are. When the first user publicly announces that he will make a pizza for anyone who gives him enough Bitcoins, then he can use Bitcoins as payment to some extent - as much as people want pizza and trust his announcement. A pizza-eating hairdresser who trusts him as a friend might then announce that she starts accepting Bitcoins as payment for fancy haircuts, and the value of the Bitcoin would be higher - now it would be backed by pizzas ”and” haircuts. When Bitcoins have become accepted widely enough, he could retire from his pizza business and still be able to use his Bitcoin-savings.

That seems to make sense — money is basically a system of transferable IOUs whereby the participants agree to cover each other’s debts. However, if anybody can create Bitcoins and spend them anonymously, how can they ever be made to make good on their debts? And even without anonymity, what prevents me from creating more Bitcoins than I will ever be able to honour and then living like a king until the day of my death? Somewhere, it seems, there has to be a mechanism to create some artificial scarcity in order for the scheme to work.

Bitcoins proposes to solve this problem by making each coin represent a proof of work: creating a Bitcoin requires a large amount of CPU power; anybody who receives a coin from you can verify that you have performed a very complex and time-consuming calculation. Coins are linked together and there is a peer-to-peer system to verify that coins are not being double-spent. As with Friedman’s approach, you can accept coins off-line if you want but then you will need to trust the payer to not deliberately cheat on you.

This way, the amount of Bitcoins in the economy is limited and grows predictably, which are two very important requirements for a usable currency. Using CPU power to back the money’s value is of course completely arbitrary, but in principle that is not an impediment for a working currency. As with a conventional fiat currency, once the pool of people willing to accept the money is large enough, it is resistant to occasional cheaters; anybody who refuses to play along is hurting themselves more than they are hurting the people who partake in the system. Obviously, getting to that point is the difficult part.

By the way, if you think that the above schemes are not secure enough to work in practice, what would you think of the following system?

  • Your bank account is represented by a single sixteen-digit number, which remains the same for several years.
  • Anybody who knows this number can use it to withdraw money from your bank account.
  • Making a payment consists of giving the number to the person you want to pay. So if you want to purchase something at a gas station, for example, you show a card with the number to the gas station attendant, after which he knows your number and you will have to trust him not to abuse it.

That must be the most horrible system anybody could possibly come up with, right? If you proposed this in an introductory computer security class for high-schoolers, your classmates would laugh you out of the room. Nobody with an ounce of common sense would every use such a horribly botched system for anything, let alone for making payments over the Internet, right?

And yet what I am describing here is, of course, the humble credit card.

I do not expect any of the cryptographic systems described above to become popular any time soon. But the most likely reason for their failure will be a combination of chicken-and-egg effect (nobody wants to use a currency which nobody else uses) and the first, non-technical problem mentioned at the start of this article. Nonetheless, it is awfully cool to consider what is possible in principle, and a good mental exercise to consider the various practical objections and try to come up with solutions to them.