The Server Does Not Trust Your Answer, It Recomputes It

A proof-of-work challenge hands you a link and asks for a nonce that makes the hash of the pair start with enough zero bits. You send the nonce back and the edge recomputes the digest itself, byte for byte, before it believes a word of what you claimed. That is the whole design: the server never has to trust your arithmetic, only your bytes, and it only spends a single hash to check them.

What makes the control interesting to build against is that the cost sits on the visitor's CPU, not the server's. The edge hands out the same work to every browser that loads the page, so the price of admission is paid in milliseconds of your own machine. This is a close relative of the clearance-cookie flow covered in Proof-of-Work and Clearance Cookies, and it is the piece a managed challenge replaces when the vendor would rather not ship a widget at all. This lesson is about the shape of that work: how the chain is seeded, what difficulty means in bits, why the scan loop is shardable, and where the interesting engineering is once you go past a single SHA-256 round.

The Shape of a Hash-Chain Challenge

The unit of work is a link: a seed string that already incorporates everything that came before it. The seed in the snippet below is a host, a path prefix and a session-scoped identifier, so two sessions on the same edge get different chains and a chain cannot be lifted from one capture into another.

From that link you scan nonces. For each candidate you build a message, hash it, and test whether the digest's leading bits are zero. The first nonce that passes becomes part of the next link, which is why the acceptance column of the trace is mostly zeros: the last link of a chain is itself a valid solution for the chain's root.

Element Where it comes from What the client may change
Challenge id the challenge document, server issued nothing
Seed / link server issued, or the previous link's digest nothing
Nonce client chosen, scanned in order everything
Algorithm named by the challenge nothing
Difficulty server issued, in bits nothing

Three of the five inputs are fixed by the server. The nonce is the only degree of freedom, which is exactly why the control is fair: it measures willingness to spend CPU, not knowledge of a secret. It also explains why the challenge survives a replay of the answer: the link carries the session, so a nonce that was accepted for one session is worthless for the next one, and an operator cannot cache a solution and rent it out.

import hashlib

# The challenge as the edge publishes it: a seed string, an algorithm name, a
# difficulty in leading zero bits, and a link count. Nothing else.
SEED = "shop.example|/akam/2c1f/pow/8f21"
LINKS = 3
HASHES = {
    "sha256": hashlib.sha256,
    "sha3_256": hashlib.sha3_256,
    "blake2s": hashlib.blake2s,
}
# A fixed planning constant, not a live measurement: hashes per second that one
# core sustains on this workload. Production reads this from its own fleet.
CORE_RATE = 250_000


def zero_bits(digest):
    '''Number of leading zero bits in a digest, counted over the whole thing.'''
    n = 0
    for byte in digest:
        if byte == 0:
            n += 8
            continue
        n += 8 - byte.bit_length()
        break
    return n


class Solver:
    '''A stateless nonce scan.

    Any worker can run any contiguous slice of the nonce space, because the
    verifier is a pure function of (link, nonce). That is what makes the work
    shardable across a fleet and what lets one challenge be amortised.
    '''

    def __init__(self, algorithm, bits):
        if algorithm not in HASHES:
            raise KeyError(algorithm)
        self.algorithm = algorithm
        self.bits = bits
        self.hash = HASHES[algorithm]

    def digest(self, link, nonce):
        return self.hash(link + nonce.to_bytes(4, "big")).digest()

    def scan(self, link, start, budget):
        '''Scan [start, start+budget). Return (nonce, attempts) or (None, attempts).

        The budget counts hashes, not seconds, so the abort decision is a pure
        function of the inputs and the table below is reproducible.
        '''
        for offset in range(budget):
            nonce = start + offset
            if zero_bits(self.digest(link, nonce)) >= self.bits:
                return nonce, offset + 1
        return None, budget

    def verify(self, link, nonce):
        '''What the edge does with the answer: recompute, compare, accept.'''
        return zero_bits(self.digest(link, nonce)) >= self.bits


def solve(algorithm, bits, links, budget_each=4_000_000):
    '''Walk the chain link by link; each accepted link seeds the next search.'''
    solver = Solver(algorithm, bits)
    link = hashlib.sha256(SEED.encode()).digest()
    trace = []
    for index in range(links):
        nonce, attempts = solver.scan(link, 0, budget_each)
        if nonce is None:
            return solver, trace, None, attempts
        link = solver.digest(link, nonce)
        trace.append((index, nonce, attempts, link))
    return solver, trace, link, sum(t[2] for t in trace)


