Pricing via processing: making junk mail expensive (Dwork and Naor 1992)

Dwork and Naor proposed that a sender attach to each message the answer to a puzzle that is moderately hard to solve but easy to check. One of their pricing functions is a square root modulo a prime: computing it takes a full modular exponentiation, checking it a single multiplication. The idea of a cost asymmetry became proof of work.

What to look for

The work to compute a root grows with the size of the prime; checking stays at one multiplication. The asymmetry here is only logarithmic, which is why Hashcash (the next example) switched to hash puzzles with tunable, exponential cost.

The history behind this experiment: Breakthroughs in Consensus.

Price one message

import matplotlib.pyplot as plt

import blockchainkit as bk

p = 2**61 - 1  # A Mersenne prime, = 3 mod 4.
message_id = int.from_bytes(bk.crypto.sha256(b"Hello, buy my product!")[:8], "big") % p
square = message_id * message_id % p  # Choose a puzzle with a guaranteed root.
answer = bk.consensus.modular_square_root(square, p)
assert answer.root * answer.root % p == square  # The recipient checks with one multiplication.
print(f"sender: {answer.multiplications} multiplications; recipient: 1")

sender: 61 multiplications; recipient: 1

Cost against prime size

primes = [n for n in range(1000, 2**20, 997) if bk.crypto.is_prime(n) and n % 4 == 3][:40]
primes += [2**31 - 1, 2**61 - 1]
work = [bk.consensus.modular_square_root(4, q).multiplications for q in primes]
fig, ax = plt.subplots(figsize=(7, 3.8))
ax.semilogx(primes, work, "o", base=2, label="compute the root")
ax.semilogx(primes, [1] * len(primes), "-", base=2, color="black", label="verify it")
ax.set(
    xlabel="prime p",
    ylabel="modular multiplications",
    title="Computing costs about 1.5 log2 p; checking costs 1",
)
ax.legend()
fig.tight_layout()

Exercise

Dwork and Naor also wanted a shortcut: a trapdoor letting a trusted authority price messages cheaply. Why is a logarithmic asymmetry too small to stop a spammer with a fast computer, and how does Hashcash fix that?