It can be be done entirely outside the blockchain, and entirely without needing everyone to download everyone's messages
and it can be done without revealing everyone's message to everyone else.
From my 'features I'd like in my alternative client document':
https://github.com/andyparkins/additup/blob/master/doc/release.mdwn### Receipts
This is slightly outside the realm of responsibility for a client, but
it would need support in the client to work.
Nobody is going to keep copious notes when they buy things with
bitcoins. With a bank, at the end of the month I get a statement that
tells me where I spent my money. With Bitcoin all I would get is a list
of addresses. My solution to this is to have a secondary distributed
system (or centralised, it doesn't matter), where vendors can publish
the details of a particular sale. Even if it was just their name.
People will obviously not want that information published, so it needs
to be encrypted if it is going to be publicised. The solution is to use
the public key of the sender of coins to encrypt the details of the
receipt, then store it in a distributed database against the transaction
hash. The client then makes a web lookup for all expenditure on a
particular address, and receives (of course) a load of encrypted
messages. Being the owner of the matching private key means that they
are (uniquely) able to decrypt those messages, which the client would
automatically do and copy the message into its local database.
I think this can be done with ECDH using the exact same keys as are used
for signing. I also can't see how it breaks security as the private key
is never used, and if it were possible to break a private key simply by
generating known messages to it, then it wouldn't be very secure anyway.
As a bonus, the message could be signed by the receiver of the coins so
that the client has a way of verifying that it came from the merchant.
This stops people from spamming transactions. If the signature signed
the encrypted message, the receipt server could verify too, and discard
messages from anyone else.
It's just another service; outside of bitcoin. But to be really useful it needs integrating into the clients; so probably should be standardised.