Skip to content

Proof Of Work (PoW) FAQ

About

This page has some possible Frequent Asked Questions (FAQ) about the Onion Services' Proof of Work (PoW) defense1.

If you have further questions, please ask them in the Tor Forum.

Acknowledgements

This FAQ adapts, summarizes and glues together a lot of the existing documentation (specs, ticket comments and custom explanations). This can be considered as written by many hands and the overall works is available thanks to the following people (see tpo/core/tor!702 for details):

  • Thanks tevador for the underlying PoW algorithm, Equi-X.
  • George Kadianakis, Mike Perry, David Goulet, and tevador for the Proof of Work for onion service specification this implements.
  • David Goulet, Roger Dingledine, Mike Perry wrote most of this implementation last year (2022).
  • Micah Elizabeth Scott did the final touch in the specs and finished the implementation, as well as testing it.

General questions

The technology

What is the Proof of Work (PoW) protection for Onion Services?

Proof of Work (PoW) is a cryptographic mechanism where a computing system can prove to another that they have performed some computational effort.

The Proof of Work (PoW) defense for Onion Services is a way to protect against Denial of Service (DoS) attacks by prioritizing, when under stress, clients that have proved to the service that they performed a number of resource-intensive operations.

It's a way to prioritize verified effort (but not a way to verify users), which means attackers would have trouble launching many requests to an Onion Service, but users will possibly have resources to do their legitimate requests.

In other words, Onion Services may be configured to offer a Client Puzzle if they're under heavy load, and to prioritize incoming client connections containing solutions to the puzzle.

Why is Proof of Work needed? (What inspired the development?)

There's a lot of computation needed in order to establish an Onion Service connection between a client and a service. This computation consumes processing time, memory, storage and energy in the server, opening the door to a vulnerability known as Denial of Service (DoS), where an attacker spawns multiple connection attempts in order to overload the service and render it inaccessible.

By design, the Onion Services technology does not make internet addresses (IPs) available to identify users connecting to a service (since it aims to be privacy-by-design compliant), and hence there's no way to apply traditional techniques of IP-based rate limits.

So a Proof of Work (PoW) mechanism was devised in order to contain DoS attacks without compromising the user privacy.

How does it work? (in simple terms)

In order to be effective against DoS attacks, a Proof of Work mechanism must run before the bulk of server-side computation happens when an Onion Service connection is established, and to be enabled only if the service is under stress.

With the Proof of Work (PoW) mechanism, the introduction phase for Onion Service connections is split in two parts:

  1. During the first part,
    • A service under load can indicate a level of effort it expect clients to employ when solving a client puzzle, as well as a random number (a "seed") used to calculate a solution.
    • Clients may offer a solution to the puzzle based on the seed and a given level of effort (which can be smaller, equal or even greater that the one suggested by the service).
    • The server validates solutions and prioritizes clients according to the employed effort: clients that have solved the puzzle with highest effort have priorities over those that used less effort and over those which didn't offered a solution at all.
  2. In the second part, the server proceeds with the more resource-intensive steps to have a working connection with clients.

The PoW implementation for Onion Services was designed in a way that this first part uses way less resources for the server than for the client. The first part also requires less resources to be processed by the server than during the second part.

The service starts with a default suggested effort value of 0, which keeps the PoW defenses dormant until it notices signs of overload.

The system is dynamic: as time goes by, the server regularly updates the suggested effort based on its load.

Without this protection, attackers can mount a Denial of Service (DoS) with minimum effort, whereas the server would need to perform many computations in order to process each connection request. Since the Onion Service cannot guess which connections comes from legitimate users and which are from attackers, the service end up processing both. And if most of the connection attempts come from attackers, only a small fraction of processed connections will be from users.

The PoW defense disincentivizes attackers, since an increasing number of requests would make the service increase the suggested effort. To have their requests queued with higher priority, attackers would need to solve the client puzzles with higher and higher effort. Many connection requests, each one with its own puzzle solution, requires an increasing amount of computing resources, up to the point that the attacker exhaust their resources or have to invest more and more with diminishing chance of success.

A legitimate user, on the other hand, needs one or only a few connections to the server, so she may be willing to expend computing resources to provide a solution that has an effort higher enough to get priority over the attacker connections, without significant impact on her system.

The expected result is that attackers won't try to DoS the service for too long, or won't even have an incentive to do so, and the PoW protection will tend to be disabled or to have an effort oscilating around zero according to fluctuations in the usual service load.

In summary, the Proof of Work (PoW) defense is a mechanism that imposes a disadvantage for those who make a huge number of connection attempts to an Onion Service, with a small side effect of requiring other users to expend a little more effort when trying to connect if the service is under high load. With the PoW defense, attackers effectively work against themselves: the more attackers hit the service, the harder it gets to hit the service.

How do I know as an end-user that an Onion Service is under stress?

As of August 2023, sites under stress will either be slow or even time out, but without a user interface indicating that the PoW protection is active.

Applications like Tor Browser could display, in the future, whether PoW is enabled in a service and it's suggested effort level for the client puzzle, which could be used to guess if a service is under stress.

If PoW is enabled and puzzles are suggested by the service, PoW-capable clients will attempt to solve them without the need for users manually turning on PoW, i.e, it's something that should happen automatically.

Do we have testing data or are planning to collect metrics to show how PoW may act as a deterrent?

First, it's very hard to measure attacks that did not happen and correlate to the PoW feature's efficacy.

It's also unfeasible to use Tor network as a testbed to do real attacks just for testing purposes.

The feature was tested, but in a small scale in order to not penalize the network. Check the onion-pow-example project for a way to test the feature without bring disruptions to the whole network.

