Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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 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? More broadly: is there any cstheory/crypto research on decentralized digital currencies or related ideas?

Notes

I cross-posted to crypto.SE after a meta discussion.

share|improve this question
1  
The 2nd chapter of the thesis "Formal and computational cryptography : protocols, hashes and commitments" (dare.ubn.kun.nl/dspace/handle/2066/40158) can be of interest. –  Oleksandr Bondarenko Jun 28 '11 at 15:24
    
This post is being discussed on this reddit thread. –  Neal Young Nov 7 '13 at 0:55

1 Answer 1

There has been a lot of work done in this area. A good survey is the first chapter of "Handbook of Financial Cryptography and Security" (for the crypto) and the seventh chapter (for a survey of technologies).

The first scheme to prevent double spending and not require a public global transcript is, to my knowledge, by Chaum, Fiat and Naor [Crypto 88]. In their model, users obtain digital cash that is unlinkable to their identity but if they double spend the coin, then with high probability it will reveal their identity when the coins are eventually returned to the bank. CFN is very inefficient and there has been much work on improving it.

share|improve this answer
1  
thanks for the reference! I looked through chapter 1, and it seems like all the systems surveyed require a central issuing authority (they also assume that this authority can be trusted). One of the fun features of bitcoins is that the system has no mint or bank (or alternatively the network of all the users is the mint). Do you know any results that don't rely on a trusted mint? Or does this not generate much interest in the e-cash community? –  Artem Kaznatcheev Jul 7 '11 at 1:23
1  
Oh I see, you are looking for a decentralized mint/bank without a public transcript? I am not aware of such a scheme (nor a compelling reason why it would be impossible). There are schemes with one of the two properties obviously (bitcoin and its predecessors, and CFN and it successors respectively). It seems difficult to achieve both but its an interesting problem that seems open. –  PulpSpy Jul 11 '11 at 13:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.