Are you talking about public keys with a proof of knowledge of the private key (i.e. a signature) ?
While you can set some output bits by grinding, that would not a little bit less, but MUCH less.
Seems you're correct, I've re-read the relevant part of the mailing list discussion and
here Peter Todd argues that it would make the "fake public keys" approach about 6-7 times more expensive regarding fees. But the downside is that according to another post by Sjors Provoost,
here, the sizes of the output scripts would increase "dramatically":
To stop that, you'd have to introduce a rule that only allows spendable public keys to be put on chain. Afaik, the only way to do that is to require a signature. That would dramatically increase the size of all output scripts.
The
prove-its-a-pubkey signature itself can carry data, if you know the 'private key' you can completely recover the nonce. (or vice versa, e.g. a predictable nonce in the signature lets you recover the data hidden in the 'valid' public key). So in that case you've just moved the storage from one place to another. Of course the storage is prunable, but so is op_return and witness data. The 'proof of key' data would be presumably MORE prunable but this starts to feel like hair splitting to me. I have suggested some more elaborate ways of proving keyness that require massive slowdowns, switch to a far sketchier bilinear group, but which eliminate the signature side channel... but they still do nothing for 'real key' storage. The work used to grind real keys is also conserved, unless address reuse is banned.
I think tromp underestimates the amount of data you can store directly in 'real' keys
toowithout using the proof sidechannel, if you don't mind the receiver having to be somewhat computationally expensive (such as requiring the resources of a fast desktop class machine to keep up with the chain) you can store on the order of 64-bits per output in the key (by DL solving the keys), 8 or more bits in amount LSB. If you don't mind building up a large stash of coins in your wallet you can store several bits per input in the form of what coins you select and what orders you select them, and so on. So at best you increase the attackers fee cost by a modest constant factor. It's not nothing but the cost it comes with in terms of reduced functionality and overhead are considerable. If they stopped the abuse completely *maybe* you could justify-- but like, say the threat that someone will embed illegal information in order to harass node operators is not going to be meaningfully stopped by making it 5x more costly because they could only store 9 bytes per 40 bytes of output data.
If that 5x increase were 'free' then sure, but you get that only after maybe doubling the amount of data needed to relay txn/blocks, doubling the validation costs, doubling the size of addresses, and radically handicapping the utility of Bitcoin. Had Satoshi thought that way payment channels likely wouldn't have been possible (one could try to carve them in since we know about them, but you can't reliably carve in stuff we don't know about). Besides, a great many people bought in to Bitcoin as programmable money, taking that away is a non-starter particular if it's "we can make some abuse a bit more expensive, without even blocking it". Bitcoin has already made storing data quite expensive, which already sheds the cost sensitive portion of the traffic. It's a reasonable assumption that what remains not particularly cost sensitive.