as long as we agree not to worry about theoretical quantum computing attacks on published public keys
We don't have to worry about that, even in a chain with only public keys, and nothing else. Because in case of some quantum attack, all of those inputs would behave just like OP_TRUE. Which means, that if you require a valid signature in spend-by-key path, and add a new requirement to accept only spend-by-new-signature-path, then it would be possible to upgrade the system in a backward-compatible way.
For example: imagine that someone could easily break all public keys. If the new system would require a valid signature in the old style, and a new stack push, where SHA-256(newData) would be equal to the x-value of that public key, then guess what: breaking ECDSA alone would not give the attacker any advantage here, because it would be needed to also break for example SHA-256 (but you can apply any not-yet-broken hash function there instead, if SHA-256 will be too weak at that time).
P2PK would also be affected by this.
There are two things: one is simplifying address types, and another one is preventing spam. For the former, something like P2PK looks fine (but it would be closer into spend-by-key in P2TR in practice, with some modifications, like prefixing keys with 02 and 03). For the latter, you would need transaction joining on the protocol level. Because if you cannot join public keys and signatures, then you cannot prevent spam. But if you can do so, then nobody can abuse the system with a lot of random public keys, because then all of them are added, and committed to a single public key, so it no longer matters if you create one UTXO or thousands of them (the on-chain size remains the same, only public keys are tweaked, to commit to your data). And in that kind of system, the only space for abuse is left in the block headers, but you would need some blockstorm, like in testnet3, to get there.
Again: A fad based on P2PKH tokens would be much more disastrous for BTC than one based on OP_RETURN tokens.
Yes. But there are two separate topics here: one is to make BTC better, and fix the system, which is already deployed. Another is to make something from scratch. And the latter is much easier than the former. But because some questions were about making simple things from scratch, then I think it is definitely possible to create a new system, that is resistant to those spam attacks.
When it comes to fixing existing system, then it is about simplifying Initial Blockchain Download, and compressing existing data. In that case, people would still need to pay the same fees as today, but it would be possible to not store and process some data, if they are not used in consensus rules.
but can it be proven that a private key exists for a given public key?
Yes. If you have any public key, and you know (x,y) coordinates, then if the equation y^2=x^3+7 is valid, when you apply modulo p-value, then it is 100% guaranteed, that there is some private key, which allows moving those funds. If you have some smaller elliptic curve, then you can brute force all of those keys. If you have slightly bigger one, then you can get a distance between any two public keys, in a reasonable time. For serious, huge elliptic curves, you cannot brute force it, but you can prove, how many points are there, because it is needed to create a valid curve in the first place, and calculate n-value, based on p-value. And if you can compute it, then you can also prove, that there are exactly N valid keys.
you have to derive a key always from another key and announce this derivation with a mathematic proof that it is spendable before you can transact value to them
It is always possible to create "trap public keys" in such system. Even more than that: in Bitcoin, you can move some coins from public keys, where nobody knows the private key, but the signature is valid, because of SIGHASH_SINGLE bug. Some example:
https://mempool.space/testnet/tx/3952b35bde53eb3f4871824f0b6b8c5ad25ca84ce83f04eb1c1d69b83ad6e448Related topic:
https://bitcointalksearch.org/topic/the-smallest-valid-signature-5373858You have this address:
https://mempool.space/testnet/address/032baf163f5e27261ab3228e61fb86dc98054abd514751fce93d7444e8fbc6a293Nobody knows the private key, but as you can see, it was spent in testnet3. And similar tricks can be used, to prove, that something is spendable during initialization, but never move that coin later in another way. However, if your public key will be committed, instead of being revealed, then creating thousands of UTXOs will have the same on-chain size, as creating a single UTXO. The only needed thing is transaction joining in non-interactive way, enforced on a protocol level (and if you create something from scratch, then it can be introduced, without worrying about backward-compatibility).
Perhaps also a proof that a public key is spendable is possible without deriving the key from an existing one?
Even if something is spendable, then the creator could simply generate private keys, move coins into public keys, and throw away those private keys. Which means, that the problem of abusing space is related more to data compression and transaction joining, than to preventing the ability to make some unspendable UTXO. But of course, having all UTXOs mathematically spendable is a nice property to have, if you want to design something new.