Hi Justus:

CC'ing mailing list because more bloom filter and HD wallet experts there can chime in for some of these thoughts.  I refined some ideas we went over earlier.

Here are some critiques/worries about the payment codes.

With identities explicitly tied to a payment code, bloom filter clients can have identities tied to them.  

1. There will be a 1:1 relationship between a payment code owner and their identity.  Presumably the payment code would be strongly and publicly tied to the identity.  This makes the notification address strongly tied to the user.  An SPV client connecting to a full node who has a list of notification address can tie an identity to a bloom filter and connecting IP.  

2. The client can use a bloom filter with a higher false positive rate.  An active attacker can counter that by sending several payment codes to an individual user.  The user would then add to their bloom filter all the shared addresses between them and the attacker.  Even with a high false positive filter, always matching all the attacker's payment codes would strongly tie the user to the filter.

Here are some data savings and privacy addition ideas:

65 bytes -> 0 bytes extra.

1. Can you choose only even or odd DER encoding?  That would save you 1 byte.  This would probably throw out 50% of possible addresses though.

2. Can the chain code be fixed or derived from the x value?  Could the chain value be the x value itself?  (The main question is can a deterministic public seed be represented as a single 32 bit number?  Maybe the chain code can be a constant.  Maybe it is ok since subsequent pubkeys are derived from this.  I only know enough crypto to be dangerous.) That would save you 32 bytes.  Someone who understands HD wallets would be better to look at this one.  it would probably be a non-standard derivation.

That leaves you with 32 bytes to communicate to bootstrap the channel.

3: Since you are already looking at the pubkey of the transaction sending the notification transaction, then you are assuming control of the sending mechanism.  If you can be sure to use a disposable bitcoin address to send the notification, then 1 more savings might be possible.  Also assuming the above two points are possible.

Can you encode the "x value" into the signature's R value?  This would basically make this transaction look like a standard bitcoin transaction and gets rid of the op_return completely.

I still like the idea of a common meeting point, a la bitmessage.  The receiver of the payment code would trial-decode all payment codes sent to a common pre-specified dead drop address (perhaps a charity address).  "to send me money, first donate to this charity of my choice."  This trades off more work on the receivers part to get some privacy as to the number of people interacting with that receiver.

-cheers

-Brian Deery