International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 28 September 2015

Alex Biryukov, Dmitry Khovratovich
ePrint Report ePrint Report
The proof-of-work is a central concept in modern cryptocurrencies, but the requirement for fast verification so

far made it an easy prey for GPU-, ASIC-, and botnet-equipped users. The attempts to rely on

memory-intensive computations in order to remedy the disparity between architectures have

resulted in slow or broken schemes.

In this paper we solve this open problem and show how to construct an \\emph{asymmetric} proof-of-work (PoW) based on a computationally hard problem, which requires a lot of memory to generate a proof (called \"memory-hardness\" feature) but is instant to verify. Our primary proposal is a PoW based on the

generalized birthday problem and enhanced Wagner\'s algorithm for it. We introduce the new technique of \\emph{algorithm binding} to prevent cost amortization and demonstrate that possible parallel implementations are constrained by memory bandwidth. Our scheme has tunable and steep time-space tradeoffs, which impose large computational penalties if less memory is used.

Our solution is practical and ready to deploy: a reference implementation of a proof-of-work requiring 700 MB of RAM runs in 30 seconds on a 1.8 GHz CPU,

increases the computations by the factor of 1000 if memory is halved, and presents a proof of just 148 bytes long.

Expand

Additional news items may be found on the IACR news page.