What would it need to add Ring Signatures to Bitcoin?
It can be done on top of Taproot. You can have a single Taproot address, which would handle N users at the same time.
if something like that happened, I wonder how all the CEX's and the KYC/ AML checkers will work out and name "dirty" coins and addresses
In the same way, as they do that on other coins, which introduced similar rules. If you use some privacy-based coin, like Monero, and you send it between exchanges, then these exchanges comply with some regulations, and the more users they have, the more traffic they can deanonymize.
But honestly, it could make things way slower and more expensive to use.
It depends, how things will be connected. Because if it will be optional, and the cost of computing things will be only on users of Ring Signatures, then it wouldn't affect the rest of the network. For example: if you have Lightning Network or sidechains, then only these users have to process, what happens inside these networks. Everyone else can just see things, as they are today, so they don't pay any additional costs.
But in either case the real efficiency problem is the impact on UTXO size. Since one can never tell which is the real input and which are the decoys, no output can be known to be definitely spent. So the UTXO set balloons to the entire TXO set, with very detrimental impact on node efficiency. It's not so noticeable on Monero yet because daily tx volumes are about 15x smaller than Bitcoin.
In the most extreme case, you need only a single UTXO per subnetwork. Which means, that if you want to peg Monero into Bitcoin, then you can have a single UTXO, with all Monero's supply, denominated in BTC, and then, from the Bitcoin's perspective, you have a single moving UTXO. But if you want to really know, what is spent, and what is unspent, then you have to connect with that subnetwork, and download their database.
Which means, that making N additional UTXOs wouldn't hurt the main network in that case, but only some subnetwork. And then, switching from one bloated network to some fresh one, is just a matter of moving your coins from one UTXO to another UTXO. And in that case, you can always leave some subnetwork, if it will be more bloated, than it should be (and also, subnetworks have a nice property, that they commit to a stronger chain, which allows pruning historical data in a way, where new nodes don't have to download that kind of data, to check, if the network is honest or not; just like you don't have to download all historical LN transactions, if they are all settled on-chain).
I'm wondering if this would not be a hard-forking change. Can you really achieve this only "tightening" some rules?
A lot of things can be made through soft-forks:
https://petertodd.org/2016/forced-soft-forksOne crucial question is: How would old nodes process these transactions?
In the same way as today. And how would old nodes process Schnorr signatures they know nothing about? How would pre-Segwit nodes process Segwit transactions? If Ring Signatures would be enabled as a feature, only for those, who will explicitly want to use it, then the rest of the users will be unaffected.
