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