Proof-of-Work CAPTCHA: Controlling Algorithm Variance

A Proof-of-Work CAPTCHA (PoW CAPTCHA) is a bot-prevention tool that asks the user’s device to solve a small computational puzzle in the background. Instead of making people click on traffic lights or decipher distorted text, the browser does the work automatically.

The result is often a smoother experience: no visual challenge, no unnecessary tracking, and usually only a short wait of a few seconds. For bots, however, the cost adds up. Every request requires device time and energy, which makes large-scale abuse more expensive.

But standard proof-of-work algorithms have a problem: they don’t measure progress. Solving the puzzle is like playing a lottery over and over until you win. Losing many times does not make the next attempt more likely to succeed.

That randomness creates a critical challenge for CAPTCHAs. If proof-of-work isn’t used properly, the CAPTCHA challenge turns into a lottery. One user might win on the first attempt, completing it in one second, while another legitimate user may need many attempts, waiting ten seconds. For websites and web applications that need to stop bots without frustrating real people, that kind of variance is unacceptable.

That is why we built Friendly Captcha, a user-friendly, open source captcha based on proof of work. Friendly Captcha solves the variance issue with a more sophisticated proof-of-work system: instead of relying on one hard, lottery-style puzzle, it splits the work into multiple smaller cryptographic puzzles. This makes solve times more predictable, smooths out unlucky outliers, and allows the widget to show progress instead of leaving users waiting blindly.

Friendly Captcha’s proof-of-work challenge doesn’t just make attacks expensive. It also makes solve times predictable and fair. We believe a good CAPTCHA should require roughly the same amount of computation from comparable devices, without ever blocking real humans.

Our proof-of-work setup

The idea behind PoW is that the puzzle (also called a challenge) must be cheap to verify, but expensive to compute.

A PoW that would be “hash this string 1 million times” would be expensive to compute, but just as expensive to verify. Instead most PoW algorithms make the user search for a needle in a haystack: we generate a puzzle string p, and ask the user to find a nonce q such that the hash of p and q concatenated meets some rare criteria. If we use a good hash function, any input string is just as likely to meet this criteria as another.

Remember that any bytes or string can be interpreted as a number. We take the first 4 bytes of the hash and interpret them as a 32 bit integer. If that number is below some threshold T (which you could call the inverse of the difficulty) then it is a valid solution. Any hash input is equally likely to meet that criteria, so to find the solution the user would just try different values for the nonce q until they find a winning solution. Not so different from playing the lottery a lot!

Verification in pseudocode

puzzleString = "my-puzzle-string"
threshold = 1000 // The lower the more difficult the puzzle is
nonce = "3456356782345" // This is the value the solver changes to try and find a valid solution

hash_result = hash(puzzleString + nonce)
value = toUint32(hash_result[0:4])

if value < threshold {
    print "Valid!"
} else {
    print "Invalid solution :("
}

How many tries does it take?

If your chances of winning the lotery are one in a million, after a million tries your odds of winning at least once is around 63.2% (1 - (1/one_million)^one_million or 1 - binom.pmf(1, one_million, 1/one_million)). Here’s a density plot:

Most people take around a million attempts, but some users will be really unlucky and instead need 3 million attemps (~5% in fact) or even more! In other words: there is a large amount of variance in how many attempts are needed. This is problematic for a PoW CAPTCHA: the user will give up on waiting if it takes 5 times longer than expected. They don’t care what the mathematical average is, they just want to sign up to your website.

For a decent user experience the user also deserves some sort of progress indicator. Just showing “solving the captcha” for 10 seconds without any indication of will make the user give up and think the website is broken. If instead there is a progress bar that increases over time it’s much more tolerable.

The issue is that there is no progress, nobody knows when they will find the nonce that creates a hash that satisfies the criteria. Fortunately, there is a straightforward solution to both the progress and variance issue: we ask users to find more than one nonce.

Multiple, easier problems

Instead of making the user find the 1 in a million nonce, we can make them find 10 nonces to a 1 in 100k problem. The expected number of attempts is still the same, but now we can show a progress bar to the user!

Not only do we solve the progress problem, we also decrease the variance of how many attempts were required in total. As we increase the number of nonces we ask, the variance decreases. Let’s plot that:

import matplotlib.pyplot as plt
import numpy as np
from scipy.stats import binom

one_million = 1000000

n_attempts = np.arange(0, 5*one_million, 1000)

fraction_still_solving_1m = [binom.cdf(1, n, 1/one_million) for n in n_attempts]
fraction_still_solving_500k = [binom.cdf(2, n, 2/one_million) for n in n_attempts]
fraction_still_solving_200k = [binom.cdf(5, n, 5/one_million) for n in n_attempts]
fraction_still_solving_100k = [binom.cdf(10, n, 10/one_million) for n in n_attempts]
fraction_still_solving_50k = [binom.cdf(20, n, 20/one_million) for n in n_attempts]

plt.figure(figsize=(12, 6))
plt.plot(n_attempts, fraction_still_solving_1m, label="1 lottery win, 1/1M")
plt.plot(n_attempts, fraction_still_solving_500k, label="2 lottery wins, 1/500K")
plt.plot(n_attempts, fraction_still_solving_200k, label="5 lottery wins, 1/200K")
plt.plot(n_attempts, fraction_still_solving_100k, label="10 lottery wins, 1/100K")
plt.plot(n_attempts, fraction_still_solving_50k, label="20 lottery wins, 1/50K")
plt.legend()
plt.ylabel("Fraction who aren't done yet")
plt.xlabel("Amount of attempts")
plt.show()

Looking at this plot we can see that if we have people play a single lottery around 1 in 10 people will take more than 4 times longer than average! That’s unacceptable for a CAPTCHA, but as we increase the amount of wins required for a simpler lottery we decrease the variance considerably. In table form, how many people would not be done yet after N attempts:

We can also plot the probability mass function (below) which shows the variance clearly as well, the expected number of attempts is about the same, but the variance is much lower.

The downsides of requiring more solutions

There are some downsides to requiring more solutions, the first is the need to submit more solutions requiring a bit more bandwidth. In Friendly Captcha every solution is an 8 byte value transmitted as base64, so going from 10 to 20 solutions would take around 106 extra characters (10*8*(4/3)).

Secondly there are simply more solutions to verify, but given that verification is cheap this doesn’t matter.

Conclusion

Proof of work usually doesn’t have any notion of progress. Any attempt is just as likely as the next to find the solution. By requiring multiple proof of work solutions we can decrease variance, as well as provide a notion of progress, both of these features are requirements for a CAPTCHA based on proof of work.

Want to see the proof of work CAPTCHA in action? Try the demo here. The open source CAPTCHA library and the widget code is found here.

FAQ