There is a problem with bitcoin because transactions are, to a certain extent, traceable. Also, it seems to be desirable to be able to pass messages between sender and recipient. This post outlines a simple method of implementing untraceable transactions to which either party can attach messages. This type of transaction will be propagated across the network and incorporated into blocks just like a normal transaction because to all observers (except the sender and intended recipient) it is indistinguishable from a normal transaction. It's not immediately obvious that Bitcoin could easily be altered to prevent this new type of transaction if the consensus was that it was undesirable.

Prerequisite: The recipient's address needs to have a publicly visible public key or alternatively the sender needs to have independent knowledge of the public key. In normal circumstances, this means that the recipient needs to have spent some of the coins sent to that address whereupon their public key is in the block chain.

Step 1: The sender performs his side of a Diffie–Hellman key exchange by multiplying the recipient's public key by his private key.

Step 2: The sender uses the hash of the resulting point as the secret key to generate another address termed the "transfer" address.

Step 3: The sender sends the bitcoins to the transfer address (plus multiples of 0.01BTC if message transmission in step 4 is desired).

Step 4: If a message transmission to the recipient is desired, the sender prepares one or more message bearing "k" values instead of random numbers. The messages m is encrypted (xor will do) with the hash of the concatenation of the secret key for the transfer address with a sequence number starting with zero. The resulting k values are used by the sender for the transfer of 0.01BTC from the transfer address to some  other addresses until the message is complete.

Step 5: The recipient monitors the network or block chain for public key revelations ie the first spend from a new address. When a new public key is detected the recipient multiplies the public key point by their secret keys for their public receiving addresses.

Step 6: The recipient uses the hashes of the resulting points as the secret keys to generate candidate transfer addresses and monitors the block chain for transactions to these addresses.

Step 7: The recipient notices that the transaction crediting the "transfer" address matches the one of the addresses calculated in step 6

Step 8: If there are any transactions from the transfer address, the recipient hashes the secret key with a trial sequence number and decrypts the "random" k parameter to recover the message.

Step 9: As both the recipient and the sender know the secret key to the transfer address, the recipient takes ownership of the coins if they wish to by transferring them (possibly in combination with other coins) to one or more new addresses. The recipient can attach a number of messages readable by the sender to these transactions using the methods of step 4.

The recipient and sender can use the transfer address indefinitely and symmetrically to transfer bitcoins and secure messages back and forth forever as they wish. The sequence numbers are incremented to ensure that k values remain distinct and remain indistinguishable to third parties from random numbers even if identical secret messages are transmitted.

Advantages: The transactions are not traceable as they transfer control of bitcoins without crediting the recipient's published receiving address. They look like normal transactions. Transfer addresses facilitate message passing in the k values of transfer signatures.

Disadvantage: Disputes between sender and recipient cannot be resolved by third parties using the block chain evidence. This is the price of this type of untraceability.

ByteCoin
 

Yeah but as far as I can tell, it doesn't help.

If recipients are generating a new address per transaction as is best practice, you cannot link people together using just the block chain. You could potentially do so if you gain access to peoples wallets, but that's true even with this proposed system as you'd want to move the coins to an address you control quickly, anyway.

So if the threat model is "attacker can see the block chain", it doesn't add much. If the threat model is "attacker can access our hard disks", you still lose.

An interesting piece of crypto for sure though. It might find other uses in future.

RE: agreed upon spot to place or distribute messages:

I think it is time to start experimenting with a <bytes> OP_DROP OP_DUP OP_HASH160 ...etc transaction type on the testnet.

And time to finish implementing headers-only-for-initial-download mode so new users don't have to wait so long to get their free Faucet bitcoins.

Yes.
As I have indicated in previous posts and indeed in the first post of this thread, encoding substantial messages in transactions is already possible. Gavin's mooted proposed tolerance of OP_DROP transactions simplifies the implementation considerably and reduces messaging overheads. It also allows the popularity of messaging to be measured.

Additionally, Gavin's opinion is that the CPU time taken to verify signatures is a bottleneck for transaction processing. My messaging scheme would result in more signature verifications whereas OP_DROP would not.

One major cause of a balooning block chain would be the use of "mixnets".

My proposed solution to a giant block chain is forgetting most of it.

ByteCoin

OP_DROP just makes you pay for network bandwidth and disk storage rather than CPU costs. I think BitCoin nodes will be CPU constrained in future so it's not as risky as Satoshi thought it might be.

That said, I'm not really sure it's necessary either. Short messages are useful for what? You already need a new address per transaction to identify which user paid you, and if you want a conversation with the merchant good old email is just as reasonable. You can state which address you were given by the merchants website and sign with that key to link the email thread and transaction together.

And yes there are lots of cool optimizations to be made in reducing storage/overhead costs ....

Is there any difference between the original post and simply sending the private key for an account? i.e. the blockchain does not know this account changed hands?

I was thinking about this a while ago, but it seemed to me that the sender could say buy a space pizza by sending his key to the pizzeria, and as long as the pizzeria doesnt spend the coins, the pizza customer could decide to keep his coins (since he still knows the private key).

I was thinking about a kind of mutual oblivious transfer preventing this? is this possible?