Experts have said that scrypt can be safely used with server relief (see link below). But I'm not sure whether PolyPasswordHasher can be safely used with server relief (i.e. without leaking secrets to the client). Perhaps someone more knowledgeable will pitch in with a better answer.
'Server relief' is dumb... correctly implementing a 'hashcash'-like scheme to prevent excessive CPU resource commitment is non-trivial. It will require either persistent pre-login server state, and/or cryptographic IP/session binding, both of which open up a second DoS vector.
Implementing Scrypt etc in the browser doesn't completely prevent DoS, and sacrifices your ability as an operator to ensure passwords are being appropriately salted and munged (because of third party clients, unauthorised API users etc). Plus, attackers can just start using malicious webpages or botnets to crowdsource their hashing efforts which, because it scales horizontally, could actually speed things up for an attacker if you're server isnt doing any rate-limiting on the final hash+authentication stage.
At some point you have to accept that administrators will need to do some work, and if 200 IPs are trying to log into the same account 5 times every 15 minutes you should probably email the user and lock the account.
Nobody stops an attacker to use a fixed password and cycle the username. If your site has lots of users this could work pretty well. Your site could even "leak" (like forums) usernames making this approach more efficient.
Does this suffer from the same issue?
It isn't necessarily an important issue. Maybe nobody will figure out they can take down your service that way. Maybe rate limiting is enough. Maybe you can solve it by having servers dedicated to hashing.
I was just curious about the performance characteristics:
Suppose that three people have passwords that are each randomly chosen and 6 characters long. A typical laptop can crack those passwords in about 1 hour. If you take the same passwords and protect them with PolyPasswordHasher, every computer on the planet working together cannot crack the password in 1 hour. In fact, to search the key space, it would take every computer on the planet longer than the universe is estimated to have existed.
The contradiction is that if users can log in to your service quickly, then they can try a lot of passwords quickly. So is this more expensive than scrypt?
If an attacker has read-only disk access, they can swipe any unencrypted data. Scrypt protects you from this, and it's straightforward about the requirements and computation costs.
In practice, what kind of CPU usage would a PolyPasswordHasher scheme need?