Prevent double-spending with decentralized digital currencies without all transactions being public?

Question

A recent approach to creating a decentralized online currency, called Bitcoin, has been generating some interest. The goal is to have a way to transfer currency without a central authority and without double spending or counterfeiting. Their approach is to have all the nodes in the network try to verify a transaction by doing a proof-of-work computation and then the transactions with the most verification are considered official. If an attacker wants to forge the official record (to reverse their first spending and use the coin again), then they must have the majority of the computing power in the network. The biggest downside is that in this scheme, the record of all transactions must be public, which the author of the Bitcoin paper assumes is a must:

The only way to confirm the absence of a transaction is to be aware of all transactions. In the mint based model, the mint was aware of all transactions and decided which arrived first. To accomplish this without a trusted party, transactions must be publicly announced.

Is it obvious that all transactions must be publicly known in any such scheme?

It is known that schemes without a public-transcript can be implemented when you have a central authority/mint, but I am only interested if it is possible for a decentralized approach.

Notes

I originally asked this question on cstheory. Also, I am not familiar with the tagging on crypto.SE, so any help is appreciated!

Answer 1

For such a scheme to work, if I have some currency, I have to be able to give it to Abel and I have to be able to give it to Beth, but I have to be unable to give it to both Abel and Beth. This means that giving the currency to Abel has to somehow make me unable to give the currency to Beth even though I previously could do that.

There are three mechanisms by which this can be accomplished:

1. There can be a central authority. To give the coins to Abel, I must tell the central authority that I have done so. The central authority would then prohibit me from giving the coins to Beth. This means giving coins requires both approval from the central authority and reporting to the central authority.

2. There can be a distributed secure device. To give the coins to Abel, I must tell the instance of the secure device that holds the coins. The device will then prohibit me from giving the coins to Beth once it has given them to Abel. This means coins must be held in a physically-secure device. In practice, it also requires a central authority to load the devices and issue keys to them. (I need to prove a secure device was involved in the transaction, which requires the device to have a certificate, which requires some authority to issue such certificates.)

3. At least some aspect of all transactions can be public. Thus, if I give the coins to Abel, there will be a record Beth can easily find. Beth will know the coins are not mine to give.

Bitcoin chooses the third approach. This seems the best approach for cryptographic decentralized currencies. There is no fourth approach known.

Now, the only information about the transaction that needs to be public is enough information to prove I have the coins and prove that I didn't transfer them elsewhere. As it happens, the Bitcoin protocol leaks much more information than this (for example, the account I transferred the coins to). The protocol could have been designed to make less information public if that was desired.

The coins need be traceable back to their origin. But whether or not you can track the particular accounts they passed through is an implementation decision.

For example, a hypothetical coin could use the following mechanism: Alice wants to send some coins to Bob. She knows Bob's public key. She generates a random private key just for this transaction and encrypts it with Bob's public key. She then publishes a transaction transferring coins to the public corresponding to the random private key she generated along with the encrypted version of that same key that she encrypted with Bob's public key.

Now, Bob will see a transaction that his private key is able to claim. Nobody else will know the transaction was to Bob because neither Bob's public key nor any analog of it appear in the block chain. Bob will have no idea the coins came from Alice and nobody else will have any idea the coins went to Bob.

This method still leaves the coins fully traceable. But no traceable accounts ever appear in the block chain.

This solves two 'problems' with Bitcoin. If I publish a bitcoin address somewhere, anyone can see how many Bitcoins that account got. If someone wants to transfer me bitcoins that cannot be traced, he must obtain a one-time use account from me, which he cannot easily do if he wishes to give me the coins anonymously.

You can still generate and use one-time accounts with Bitcoin, but you cannot broadcast them or they cease to be one-time accounts. And there is no easy way for someone to anonymously request one from you.

You might think this means every account must be tested to claim every transaction, resulting in an inefficient scheme and making things like web-based mass wallets computationally impractical. However, I've discovered a truly marvelous solution to this problem, but this answer is already too long.

Answer 2

Zerocash is such a decentralized currency scheme. A Zerocash transaction completely hides the origin, amount, and destination of the transaction.

It achieves this via a cryptographic tool called a zkSNARK, which effectively allows you to prove the validity of a statement in "zero knowledge", i.e. you leak nothing more than the truth of the statement.

In Bitcoin, you prove that you own a coin by using your private key to sign a transaction on that coin. As an analogy, consider the coin to be a locked box that you unlock to prove that you own it. In Zerocash, however, you use a zkSNARK to prove that you can unlock the box. Since this is done in zero knowledge, no information except for the truth of this statement is leaked.

It's more complicated than this, and I'm leaving out many details, but its a decent approximation of what's happening.