Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. 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 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!

share|improve this question
    
Welcome to Cryptography Stack Exchange. The only other fitting tag here would be [protocol-design], so I added this. I also edited your question title to be in the form of a question, I hope you don't mind. –  Paŭlo Ebermann Aug 25 '11 at 12:04
    
@Paŭlo thank you! –  Artem Kaznatcheev Aug 25 '11 at 12:09
    
Once the Bitcoin Stackexchange site is in public beta, should this question be migrated there? bitcoin.stackexchange.com –  ripper234 Aug 31 '11 at 0:22
2  
@ripper234 no, it shouldn't. This is already the second place I asked the question (it was asked at cstheory originally) and it was decided in a meta discussion there that I should repost. Usually questions are only migrated if they are off-topic on the original site; this question seems to be ontopic here, and already generated a very good answer. –  Artem Kaznatcheev Aug 31 '11 at 0:30
    
Agreed, digital currency theory should remain inside crypto.SE. –  Jeff Burdges Dec 3 '11 at 21:14

1 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.

share|improve this answer
    
can you give an explanation of an implementation that does not keep track of the accounts the coins passed through? Since that would answer my question very nicely. –  Artem Kaznatcheev Aug 25 '11 at 17:07
    
Sure. To transfer coins to Beth, you perform the following operations: 1) Generate a random secret key. 2) Encrypt the secret key with Beth's public key. 3) Publish the transfer of the coins to the public key corresponding to the secret key you generated and the encrypted private key. 4) To claim the coins, Beth decrypts the secret key using her secret key and can then spend the coins. 5) Beth's public key or account information is never disclosed. Effectively, you generate a one-time account just to receive these coins and tell Beth how to claim them in a way only Beth can understand. –  David Schwartz Aug 25 '11 at 17:16
1  
@David: as I understand Bitcoin, anybody can have as many accounts as one wants, and it is even recommended to use a new account number (= key pair) for each transaction one is receiving. Isn't this equivalent to your proposed scheme (other that Beth now needs to keep track of more private keys)? (Also, your usage of private and secret seems a bit mixed up.) –  Paŭlo Ebermann Aug 26 '11 at 11:09
1  
No, it's not equivalent. Say I want to run an advertisement in a magazine and give people an address they can use to send me bitcoins. How can I do that and hide how many bitcoins the advertisement yielded? And Beth needn't keep track of any additional private keys -- the encrypted private key is published in the block chain. She can decrypt it with her single private key whenever she needs it. –  David Schwartz Aug 26 '11 at 11:34
1  
"However, I've discovered a truly marvelous solution to this problem, but this answer is already too long.", I'm sure you did Mr. Fermat ;) –  capn Apr 19 '12 at 17:58

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.