Generating challenges is really cheap. Calculating a single SHA256 or sth out of a querystring+salt. Can be done on separate layer so requests without valid PoW won't even register on your main system.
I actually do like your puzzle challenge idea from an obfuscation standpoint of making an API less attractive for clients that aren't your own, though. A challenge system + an annoying format like Protobufs instead of JSON is too much work for a lot of abusers.
Biggest problem with DDOS though is that if the volume is even reaching your application server, you're probably hosed.
It means that on this hardware they can make one request per two seconds not thousands per second.
And it affects all of the hardware under the control of an attacker, so his attack becomes thousands times less dangerous.
> Biggest problem with DDOS though is that if the volume is even reaching your application server, you're probably hosed.
That's why I'm suggesting that challenge generation and validation can be done on separate machines. So your application servers can be safe.
Obfuscation is a valid point too.
I thought about it for a bit, made some experiments. Now I think the challenge should be completely random but the server needs to keep track of recently issued challenges and solved challenges to prevent reusing of already calculated solutions. I think bloom filters would be perfect for that because some small percentage of false negatives doesn't matter.
If somebody wants to access endpoint you might send him a challenge first. Random text. The client must append to the text some other text chosen by him, so that when you calculate sha256 on concatenated text, first byte or two of it will be zeros.
To access your actual endpoint client needs to send that generated text and you can check it if it results in the required number of zeros. You might demand more zeros in times of heavier load. Each additional bit that you require to be zero increases number of random attempts to find the text by a factor of two.
To make stuff easier for yourself the challenge text instead of being random might be a hash of clients request parameters and some secret salt. Then you don't have to remember the text or any context at all between client requests. You can regenerate it when the client sends second requests with answer.
Honestly I don't know why this isn't a standard option in frameworks for building public facing apis that are expected to be used reasonably.