[IngvarLynn]

You're trying to solve a straightforward engineering problem with an unfit solution to an ill-defined problem. The solution of sybil problem would not solve the case of coordinated attack by multiple nefarious agents. You can also call this meat botnet owned by master-coordinator. The solution would distinguish this from a normal botnet but in the end your service down in the very same manner and clients gave up most of their privacy for nothing.

Imagine instead the following trivial scheme: instead of burning resources the client would pay to be served in reverse order of payment value. Let's say client is willing to pay 1 cent to be served in the next 10 seconds. The attacker would have to pay more as he have to occupy the whole head of this queue all the time to be successful. Let's say server can process 100 rps - now he's making over a dollar per second, which he can use to scale his serving capacity.

[Uptrenda]

Introducing the requirement to spend money to use the service would drastically reduce its value. It wouldn't be Tor anymore. Payments would make it easier to link identities and filter access to it. It would also mean not everyone could afford to pay for the service.

>and clients gave up most of their privacy for nothing.

Also not really sure how giving up privacy comes into this? Depending on how the scheme is implemented you can still preserve all the same privacy of using Tor with provisioning keys. E.g. you might use enclaves and keep verification hidden inside enclaves (so hosts cannot see the challenge protocol) or use zero-knowledge proofs to hide everything.

There may even be simpler algorithms since the certificate chain would be using something like RSA SHA256 (which have some neat math tricks to modify them more compared to other algorithms.)