The computational approach to combating spam has been proposed in a paper by Dwork and Naor. This approach requires a sender to attach a proof of effort that is specific to the message, the sender, and the receiver. The proof of effort should require moderate resources to compute so that the sender is effectively charged a small cost. However, the resources needed to verify should be tiny, so that little overhead is incurred by the recipient.
Original proposal was to use a CPU-intensive function, such as HashCash . Mike Burrows proposed to use memory-bound functions, which are more egalitarian: the difference between a new high-end and an old low-end machine speed is much less than for HashCash, making the antispam approach more acceptable to users with older hardware. The first moderately-hard memory-bound function was proposed in a paper by Abadi, Burrows, Manasse, and Wobber. An alternative memory-bound function with certain provable lower bounds is proposed in a paper by Dwork, Goldberg, and Naor.
We present a prototype implementation of computational antispam approach. We implement both HashCash and the latter memory-bound function variants. Our implementation demonstrates the difference between the CPU and the memory-bound approach. The implementation also demonstrates user experience.
Another interesting aspect of our implementation is its simple architecture. A proxy runs on each client machine and communication between a mail server a client goes through the proxy. The proxy computes and attaches proofs of effort to outgoing mail and checks for such proofs in the incoming mail. Messages without a valid proof are tagged as spam and (optionally) bounced.