For real DoS events happening after the release of this feature, it's possible to collect PoW metrics in the following ways:

  1. Indirect measurements on some public services that may be or are known DoS targets, using tools like Onionprobe to parse Onion Service descriptors and look for the suggested effort at the pow-params field (check tpo/onion-services/onionprobe#78 for details).

  2. Direct measurements, made by operators when their Onion Services are under attack. These can be collected using the MetricsPort feature, and used to analyze how effective is the PoW protection. But beware that sharing MetricsPort data has security/privacy implications, so this needs to be done privately and carefully within a team that will analyze the data before releasing conclusions (and cleaned/harmless data) publicly.

How is this different (or the same) from PoW in the cryptocurrency space?

The Onion Service Proof of Work (PoW) mechanism was designed to address the specific challenges to the Tor network, and has different properties from the bitcoin PoW. Members of the Tor Project team who designed Onion Services' PoW had been working on similar projects in the cryptocurrency space in the past.

There are algorithmic similarities to what people see in cryptocurrencies, but there are a few important differences:

  1. Our parameter choices are quite different and the goal is not to use PoW as a currency generator mechanism, but to ask clients to provide a fair work effort to match what they're asking servers to do. DoS is a dynamic problem where the attacker's capabilities constantly change, and hence we want our proof-of-work system to be dynamic and not stuck with a static difficulty setting. Hence, instead of forcing clients to go after 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.

  2. While PoW algorithms for cryptocurrencies are optimizable for special-purpose hardware such as ASICs, PoW for Onion Services was designed to not be optimizable that way, in order to disincentive attackers to build special hardware in order to attack Onion Services.

  3. PoW for Onion Services enforces a cooperative scenario. Our PoW mechanism does not work towards making users and attackers (and "mining pools") to always compete with each other for who's the first to solve a puzzle. In our PoW model, competition tends to increase the effort needed to access a service. The only way to keep the effort low is to "cooperate" in the sense of not requesting to the Onion Service more than what it's able to offer, to keep effort low (or absent) and consequently saving resources.

What about energy consumption? Is this PoW implementation eco friendly?

There are legitimate concerns that Proof of Work (PoW) is an energy intensive protocol and can have a negative impact on the environment.

The PoW protocol for Onion Services is written as a deterrent -- it only requires work when there is an active attacker, and then forces the attacker to do increasing amounts of work to exceed the amount of work that clients are willing to do in order to get access. That is the equilibrium point.

As with efforts to combat any DoS attack, the defense works by making attacks expensive only when they occur, while still allowing patient clients to connect, so that the incentive to attack an Onion Service goes away.

That's why we believe that the PoW protection for Onion Services has the potential to avoid energy waste caused by DoS attacks on the Tor network by making those attacks impractical - and ultimately preventing them - thus reducing energy consumption.

Without the PoW protection, attacks against an Onion Service means an energy waste everywhere in the Tor network: on the attacker side (by using many machines to mount the attack), on the Tor relays (by having to deal the additional load imposed by the attack), on the Onion Service (by being overloaded with requests) and also for other clients trying to access the service (by having to repeat their connection attempts).

With the PoW protection, the energy savings happens because of the attacks that did not happen, or stopped early, because the attacker realized they were too expensive to perform, and are not actually preventing access.

For more information:

Could we have a rough estimate on the energy spent during an attack, even if just speculative? Or get historical data of how much energy previous attacks have consumed?

We don't have this estimation. But to have a rough idea, during DoS attacks the number of requests a Tor relay needs to handle is in the order of billions, which means a lot more energy spent, especially because requests involves many expensive cryptographic operations.

Could you explain a bit more how PoW for Onion Services works?

Let's use an analogy with a "sold out music concert".

When a service is under attack, the queue (ticket line) overflows and it stops answering requests to users (selling new tickets). This is the goal of a DoS. The service is "sold out" of spots in the queue to service requests.

What the PoW defense allows you to do is "buy" a ticket on "stubhub" for the cost of computation, and thus get in to the concert without using the regular ticket line. The bidding process on "stubhub" (the work difficulty level advertised by the service) forces the adversary to waste far more resources to keep you out, by also doing enough work to keep the "stubhub" inventory empty to keep bidding users out. This makes the attack far more expensive for them to sustain. And thus they are deterred from mounting attacks that don't actually keep people out of the "concert".

"Buying" in this case would happen with some sort of "special cryptocurrency" that:

  1. Anyone can "mine" (generate), without the need for a dedicated hardware, although some low-end devices may need more time and so they can miss the current concert.

  2. Is "onetime use" only, i.e, neither legitimate users or attackers can stockpile to buy the whole venue. Hence, there's no "blockchain" or banks involved in this special currency system.

  3. Generating a single ticket won't consume much resources, but generating many does, no matter how powerful is the attacker's hardware.

  4. It's possible to put more or less "effort" into mining (using more or less resources, taking more or less time), so the generate currency has more or less "value". The more "value", the greater is the chance to get a ticket ("stubhub" actually sells tickets through auctions, and to the highest bidders).

Please note that the music concert is usually for free, except when the ticket line is under attack.

There's some differences because the queue constantly serviced, rather than having a fixed initial quantity of tickets, but these are in the margins in respect to understanding the overall concept.

It could be said that "concerts" happens regularly, like in a circus. So if you miss one spectacle you can get back to the ticket line for the next one (and at that point the attack might have gone and you might get a ticket for free after waiting a bit on the line).

Going further on the economic side of this analogy, this "special cryptocurrency" is important to avoid "concentration of access" by an attacker monopolizing all access to a service as well as denying access from others, and is intended to make sure everyone can go to the concert, as much as possible.

The important thing to convey is that deterrence is provided by bidding for a spot in the queue and making it expensive to fill the whole queue. This is far more expensive for the attacker, as compared to the cost to a client of buying a slightly more expensive ticket, in order to "jump the line".

This key idea is why this defense works as a deterrent, doesn't burn energy for no reason, and can still provide access under an active attack.

Adapted from discussion in this thread.

What performance improvements will the implementation of PoW bring to the Tor network, i.e. faster speeds, censorship resistance etc?

PoW does not bring a performance improvement per se, but it works the other way around: it avoid performance penalties and lower speeds imposed by Denial Of Service attacks. So it's a protection to avoid attackers wasting the available resources. In that specific way it can be thought as a performance and speed improvement.

Does this feature solve all Denial of Service (DoS) issues with Onion Services or with the Tor network?

It's expected that a whole class of DoS attacks against Onion Services will simply disappear.

It also means that Onion Services is one of a few communication protocols that have built-in protections against Denial of Services.

But this defense does not solve all DoS problems in the Tor Network.

We can imagine scenarios such of an Onion Service from a news agency that suddenly publishes a very popular news article, attracting more legitimate users than it used to. A huge flock of legitimate users, all willing to solve client puzzles, could deny the service functioning but without being considered as an "attack". For these cases:

  • Many users whose clients haven't solved the puzzle with enough effort will have their connection attempts simply to timeout, so they'll be unable to access the news article. For those, the service will be unreachable and they will probably give up.

  • The number of users trying to access the article will then reduce, which will make the Onion Service to reduce the expected effort, which will then allow some more users to connect, and so on.

  • The system is dynamic, preventing connection spikes to affect the service at the same time that it makes spikes to fade away by timing out connection attempts that does not have a higher-enough effort.

In this scenario, a high-traffic website such as a news outlet can plan in advance the expected throughput and adjust the PoW configuration accordingly. There are also other settings both in the Tor and the website software than can be tuned server-side to keep the load and that can be used altogether with PoW to mitigate cases where a huge number of users are willing to expend effort[, but that would ultimately boils down to the existing resources available in the Onion Service].

Generally speaking about the Tor network, there are still many DoS attacks possible out there. Some are being investigated, and some may already have mitigations. For an overview of the current state (as of July 2023), check this e-mail thread from June/July 2023 explaining the existing of DoS attacks against the Tor Network.

Is this feature equally effective against DoS and DDoS (Distributed DoS), where the attacker is coming from a fixed or limited set of IP addresses?

The PoW subsystem doesn't care where a particular request is coming from, and because of the anonymity provided by Tor we generally don't know where requests are coming from anyhow. We've had other DoS mitigations that try to prevent people from entering the network and creating too many connections from too few IPs. Those mitigations are independent and we expect them to complement each other.

Regarding the different levels of attacker capability, it might be useful to refer to the analysis in the proposal. We aren't trying to defend against arbitrarily large attackers, it's more like a low-impact mitigation for low-to-mid-effort attacks.

Well what about a botnet of compromised machines? That doesn't cost an attacker anything.

There are two responses to this:

  1. Compromised machines (that are "free" to such an attacker) used in this case have an opportunity cost to an attacker. They could be mining Monero with that CPU usage, instead. They are also sold for use in other ways in the criminal underground, which are more popular than Monero mining, because:

  2. High CPU usage from a compromised machine sets off alarm bells to people -- when your fans start blasting on a laptop non-stop, or your phone gets red-hot and your battery life plummets, you know something is wrong, and investigate, or reinstall. This is different for compromised machines that just blast network activity. Those tend not to get noticed unless the ISP yells at you, which can take much longer and allows much higher volumes of attack traffic before they care.

Answer originally provided in this thread.

What are the next steps for the Tor Project to improve performance?

The Tor Project is tirelessly working on improving the user experience and increasing adoption of our technologies globally to provide a safe and secure internet experience to as many people as possible.

In the near- to mid-term we are focused on network health, speed improvements, and the mobile experience among other milestones. We have rolled out Congestion Control and Conflux which aim at helping with network speeds. We continue to rewrite our core software in Rust, which will bring with it significant security improvements across the ecosystem, easier developer integration and faster feature iteration.

It's usability

When and how should a user enable PoW?

As of 16th August 2023, this feature is available and enabled for users as long as they're:

  1. Using the most up-to-date Tor software on their applications (tor 0.4.8.1-alpha or later).
  2. Their applications uses a GPL-licensed Tor binary, such as Tor Browser 13.0a1.

Currently, there's no way to configure the settings for the client puzzle, but the PoW implementation was designed in a way that should work without user interaction and to avoid trying to solve a challenge with an effort that's too high.

When the client first attempts to solve a client puzzle, it can estimate of the duration of the PoW. In the future, this estimation could be displayed in the application, such that the browser could display how long the PoW is expected to take on their device.

If the device is a mobile platform, and this time estimation is large, it could recommend that the user try from a desktop machine.

And it's worth note that, as of August 2023, the PoW defense is not available on either mobile or desktop applications based on Arti, whose implementation is still under development.

Can I use any device? What if my device is slow? (Minimum device requirements)

It may happen that users of low-end, slow devices be unable to connect to PoW-enabled Onion Services during Denial of Service (DoS) attacks, since these devices may be unable to provide solutions to the client puzzles with enough effort in order to be prioritized in the connection queue.

This is a drawback in the PoW protection, but we expect that most DoS attacks won't happen anymore for PoW-enabled Onion Services, or that won't last for long periods. So under normal conditions -- i.e, without DoS attacks happening -- slower devices will still be able to connect to PoW-enabled Onion Services without problems.

Speed mainly depends on the architecture of your device. If it's 64 bit-based (like x86_64 or aarch64/arm64), then the PoW hash implementation (hashx) will probably run at compiled speed, tending to be fast. Otherwise, the implementation will run as interpreted code, and tend to be around 10 to 40 times slower. So a puzzle that takes 0.5 seconds to be solved by a compiled implementation can take around 5 seconds or even more by an interpreted one.

In the worst case scenarios, when the effort is high, interpreted implementations might take so long (like minutes) that the connection attempt might timeout before solving the puzzle.

Detailed questions

What is the Proof of Work (PoW) protection?

This protection aims to thwart introduction flooding DoS attacks by introducing a dynamic Proof of Work (PoW) protocol that occurs over introduction circuits.

With the right parameters, this proof-of-work scheme acts as a gatekeeper to block amplification attacks by attackers while letting legitimate clients through.

This protection is written to thwart specific attackers. A simple PoW proposal cannot defend against all and every DoS attack on the Internet, but there are adversary models we can defend against.

We hope that this proposal can help us defend against the script-kiddie attacker and small botnets. To defend against a large botnet we would need more tools at our disposal.

We hope that this proposal will allow the motivated user to always connect where they want to connect to, and also give more chances to the other user groups to reach the destination.

This mechanism is not perfect and it does not cover all the use cases. Still, we think that by covering some use cases and giving reachability to the people who really need it, we will severely demotivate the attackers from continuing the DoS attacks and hence stop the DoS threat all together. Furthermore, by increasing the cost to launch a DoS attack, a big class of DoS attackers will disappear from the map, since the expected Return of Investment (ROI) will decrease.

Why is Proof of Work needed? (What inspired the development?)

So far our past attempts at limiting the impact of introduction flooding DoS attacks on onion services has been focused on horizontal scaling with Onionbalance, optimizing the CPU usage of Tor and applying rate limiting. While these measures move the goalpost forward, a core problem with onion service DoS is that building rendezvous circuits is a costly procedure both for the service and for the network. For more information on the limitations of rate-limiting when defending against Distributed Denial of Service (DDoS).

In order to have truly reachable global Onion Services, it's crucial to make it harder for attackers to overload the service with introduction requests. This protection achieves this by allowing Onion Services to specify an optional dynamic proof-of-work scheme that its clients need to participate in if they want to get served.

How does it work?

The Proof of Work (PoW) protection for Onion Services Introduction Points mechanism is detailed at Tor's Proof of Work for onion service specification. Here a brief summary is provided with details about how it works (as of August 2023), along with some interpretation and further references.

Overview

The system described in this proposal is not meant to be on all the time, and it can be entirely disabled for services that do not experience DoS attacks.

When the subsystem is enabled, suggested effort is continuously adjusted and the computational puzzle can be bypassed entirely when the effort reaches zero. In these cases, the proof-of-work subsystem can be dormant but still provide the necessary parameters for clients to voluntarily provide effort in order to get better placement in a priority queue.

The proof-of-work scheme specified in this proposal takes place during the introduction phase of the Onion Service protocol, and the mechanism involves the following major steps:

  1. The server encodes PoW parameters in the Onion Service descriptor.
  2. The client fetches descriptor and computes PoW.
  3. The client completes the PoW client puzzle and sends the solution in an introduction cell.
  4. The server verifies PoW and queues introduction based on PoW effort.
  5. Requests are continuously drained from the queue, highest effort first, subject to multiple constraints on speed.
                                          +----------------------------------+
                                          |          Onion Service           |
   +-------+ INTRO1  +-----------+ INTRO2 +--------+                         |
   |Client |-------->|Intro Point|------->|  PoW   |-----------+             |
   +-------+         +-----------+        |Verifier|           |             |
                                          +--------+           |             |
                                          |                    |             |
                                          |                    |             |
                                          |         +----------v---------+   |
                                          |         |Intro Priority Queue|   |
                                          +---------+--------------------+---+
                                                           |  |  |
                                                Rendezvous |  |  |
                                                  circuits |  |  |
                                                           v  v  v

Descriptor fields

This whole protocol starts with the service encoding the PoW parameters in the 'encrypted' (inner) part of the Onion Service v3 descriptor.

As a way to improve reachability and UX, the service tries to estimate the effort needed for clients to get access at any given time and places it in the descriptor, in the following format:

 "pow-params" SP type SP seed-b64 SP suggested-effort
              SP expiration-time NL

where:

  type: The type of PoW system used. We call the one specified here "v1".

  seed-b64: A random seed that should be used as the input to the PoW
            hash function. The PoW defense also changes the seed regularly
            as part of its _replay attack_ protection. A replay attack in
            this context is one where a client sends the same solution for
            multiple connection attempts in order to do effort only once,
            defeating the purpose of the PoW. The defense has an internal
            cache to keep track of already provided solutions. But in order
            to not let this cache grow to much, the seed needs to change
            regularly.

  suggested-effort: An effort value that clients should aim for
                    when contacting the service. Can be zero to
                    mean that PoW is available but not currently
                    suggested for a first connection attempt.

  expiration-time: A timestamp after which the above seed expires and
                   is no longer valid as the input for PoW. It's needed
                   so that our replay cache does not grow infinitely.

Descriptor parsing and puzzle solving

If a client receives a descriptor with "pow-params", it should assume that the service is prepared to receive PoW solutions as part of the introduction protocol.

The client parses the descriptor and extracts the PoW parameters. It makes sure that the has not expired and if it has, it needs to fetch a new descriptor.

The client should then extract the field to configure its PoW 'target', and the client SHOULD NOT accept 'target' values that will cause unacceptably long PoW computation.

The first implemented proof-of-work function is the Equi-X scheme by tevador, which uses HashX under the hood. It features lightning fast verification speed, and also aims to minimize the asymmetry between CPU and GPU. Furthermore, it's designed for this particular use-case and hence cryptocurrency miners are not incentivized to make optimized ASICs for it.

At the end of the calculation procedure, the client should have solution of the Equix-X. How quickly this happens depends solely on the target effort parameter.

The algorithm is suitable for single-threaded computation. Optionally, a client may attempt several solutions in parallel on separate CPU cores, and parallelization choices do not impact the network protocol's interoperability at all.

Connecting to a PoW-enabled Onion Service

Now that the client has an answer to the puzzle it's time to encode it into an INTRODUCE1 Tor cell.

When a service receives an INTRODUCE1 with the PoW extension, it should check its configuration on whether proof-of-work is enabled on the service. If it's not enabled, the extension SHOULD BE ignored. If enabled, even if the suggested effort is currently zero, the service follows the procedure detailed in this section.

If the service requires the PoW extension but received an INTRODUCE1 cell without any embedded proof-of-work, the service SHOULD consider this cell as a zero-effort introduction for the purposes of the priority queue.

The server then proceeds by verifying the solution and calculating the effort employed for each introduction request, and updating the priority queue accordingly.

We call the above steps the "top half" of introduction handling. If all the steps of the "top half" have passed, then the circuit is added to the introduction queue as detailed for the "bottom half". Most of the resource-intensive operations for establishing an Onion Service connection happens in the "bottom-half", so the "top-half" is mainly intended to prioritize requests based on client effort and without expending much resources from the server.

The service starts with a default suggested-effort value of 0, which keeps the PoW defenses dormant until we notice signs of overload. Then, introduction requests with higher priority are processed first, while low-priority ones are delayed and may even timeout, requiring that the client to try again.

If the rendezvous request times out, the client SHOULD fetch a new descriptor for the service to make sure that it's using the right suggested-effort for the PoW and the right PoW seed. If the fetched descriptor includes a new suggested effort or seed, it should first retry the request with these parameters.

Every time the client retries the connection, it will count these failures per-introduction-point. These counts of previous retries are combined with the service's suggested_effort when calculating the actual effort to spend on any individual request to a service that advertises PoW support, even when the currently advertised suggested_effort is zero.

Effort estimation

The overall process of determining effort can be thought of as a set of multiple coupled feedback loops. Clients perform their own effort atop a base effort suggested by the service. That suggestion incorporates the service's control adjustments atop a base effort calculated using a sum of currently-queued client effort.

Each feedback loop has an opportunity to cover different time scales. Clients can make adjustments at every single circuit creation request, whereas services are limited by the extra load that frequent updates would place on HSDir nodes.

In the combined client/service system these client-side increases are expected to provide the most effective quick response to an emerging DoS attack. After early clients increase the effort, later clients will benefit from the service detecting this increased queued effort and offering a larger suggested_effort.

Effort increases and decreases both have an intrinsic cost. Increasing effort will make the service more expensive to contact, and decreasing effort makes new requests likely to become backlogged behind older requests. The steady state condition is preferable to either of these side-effects, but ultimately it's expected that the control loop always oscillates to some degree.

Services keep an internal effort estimation which updates on a regular periodic timer in response to measurements made on the queueing behavior in the previous period, taking inspiration from TCP congestion control's Additive Increase / Multiplicative Decrease (AIMD) approach, which works towards achieving efficiency and fairness.

Practical questions

How to enable this as a user?

Users don't need to do anything to use this feature except for making sure they're using the most recent and GPL-licensed Tor binary.

How can I try this feature as a service operator, before using it in production?

Try the onion-pow-example project.

How to enable this as a service operator?

Check if your C Tor has the PoW defense

PoW is enabled by default on C Tor versions 0.4.8.1-alpha onwards (but can be disabled if configured to be compiled with --disable-module-pow). Basic PoW support can be checked by running this command:

tor --list-modules
relay: yes
dirauth: yes
dircache: yes
pow: yes

If you have pow: yes, then you have the PoW defense mechanism built into C Tor.

But due to license requirements, the PoW v1 client puzzle libraries (Equi-X and HashX by tevador, both under the LGPL-3.0) are enabled only if C Tor is compiled with --enable-gpl. This can be confirmed by running the following command:

tor --version
Tor version 0.4.8.3-rc.
This build of Tor is covered by the GNU General Public License (https://www.gnu.org/licenses/gpl-3.0.en.html)
Tor is running on Linux with Libevent 2.1.12-stable, OpenSSL 3.0.9, Zlib 1.2.13, Liblzma 5.4.1, Libzstd N/A and Glibc 2.36 as libc.
Tor compiled with GCC version 12.2.0

If your installed C Tor does not have PoW enabled or is not built with GNU GPL support, then you'll have to look for other packages or compile it yourself.

Compiling C Tor with the PoW defense

The following examples assumes a Debian system, can be easily adapted to other systems as is only a reference on how to build C Tor with a functional PoW implementation.

  1. Download C Tor and make sure to check the signature.

  2. Install the needed dependencies:

sudo apt-get install -y \
    bash                \
    automake            \
    build-essential     \
    ca-certificates     \
    git                 \
    libevent-dev        \
    liblzma-dev         \
    libscrypt-dev       \
    libseccomp-dev      \
    libssl-dev          \
    pkg-config          \
    python3             \
    python3-qrcode      \
    python3-requests    \
    python3-stem        \
    tmux                \
    zlib1g-dev          \

  1. Unpack the C Tor source code and go to it's folder.

  2. Configure C Tor with GNU GPL support, which allows the inclusion of GPL-licensed code, building a version of tor and libtor covered by the GPL:

./configure --enable-gpl
  1. Compile:
make
make test

At the end of the process, you'll have a working Tor binary on ./src/app/tor, and from there you can run it, install somewhere on your system or build a package.

Configuring an Onion Service with the PoW protection

PoW is enabled in a per-onion service basis. So, for each of your Onion Services, you have the following options available -- from tor(1) manpage:

HiddenServicePoWDefensesEnabled:

Enable proof-of-work based service DoS mitigation. If set to 1 (enabled),
tor will include parameters for an optional client puzzle in the encrypted
portion of this hidden service's descriptor. Incoming rendezvous requests
will be prioritized based on the amount of effort a client chooses to make
when computing a solution to the puzzle. The service will periodically update
a suggested amount of effort, based on attack load, and disable the puzzle
entirely when the service is not overloaded.
(Default: 0)

HiddenServicePoWQueueRate:

The sustained rate of rendezvous requests to dispatch per second from
the priority queue. Has no effect when proof-of-work is disabled.
If this is set to 0 there's no explicit limit and we will process
requests as quickly as possible.
(Default: 250)

HiddenServicePoWQueueBurst:

The maximum burst size for rendezvous requests handled from the
priority queue at once. (Default: 2500)

The following global option is applicable to both onion services and their clients:

CompiledProofOfWorkHash: When proof-of-work DoS mitigation is active, both the services themselves and the clients which connect will use a dynamically generated hash function as part of the puzzle computation.

If this option is set to 1, puzzles will only be solved and verified using
the compiled implementation (about 20x faster) and we choose to fail rather
than using a slower fallback. If it's 0, the compiler will never be used.
By default, the compiler is always tried if possible but the interpreter is
available as a fallback. (Default: auto)

You'll hardly need to touch the CompiledProofOfWorkHash parameters, except for testing purposes.

Example configuration

The simplest case would be to just enable the feature and use the default values for the queue rate and the queue burst. For the Onion Service "myservice", use the following torrc configuration (and adapt to your HiddenServiceDir conventions and HiddenServicePort needs):

HiddenServiceDir hidden/myservice
HiddenServicePort 80 127.0.0.1:8080
HiddenServicePoWDefensesEnabled 1

You can tune the setup by specifying the queue and burst rates for the introduction queue, such as:

HiddenServiceDir hidden/myservice
HiddenServicePort 80 127.0.0.1:8080
HiddenServicePoWDefensesEnabled 1
HiddenServicePoWQueueRate 200
HiddenServicePoWQueueBurst 1000

The lower the queue and burst rates, the higher the puzzle effort tends to be for users. In other words, the Onion Service will later adjust the suggested puzzle effort on it's published descriptor according to the recent queue and burst rates, which are constrained by these configuration parameters. You might want to use lower or higher values depending on the overall capacity of your system to handle requests and with the current load of your system.

How to monitor and tune it?

The MetricsPort is now exporting more Onion Service metrics that can be used to monitor overall service health, including the following PoW data:

  • tor_hs_rdv_pow_pqueue_count (gauge): Number of requests waiting in the proof of work priority queue.
  • tor_hs_pow_suggested_effort (gauge): Suggested effort for requests with a proof of work client puzzle.

These gauges can be combined with other Onion Service, general Tor and system metrics (such as CPU, memory and bandwidth) to monitor load.

Onionprobe metrics for the pow-params field are also in the plans, which can used to monitor the service from the outside: https://gitlab.torproject.org/tpo/onion-services/onionprobe/-/issues/78

With these metrics, it's possible to calibrate your setup (such as tuning PoW configuration parameters) to better respond to the current service usage as well as to avoid successful DoS attacks.

Technical questions

What if my client does not support it?

A user running an outdated client software that does not have the PoW functionality can still access Onion Services that have the PoW puzzle enabled. What can happen is, if the service is under load, the user attempt will get lower priority since its connection requests won't contain a puzzle solution.

Can attackers build special hardware to bypass PoW?

They can, in theory, but the expected ROI (Return Of Investment) for this kind of hardware tends to be extremely low, since a reimplementation in hardware (ASIC) would need to implement much of a CPU to compute these functions efficiently due to the specific choices made for the algorithm, and the cost of building such special hardware is very high.

See this section of the specification for details.

Does mobile clients support it?

Mobile clients should support it as long as they're built with a recent C Tor version that was compiled with full PoW support.

What would really depends is whether the PoW hash implementation is compiled or interpreted, as well as how fast is a given device (see question below).

Do you have some numbers? What if I'm using a slow device, such as an old

mobile phone?

The client effort limit is currently hardcoded but there's a bug open to have it dynamically set, and this hardcoded maximum effort of 10000 should be about 1 minute of CPU time on a desktop computer (it's small because we have no cancellation mechanism for queued solution yet).

Average time per-solve for the puzzle is around:

  • 5 milliseconds for a "fast computer".
  • 10ms for an "average computer".
  • 30ms for slower devices.

These are times per-solve, but the solutions-per-seed is about 2 on average, and effort sets the number of solutions rather than the number of solver runs necessary. The effort of 10000 is about 1 minute on a desktop PC.

The ratios between devices are kinda roughly about right, but the main point to take home is that the difference between the fastest and slowest CPU is not that extreme so long as both are either x86_64 or aarch64. We've seen 250 solutions per sec in a fast desktop CPU, 180 on in an old dev machine, and 87 on a phone from 2018.

That would be 40 seconds on the fast CPU, 55 secs on the middle machine, or 115 seconds on the phone, average time for effort 10000.

Times will be much higher on architectures that aren't x86_64 or aarch64, running on the interpreted hashx. (Those same three computers, using the interpreted hashx, would take 13.2 minutes, 24.8 minutes, and 25.6 minutes for effort 10000).

You can verify the performance of a particular device using the Equi-X benchmarks. We would suggest the benchmark suite included in Arti to compare between implementations, but the original C benchmark in equix is a bit more convenient for getting raw number of solutions per second.

There are currently no special choices made based on CPU speed or platform, the client will always choose efforts in the same way. Speed will vary by 1-10x based on actual CPU speed if the platform is some kind of x86_64 or aarch64 where the hashx compiler is supported, but it will vary more like 10x-40x between those compiled architectures and others. This is all to say that there are a few reasons why things may appear to be fast or slow, and we don't currently have an easy way to display this to the user. Waiting on a proof-of-work solution, to the user, looks the same as waiting on a slow network connection.

How/whether clients can specify effort?

Not implemented yet, but we'd like to at the very least have torrc config options that affect client-side effort choice.

Does the algorithm take into account the limits of my hardware when determining the client effort?

Not yet, but it may in the future. Issue #40787 would cover some system that lets us specify effort based on expected time instead of some numeric value, and that could be used to balance the time we spend solving with the time we spend waiting in queue.

Does this feature need to stay enabled all the time?

The PoW protection does not need on all the time, and it can be entirely disabled for services that do not experience DoS attacks.

But since the protection is dynamically tuned, it won't hurt configuring it for public facing onionsites. If the service is not under high load, the suggested for will be zero or a very small value, and the service will be ready for eventual attacks.

Private .onion services such as those used to share files with OnionShare between friends will hardly be subject of a DoS attack, and won't need the protection.

Does PoW computations show up in server logs in a way that would let an adversary infer someone was trying to access an onion router?

The proof of work subsystem is part of the tor daemon, and like the rest of tor it does not log activity unless debugging options are enabled.

An adversary with access to observe your client machine during use could notice that tor has a different CPU usage pattern, perhaps, but this could already imply that the adversary already has a compromising level of control.

Say an attacker deliberately uses older clients which do not support puzzles. Isn't it still possible to cause a DoS with enough, albeit queued, intro requests? Is there a way to reject clients which do not provide puzzle solutions when puzzles are enabled?

This question is about what happens if ALL clients provide no puzzle and thus fill in the queue.

What will happen is that the service will raise the needed effort but that won't change anything because all intro requests in the queue have no puzzle. Then, the service will just process these based on its rate/burst for handling that queue avoiding it to be overloaded.

The service automatically drops requests off the bottom of the queue if it's growing too large. It's inexpensive to put these zero-effort requests into the queue and then forget about them.

See HiddenServicePoWQueueRate and HiddenServicePoWQueueBurst configuration settings.

It has also been discussed whether there should be an option to discard clients that does not provide a puzzle, but there were concerns that such optimization would create more problems than it solves, since it opens a lot of questions around low-load situations and how this early dismissal would be enabled or disabled. Simpler and more predictable to rely on the existing priority queue mechanism.

Does the new PoW defense supersedes the existing Anti-DoS parameters at torrc?

No. The PoW defenses is a compliment to the existing protections:

  • The PoW protection acts during the introduction phase of connection to an Onion Service, making sure that clients offering valid puzzle solutions with highest effort gets a connection first.

  • There are still other parameters that can be tuned for rate limiting the number of introduction request coming to the Onion Service (HiddenServiceEnableIntroDoSDefense, HiddenServiceEnableIntroDoSBurstPerSec and HiddenServiceEnableIntroDoSRatePerSec). Effectively, Intropoint protections prevents onion service DoS from becoming a DoS for the entire machine and its guard.

  • But after the connection is established, it's still possible that an Onion Service suffers from a high load from clients that were able to establish a connection. For these cases, the HiddenServiceMaxStreams and HiddenServiceMaxStreamsCloseCircuit configuration settings may help.

  • The application running at the backend of the Onion Service (like a web server, proxy or other TCP connector) can also have it's own protections against DoS, such as caching and rate limiting, that can be coupled with the HiddenServiceExportCircuitID torrc option.

Please check the Onion service DoS guidelines for the available countermeasures.

Is the PoW defense compatible with Onionbalance?

As of August 2023, both approaches won't work together as expected. You can setup PoW in your Onion Service backends but it's parameters won't be propagated to the public frontend descriptor, so clients won't have a way to know whether PoW is enabled (or which PoW parameters are actually being used by each backend).

The HiddenServicePoWDefensesEnabled, HiddenServicePoWQueueRate and HiddenServicePoWQueueBurst configuration settings can still be set and will work on backends, but they'll act as simple queue limits without request prioritization, given that clients won't pick the suggested effort and random seed, since they won't be available in the frontend descriptor. While this tends to protect the backends against a DoS attack -- they'll simply discard excessive introduction requests from the queue --, it can reduce the probability of legitimate clients to access the service -- as requests won't contain a puzzle solution, providing no way for the backends to do any prioritization.

Additional work on Onionbalance still need to be done to support the pow-params descriptor field. Until that does not happen, you'll need to choose between PoW or Onionbalance to regulate load on your service, whichever suits you best.

It's worth note that if you choose PoW, you might still be able to get some load balancing by running multiple instances of the same Onion Service in different machines (and starting on different times so descriptors are published on different times as well).

The important thing is to make sure each instance publishes the descriptor at a different time, otherwise the setup won't be distributing load but only acting as a fallback system. That might be a bit tricky to do (with Onionbalance, one don't need to think about that), but it's the current way to have both load balance and PoW protection.

