I only know of one site that worked the way you propose: TicketMaster, a long time ago. They used it as a less harsh form of blocking for IPs that they strongly suspected were bots, which is what you suggest indeed. But 99% of the hard work of that system was in scoring the connections. The actual PoW part didn't work that great because bots have much more patience than humans do.

Other sites also use proofs of work, but they're CAPTCHAs i.e. human PoWs. And unfortunately those don't work very well these days either :(

 

Yes, I understand, but then you're back to scoring clients - the hard part - and the only question is do you slow down that client by sticking them at the bottom of a work queue or by requiring them to solve a difficult PoW. The best approach is the first one because that scales naturally .... you don't have to define some notion of misbehaviour, you just prioritise amongst clients. 

The current notion of "misbehaviour" is only somewhat useful. It's easy to classify reasonable behaviour as harmful and shoot yourself in the foot. We managed this at least once back in 2010 when we actually released a version of Bitcoin that interpreted a normal request to serve the block chain as a DoS attack! It couldn't serve the chain at all! Additionally many things that can be interpreted as an attack like sending a message with a bad signature can also be caused just by mistakes, or version skew during software upgrades. So it's very tricky to get this right.

That's important because one quite common way big sites suffer DoS attacks is by accidentally having real users create a DoS "attack" by e.g. pushing a bad software update, or by having sudden and unexpected press-driven growth, etc. You really don't want to force users to sit around waiting and wasting battery. It's better to serve as many requests as you can up to your absolute limit and try to ensure as many of them as possible are good.

 

I doubt it matters. Any DoS attack that's powerful enough to use up most of the networks resources is probably being driven by a botnet of some kind, and all legitimate users will lose in an even fight against a botnet.

Cookies can be somewhat anonymized. For example a cookie that is merely a signature over a timestamp of some kind (doesn't have to be an secp256k1 signature) can be normalised to the day or week. So you can prove you've been using Bitcoin for say 3 years but it doesn't pin you down precisely.

This isn't perfect:  attackers can and do "age" accounts before preparing for abuse. Proof of UTXO is another way to rank users. If you're richer you're presumably more important for the network to process than poor people. However you end up back at a CPU imbalance. PoW can possibly play a role here to even it out: the cost of submitting a UTXO proof should be at least equal to the cost of verifying the signature, but that is a PoW small enough that users would not notice.