Exponential Memory-Bound Functions for Proof of Work Protocols.
Fabien Coelho · 2005
In year 2005, Internet users are twice more likely to receive unsolicited electronic messages, known as spams, than regular emails. Proof of work protocols are designed to limit such phenomena and other denial-of-service attacks by requiring some kind of virtual stamping. These schemes require computing an easy to verify but hard to find solution to some problem. As cpu-intensive computations are badly hit over time by Moore's law, memory-bound computations have been suggested as an alternative to deal with heterogeneous hardware. We introduce new memory-bound functions suitable to these protocols, in which the client-side work to compute the response is exponential with respect to the server-side work needed to set the challenge or check it, instead of polynomial. One-side noninteractive solution-verification variants are also presented. Our experimental results and technical arguments show that any such memory-bound function is inherently parallel, thus bound by memory bandwidth and not by memory latency, as previously claimed by others.