Now let’s turn to cash. We compared cash and credit earlier, and noted that a cash system needs to be “bootstrapped,” but the benefit is that it avoids the possibility of a buyer defaulting on her debt. Cash offers two additional advantages. The first is better anonymity. Since your credit card is issued in your name, the bank can track all your spending. But when you pay in cash, the bank doesn’t come into the picture, and the other party doesn’t need to know who you are. Second, cash can enable offline transactions where there’s no need to phone home to a third party in order to get the transaction approved. Maybe later, they go to a third party like a bank to deposit the cash, but that’s much less of a hassle.
Bitcoin doesn’t quite offer these two properties, but comes close enough to be useful. Bitcoin is not anonymous to the same level as cash is. You don’t need to use your real identity to pay in Bitcoin, but it’s possible that your transactions can be tied together based on the public ledger of transactions with clever algorithms, and then further linked to your identity if you’re not careful. We’ll get into the messy but fascinating details behind Bitcoin anonymity.
Bitcoin doesn’t work in a fully offline way either. The good news is it doesn’t require a central server, instead relying on a peer-to-peer network which is resilient in the way that the Internet itself is. In Chapter 3 we’ll look at tricks like “green addresses” and micropayments which allow us to do offline payments in certain situations or under certain assumptions.
The earliest ideas of applying cryptography to cash came from David Chaum in 1983. Let’s understand this through a physical analogy. Let’s say I start giving out pieces of paper that say: “The bearer of this note may redeem it for one dollar by presenting it to me” with my signature attached. If people trust that I’ll keep my promise and consider my signature unforgeable, they can pass around these pieces of paper just like banknotes. In fact, banknotes themselves got their start as promissory notes issued by commercial banks. It’s only in fairly recent history that governments stepped in to centralize the money supply and legally require banks to redeem notes.
I can do the same thing electronically with digital signatures, but that runs into the annoying “double spending” problem — if you receive a piece of data representing a unit of virtual cash, you can make two (or more) copies of it and pass it on to different people. To stick with our analogy, let’s stretch it a little bit and assume that people can make perfect copies and we have no way to tell copies from the original. Can we solve double spending in this world?
Here’s a possible solution: I put unique serial numbers into each note I give out. When you receive such a note from someone, you check my signature, but you also call me on the phone to ask if a note with that serial number has already been spent. Hopefully I’ll say no, in which case you accept the note. I’ll record the serial number as spent in my ledger, and if you try to spend that note, it won’t work because the recipient will call me and I’ll tell them the note has already been spent. What you’ll need to do instead is to periodically bring me all the notes you’ve received, and I’ll issue you the same number of new notes with fresh serial numbers.
This works. It’s cumbersome in real life, but straightforward digitally provided I’ve set up a server to do the signing and record-keeping of serial numbers. The only problem is that this isn’t really cash any more, because it’s not anonymous — when I issue a note to you I can record the serial number along with your identity, and I can do the same when someone else later redeems it. That means I can keep track of all the places where you’re spending your money.
This is where Chaum’s innovation comes in. He figured out to both keep the system anonymous and prevent double-spending by inventing the digital equivalent of the following procedure: when I issue a new note to you, you pick the serial number. You write it down on the piece of paper, but cover it so that I can’t see it. Then I’ll sign it, still unable to see the serial number. This is called a “blind signature” in cryptography. It’ll be in your interest to pick a long, random serial number to ensure that it will
most likely be unique. I don’t have to worry that you’ll pick a serial number that’s already been picked
— you can only shoot yourself in the foot by doing so and end up with a note that can’t be spent.
This was the first serious digital cash proposal. It works, but it still requires a server run by a central authority, such as a bank, and for everyone to trust that entity. Moreover, every transaction needs the participation of this server to go through. If the server goes down temporarily, payments grind to
a halt. A few years later, in 1988, Chaum in collaboration with two other cryptographers Fiat and Naor proposed offline electronic cash. At first sight this might seem to be impossible: if you try to spend the same digital note or coin at two different shops, how can they possibly stop this unless they’re both connected to the same payment network or central entity?
The clever idea is to stop worrying about preventing double-spending and focus on detecting it, after the fact, when the merchant re-connects to the bank server. After all, this is why you’re able to use your credit card on an airplane even if there is no network connection up in the skies. The transaction processing happens later when the airline is able to re-connect to the network. If your card is denied, you’ll owe the airline (or your bank) money. If you think about it, quite a bit of traditional finance is based on the idea of detecting an error or loss, followed by attempting to recover the money or punish the perpetrator. If you write someone a personal check, they have no guarantee that the money is actually in your account, but they can come after you if the check bounces. Conceivably, if an offline electronic cash system were widely adopted, the legal system would come to recognize double spending as a crime.
Chaum, Fiat, and Naor’s idea for detecting double spending was an intricate cryptographic dance. At a high level, what it achieved was this: every digital coin issued to you encodes your identity, but in such a way that no one except you, not even the bank, can decode it. Every time you spend your coin, the recipient will require you to decode a random subset of the encoding, and they’ll keep a record of this. This decoding isn’t enough to allow them to determine your identity. But if you ever double spend a coin, eventually both recipients will go to the bank to redeem their notes, and when they do this, the bank can put the two pieces of information together to decode your identity completely, with an overwhelmingly high probability.
You might wonder if someone can frame you as a double spender in this system. Say you spend a coin with me, and then I turned around and tried to double-spend it (without redeeming it with the bank and getting a new coin with my identity encoded). This won’t work — the new recipient will ask me to decode a random subset, and this will almost certainly not be the same as the subset you decoded for me, so I won’t be able to comply with their decoding request.
Over the years, many cryptographers have looked at this construction and improved it in various ways. In the Chaum-Fiat-Naor scheme, if a coin is worth $100, and you wanted to buy something that cost only $75, say, there’s no way to split that coin into $75 and a $25. All you could do is go back to the bank, cash in the $100 coin, and ask for a $75 coin and a $25 coin. But a paper by Okamoto and Ohta uses “Merkle trees” to create a system that does allow you to subdivide your coins. Merkle trees would show up in Bitcoin as well, and we’ll meet them in Chapter 1. The Chaum-Fiat-Naor scheme also leaves a lot of room for improvements in efficiency. In particular, the application of something called zero-knowledge proofs to this scheme (most notably by Brands; and Camenisch, Hohenberger, and Lysyanskaya) was very fruitful—zero-knowledge proofs have also been applied to Bitcoin.
But back to Chaum: he took his ideas and commercialized them. He formed a company in 1989 called DigiCash, probably the earliest company that tried to solve the problem of online payments. They had about a five-year head start on other companies like FirstVirtual and CyberCash that we just discussed. The actual cash in Digicash’s system was called Ecash and they had another system called cyberbucks. There were banks that actually implemented it — a few in the US and at least one in Finland. This was in the 1990s, long before Bitcoin, which might come as surprise to some Bitcoin enthusiasts who view banks as tech-phobic, anti-innovative behemoths.
Ecash is based on Chaum’s protocols. Clients are anonymous, so banks can’t trace how they’re spending their money. But merchants in ecash aren’t anonymous. They have to return coins as soon as they receive them, so the bank knows how much they’re making, at what times, and so on.
Figure 2 shows a screenshot from the software. As you can see, it shows you your balance as well as all the coins that you have that have been issued to you from the bank. Since there’s no way to split your coins, the bank issues you a whole set of coins in denominations of a cent, two cents, four cents,
and so on — powers of two. That way, you (or your software, on your behalf) can always select a set of coins to pay for the exact amount of a transaction.
When you want to make a transaction, say, as in this example, you want to make a donation to the non-profit privacy group EPIC, you’d click on a donation link that takes you to the Digicash website. That would then open a reverse web connection back to your computer. That means your computer had to have the ability to accept incoming connections and act as a server. You’d have to have your own IP address and your ISP would have to allow incoming connections. If the connection was successful, then the ecash software would launch on your computer and you’d be able to approve the transaction and send the money.
Chaum had several patents on Digicash technology, in particular, the blind-signature scheme that it used. This was controversial, and it stopped other people from developing ecash systems that used the same protocol. But a bunch of cryptographers who hung out on what was called the cypherpunks mailing list wanted an alternative. Cyperpunks was the predecessor to the mailing list where Satoshi Nakamoto would later announce Bitcoin to the world, and this is no coincidence. We’ll talk about the cypherpunk movement and the roots of Bitcoin.
The cypherpunk cryptographers implemented a version of of ecash called MagicMoney. It did violate the patents, but was billed as being only for experimental use. It was a fun piece of software to play with. The interface was all text-based. You could send transactions by email. You would just copy and paste the transactions into your email and send it to another user. Hopefully, you’d use end-to-end email encryption software such as PGP to protect the transaction in transit.
Then there’s a proposal called Lucre by Ben Laurie with contributions from many other people. Lucre tries to replace the blind-signature scheme in ecash with a non-patent-encumbered alternative, with the rest of the system largely the same.
Yet another proposal, by Ian Goldberg, tries to fix the problem of not being able to split your coins to make change. His idea was that the merchant could send you coins back if they had some coins, so that you might overpay for the item if you didn’t have exact change, and then you’d get some coins back. But notice that this introduces an anonymity problem. As we saw earlier, in ecash, senders are anonymous but merchants aren’t. When the merchant sends cash back, technically, they’re the sender, so they’re anonymous. But you, as someone who has to return this cash to the bank, aren’t anonymous. There’s no way to design this system without breaking the anonymity of users trying to buy goods. So Goldberg came up with a proposal where there were different types of coins that would allow these transactions to occur, allow you to get change back, and still preserve your anonymity.
Now, why did DigiCash fail? The main problem with DigiCash was that it was hard to persuade the banks and the merchants to adopt it. Since there weren’t many merchants that accepted ecash, users didn’t want it either. Worse, it didn’t support user-to-user transactions, or at least not very well. It was really centered on the user-to-merchant transaction. So if merchants weren’t on board, there was no other way to bootstrap interest in the system. So at the end of the day, DigiCash lost and the credit card companies won.
As a side note, Bitcoin allows user-to-merchant and user-to-user transactions. In fact, the protocol doesn’t have a notion of merchant that’s separate from the notion of user. The support for
user-to-user transactions probably contributed to Bitcoin’s success. There was something to do with your bitcoins right from the beginning: send it to other users, while the community tried to drum up support for Bitcoin and get merchants to accept it.
In the later years of the company, DigiCash also experimented with tamper-resistant hardware to try to prevent double-spending rather than just detecting it. In this system, you’d get a small hardware device that was usually called a wallet, or some sort of card. The device would keep track of your balance, which would decrease when you spent money and increase if you loaded the card with more money. The point of the device is that there should be no way to physically or digitally go in and tamper with its counter. So if the counter hits zero, then the card stops being able to spend money until it’s re-loaded.
There were many other companies that had electronic cash systems based on tamper-resistant hardware. DigiCash later worked with a company called CAFE which was based in Europe. Another company formed around this idea was called Mondex and it was later acquired by Mastercard. Visa also had their own variant called VisaCash.
Figure 3 shows the user side of the Mondex system. There’s a smart card and there’s a wallet unit, and you can load either of them with cash. And if you wanted to do user-to-user swap of money, the giver user would first put their card into the wallet and move money off of the card onto the wallet. Then the receiver would stick their card in the wallet then you’d move the money onto the second card. This was a way to exchange digital cash, and it was anonymous.
Mondex trialled their technology in a bunch of communities. One community happened to be a city very close to where I grew up: Guelph, Ontario. You’ve probably already guessed that it didn’t really catch on. A major problem with Mondex cards is that they’re like cash — if you lose them or they get stolen, the money’s gone. Worse, if there’s some sort of malfunction with the card, if the card reader wouldn’t read it, there’s no way to figure out if that card had balance on it or not. In these scenarios, Mondex would typically eat the cost. They’d assume that the card was loaded and reimburse the user for that lost money. Of course, that can cost a company a lot of money.
Further, the wallet was slow and clunky. It was much faster to pay with a credit card or with cash. And retailers hated having several payment terminals; they wanted just one for credit cards. All these factors together did Mondex in.
However, these cards were smart cards, which means that they have small microcontrollers on them, and that technology has proved successful. In many countries today, including Canada, where I live, every single credit card and every single debit card now has smart card technology in it. It’s used for a different purpose, though. It’s not used to prevent double-spending — the problem doesn’t arise since it’s not a cash-based technology. The bank, rather than your card, keeps track of your balance or available credit. Instead the chip is used for authentication, that is, to prove that you know the PIN that’s associated with your account. But Mondex was using it long before this technology was adopted widely by the banking industry.
