Chris Hallberg

Proof of Work

2026-05-08

Have you seen these?

What are they?

These are CAPTCHAs: widgets that try to stop robots from visiting a website or submitting a form. Without these protections, robots will flood every comments section with ads and use contact forms to send thousands of emails. You might recognize CAPTCHAs from making you type a warped word or click on all the pictures of buses.

Since their introduction in 1997, they have relied on challenging the visitor to do a task that a robot could not. Thirty years later, this approach has two problems:

1. Computers these days are approximately 100 times more powerful than they were in 1997. This has made many of the challenges designed for CAPTCHAs trivial for computers to solve.
2. As the CAPTCHA challenges have been made harder, visitors have gone from annoyed by CAPTCHAs to frustrated by CAPTCHAs to unable to complete CAPTCHAs.

These new CAPTCHAs take a new approach to this problem: make overwhelming the website expensive. Instead of presenting a challenge that meets some definition of "hard", they present a challenge that is guaranteed to take a lot of tedious work. These new CAPTCHAs make every visitor do math homework and show their work.

Sending thousands of emails, adding hundreds of comments, and stealing every website for the Job-Stealing Machine becomes a lot less feasible if it takes a long time and makes the computer running the robot draw more power by doing millions of needless calculations. Compared to a robot trying to do millions of interactions per second, a human visitor is doing little extra work and will not suffer from these costs.

Proof of Work

How do we make visitors do a lot of work, and prove it, without melting a website's server by doing the same work. By asking a clever math question. Which of these questions is easier to answer?

1. What number can you multiply by 279,439 that would result in a number that has three consecutive zeroes?
2. Does the number 100,039,162 have three consecutive zeroes?

There is no easy way to answer the first question. You would need to check many numbers, multiplying each by a six-digit number, and checking the product to see if it contains three zeroes in-a-row. This is the challenge the CAPTCHA makes the visitor do. When the visitor then sends their answer, checking if the answer is correct is as easy as doing a single multiplication.

279,439 × 358 = 100,039,162

Much more work for the visitor than the server.

What is "difficulty"?

In this case, we are looking for three consecutive zeroes. This takes an expected number of guesses, in average in the low hundreds. "Difficulty" is our way of adjusting how many zeroes we demand from an answer. Developers can increase the difficulty of the challenge when a website is experiencing unusually high traffic or if a visitor is acting suspiciously. When we need more zeroes, the problem takes longer and becomes more expensive to solve.

Below you can see three example widgets. They are each given a random number ("Seed") and need to find an Answer that results in a product with a different number of zeroes in-a-row. You can see that a widget tends to take longer to find a valid Answer when it has a higher Difficulty.

Math homework for computers

For computers, this example math problem is trivial. I limited the examples to about 60 guesses per second, but an iPhone 15 Pro can do about two trillion operations per second, which would easily be billions of guesses per second. We need something much harder.

Hashing

Turnstyle, Anubis, and Bitcoin (surprise) use a useful computer math problem called a hash to demand proof of work. A hash is a unique signature that can be calculated from a number, document, file - any data available to computers. What matters for proof of work is two effects of creating these unique hashes:

1. They are unpredictable. Good hashes vary wildly when the data has even minor changes. This makes finding hashes that have certain properties need a lot of guessing work.
2. They are expensive. The algorithms that generate these hashes require multiple rounds of multiple calculations. Here is a step-by-step demonstration of a popular hash algorithm. You need to do all of that once for every guess, hundreds or thousands of times to meet an expected difficulty.

If you've seen something like the below online, you've likely seen a hash. It's a mix of letters and numbers because it's a large number presented in hexadecimal (base 16). For reasons.

d6ea8f9a1f22e1298e5a9506bd066f23cc56001f5d36582344a628649df53ae8

The traditional challenge is demand that a hash of a large number (like 70 digits long) plus an answer starts with a certain number of zeroes. This challenge is so hard that the race to be the first person to find the answer in the context of securing Bitcoin consumes 26 nuclear power plants' worth of electricity every year.

While our poor CPUs have to strain to prove our benevelence, I hope Cloudflare and the makers of Anubis can find ways to make these expensive calculations more useful.