print("hash-chain proof of work: attempt counts are exact, no clock, no network")
print("seed  : {} (sha256 root link, {} links per solution)".format(SEED, LINKS))
print()
print("every accepted digest starts with the difficulty's zero bits, which is why")
print("the head column below is mostly zeros: the last link is itself a solution.")
print()
print("{:<5} {:<10} {:>5} {:>10} {:>10} {:>6} {:>9}  {}".format(
    "bits", "algorithm", "lnk", "attempts", "expected", "ratio", "nonce", "accepted digest[:16]"))
print("-" * 100)
for algorithm in ("sha256", "sha3_256", "blake2s"):
    for bits in (12, 16, 18):
        links = LINKS if bits == 16 else 1
        _solver, trace, head, total = solve(algorithm, bits, links)
        expected = links * (1 << bits)
        print("{:<5} {:<10} {:>5} {:>10,} {:>10,} {:>6.2f} {:>9,}  {}".format(
            bits, algorithm, links, total, expected, total / expected,
            trace[-1][1], head[:8].hex()))

print()
print("per-link trace at 16 bits over 3 links, sha256; each link seeds the next")
print("{:<5} {:>10} {:>10} {:>10}  {}".format("link", "nonce", "attempts", "running", "digest[:24]"))
print("-" * 70)
_solver, trace, _head, _total = solve("sha256", 16, LINKS)
running = 0
for index, nonce, attempts, link in trace:
    running += attempts
    print("{:<5} {:>10,} {:>10,} {:>10,}  {}".format(index, nonce, attempts, running, link[:12].hex()))

print()
print("abort and timeout handling: a link that exhausts its budget is a failure")
print("{:<6} {:>10} {:>10} {:<8} {:>8}  {}".format(
    "bits", "budget", "expected", "outcome", "spent", "what the caller must do"))
print("-" * 92)
for bits, budget in ((12, 500), (12, 8_000), (18, 500), (18, 600_000)):
    solver, trace, head, spent = solve("sha256", bits, 1, budget_each=budget)
    done = head is not None
    print("{:<6} {:>10,} {:>10,} {:<8} {:>8,}  {}".format(
        bits, budget, 1 << bits, "solved" if done else "ABORT", spent,
        "post the chain head with the retry token" if done
        else "abandon the page, re-fetch, log a failed challenge"))

print()
print("amortising one challenge across a fleet: expected work divided by cores")
print("difficulty 22 bits is {:,} expected hashes at {:,} H/s per core".format(
    1 << 22, CORE_RATE))
