Proof-of-Work Defense for Onion Services
blog.torproject.org
blog.torproject.org
> make it harder for attackers to overload the service with introduction request
> We hope that this proposal can help us defend against the script-kiddie attacker and small botnets.
Sets expectations: does not counter large botnets.
> We hope that this proposal will allow the motivated user to always connect
A user who really wants to connect can get through durring a DoS attack, but it may still take work.
Interesting choice of PoW algorithm: https://github.com/tevador/equix
> Hence, instead of forcing clients to go below a static target like in Bitcoin to be successful, we ask clients to "bid" using their PoW effort. Effectively, a client gets higher priority the higher effort they put into their proof-of-work. This is similar to how proof-of-stake works but instead of staking coins, you stake work.
[1] https://gitlab.torproject.org/tpo/core/torspec/-/raw/main/pr...
> The service would give the request a priority value based on the "difficulty" of the puzzle solution.
Seems like single clients could increase the difficulty to higher than what the bot net would do (so it gets priority), and hence get access. Operators of the bot net would probably hard code one value as the difficulty, and it would be lower than what you could typically set on consumer hardware.
Maybe user agents could even do this increase automatically?
Bad assumption.
Assumptions like these never last. People who say “I don’t have any money” are still valuable to hackers as phishing senders, legitimate social media accounts, residential + non-cloud + regionally convenient IP space, etc. If consuming connection / server resources becomes valuable then botnet controllers will find a way to pay the cost. It’s easy because someone else is paying for the hardware, bandwidth, and power costs.
But the effect of a market of PoW is the same — there is game theory involved in bidding (just like a silent auction). Even if a botnet uses a dynamic priority bid system, the cost increases as the botnet tries to starve the server of resources. The server’s resources are always zero-sum and the bidding will get progressively more expensive until the opportunity cost of the botnet changes behavior.
> The large botnet is a serious operation with many thousands of computers organized to do this attack. Assuming 100k medium-range computers, we are talking about an attacker with total access to 200 THz of CPU and 200 TB of RAM. The upfront cost for this attacker is about $36k.
They appear to define it by compute capacity, so I'd expect the attacker can solve harder puzzles than legitimate users would attempt.
This version is good, don't get me wrong, but adding value transfer would be better imo.
There might be legal issues for the users too-- e.g. upgrading copyright infringement into criminally prosecutable commercial copyright infringement.
Obtaining the funds creates extra friction, yes, but it’s possible the benefit outweighs the cost — e.g. because an attacker can no longer utilize the idle CPUs of botnet devices.
Ultimately, any form of anti-DoS protection also punishes legitimate users. The question is (1) how much it punishes attackers relative to this, and (2) whether this punishment for legitimate users deters them, too.
Plus, PoW is nothing but wasted, needless computation. Computing is not free. Every watt spent doing anything PoW is just that much more intensification of our current climate crisis.
As someone with temps of 109 with heat index of 120 coming in the next few days, with all due respect, fuck anyone who proposes PoW is a good idea for anything.
It isn't interesting. It's the most egregious example of conspicuous consumption on the planet.
Remember that this PoW proposal is a market. If the server has unconsumed cycles (eg. Is not saturated), the POW spot price can remain 0. The server only needs to set a PoW price after the server’s resources near saturation. For the same reason auctions end because nobody is willing to pay infinity dollars, clients can forego PoW and can opt to check back in on the server later when costs subside.
If this is the case and in practice PoW is never required, then your rant is moot, and instead it is interesting that this effect occurs.
That's an appeal to authority and an attempt to shut down inquisitive thought and investigation.
Imo, this goes against the spirit of HN.
A better response might have been to point out that the level of POW is reactive. If there are no attacks ongoing it will use little to no resources. If it's effective, the attacks will largely stop (no point in attempting an attack that won't work) and so paradoxically this can potentially provide its benefit without actually having much usage.
If it works out that way the benefit vs costs are very good for pretty much any way of evaluating the costs. This is the kind of nuanced thinking that you'd expect from smart people, as the prior poster suggested (and, in fact, is pointed out in the design document).
It's not even impossible for increased consumption to lower carbon emissions, because to meet the higher peak demand you may need to add more generating capacity. When the new capacity is renewables or nuclear then it adds no carbon emissions during peak usage times and allows for a reduction in carbon emissions whenever the grid is at less than full capacity by assigning the remaining load to the new plants and spinning down the legacy fossil fuel ones that would otherwise have been used.
Everything has drawbacks. It's always a tradeoff in software. You want a really simple interface? Now you can't do complex things. And so on.
Instead of complaining loudly, why not be the change you want to see? Proof of CPU makes you hot? How about proof of RAM? How about about something else, which you thought of yourself, which is a great idea, which you shared with their team, which they would eagerly accept as a superior solution to proof of work?
With the proof of work, I think the assumption is that a legitimate user will be willing to accept a sufficient delay to make botnet DoS attack impossible.
The counter argument might be that the botnet can generate arbitrarily hard proof of work, but this isn't true. Assuming some fixed capacity by the botnet, and that the botnet needs to send some amount of requests per time in order for the attack to be effective (e.g., if they only send one proof of work request per minute, then the "bid" for the rest of the time is quite low), then there's some maximum effective "price" based on the capacity of the botnet past which a user is guaranteed access.
For example say a botnet has access to a million compute nodes, so they have 1 million proof of work seconds per second.
If there's a service which can serve 1000 requests per second, then the average proof of work seconds they have per request is 1000 seconds of proof, so as long as the user is able to provide 17 minutes of proof of work, they can get access. In reality, the user's hardware is likely more capable than the attacker's botnet (which is probably IoT devices etc.,) so the ratio is more favorable.
I find it amusing that this approach is pretty on brand for onion services, as an invisible hand type market solution from what I'd consider to be a fairly libertarian leaning group.
That's the whole point.
Sorry it's hot there but this is absurd virtue signaling and should under no circumstance come into view as a reason to not do PoW.
Every watt spent doing anything, period, right? Like using your computer to send comments on HN?
Or streaming video? Or any one of a million things that humans do which aren't strictly necessary for survival but we do them anyway?
The tirade against PoW is absurd. It's useful, get over it.
> It isn't interesting. It's the most egregious example of conspicuous consumption on the planet.
This cannot be overstated. PoW needs to die. It is a lazy implementation that just sounds clever but is nothing of the sort. It kills our habitat. It has to go.
Appearently the PoW function they chose is equi-X.
I'm wondering how much this will decrease load on the service being proxied vs the nodes themselves though, I assume it'll have more benefit to services since access is spread out between multiple nodes.
[0]: https://gitlab.torproject.org/tpo/core/torspec/-/blob/main/p...
It should have been, but was delayed by people shrieking about oceans boiling.
No one is doing any such thing.
>salawat
>PoW is nothing but wasted, needless computation. Computing is not free. Every watt spent doing anything PoW is just that much more intensification of our current climate crisis.
>As someone with temps of 109 with heat index of 120 coming in the next few days, with all due respect, fuck anyone who proposes PoW is a good idea for anything.
>It isn't interesting. It's the most egregious example of conspicuous consumption on the planet.
Cloudflare could do this, too. Every time you access a busy site, seconds to minutes of useless crunching. The overall effect would be to drain batteries worldwide.
It served as the inspiration for Bitcoin's PoW mining, interestingly enough.
>With a JS challenge, Cloudflare presents challenge page that requires no interaction from a visitor, but rather JavaScript processing by their browser.
>The visitor will have to wait until their browser finishes processing the JavaScript, which should be less than five seconds.
https://developers.cloudflare.com/fundamentals/get-started/c...
It would also dump greenhouse gasses into the atmosphere.
Edit: looks like PoW is set per "service" that's under attack rather than client?
It seems that they're targeting memory as a way to make it more costly for botnets. I think that there are many other ways to help minimize this attack scenario, too. The same logic could also be applied to mobile phones using ESIM. Later authentication with the mobile network uses public key crypto so I feel like you could also do unique proofs there, too.
This is just a throw away comment though. I am probably missing obvious problems with this scheme.
The strongest privacy guarantee I've heard behind attestation is it would require two parties to collaborate to break it. If Google attests to a Cloudflare protected site, they can determine who you are by cooperating.
They chose memory-hungry algorithm because that would prevent use of specific hardware (ASICs).
Overall, they will have more leverage from these resources than the number of systems they have access to. But you could at least restrict this to the number of systems with provisioning keys. The idea behind memory bound hash functions is that you're trying to make it hard to paralyze the challenge to a farm. But many systems in the farm are still going to have multiple cores and gigabytes of RAM (so they can be used to leverage multiple challenges simultaneously.) The underlying problem to solve here is an identity problem: allowing an individual machine to act as a single identity which various proof-of-work schemes have tried to achieve.
The ideal solution would also limit connections made by the same actors but that is probably not something you can achieve with something like TOR. This is a sybil problem, by the way.
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.
>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.)
In the same vein, how about the server would hold a pool of IPs in which the client has to return a proof of port knocking? e.g. here is a token, send that to this IP:port and wait for a unique response I can verify. Call this proof of latency. It would be low CPU, would spread the load across various machines and ports. On the downside, of course, you need multiple IPs and potentially servers. It could be implemented on the same machine but that would shift the cpu load to port connections.
It allows you to scale your workload, but "just pay for more servers and outscale the attacker" isn't generally an acceptable way to deal with DDOS.
The current proposal discussed in the post talks about "prioritize verified network traffic". It would be interesting if sharing "file pieces" could prioritize your traffic since you're actually helping the network. Instead of "proof-of-work" it would be "proof-of-bandwidth-contribution".
I dont really see how it minimizes traffic on the network though. You still have to talk to the CDN nodes.
Personally I dislike proof of work, it's basically bloat as a defense mechanism in this case and can obsolete older hardware fast while consuming in aggregate probably a lot of power across the devices it affects. At scale it would be quite a large environmental burden.
I also think a lot of attackers will consider it a success to get it to that high difficulty as users who have to wait 1 minute of their device being 100% pegged will probably choose to disengage a lot of the time.
That said it's quite a good way of mitigating DOS attacks while not doing anything to compromise user anonymity, so from that point of view it's a good solution despite the drawbacks. As it exists on tor, I don't have too much of a problem with it but I'd consider it a total disaster if applied to the regular web.
Also, since it is DDOSing, the server’s work is embarrassingly parallel, but the client work isn’t necessarily parallelized at all.
Even if it is only a factor of 6 (or one) they are talking about 1 minute solve times once a DDOS is detected.
At that point the service is basically down anyway, right?
The limiting factor if equihash is allegedly memory bandwidth, which maybe doesn't vary that much between srrvers and phones.
> they are talking about 1 minute solve times once a DDOS is detected.
The point of this is to prevent an existing easy DoS attack (introduction flooding) into a partial outage/slow down. It's an incremental improvement on a hard problem.
https://www.benthamsgaze.org/wp-content/uploads/2015/11/sucu...
I think this[1] would help.
I think there is a second cost aspect to this as well; right now, hacking low-powered IoT devices and making them part of your botnet is (relatively) easy and valuable, but as their computing power is quite limited, a PoW defense should make them less viable for DDoS attacks, decreasing the amount of free attack power.
It takes much, much, much more (proven) work to DoS a service than it does to use it normally.
Like the idea otherwise.
With Onion Services however, there is no exit relay. Services are encrypted end to end between the client and the hidden service.
And is that the kind of hardware that the users in regimes that TOR is supposed to help have?
Maybe captcha serving itself can be DDoSed, because of the image size?
Whereas with captchas, the government need to pay real people to fill them, which doesn’t scale
Edit: I read the paper (https://gitlab.torproject.org/tpo/core/torspec/-/blob/main/p...) and I understand what you meant. This is not meant to replace captchas but to automatically discard low profile attacks. Nice.
The article says they target 1 minute solve times under load. If that’s 1 minute on a 5GHz, 64 core machine with 512GB ram, an A100 and an FPGA, then it’s going to be at least 5-15 minutes on your phone.
Also, the server farm can parallelize work across an arbitrary number of challenges, but legitimate users cannot.
If the server can process 10k requests per minute, and you need to send 10 requests per minute, you only need 0.1% as much power.
No, the point of the PoW is only to mitigate DDoS and it can do that.
The problem is that we don't know how much is a cheap computation without first relying on a marketplace of computation and discovering the price. That marketplace of computation does exist, and it's called blockchain.
The upside is that the server does not go down, so at least some users will be able to access the website, compared to zero users
Yes but the price is very important. Imagine you visit a country, and paid car rides, (i.e. taxis) cost one thousand dollars per hour. It might be the best ride you have ever taken, but it excludes 99.999% of the users due to price.
The problem is, it is impossible to figure out, how much computation is a cheap computation without first relying on a marketplace of computation and discover the price that way. The blockchain technology serves exactly that purpose. The producers of PoW, the miners, sell their PoW to consumers. Consumers bargain the price, by using it less when it's expensive, and more when it's cheap.
The blockchain logic states that: "Requiring users to give proof of burnt energy -> good idea" "Requiring users to burn energy themselves and then give proof of burnt energy -> terrible idea"
Basically it goes like this:
You are challenged to use some piece of data given to you, and to add some data to it, which will produce a hash with a given number of leading zeroes.
For example let’s say I challenge you to find a sha3 hash of (“response to codetrotter for comment 37255449 on HN” + any data of your choosing), with difficulty set to 3. Meaning that in order for me to accept the hash, it has to have at least three leading zeroes.
The higher the difficulty, the higher number of leading zeroes I ask for from you. Which in turn means it will take you more time to find. Because the only way to find a fitting hash is to try a bunch of different data until you find a fitting hash.
The neat thing is that while it takes a lot of time for you to find a matching hash, it is trivially simple for me to validate your claim when you’ve found a matching hash.
For this kind of PoW, people have developed software that runs on GPU faster than most CPU can do. And then they developed specialised hardware to be even faster - ASICs.
That in turn is where memory-based algorithms come into play. To make the people with GPUs and ASICs not have an advantage over others.
RandomX (Execution of a random program): Memory Hardness (Inc. cache sizes), Speculative Execution/Branching, ILP, some sort of chaining https://github.com/tevador/RandomX/blob/master/doc/design.md
Edit: these are examples of CPU-bound PoW. But the general idea with PoW is that you have some hash-like function H() with no known inverse function such that the only feasible way to determine the output is just running the function. The client runs H(x) with a different input x every time. If the output is a high enough number, the server lets the client though.
The server runs H() to verify, and this is easy to parallelize. But in order to get through the server, the client must run H() many times on average.
Also server provides a salt to prevent the client from reusing their old hashes. And the server usually indicates how high the output of H() must be (this is called the difficulty).
No; that's a particular PoW algorithm called Hashcash [1]. There are other, asymmetric ones, where PoW verification is different from a solution attempt, including the Equi-X PoW that ToR is implementing.
I'm not sure which are specialized for GPU-resistance, probably not prime factorization given it can be parallelized
It makes me wonder if there would ever be a way to actually do the opposite - your "proof of work" is somehow linked to extracting CO2 from the atmosphere?
Don't hate on the BTC crowd, some of us also care about ecological load.
The problem is, such integration would require the chosen coin to be anonymous, which is essentially forbidden: https://www.theverge.com/2023/8/23/23843161/tornado-cash-ind...
This proof of work doesn't mean crypto currency, it doesn't mean coins, it doesn't mean buying or selling tokens. It means proof of work. More exactly, having to put your computer at work in order to solve an equation. If you do that, the server lets you in. If you don't, you can't enter.
This is the original proof of work. It's also proof of work when you solve a captcha, it's just a different proof of work, a human, mental one. Here, it's a computer one, meaning in order to access a website a thousand times, you would have to run the proof of work a thousand times, so a thousand times more ressource.
I really wished you gave the article a read, before saying Torproject is a shame. Maybe you are?
Well, yes, I should've said 30 years, not 10.
You can start educating yourself on cryptocurrencies with the monero case: monero payments were used instead of captcha on an internet forum about 10 years ago.
That said, modeling it after a general cryptocurrency is probably a bad idea since it rising prices may prevent legitimate clients from being able to connect to onion services due to the challenge being too expensive (either in terms of computation or accusation). I think a much practical approach is to have each visitor contribute to a partial solution that can then be combined to derive funds (much like how mining pools work). That way, clients will be completely isolated from cryptocurrency and sites can actually benefit from the work rather than just throwing it away. It's a win-win situation.
I hope the next generation learns from our senseless technology-burnings.
Not modelling after but integrating of an existing one. Because this saves massive amount of engineering effort.
>rising prices may prevent legitimate clients from being able to connect to onion services due to the challenge being too expensive
Obviously, the price for legitimate clients would be much cheaper, as their requests shall be placed in the middle of priority queue (clients can wait a few seconds) while the attacker have to occupy the very top of this queue all the time. Also note that the bigger the DDoS in this scheme - the bigger profits server could make, which he could spend on expanding capacity.
>each visitor contribute to a partial solution that can then be combined to derive funds
This scheme predates monero, which was about 10 years ago.
>the next generation learns from our senseless technology-burnings.
Not if they would reinvent the wheel each time instead of adapting of existing tech to current needs.