Why memory-hard proof-of-work hashes are not a popular choice for CAPTCHA

In a recently celebrated 1-year long feat of adding WebAssembly to Anubis v1.28.0, where Argon2id hash capability was added, there was only one “uncomfortable” issue - validation concurrency limit of 4. Commit 65fc2ac13 defines var verificationSlots = make(chan struct{}, 4) (a ’lazy’ semaphore in Go). What it means in practice that max RPS of your server becomes 4 at the time of the imaginative peak load - not something you really want to have in production. Why such a strange limit in the first place? (and why it is not configurable)

Memory-hard vs Compute-hard PoW hashes

How proof-of-work hashes work in general

The logic is quite simple on paper: the server sends a random challenge and the client must find a nonce such that Hash(challenge + nonce) has at least d leading zero bits.

This is the same idea as signing blocks in Bitcoin. Each try succeeds with probability 2^-d, so the expected cost is 2^d tries, and each extra (empty) bit doubles the work. The choice of Hash decides what a single attempt “costs” (in resources).

Compute-hard hash

blake2b, used in Private Captcha by default till recently, is a pure CPU arithmetic - it works relatively fast and uses a small fixed memory (size depends on what kind of Blake hash is used - e.g. 128 or 256 bytes). Potentially an ASIC farm can make the computation take an order of magnitude less resources than a browser.

Memory-hard hash

Argon2id, on the other hand, requires allocating a (more substantial) band of memory first (think 16-64 MiB vs < 1KiB for blake2b). Its main parameters are m (memory allocation in KiB), t (number of memory passes), and p (parallelism). Each attempt must fill and repeatedly access its own buffer, and later accesses depend on earlier data, so you can’t cheaply skip or recompute parts of it. A (potential) GPU/ASIC attacker will run out of memory before it runs out of cores.

The unit economy of PoW CAPTCHA

The basic premise of proof-of-work CAPTCHAs is that server-side verification must be disproportionally cheaper than finding the nonce in the first place by a client. And the harder the difficulty parameter, the more disproportionate that becomes. Even though Anubis has a few real-life limitations, it too is built on such a premise.

For compute-hard hashes, this premise holds: server-side validation is easy on resources required for the validation itself. For example, on a decent server, load tests for Private Captcha server sustain hundreds of thousands of parallel blake2b verification requests (after adjusting the ulimit and sysctl settings). For memory-hard hashes, however, the story is very different.

On the server-side, each argon2id hash must allocate m bytes (m is one of the parameters of Argon2id). Anubis is currently using Rust-default Argon2id parameters m = 19MiB, p = 1 (parallelism) and t = 2 (2 passes). With a very generous paper math, even a modestly beefy server with 32GB of RAM can fit max ~1500 concurrent verification requests, which is not that much for a popular service. And for enthusiasts, who likely have much smaller servers (e.g. 1-4GB RAM) that means max 50-200 parallel verification requests. In reality, of course, not all RAM will be available for allocating of your Argon2id buffers. In case of Anubis it is even slightly worse as it uses WebAssembly for verification on the server-side too, which allocates an additional memory just for its existence.

With this in mind, you can see that some limit has to be in place - just having IO-bounded compute (like in blake2b case) is simply not feasible. Having said that, it is still not clear to me why Anubis devs decided that exactly 4 parallel verification requests “will be enough for everybody” (and why it’s not a configuration value, like everything else in Anubis). Private Captcha also has such a limit (PC_ARGON2_MEMORY_BUDGET_MIB env variable), but it is configurable as max memory in MiB that can be allocated for Argon2id verification, rather than requests count. However, in our SaaS version this limit is way higher in total due to the horizontal scaling.

Conclusion

So as sad as it may sound, the memory-hard challenges are less popular due to the server-side validation constraints and not the client-side issues. Using them for self-hosted solutions like Anubis means your (single) server’s resources can be easier exhausted, than if you used a compute-hard one.