print("{:<8} {:>12} {:>12} {:>12}  {}".format("workers", "total work", "per worker", "wall secs", "nonce range each worker owns"))
print("-" * 100)
for workers in (1, 8, 64, 256):
    work = 1 << 22
    print("{:<8} {:>12,} {:>12,} {:>12.2f}  {}".format(
        workers, work, work // workers, work / float(CORE_RATE * workers),
        "0..{}".format(work // workers - 1)))

print()
print("an Argon2id-shaped challenge, modelled as lanes of 1 KiB compression blocks")
print("the permutation below is blake2b, not argon2's; what it reproduces is the")
print("shape of the cost: work is proportional to memory times passes, and the only")
print("parallelism is the lane count, because consecutive blocks depend on each other.")
LANES, BLOCKS, PASSES = 4, 64, 3
BLOCK_BYTES = 1024
matrix = [[bytes(1024) for _ in range(BLOCKS)] for _ in range(LANES)]
accesses = 0
for _pass in range(PASSES):
    for lane in range(LANES):
        for column in range(BLOCKS):
            previous = matrix[lane][column - 1]
            # A 2-input compression with a chained carry, which is what makes
            # the next block's input depend on the current block's output.
            carry = hashlib.blake2b(matrix[lane][column] + previous, digest_size=64).digest()
            accesses += 1
            matrix[lane][column] = (carry * 16)[:BLOCK_BYTES]
print("{:<6} {:<7} {:>10} {:>12} {:>12}  {}".format(
    "lanes", "passes", "blocks", "accesses", "memory", "parallelism"))
print("-" * 92)
for lanes in (1, 4, 16):
    blocks = LANES * BLOCKS
    print("{:<6} {:<7} {:>10,} {:>12,} {:>10,} KiB  {:,} lanes, no more".format(
        lanes, PASSES, blocks, lanes * BLOCKS * PASSES,
        lanes * BLOCKS * BLOCK_BYTES // 1024, lanes))
print("modelled above: {} lanes x {} blocks x {} passes = {:,} block compressions, "
      "{} KiB resident".format(LANES, BLOCKS, PASSES, accesses,
                               LANES * BLOCKS * BLOCK_BYTES // 1024))

print()
print("algorithm rotation: a solver is built against the name in the challenge")
print("{:<12} {:>7} {:<10} {:>11}  {}".format(
    "algorithm", "digest", "registry", "work growth", "behaviour of a solver not registered for it"))
print("-" * 104)
for name, size in (("sha256", 32), ("sha3_256", 32), ("blake2s", 32),
                   ("argon2id", 32), ("md5", 16)):
    known = name in HASHES
    print("{:<12} {:>7} {:<10} {:>11}  {}".format(
        name, size, "yes" if known else "no", "2 to the n",
        "verifies the chain head" if known else "KeyError, no answer posted, challenge re-read"))

print()
print("rotation drill: the site moves the challenge from sha256 to blake2s mid-run")
for name in ("sha256", "blake2s", "argon2id"):
    try:
        Solver(name, 12)
        print("  {:<10} registered, solve as normal".format(name))
    except KeyError as exc:
        print("  {:<10} NOT registered ({}) - re-read the challenge and register it".format(
            name, exc))

print()
print("verifier: the edge recomputes, so a wrong algorithm cannot be faked")
stale, trace, head, spent = solve("sha256", 12, 1)
wrong = Solver("blake2s", 12)
print("  chain head solved with sha256, announced as blake2s: verify={}".format(
    wrong.verify(hashlib.sha256(SEED.encode()).digest(), trace[-1][1])))
print("  chain head solved with sha256, announced correctly:      verify={}".format(
    stale.verify(hashlib.sha256(SEED.encode()).digest(), trace[-1][1])))
print("  the head is {} bits of zeros wide, so the answer carries its own proof".format(
    zero_bits(head)))

hash-chain proof of work: attempt counts are exact, no clock, no network
seed  : shop.example|/akam/2c1f/pow/8f21 (sha256 root link, 3 links per solution)

every accepted digest starts with the difficulty's zero bits, which is why
the head column below is mostly zeros: the last link is itself a solution.

bits  algorithm    lnk   attempts   expected  ratio     nonce  accepted digest[:16]
----------------------------------------------------------------------------------------------------
12    sha256         1      1,367      4,096   0.33     1,366  000638b67096fe5c
16    sha256         3     50,554    196,608   0.26     1,527  0000ef9dc8cddbc1
18    sha256         1    428,536    262,144   1.63   428,535  000011d9744c5419
12    sha3_256       1        556      4,096   0.14       555  0009b38dda64670e
16    sha3_256       3    211,270    196,608   1.07     8,841  00003a98ca33d718
18    sha3_256       1    349,671    262,144   1.33   349,670  00000c26baeefee6
12    blake2s        1      5,848      4,096   1.43     5,847  000d048caad394f5
16    blake2s        3    133,231    196,608   0.68    15,783  0000d9a4e042534c
18    blake2s        1     21,201    262,144   0.08    21,200  0000142da05d9e36

per-link trace at 16 bits over 3 links, sha256; each link seeds the next
link       nonce   attempts    running  digest[:24]
----------------------------------------------------------------------
0         22,363     22,364     22,364  0000681e05f30b894e25842d
1         26,661     26,662     49,026  00005d098db5e2305e7f0197
2          1,527      1,528     50,554  0000ef9dc8cddbc175538a77

abort and timeout handling: a link that exhausts its budget is a failure
bits       budget   expected outcome     spent  what the caller must do
--------------------------------------------------------------------------------------------
12            500      4,096 ABORT         500  abandon the page, re-fetch, log a failed challenge
12          8,000      4,096 solved      1,367  post the chain head with the retry token
18            500    262,144 ABORT         500  abandon the page, re-fetch, log a failed challenge
18        600,000    262,144 solved    428,536  post the chain head with the retry token

amortising one challenge across a fleet: expected work divided by cores
difficulty 22 bits is 4,194,304 expected hashes at 250,000 H/s per core
workers    total work   per worker    wall secs  nonce range each worker owns
----------------------------------------------------------------------------------------------------
1           4,194,304    4,194,304        16.78  0..4194303
8           4,194,304      524,288         2.10  0..524287
64          4,194,304       65,536         0.26  0..65535
256         4,194,304       16,384         0.07  0..16383

an Argon2id-shaped challenge, modelled as lanes of 1 KiB compression blocks
the permutation below is blake2b, not argon2's; what it reproduces is the
shape of the cost: work is proportional to memory times passes, and the only
parallelism is the lane count, because consecutive blocks depend on each other.
lanes  passes      blocks     accesses       memory  parallelism
--------------------------------------------------------------------------------------------
1      3              256          192         64 KiB  1 lanes, no more
4      3              256          768        256 KiB  4 lanes, no more
16     3              256        3,072      1,024 KiB  16 lanes, no more
modelled above: 4 lanes x 64 blocks x 3 passes = 768 block compressions, 256 KiB resident

algorithm rotation: a solver is built against the name in the challenge
algorithm     digest registry   work growth  behaviour of a solver not registered for it
--------------------------------------------------------------------------------------------------------
sha256            32 yes         2 to the n  verifies the chain head
sha3_256          32 yes         2 to the n  verifies the chain head
blake2s           32 yes         2 to the n  verifies the chain head
argon2id          32 no          2 to the n  KeyError, no answer posted, challenge re-read
md5               16 no          2 to the n  KeyError, no answer posted, challenge re-read

rotation drill: the site moves the challenge from sha256 to blake2s mid-run
  sha256     registered, solve as normal
  blake2s    registered, solve as normal
  argon2id   NOT registered ('argon2id') - re-read the challenge and register it

verifier: the edge recomputes, so a wrong algorithm cannot be faked
  chain head solved with sha256, announced as blake2s: verify=False
  chain head solved with sha256, announced correctly:      verify=True
  the head is 13 bits of zeros wide, so the answer carries its own proof

Difficulty Is Measured in Bits, Not Iterations

Older interfaces stated a target number of hash rounds. Modern ones state a bit count, and the difference matters for your cost model, because a bit count compounds. Going from 16 to 18 bits doubles the expected work; going from 16 to 20 quadruples it. There is no per-iteration overhead to amortise, because the expected number of attempts is exactly 2 to the power of the difficulty, with no constant factor to tune.

The ratio column in the run below is attempts divided by expectation, and it is worth staring at. It wanders between 0.08 and 1.63 across nine independent samples. A single solve is a coin-flip-heavy process; only the expectation is stable. Any code that budgets wall-clock time from one observed solve will miscalculate, because the sample variance at 18 bits is enormous in absolute terms even though the distribution is perfectly tight in relative terms. Plan from 2 to the power of the bits, never from the last run's stopwatch.

The Scan Loop Is a Pure Function of Its Inputs

The scan takes a link, a starting nonce and a budget measured in hashes, and returns either a nonce or nothing. There is no shared state, no lock, no ordering requirement between workers. That is not an implementation detail, it is the property that makes the control tractable: any worker can own any contiguous slice of the nonce space, and the union of the slices is the whole space.

The trace shows the three links of one 16-bit chain, each seeding the next, with the running total after every link. Fifty-four thousand hashes for sixteen bits over three links is unremarkable; twenty-two bits over three links is four million and takes a different class of machine budget. Decide which of those you are actually facing before you write any optimisation, because the two situations call for completely different code: one fits in a request handler, the other is a job scheduler.

Memory-Hard Variants Change the Bottleneck

Once a challenge is memory-hard the arithmetic stops being the interesting part. Argon2id's cost is memory multiplied by passes, and its parallelism is exactly the lane count, because block n depends on block n-1 within a lane. The snippet models this with blake2b, because blake2b is in the standard library and the point is the shape of the cost rather than byte-exact compatibility.

The table is the useful part. Doubling the lanes doubles resident memory and doubles the parallel speedup, and it does not change the total block count. What it changes is the failure mode: a container with a 256 MiB limit will let a 4-lane, 64-block, 3-pass job run and will kill a 16-lane one, so the parameters you copy out of a challenge document are not the parameters you can always afford. Read the parameters, then read your own memory limit, and decide which one you are going to change.

Algorithm Rotation Is a Compatibility Problem

Challengers rotate digests. The snippet registers three algorithms and then drills what happens when the site switches mid-run to one you have never seen: the lookup raises, no answer is posted, and the challenge has to be re-read.

The failure is loud, which is the right property, but only if you handle it as a rotation signal rather than as a crash. Treat an unregistered algorithm name as data, not as an exception, and re-read the challenge. A solver that hard-codes hashlib.sha256 is correct for one week and then fails silently on the subset of sessions that happen to be served a rotated challenge, which is the worst kind of intermittent failure to debug. Keep a registry keyed by the name the challenge actually printed, and let an unknown key mean "ask again" rather than "give up".

What the Verifier Actually Checks

The last section is the one that keeps the design honest. Solve a chain head with SHA-256 and announce it as BLAKE2s and verification fails, because the edge recomputed with the announced algorithm and got a different digest. Solve it and announce it correctly and it passes.

Notice what the verifier does not need: your process, your code, your machine, any trust in you at all. It needs the link, the nonce and the algorithm name, and it needs one hash. This is the property that separates a proof-of-work control from a CAPTCHA, and it is why a proof-of-work control stays cheap for the defender and expensive only for someone trying to answer an unbounded number of them. It is also why there is no solver artefact to steal: nothing you produce is reusable against a different session.

Amortising One Challenge Across a Fleet

Total expected work does not change when you add workers; what changes is wall clock time and the size of each worker's slice. At twenty-two bits, four million expected hashes against a rate of a quarter-million hashes per second per core is under seventeen seconds on one core and a fraction of a second across a hundred and sixty-four.

Two practical consequences. First, the fan-out is nearly free in wall-clock terms and expensive in coordination, so beyond roughly the point where each worker owns less than a few thousand hashes you are paying more in task dispatch than in hashing. Second, the nonce range in the table is the natural partition key, so workers never need to talk to each other; the only shared artefact is the winning nonce at the end. That is the whole reason a proof-of-work challenge is a poor bot control against anyone with a fleet, and the reason distributed fleets treat it as a scheduling exercise rather than a cryptographic one.

Measuring a Solver Instead of Guessing at One

The metrics worth logging per solve are hashes per second per worker, attempts consumed against expectation, aborts, and the time between challenge fetch and answer post. The abort table is the part that shows up in production: a budget of 500 hashes against a twelve-bit difficulty has a roughly 88 percent chance of aborting, because the expectation is 4,096. Budgets should be set several times the expectation, and the expectation should be recomputed whenever the difficulty moves.

If you cannot log attempts against expectation, you cannot tell a slow machine from a rotated challenge, and those two failures have opposite responses: one wants more cores, the other wants a new algorithm registration. When neither number explains the symptoms, the next place to look is the capture, and challenge debugging with recorded traffic is where a solver's belief and the wire finally line up.

Checklist

  • Read the difficulty as a bit count, and compute expected work as 2 to the power of that count.
  • Seed the scan from the server's link, and never from a value you cached.
  • Budget in hashes, not seconds, so the abort decision is reproducible.
  • Partition the nonce space by contiguous ranges; workers should not coordinate.
  • Expect a wide attempt-to-expectation ratio and never plan from a single solve.
  • Register every algorithm the challenge names, and treat an unknown name as a re-read trigger rather than as a fatal error.
  • Check memory-hard parameters against your container's actual memory limit, not against the defaults in the vendor's example code.
  • Log attempts, expectation, aborts and hashes per second for every solve, and alert when attempts sit below half of expectation for a sustained period.

The Legitimate Route

If you own the site, this work is yours to tune: keep the difficulty low enough that a mid-range phone clears it in a frame budget, and spend the budget on the edge instead. If you are collecting data you have a right to, an official API, a partner feed, or a written agreement with the site usually costs less than the maintenance on a solver, and the operator will usually hand you a key for less work than you are about to write. Defeating a paywall or re-adding traffic after a block is a different act from paying a CPU toll, and no amount of engineering makes those two the same thing. The practical test is the one an operator will already apply: if the challenge is there to ration a resource the owner sells, the solver is not a compatibility layer, and the correct next step is to ask for a commercial arrangement rather than to make the toll cheaper.