[Resource Topic] 2005/356: Exponential Memory-Bound Functions for Proof of Work Protocols

Welcome to the resource topic for 2005/356

Exponential Memory-Bound Functions for Proof of Work Protocols

Authors: Fabien Coelho


In Year 2005, Internet users were twice more likely to receive
unsolicited electronic messages, known as spams, than regular emails.
Proof of work protocols are designed to deter such phenomena
and other denial-of-service attacks by requiring computed stamps
based on hard-to-solve problems with easy-to-verify solutions.
As cpu-intensive computations are badly hit over time by Moore’s law,
memory-bound computations have been suggested to deal with heterogeneous hardware.
We introduce new practical, optimal, proven and possibly memory-bound
functions suitable to these protocols,
in which the client-side work to compute the response is intrinsically
exponential with respect to the server-side work needed to set or check the challenge.
One-way non-interactive solution-verification variants are also presented.
Although simple implementations of such functions are bound
by memory latency, optimized versions are shown to be bound
by memory bandwidth instead.

ePrint: https://eprint.iacr.org/2005/356

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .