It seems to me you could make public derivation unlinkable eg by creating a random secret "chain code" and encrypting it for the recipient. So c' = random, Qi = c'G+Q, E( Q, c' ). Where E is public key encryption with Q public key, such as EC elgamal E(Q,c') = (A,B) where k=random, point C=[c',f(c')] where EC is defined by function f, A=C+kQ, B=kG. Decryption is c'=[A-xB].x. Now to receive transactions you need a full client and attempt to decrypt c" values and check if c"*Q=?Qi.
Apparently forum user bytecode proposed something related to this in the past.
Some update on this. I had discussed on IRC the idea of using a 'bloom-bait' to make this a little more SPV friendly, eg by including the last byte of the public key, but it does erode the anonymity set though.
Alternatively one could make a separate pairing message with no inputs (other then anonymous unlinkable fee for anti-DoS) to send E. In this way the pairing message sends E(Q,c') (actually deterministic c' for idempotency/crash recovery reasons). And c' becomes the shared chaincode for a normal BIP 32 HD sub-wallet specific to sender-recipient pair and secret to them. There is some risk of time correlation of pairing and first payment are made immediately, and some risk of failure due to non-communication of the pairing message, meaning the recipient does not know c'. This part is not ideal, sending a single combined message is preferable but incurs trial-decryption and a full node, or a delegation to a full-node that learns the chain-code and does the trial decryption. Probably one could delegate trial decryption to a full node, and the payload is a super-encrypted chain-code.
I am not sure if its analogous to bytecode's idea or not (didnt find the original), but retep also proposed on idea another variant of this same idea: to use static DH for the encoding instead of EC Elgamal (aka ECIES), which is basically centered on the artefact that the paired users dont care to choose a chaincode, a random, negotiated one would do. For that eg the sender has a public key from an input say P=eG, and the recipient has public key Q=dG, then they use ECDH to arrive at shared code c'=H(eQ)=H(dP). retep called this a stealth-address, so using BIP 32 it creates a sequence of HD addesses as Si=M(c',i), and the recipient compressed address is S'i=H(Si) so the recipient with a full node can scan for these. Or delegate scanning to a full node.
Again an explicit bloom-bait tag could be used to reduce scanning at the cost of anonymity set. To make it backwards compatible retep suggested to grind the address to give it a prefix with the added bonus that many tools already keep address prefix indexes. (Address grinding might modify BIP32 to add a grinding counter: Si=M(c',i,ctr)). That does imply some grinding cost which slows things down, but its somewhat backwards compatible and arguably indistinguishble to some extent. Ground address prefixes, or explicit bloom-bait tags, may have adverse effects on CoinJoin as the tag/mark is visible and anonymity set reducing.
To my way of thinking therefore there are still gaps in the viability of this approach. While it is quite attractive to have a safe way to have static base addresses with sender derived addresses or chain codes, it is not so far scalable to light nodes. But if a way can be found to make this scale to light nodes without introducing an anonymity set problem it could be a big step forward as seemingly users on a recurring and on going basis dont understand and dont like single-use addresses on the receiving end. Clearly single use addresses are problematic.
This approach above could work for recurring business things like exchanges, payment processors etc as those entities are typically running full nodes anyway. You could say those entities anyway
have the infrastructure and communication pattern to support HD sub-wallet addresses.
There is one additional advantage of sender derived addresses: the recipient has a global shared static address so it can act as a trust anchor to ward off diversion attacks in a simple and space efficient way without signatures. It can act like an SSH TOFU (trust on first use) fingerprint. Users can compare fingerprints, call up the company, expect the fingerprint advertised on all official emails, SSL static content web site, business cards, trust directories, PGP signed by key employees etc. (Diversion attack meaning where someone hacks a server and replaces the addresses with their own). Furthermore people can check that fingerprint in their offline wallet for investment level amounts.
Adam
[edit: NB for this general scheme to work, the recipient needs to advertis an uncompressed address, ie the x-coord of Q, rather than H(Q). That might even be compatible with older uncompressed BTC addresses, I am not sure]
