Sunday, May 6, 2012

The future of electronic currency

(source/cc)
Crypto is fantastic for many things, but those who read this blog know that I have a particular fascination for its privacy applications. Specifically, what interests me are the ways we can use cryptography to transact (securely) online, without revealing what we're doing, or who we're doing it with.

This is particularly relevant, since today we're in the middle of an unprecedented social and technological experiment: moving our entire economy out of metal and paper and into the 'net. I've already had to explain to my four-year old what newspapers are; I imagine he'll have a similarly experience when his children ask why people once carried funny pieces of paper around in their wallet.

Between credit and debit cards, EFT, online banking and NFC, it seems like the days of cash are numbered. Unfortunately, all is not sunshine and roses. The combination of easy-to-search electronic records and big data seems like a death-knell for our individual privacy. Cryptography holds the promise to get some of that privacy back, if we want it.

In this post I'm going to take a very quick look at a few privacy-preserving 'e-cash' technologies that might help us do just that. (And yes, I'll also talk about Bitcoin.)

Why don't we have electronic cash today?

The simple answer is that we already have electronic money; we just don't call it that. Right now in its mainstream incarnation, it takes the form of little plastic cards that we carry around in our wallets. If you live in a developed nation and aren't too particular about tipping valets, you can pretty much survive without ever touching hard currency.

The problem is that credit and debit cards are not cash. They're very good for money transfers, but they have two specific limitations: first, they require you to access an online payment network. This means that they lose their usefulness at exactly the moment when you need them most: typically, after a disaster has wiped out or severely limited your connectivity (e.g., most hurricanes in Florida, NYC the morning after 9/11, etc).

Secondly, funds transfer systems offer none of the privacy advantages of real cash. This is probably by (government) preference: untraceable cash lends itself to unsavory activities, stuff like drug dealing, arms purchases and tax evasion. Our modern banking system doesn't necessarily stop these activities, but it's a godsend for law enforcement: just about every transaction can be traced down to the $0.01. (And even if you aren't a drug dealer, there are still plenty of folks who'll pay good money for a copy of your spending history, just so they can sell you stuff.)

The genesis of private e-cash

David Chaum, holding
$1 billion in private,
anonymous coins.
Credit for the invention of true, privacy-preserving electronic cash generally goes to David Chaum. Chaum proposed his ideas in a series of papers throughout the 1980s, then made a fortune providing the world with untraceable electronic cash.

Well, actually, the statement above is not quite accurate. According to legend, Chaum turned down lucrative offers from major credit card companies in favor of starting his own e-cash venture. I don't need to tell you how the story ends -- you've probably already noticed that your wallet isn't full of untraceable electronic dollars (and if it is: I'm sorry.)

There's an important lesson here, which is that getting people to adopt electronic cash requires a lot more than just technology. Fortunately, the failure of e-cash has a silver lining, at least for the field of cryptography: Chaum went on to pioneer anonymous electronic voting and a whole mess of other useful stuff.

Like many e-cash systems since, Chaum's earliest paper on the e-cash proposed to use digital 'coins', each of some fixed denomination (say, $1). A coin was simply a unique serial number, generated by the holder and digitally signed using a private key known only to the bank. When a user 'spends' a coin, the merchant can verify the signature and 'deposit' the coin with the bank -- which will reject any coin that's already been spent.

(Of course, this doesn't prevent the merchant from re-spending your hard earned money. To deal with this, the user can replace that serial number with a freshly-generated public key for a signature scheme. The bank will sign the public key, then the user can provide the merchant with the public key -- signed by the bank -- and use the corresponding signing key to sign the merchant's name and transaction info.)

However you do it, the system as described has a crucial missing element: it's not private. The bank knows which serial numbers it signs for you, and also knows where they're being spent. This provides a linkage between you and, say, that anarchist bookstore where you're blowing your cash.

To address this, Chaum replaced the signing process with a novel blind signature protocol. Blind signature is exactly what it sounds like: a way for the bank to sign a message without actually seeing it. Using this technology, the user could make up a serial number and not tell the bank; the blind signature protocol would provide the necessary signature. Even if the bank was trying to track the coins, it wouldn't be able to link them to the user.

Chaum even provided a nice real-world analogy for his idea: place a document inside of an element along with a sheet of carbon paper, then let the bank sign the outside of the envelope, conveying the signature through and onto the document. This doesn't literally describe how blind signatures work, but the real cryptographic constructions aren't that much worse: you can readily obtain blind versions of RSADSA and the Schnorr/Elgamal signatures without (mostly) breaking a sweat (see this footnote for details).

The double-spending problem and going offline

Digital signatures do one thing very well: they prevent unauthorized users from issuing their own coins. Unfortunately they don't prevent a second serious problem: users who copy legitimate coins.

