A more effective and efficient PoW. An optional visual challenge to reduce the maximum wait time.

[Igguprofen]

TL;DR: A better PoW solver implementation is needed in my opinion, and it is time to stop assuming that "computing power equals genuine users" ("Anubis uses proof of work in order to validate that clients are genuine"), the current implementation isn't imposing a real computational burden on "bad actors" (or maybe scrappers to be more accurate). Real users with computers and phones represent a far more complex combination than just SHA256 operations. Memory, bandwidth (upload), and the user themselves (psycho-visual, cognitive), combined. For some websites (StartPage) Anubis is already a DoS problem.

First, these are the aspects I agree with or like about the project Anubis (and other similar):

1. It reduces the current scrapper problem that is killing websites.
2. It is decentralized and open source.
3. It does not significantly degrade site usability, for example by allowing the PoW challenge to be solved in the background to maintain the QoL (other PoW implementations are incredibly annoying because they force you to keep the tab active).

---

Now the problems:

1. The current PoW challenge is a "non-human" or "bot-friendly" problem, because it is simple math and purely limited by the user's computational power. This inherently puts real users at a disadvantage, especially at higher difficulties (eg. 6). It may have been usable as anti-bot method in 1998, but not today, after GPGPU and Bitcoin universalized their use as PoW solvers, that kind of problem isn't useful, not even as anti-DDoS (I'm aware that it isn't the goal of this project).

2. More problematic is the current implementation of the PoW solver. The user should always have an implementation of the PoW solver as efficient as possible, or close to it. If bots have an considerable advantage because they need 100 to 10,000 times fewer resources to be validated, then the PoW is biased in favor of bots. It's possible to make a PoW solver 50-100 times faster on an old 4-core CPU, but someone with a real interest in mass scraping can implement a solver that is 10,000 times faster than Anubis's current one, and that is before considering GPUs. I only needed 1-2 hours to create a GM script + Python (+ C code) to reduce the wait time from 1-5 minutes to 1-5 seconds (for startpage).

3. If the user often has to wait 30 to 300 seconds, and Anubis does not leverage the advantage that any human has (psycho-visual) to reduce that time, then Anubis does not solve the bot problem, it simply becomes another DoS tool, because it can be manipulated by a third party to cause harm.

---

To be more precise (this applies to any PoW using a similar system, not only Anubis):

1. It uses "string + nonce" instead of "nonce + string." A bot will compute " hash(digest_hash(string), nonce)" instead of repeating two-thirds of the operations for each nonce. That is the most obvious optimization besides not using JS/the browser.

2. It uses a loop that calls the SHA-256 function too many times. Currently, the PoW solver spends 90-95% of its time initiating and finalizing these calls. Using Firefox with longer hashes (e.g., a 1MB sparse matrix with nonce as prefix) is at least 10 times faster (+1 MH/s on an old CPU), reducing the calls from many million to ~10k is enough to reduce the overhead to ~50% iirc.

3. It does not use WASM (maybe not the best solution) or make a better use of the browser's native SHA-256 implementation (the sparse matrix example).

4. It does not use RAM or bandwidth (upload). The "nonce problem" should be considered harmful and be deprecated (I just wanted to say it). Consider alternative asymmetric problems usable as PoW (including image encoding/decoding, compressing) but without overloading the server.

5. It does not use the "human user" to reduce wait time for higher difficulties. Currently, StartPage gives me a difficulty 6 problem, and without the "proof-of-concept" I made, it is unusable. Increasing difficulty with the current code is trivial but it always detrimental.

Note: Keeping the current PoW (but adjusted per (1) ) and maybe using (2) to increase difficulty beyond 3 - 4 (the idea being that the server should not have to exert extra effort just because someone sends string + fake_nonce). However, at some point, the user should have the alternative to reduce wait time, even if that goes against the "solved in the background" for those cases (not for the easier challenges).