This post summarizes Cynthia Dwork and Moni Naor’s paper, “Pricing via Processing or Combatting Junk Mail,” as it relates to blockchain and the pre-Bitcoin history. The authors propose computational puzzles requiring CPU effort to access resources, a direct precursor to proof-of-work in Bitcoin. Satoshi did not cite this paper, but Satoshi did cite Adam Back, the creator of Hashcash. Commenting on his 1997 paper, Back wrote: “At the time of publication of [Back’s 1997 paper] the author [i.e. Back] was not aware of the prior work by Dwork and Naor in [this pricing paper] who proposed a CPU pricing function for the application of combatting junk email. Subsequently applications for cost-functions have been further discussed by Juels and Brainard…” Apparently the stars were beginning to align for proof-of-work to take shape since different people were - to some extent - independently arriving at similar solutions. Therefore some time is given to understanding the Dwork and Naor paper.
Dwork, C., Naor, M. (1993). Pricing via Processing or Combatting Junk Mail. In: Brickell, E.F. (eds) Advances in Cryptology — CRYPTO’ 92. CRYPTO 1992. Lecture Notes in Computer Science, vol 740. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48071-4_10
Two Ideas
In solving the problem of junk mail, my opinion is that the Dwork-Naor paper contains two ideas worth understanding.
- A new way to gauge the difficulty or hardness of a function.
- The introduction of computational puzzles as a pricing function to make spam costly.
Both of these ideas will be introduced and then applied to how they solve the junk mail problem. Some of the sections in the paper are mathy, and that will be discussed less than some of the formalities around property definitions and remarks given by Dwork and Naor about those properties.
Shifting Focus from Asymptotic Complexity to Measures of Hardness
When computer scientists design an algorithm to solve a problem, such as a sorting problem, they want a way of determining whether the algorithm is better or worse than alternative solutions to that problem. The solution must be measured not in terms of a given input but in terms of how the efficiency scales with the input size. Here is how CLRS describe it in their Introduction to Algorithms, Third Edition:
When we look at input sizes large enough to make only the order of growth of the running time relevant, we are studying the asymptotic efficiency of algorithms. That is, we are concerned with how the running time of an algorithm increases with the size of the input in the limit, as the size of the input increases without bound. (Cormen, Leiserson, Rivest, Stein; p. 43)
One way to measure the efficiency of an algorithm is by testing with different inputs through a run-time analysis and graphing out how long it takes. One can see whether it takes linear time or logarithmic time, etc. Another way is to count up the number of steps it takes for an algorithm to complete some task, either for the problem itself or some subtask. The measurement is then given a math framing in notations like Big-O, which captures the upper bound. One does not include constant values. The description here is given in terms of time, but one could also measure how much memory is required as the input size scales up. There is plenty to find on the internet about this and so I will not repeat how this works in more detail.
Efficiency and hardness are different properties. Efficiency typically refers to how well an algorithm solves a problem, measured by its resource usage (like time or space) as input size grows, as just discussed. Hardness, in contrast, describes the inherent difficulty of a problem itself — how challenging it is to find any efficient algorithm to solve it. In computational complexity, a “hard” problem might be NP-hard (no known polynomial-time algorithm exists, and it’s at least as hard as the hardest problems in NP) or require exponential time in the worst case. In the context of the Dwork-Naor paper, hardness is about designing functions that are computationally expensive on average to deter spam, not about optimizing for speed. Put another way, think of hardness as how much effort is needed due to the nature of the problem itself rather than how fast one’s algorithm solves the problem.
Three classes of relative difficulty are introduced: easy, moderate, and hard.
The term moderate can be viewed in two different ways. As an upper bound, it means that computation should be at most moderately hard (as opposed to hard); as a lower bound it means that computation should be at least moderately hard (as opposed to easy). The precise definition of easy and moderate and hard will depend on the particular implementation. However, there must be some significant gap between easy and moderately hard. As usual, hard means intractable in reasonable time, such as factoring a 1024-bit product of two large primes. (p. 2)
(Note: This 1024-bit factoring example reflected the state of computing in 1992; in 2025, due to advances in factorization techniques and hardware, 1024-bit RSA is no longer considered intractable and has been deprecated.)
The goal here is to introduce a relative complexity measure for which it could be hard for a spammer to send thousands of junk mail, but relatively easy for the legitimate user to send a single email. To accomplish this goal, a difference parameter is proposed to serve a role analogous to a security parameter. This parameter is like a knob one can adjust to tune the difficulty or hardness.
Let a shortcut be some additional information to make access to a resource (e.g., an email) less expensive due to bypassing a control mechanism—the thing that makes the algorithm hard. Then the larger the difference parameter, the harder it is for the function to evaluate the input without the shortcut.
It is worth noting that Dwork and Naor suggest evaluating that a function has performed its task correctly should be easy, whereas the function evaluating the input should be hard. That is, verifying whether the function solved a task should not require as much resources and will typically be much faster than the function doing the guessing.
The Pricing Function
Dwork and Naor provide the following jointly sufficient conditions for being a pricing function f:
- f is moderately easy to compute;
- f is not amenable to amortization: given l values $m{_1}$,…$m{_l}$, the amortized cost of computing f($m{_1}$),…,f($m{_l}$) is comparable to computing f($m{_i}$) for any 1 ≤ i ≤ l;
- given x and y it is easy to determine if y = f(x).
Dwork and Naor say that f can be a relation. So think of the pricing function as the algorithm rather than a specific block of code. It should be moderately easy to compute because if it were harder, the regular user would be inhibited from sending legitimate emails due to an overly cautious anti-spam disincentive. But it should be easy to verify, as discussed above.
To say that f is not amenable to amortization means that spammers cannot cheaply compute the function for many inputs at once (e.g., via batching or parallel tricks) to reduce the per-email cost. Amortized functions can make use of caches, for instance, to not have to repeat certain computations already solved. (To see how this can work, search online for algorithms that implement fibonacci with and without amortization.) Instead, the total effort scales linearly with the number of emails, making bulk spam prohibitively expensive without unfairly burdening single senders.
Combatting junk mail is not the proposal of a single pricing function. Dwork and Naor write, “We will be interested in a collection of families of pricing function $\mathcal{F}$ = {$F{_k}$|k ≥ 1}, indexed by a difference parameter k, where the hardness of evaluating $f{_s}$ ∈ $F{_k}$ should increase with k” (pp. 2-3). F is the family of pricing functions. $\mathcal{F}$ is the collection of families of pricing functions indexed by s ∈ S ⊆ {0, 1}*. s is just a seed-like a random key or starting point you pick from the big set S, the space of all possible seeds. The seeds index puzzles to be solved. Once s is chosen randomly (so spammers cannot guess ahead), s defines one particular pricing puzzle $f{_s}$, different from all the others. So then S is the collection of possible puzzles, and s the particular puzzle chosen at some time for which the mailer has to solve the puzzle defined by $f{_s}$ for each email. The core idea is that there is a family of such pricing functions from which to choose a specific one, and each function—tuned by the difficulty parameter k—takes a binary input (a string of 0s and 1s) and produces a binary output, denoted by {0,1}${^*}$.
Dwork and Naor say in Remark 2.1: “It is important to not choose a function that after some preprocessing can be computed very efficiently… Thus, there could be a large difference between the time spent evaluating $f{_s}$ on a large number k of different inputs, such as would be necessary for sending bulk mail, and k individual computations of $f{_s}$ from scratch. This is clearly undesirable.” (p. 3)
What is happening in the omitted ellipsis needs commentary because Dwork and Naor assume familiarity with the matter by the reader. They illustrate the problem of permitting shortcuts or amortization with the subset sum problem. The subset sum problem is a computational challenge such that given a set of integers and a target value x, one must determine if there exists a subset of those integers that sums to x. It is NP-complete, meaning that it is computationally intensive to solve for large instances but easy to verify a proposed solution. Pure exponential difficulty, by contrast, is not difficult enough for security because Schroeppel and Shamir showed you could use a shortcut (meet-in-the-middle approach) to solve it more quickly with preprocessing. So if a spammer could use a shortcut to bypass the control mechanism (i.e., computational puzzle solving), the spammer could continue to send mass junk mail. So the family of pricing functions requires problems that resist such preprocessing shortcuts, even if NP-complete (as subset sum is an example of an NP-complete problem that is vulnerable and thus undesirable).
In addition, finding the shortcut given s should be hard. If finding the shortcut to bypass the control mechanism were easy, it would undermine the point of the control mechanism.
The Solution
Given the above concepts of a pricing-function and a way to measure difficulty, how does the flow work for combatting junk mail? In addition, what is the proof-of-work precursor more exactly? The purpose of this section is to answer these questions. How does it work then?
Imagine there is a network of machines to communicate with each other. There is a pricing authority that selects the pricing function, hash function, and sets usage fees. The users must agree to obey the authority. The authority makes known to all users the pricing function $f{_s}$ and hash function h. Agents charge users per service; the pricing authority charges agents once for c access. That is, the usage fee is paid by the trusted agent to the pricing authority for access to the shortcut. Trusted agents pay the pricing authority for this shortcut. Regular users do not get the shortcut, and as long as regular users are not engaging in bulk emails, they only have to pay the cost of the computational task without the shortcut.
A regular user will hash the combination of the message, the time, and the destination (intended recipient), and will determine the output of the announced pricing function $f{_s}$ on that hash to return a value y. The sender will include y with the message and the time to the recipient. This is a single email and so the trusted agents are irrelevant to this part. The recipient’s software will verify that y equals the pricing function of a hash over the message, the time, and the destination (e.g., the recipient’s email). If it passes the verification step, the message will become available to the user (i.e. the person instead of the software).
Single emails
- Work of the sender: y = $f{_s}$(h(⟨m,t,d⟩))
- Sender sends to recipient: ⟨y,m,t⟩
- Recipient verifies: y = $f{_s}$(h(⟨m,t,d⟩))
- Recipient either: If verification failure, notify the sender, otherwise release the message m to the user as available for opening.
The sender is computing what y is and sending that to the recipient. Depending on the difficulty parameter k, it will take more or less work to find a value y that is equal to the pricing function on the hash of ⟨m,t,d⟩. The recipient is not computing for y, but is running a boolean check: are the two values equal or not? The cost to the recipient is almost nothing other than the electricity to perform a comparison. The cost to the sender should be negligible for a single email, depending on k.
Bulk emails
When the user wants to send something in bulk, the sender pays a fee to a trusted agent and a list of ⟨m,t,d⟩ tuples for all intended emails. The trusted agent, having the shortcut c from the pricing authority, can efficiently compute all the y values without solving the hard puzzles. The trusted agent will return the y values back to the sender instead of routing to the recipient. The trusted agent is not a necessary middle man but optional. But if the trusted agent suspects spam, the trusted agent will likely not return the computational result for each of the tuples. (Possibly, the trusted agent is in on the scam and returns correct values via the shortcut. But then the agent risks losing the trusted agent role with the pricing authority.) The spammer who wished to send the bulk email will have lost the fee negotiated between the sender and the agent. A spammer will be blocked by the trusted agent. The spammer must either shop for another trusted agent or perform the computational tasks. In either case, there is a cost associated with bad behavior.
Optimizing the system
Once users have performed verifications from other senders, there is an option to build in a frequent correspondent list. Doing this will remove the verification requirement for known senders. This is merely a whitelisting mechanism.
Pricing Functions and Hash Functions
Dwork and Naor provide candidates of pricing functions using “number-theoretic algorithms”. These are math puzzles that actually existed at the time. The details there do not matter to us other than knowing the mathematical puzzles or computationally intensive tasks did exist; this is not a totally theoretical system. One of the puzzles is Fiat-Shamir, which is a zero-knowledge proof which allows one to prove that one knows a value without revealing what that value is. (I do not go into how that works here.) Dwork and Naor write that this puzzle “is the most flexible and enjoys the greatest difference function: changing k by 1 doubles the difference.” (p. 9)
Earlier it was stated that the use of hash functions would be explained. There are two reasons given for them:
- “We need hashing in the pricing function based on the signature scheme of Fiat-Shamir” (p. 6)
- Hashing down the emails to a common length, e.g., 512 bits, so the pricing functions get the same sized input value
Further research
In my opinion, the clever move by the authors was the provide a financial disincentive to trying to cheat or be a bad actor. One can scale nodes of bots cheaply, but one cannot as easily scale the finances to pay for the throughput. It is worth citing their last two paragraphs on page 9:
A growing area of research is the economics of networks … where issues such as the effect of pricing on the network behavior are investigated. It is interesting to see whether there are connection [sic] between this direction and the ideas suggested in this paper.
Finally, the evaluation of the pricing function serves no useful purpose, except serving as a deterrent. It would be exciting to come up with a scheme in which evaluating the pricing function serves some additional purpose.
Bitcoin, which implements these proof-of-work ideas at scale, is today trading over $100k— a testament to how prescient Dwork and Naor’s economic insights were.