Public key validation would work if those were being used to store the spam, but what happens if it's address hashes a la base58 or bech32? Verification becomes impossible as the key is not even known.
Yes, that's true. The main effect is that spam would become more expensive because the "grinding process" to figure out the addresses would not allow a similar efficiency to storage in the "public keys" (e.g. in P2MS like some of these protocols do).
I don't remember "how much" more expensive data storage would become due to such a measure (should be buried deep in the bitcoin-dev discussion about the OP_RETURN change). IMO it was significant but a malicious spammer would still be able to afford it. But in the bitcoin-dev discussion it was argued that also regular Bitcoin transactions would become more expensive as you would have to store more data in the script, like a signature. See also @gmaxwell's answer here:
There are several fairly straightforward ways to transform arbitrary data to and from an indistinguishable valid pubkey. One is in the bitcoin codebase already for the P2P encryption. So what, permanently increase the validation cost of every txn by 1/4 or something to make the opponent copy and paste a bit of existing code?
A slight doubt I had about your post, @gmaxwell:
So not only would that fail, it would also make things worse since at least now a node could expand its definition of unspendable outputs to include the ~half of these that aren't valid points and exclude them from their UTXO set. But if blocked and then they move to adjusting the encoding so they're always valid points (or just changes to make them 256 bit "script hashes") this option goes away.
I interpret that "currently" there would be some methods for nodes to exclude these "fake public keys" from their UTXO set already, but if the validation was changed, that would not longer be possible. So does this mean that there could be indeed some "spam-pruning" methods to be set up for the case the fake public key method become too widespread? I guess the primary question would be the cost of this method for nodes vs. the cost of storing the data.
Of course spammers, if they really want to be sure that their data remains on the blockchain, could already now develop a completely "safe" protocol, for example encoding the data directly into pubkey hashes or addresses. Not even a method based on UTXO expiration (with recovery option, see
my thread here) would really help in this case, although it would increase the costs to store that content "forever" if the UTXO expiration also allows nodes to prune the UTXOs from blockchain data.
The other method we have is to enforce transaction (not block!) pruning as an optional command-line option, by using a bloom filter to completely ignore Bitcoin eater addresses, invalid keys, OP_RETURN.
I guess that is what @gmaxwell wrote above. As long as full nodes need to archive everything, however, that would indeed only be useful for "passive" nodes, i.e. not those actively distributing the blockchain.