So, for now, operators can choose between Onionbalance with queue handling but without PoW and simple load balancing with PoW.

Check this issue for details about how PoW can be supported by Onionbalance: tpo/onion-services/onionbalance#13.

Is this feature already implemented on Arti? If not, what's the roadmap?

As of August 2023, we have a pretty solid first pass at implementing HashX and Equi-X in Rust. The hashx and equix crates are now in main, along with benchmarks and fuzzers. They have APIs that seem fairly stable and serve the needs of Arti as well as the benchmarking, testing, and fuzzing infrastructure so far. The hash function compiler works on x86_64 and aarch64, and memory footprint for equix is about the same as the C implementation.

Correctness is good so far, the fuzzers and unit tests are verifying that the Rust and C implementations produce the same output.

Speed is usable but it could be better. The solver isn't far behind the C implementation (about 10%) but the verifier is more like 40% slower than the C implementation in the worst cases. This will impact the CPU efficiency of services that are under attack. A full set of comparison benchmarks between the C and Rust implementations can now be run on any machine easily with cargo bench from the equix/bench or hashx/bench crates.

The next steps for bringing this into Arti include:

  • Now that we have the cross-implementation fuzzer, we could confidently try to simplify or reduce the program generator further.

    • This has overlapping goals of performance and code clarity.

  • Further develop the tor-hspow API:

    • A strategy for threading and event loop integration seems like a fairly well-specified next step.
    • Less well specified would be a higher level API for the crate, which could provide a plausibly future-proofed way to represent version-independent PoW data.
    • Add benchmarking and fuzzing at this layer too.
    • Work out how we interact with other hs replay caches.

