Summary

  • Dwork and Naor's 1992 pricing function was designed to make each request moderately costly to create, easy to verify and resistant to amortisation across recipients.
  • Its exceptions were architectural, not cosmetic: a pricing authority could issue shortcuts, while recipients could exempt familiar correspondents. Later memory-bound work confronted the unequal prices imposed by unequal hardware.

The economic defect in electronic junk mail was not that a message cost nothing. It was that copying the next message cost almost nothing. One person could still spend time composing a letter while a bulk sender reused the same content, software and network path at a scale the recipient had never agreed to subsidise.

Cynthia Dwork and Moni Naor approached that asymmetry by refusing to price words, bytes or postage. Their object was the request. In the paper presented in preliminary form at CRYPTO '92, Pricing via Processing or Combatting Junk Mail, the sender would have to compute a function that was neither easy nor impossibly hard. The result would travel with the request. The receiving system could check it cheaply before admitting the message.

That sounds like a simple toll. The paper's sharper contribution was a condition on reuse: a pricing function should not be amenable to amortisation. Work performed for one input should not make a long run of other inputs substantially cheaper. A cost that can be prepaid once and spread across a million recipients is not a restraint on bulk behaviour. It is merely another fixed expense.

The price belonged to a request

The design bound the computation to material that could include the message, time and destination. Changing the recipient meant changing the input. Changing the message meant changing the input. Time helped make stale results unacceptable. The paper also required a large gap between the effort of producing an answer and the effort of checking it.

This division protected the receiver. If verification were nearly as expensive as production, an attacker could turn the defence into another denial-of-service instrument: send cheap garbage that forces costly checking. Dwork and Naor instead treated asymmetric effort as an operational property. The requester does repeated work; the resource manager makes a quick admission decision.

The candidate functions in the paper came from number theory and deliberately weakened cryptographic constructions. One involved extracting square roots modulo a prime. Others adapted the Fiat–Shamir signature scheme and a broken Ong–Schnorr–Shamir scheme. The point was not to protect a secret with infeasible computation. It was to manufacture a tunable interval between easy and hard—a task expensive enough to discourage repetition but still feasible for an ordinary request.

The authors were explicit that conventional complexity theory offered little guidance for this middle ground. Cryptography usually asks whether an adversary can cross a wall. Pricing asks how high a step should be, how quickly machines will make it smaller and whether many steps can be climbed together. That is an economic question expressed through algorithms.

Exceptions revealed the governor

The proposal did not pretend every high-volume message was abuse. A conference announcement, a professional mailing list or a product notice might be wanted by thousands of people. Requiring full computation for every recipient could suppress legitimate bulk communication together with junk.

The paper therefore described shortcuts. A pricing authority could give trusted agents information that made the pricing function cheap to evaluate. Legitimate bulk senders could use that route under terms set by the manager. Recipients could separately keep local lists of frequent correspondents whose messages bypassed verification, as well as senders whose access was categorically denied.

Those details complicate the popular memory of proof of work as a neutral mathematical barrier. The barrier had an operator. Someone chose the function, its difficulty and the holders of shortcut information. Each recipient also retained a local boundary around familiar traffic. Computation supplied evidence of expenditure; it did not decide which institutions deserved exemptions.

The risk of a shortcut was different from the risk of a broken cryptographic key. The authors argued that a cheaper way to evaluate a pricing function would be observable through renewed bulk abuse, after which the function or key could change. The consequence was economic leakage rather than retrospective disclosure of protected messages. Even so, replacement and detection depended on an authority able to observe the failure and coordinate a new price.

Hardware changed who paid

A decade later, Dwork, Andrew Goldberg and Naor reopened the hardware question in On Memory-Bound Functions for Fighting Spam. CPU-bound work did not impose the same elapsed-time price on a fast server and an old desktop. A bulk sender with specialised or newer machines could receive a discount unavailable to the ordinary correspondent the scheme was meant to protect.

The later paper investigated scattered memory accesses because memory latency varied less dramatically across its test machines than processor speed. It formalised the desired asymmetry: the sender should make many unrelated accesses while verification should require far fewer, or even no, memory accesses. It also bound proofs to a message, sender, receiver and date, and rejected duplicates and stale proofs.

Its experimental result was bounded. One concrete construction was about four times slower on a 233 MHz set-top box than on a 3.06 GHz workstation. That did not prove equality across all devices, eras or adversarial hardware. The authors even questioned whether egalitarian pricing was always desirable: forcing a spammer to acquire costly equipment might matter more than equalising every user's delay, while slow devices could outsource work to a service. The paper turns fairness into a design choice rather than a slogan.

Influence is not identity

Harvard's publication record and intellectual biography place the spam work within a much wider career in distributed computing, cryptography, differential privacy and algorithmic fairness. The biography says the work helped form the basis of cryptocurrencies. Microsoft Research's record likewise preserves the original access-control claim.

That lineage should not collapse distinct systems into one invention. The 1992 proposal did not describe Bitcoin's consensus, issuance or chain selection, and it did not use the later system's terminology. Its durable object was narrower and more general: how a resource manager can demand evidence of a deliberately incurred, non-reusable cost before granting access.

The paper matters because it separated five questions that are still too often bundled together. What is the scarce resource? Which request is the work bound to? Can production be amortised or replayed? How cheap is verification? Who changes the price and grants exceptions? “Proof of work” answers none of them until a system supplies those details.