Given the pure stealth address are essentially generating fresh ethereum addresses for the purposes of this scenario wouldn’t it make more sense to implement as a wallet level protocol rather than in a token standard?
As @vbuterin stated above this would make the most sense in a smart contract wallet, but the problem remains that has needs to be paid in an unlinkable way otherwise the protocol would only delay the construction of a transaction graph by an observer rather than properly prevent it.
I see 2 approaches here assuming our stealth address protocol is smart contract wallet based: A) an out of band payment is made to compensate a gas related, or B) the transaction compensates a gas relayer from a seperate stealth address where stealth addresses. B is the ‘decentralized’ approach, but would only really achieve UTXO levels of privacy, A would be as private as the out of band payment method to the gas relayer and strongly private to everyone else assuming the gas relayer can be trusted to not reveal any data they obtain but this is obviously a fairly centralized approach.
Side note: Using a zk shielded pool with approach B would prevent visibility of the transaction graph which should result in a strongly private protocol, I’m not sure another generalized approach is possible without a significant change to Ethereum’s transaction format.