See the Rust implementation of Equi-X and dependencies ticket for details.

Are there licensing considerations with the PoW mechanism?

Yes.

The PoW v1 client puzzle libraries are Equi-X and HashX by tevador, both of which are under the GNU Lesser General Public License v3.0, whereas C Tor is distributed under the 3-clause BSD license.

So right now, the only way to run the PoW mechanism is to have a GNU GPL-compliant C Tor binary. This can be done by compiling tor with --enable-gpl.

Please check the licensing compliance of your software when bundling a C Tor with PoW on your application.

How/when the server calculates the suggested client effort E, published in the HsDir?

For the suggested effort that clients should use (published in HsDir), this algorithm is described in section 3.4.3 of Proposal 327 and also at Overall strategy for effort determination of the current specification. It happens on a timer, currently fixed at every 5 minutes. Timed updates rather than continuous updates help the service regulate how quickly it needs to publish changes to the HsDir. The summary is that it's trying to estimate how much effort would be needed in order to successfully make it through the priority queue. There's a bit more to it, and Proposal 327 as well as the current specification does a pretty complete job of explaining the rules.

For the proven effort for an incoming request, i.e, about how we figure out what effort was used for a particular request, the effort is included in the solution, and we cryptographically verify it as part of verifying the solution. (A combination of the blake2b effort check plus the effort's inclusion in the Equi-X challenge string).

How this "bid" logic works?

The clients "bid" by choosing an effort, and lock in that bid by running the solver and sending results along with an introduction request. Those requests are processed in order by effort, it's a straightforward priority queue. This is described in 3.4.2 of Proposal 327, "The Introduction Queue [INTRO_QUEUE]" or at the The introduction queue section of the current specification

Additional discussion can be found on Proposal 327's Sections 3.4.3 and 3.4.1, corresponding to sections Common protocol and Service verifies PoW and handles the introduction of the current specification.

How the PoW User Interface (UI) for TBB will look like?

This is what the spec says about effort estimation:

3.2. Client fetches descriptor and computes PoW [CLIENT_POW]

[...]

The client should then extract the field to configure its PoW 'target' (see [REF_TARGET]). The client SHOULD NOT accept 'target' values that will cause unacceptably long PoW computation.

Currently this happens under the hood, and without any user interaction, but the spec also gives a hint in how an application could know that PoW is enabled for a service and how an effort choice could be communicated to the user:

7.1. UX

This proposal has user facing UX consequences.

When the client first attempts a pow, it can note how long iterations of the hash function take, and then use this to determine an estimation of the duration of the PoW. This estimation could be communicated via the control port or other mechanism, such that the browser could display how long the PoW is expected to take on their device. If the device is a mobile platform, and this time estimation is large, it could recommend that the user try from a desktop machine.

Currently, Tor Browser alpha (as of August 2023) does not implement any UX mechanism to display to the user whether client puzzles are being solved or how long they're going to take.

One simple behavior that could be implemented is indicating in a connection error message whether PoW parameters are found in the Onion Service descriptor field, and with some hint whether the service is under stress according to the suggested effort value.

How can I integrate PoW data into my app UI?

The control port will give you per-circuit information on the PoW effort used, if any. This is used in the onion-pow-example via stem. Look for the HS_POW value coming through on CIRC events: (The same interface works for client and service side).

The [following example code][] shows how that can be done: service.py.

This will be a string like "v1,12345" where "v1" is the puzzle version and "12345" is the effort. These details may not be useful to users except as a debugging footnote, but you can use the presence of HS_POW to indicate that proof-of-work is being used.

How long was the developed phase (quick historical background)?

It took around three years, according to this timeline:

Who was involved in the development (main references and credits)?

See the "Acknowledgements" section.

Can PoW be implemented for other parts of the Tor network, such as for regular relay connections?

There were a number of discussions about how to increase DoS protection at the Tor network. Using Proof Of Work on other parts of the network is one thing that could be considered in the future.

Another interesting proposal (but still for Onion Services) is the Res tokens: Anonymous Credentials for Onion Service DoS Resilience.

Does TLS already have protections against such attacks? If not, why?

There are existing protections for services using HTTPS, such as Content Delivery Networks (CDNs) and rate limiting. But they're basically about dynamically limiting bandwidth or throwing hardware at the problem.

Also, some TLS DoS protections are services that requires keys to be managed by a third party, which implies in delegating trust to another service operator.

There are some proposals about bringing PoW/client puzzles directly to TLS, but they're rough drafts which does not seem to be actively developed (as of August 2023):

Maybe Tor's Onion Services PoW can be an inspiring reference for client puzzles in other protocols such as TLS!

Notes

  1. For more information about how this document originated, check issues tpo/community/team#93 and tpo/web/community#312. ↩