You are looking at a specific version 20061107:100848 of this paper. See the latest version.

Paper 2005/356

Exponential Memory-Bound Functions for Proof of Work Protocols

Fabien Coelho

Abstract

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.

Note: Overall presentation simplified by focussing on one variant. Proof of the scheme added, including an optimality claim, replacing a lot of hand-waving.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Submitted to a conference. TR Ecole des mines de Paris A/370/CRI.
Keywords
electronic commerce and payment
Contact author(s)
fabien coelho @ ensmp fr
History
2006-11-07: last of 3 revisions
2005-10-09: received
See all versions
Short URL
https://ia.cr/2005/356
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.