Copying is where electronic cash really differs from its physical equivalent. Real money is hard to copy -- by design. If it wasn't, we wouldn't use it. When people get too clever at copying it, we even send men with guns to shut them down.

Electronic coins are very different. It's almost impossible to work with data without copying it; from long-term storage to RAM, from RAM to the processor cache, from one computer to another over a network. Electronic coins must be copied, and this fundamentally changes the nature of the problem. The boogeyman here is 'double spending', where a user tries to spend the same valid coin with many different merchants. Left unchecked, double-sending does more than screw over a merchant. It can totally debase the currency supply, making coins almost impossible for merchants to trust.

Chaum's original solution dealt with double-spenders by requiring the bank to be online, so users could immediately deposit their coins -- and make sure they were fresh. This works great, but it's damn hard to handle in a system that works offline, i.e., without a live network connection. Indeed, offline spending is the big problem that most e-cash solutions have tried to tackle.

There are two basic solutions to the offline problem. Neither is perfect. They are:
  • Use trusted hardware. Force users to store their coins inside of some piece of bank-trusted (and tamper-resistant) piece of hardware such as a cryptographic smartcard. The hardware can enforce correct behavior, and prevent users from learning the actual coin values.
  • Revoke double-spenders' anonymity. Alternatively, it's possible to build e-cash systems that retain the users' anonymity when they participate honestly, but immediately revokes their anonymity when they cheat (i.e., double-spend the same coin).
Although these solutions are elegant, they also kind of suck. This is because neither is really sufficient to deal with the magnitude of the double-spending problem.

To understand what I'm talking about, consider the following scam: I withdraw $10,000 from the bank, then spend each of my coins with 1,000 different offline merchants. At the end of the day, I've potentially walked away with $10,000,000 in merchandise (assuming it's portable) before anyone realizes what I've done. That's a lot of dough for a single scam.

In fact, it's enough dough that it would justify some serious investment in hardware reverse-engineering, which makes it hard to find cost-effective hardware that's sufficient to handle the threat. Finding the owner of the coin isn't much of a deterrent either -- most likely you'll just find some guy in Illinois who had his wallet stolen.

That doesn't mean these approaches are useless: in fact, they're very useful in certain circumstances, particularly if used in combination with an online bank. Moreover the problem of revealing a user's identity (on double-spend) is an interesting one. There are several schemes that do this, including one by Chaum, Fiat and Naor, and a later (very elegant) scheme by Stefan Brands. (For a bit more about these schemes, see this footnote.)

Compact wallets and beyond

There have been quite a few developments over the past few years, but none are as dramatic as the original schemes. Still, they're pretty cool.

One scheme that deserves a few words is the 'Compact e-Cash' system of Camenisch, Hohenberger and Lysyanskaya. This system is nice because users can store millions of e-coins in a relatively small format, but also because it uses lots of neat crypto -- including signatures with efficient protocols and zero-knowledge proofs.

At a very high level, when a user withdraws n coins from the bank in this system, the bank provides the user with a digital signature on the following values: the user's public key, the number of coins n withdrawn, and a secret seed value seed that's generated cooperatively by the bank and the user.

The bank learns the number of coins and user's public key, but only the user learns seed. To spend the ith coin in the wallet, the user generates a 'serial number' SN = F(seed, i), where F is some pseudo-random function. The user also provides a non-interactive zero-knowledge proof that (a) 0 < i < n, (b) SN is correctly formed, and (c) she has a signature on seed from the bank (among other things). This zero-knowledge proof is a beautiful thing, because it does not leak any information beyond these statements, and can't even be linked back to the user's key in the event that she loses it. The online bank records each serial number it sees, ensuring that no coin will ever be spent twice.

This may seem pretty complicated, but the basic lesson is that we can do lots of neat things with these technologies. We can even build coins that can be spent k times for some arbitrary k, only revealing your identity if they're used more times than that; this turns out to be useful anonymous login applications, where users want to access a resource a fixed number of times, but don't want anyone counting their accesses.

Unfortunately, we haven't managed to build any of this stuff and deploy it in a practical setting.

Bitcoin

Which brings us to the one widely-deployed, practical electronic cash system in the world today. What about Bitcoin?

I'm a big fan of Bitcoin (from a technical perspective), but it has a few limitations that make Bitcoins a little bit less private than real e-cash should be.

Despite the name, Bitcoin doesn't really deal with 'coins': it's actually a transaction network. Users generate blocks of a certain value then transfer quantities of currency using ECDSA public keys as identifiers. The core innovation in Bitcoin is a distributed public bulletin-board (the 'block-chain') that records every transaction in Bitcoin's history. This history lets you check that any given chunk of currency has a valid pedigree.

While the Bitcoin block-chain is essential to security, it's also Bitcoin's privacy achilles heel. Since every transaction is public -- and widely disseminated -- there's no hiding that it took place. To make up for this, Bitcoin offers pseudonymity: your public key isn't tied to your identity in any way, and indeed, you can make as many of them as you want. You can even transfer your coins from one key to another.

Now, I'm not really complaining about this. But it should be noted that pseudonymity is to anonymity what sugar-free chocolates are to the real thing. While I don't know of anyone who's actively looking to de-anonymize Bitcoin transactions (scratch that, Zooko points out that some people are), there has been plenty of work on extracting (or 're-identifying') pseudonymized data sets. If you don't believe me, see this work by Narayanan and Shamtikov on de-anonymizing social network data, or this one that does the same thing for the Netflix prize dataset. And those are just two of many examples.

Many knowledgable Bitcoin users know this, and some have even developed Bitcoin 'mixers' that stir up large pools of Bitcoin from different users, in the hopes that this will obfuscate the transaction history. This sounds promising, but has a lot of problems -- starting with the fact that none few seem to be actually online as I write this post.* Even if one was available, you'd basically be placing your privacy trust into the hands of one party who could totally screw you. (A large, distributed system like Tor could do the job, but none seems to be on the horizon). Finally, you'd need a lot of transaction volume to stay safe.

At the same time, it seems difficult to shoehorn the e-cash techniques from the previous sections into Bitcoin, because those systems rely on a centralized bank, and also assume that coins are used only once. Bitcoin has no center, and coins are used over and over again forever as they move from user to user. Any anonymous coin solution would have to break this linkage, which seems fundamentally at odds with the Bitcoin design. (Of course that doesn't mean it isn't possible! ;)**

In summary

This has hardly been an exhaustive summary of how e-cash works, but hopefully it gives you a flavor of the problem, along with a few pointers for further reading.

I should say that I don't live the most interesting life, and about the only embarrassing thing you'll see on my credit cards is the amount of money we waste on Diet Coke (which is totally sick). Still, this isn't about me. As our society moves away from dirty, messy cash and into clean -- and traceable -- electronic transactions, I really do worry that we're losing something important. Something fundamental.

This isn't about avoiding marketers, or making it easier for people to have affairs. Privacy is something humans value instinctively even when we don't have that much to hide. It's the reason we have curtains on our windows. We may let go of our privacy today when we don't realize what we're losing, but at some point we will realize the costs of this convenience. The only question is when that will be, and what we'll do about it when the day comes.

Notes:

* I was wrong about this: a commenter points out that Bitcoin Fog is up and running as a Tor hidden service. I've never tried this, so I don't know how well it works. My conclusion still stands: mixing works well if you trust the BF operators and there's enough transaction volume to truly mix your spending. We shouldn't have to trust anyone.

** Some people have tried though: for example, OpenCoin tries to add Chaum-style cash to Bitcoin. Ditto Open Transactions. From what I can tell, these protocols still do Chaumian cash 'old style': that is, they require a trusted 'bank', or 'issuer' and don't actually integrate into the distributed trust framework of Bitcoin. Still very nice work. h/t commenters and Stephen Gornick (who also fixed a few typos).

23 comments:

  1. Research in de-anonymizing Bitcoin transactions:

    http://anonymity-in-bitcoin.blogspot.com/2011/07/bitcoin-is-not-anonymous.html

    It's slightly more exciting of a read than most academic papers, because the data they used to demonstrate their techniques was the actual transactions of actual internet crooks. I kept wondering if they were going to perfect their techniques, link the transactions to the real-world identities of a bunch of net crook mafia, and then disappear.

    ReplyDelete
    Replies
    1. Thanks Zooko. That's a great link.

      Delete
    2. They made the claim in that linked article that Bitcoin was not anonymous (and okay, I get that it isn't 100% anonymous-perfect), but they were still unable to give a single name or identity after all their work. They made pretty charts, but no identities were revealed. That article almost made the case that Bitcoin should, to some extent, be considered relatively anonymous. Anonymity with Bitcoin may be asymptotic - you can't achieve total anonymity, but you can get darn far up that curve, and perhaps we shouldn't let the perfect be the enemy of the great.

      Delete
    3. This comment has been removed by the author.

      Delete
    4. @Erik Voorhees:

      "That article almost made the case that Bitcoin should, to some extent, be considered relatively anonymous."

      For the record, I disagree with that intrepretation of our work.

      If you advocate this interpretation in future, I would be grateful if you would reference the discussion we had at the time, in the comments on the original blog post.

      We published our findings. I don't know who it would help if we went around publishing the identities we observed, and the relations between them. (Mainly twitter accounts, forum accounts, organisations; covering some portion of the users; some of which were easy to resolve to a real individual).

      I think the only reasonable conclusion is that people with requirements for anonymity should not trust that Bitcoin is automatically providing it for them.

      Proper anonymity is hard. If you want to have a chance of it, it really has to be explicitly designed in to a protocol.

      Delete
  2. That's an interesting and enjoyable overview to read, Matthew. The article doesn't really emphasize the distributed and decentralised nature of the bitcoin network which is precisely what creates the trade-off between full anonymity and diet-anonymity. The centralised issuing/reissuing mints do offer enhanced privacy, but it's their centralised nature that puts them at risk. Careful bitcoin users can practically get to that same level of privacy.

    The reason e-cash schemes of the future will require decentralisation is for ultimate resiliency. Like taking people's guns just before the State implemented martial law in Poland -- you don't know when you'll need it, but when you do need it you really need it.

    ReplyDelete
  3. A thought provoking read. Thanks Matthew.

    ReplyDelete
  4. Good article, a few points to add. There has been back and forth on how to give bitcoin strong anonymity on the forums for a long time. As you note, it is a tough problem but the reward will be worth it, imo.

    https://bitcointalk.org/index.php?topic=241.0

    There are a few alpha projects that put a Chaumian cash layer on top of bitcoin, like Open Transactions, OpenCoin, BlindBitcoin (shutdown).

    Interestingly it is not just user privacy that is affected with loss of anonymity, since 'tainted' coins that are identified to be involved in socially unacceptable activities can lose fungibility as users prefer 'clean' coins. In this way, the functioning of the money system can also then be affected by the low anonymity of the users, this is somewhat similar to serial numbers on 'dirty' paper cash but they can be removed from circulation or otherwise 'cleaned' unlike bitcoin transaction records that exists forever.

    One final note, there is already a bitcoin mixing system running as a hidden Tor service Bitcoin Fog
    http://www.bitcoinfog.com/
    cannot testify to it's veracity or effectiveness.

    ReplyDelete
    Replies
    1. Thanks for these notes! I've updated the article to point these out.

      Delete
  5. "This sounds promising, but has a lot of problems -- starting with the fact that none seem to be actually online as I write this post." ??? I used many times this - http://www.bitcoinfog.com/ and it works great.

    ReplyDelete
  6. And there's a failure here to address physical transference of an entire wallet, for instance on a USB drive. Once this transfer takes place, you break any chain you may have had on the network. This would anonymize you the same way cash does.

    ReplyDelete
    Replies
    1. Great point. Since you can write private keys on paper, and transfer the paper, you can achieve roughly the same effect that cash has. Transaction history broken. It also provides plausible deniability, because there is little or no way to prove that a transaction chain was NOT broken by this manual meatspace overide.

      Delete
  7. Yes, this, this is a very key point, and you can even create a marketplace that lets you buy wallet files loaded with bitcoins ... for bitcoins. ;) BICKETY-BAM anonymized. Or at least now holding someone elses TX history and lolling while enjoying a snack of roflcakes.

    ReplyDelete
  8. Great read! Thank you

    ReplyDelete
  9. ""The problem is that credit and debit cards are not cash. They're very good for money transfers, but they have two specific limitations: first, they require you to access an online payment network.""

    I want to point, that credit cards worked without any on-line from very beginning (VISA started at 1958, and MAsterCard is here from 1966, before Internet) and I've paid with real paper slip (without any connectivity) by Visa Classic card two ears ago in UK.

    ReplyDelete
  10. 97% of monetary value only exist in digits.Rest 3% is backed by currency and coins. Plastic card is only solution to this real world problem.

    ReplyDelete
  11. Great Article, lots of information which can help many people. The electronic cash-system is designed to contribute to the successive replacement of cash in the retail sector, can be used by issuers and acquirers in the entire euro payment area.

    ReplyDelete
  12. There already is a design outline for a decentralized anonymous coin using zero-knowledge proofs:

    https://bitslog.wordpress.com/2012/07/27/appecoin-anonymous-peer-to-peer-electronic-coin-design/

    ReplyDelete
  13. I like your article. It is very informative. Thank you so much for sharing such priceless information. Hats-off to the writer. Keep on posting such nice articles. Love to read you. Thank you so much.
    http://www.financetics.com/2013/03/want-your-own-digital-currency.html

    ReplyDelete
  14. One of the best master's dissertation blogs I have ever come across on the internet. Very well written, precise and to the point. Thanks for sharing. undergraduate dissertation

    ReplyDelete
  15. Privacy is something humans value instinctively even when we don't have that much to hide. It's the reason we have curtains on our windows. postallads4free.com We may let go of our privacy today when we don't realize what we're losing, but at some point we will realize the costs of this convenience.

    ReplyDelete