Paper published in a book (Scientific congresses, symposiums and conference proceedings)
Equihash: asymmetric proof-of-work based on the Generalized Birthday problem
Biryukov, Alex; Khovratovich, Dmitry
2016In Proceedings of NDSS 2016
Peer reviewed
 

Files


Full Text
946.pdf
Author postprint (479.96 kB)
Download

All documents in ORBilu are protected by a user license.

Send to



Details



Keywords :
Bitcoin; proof-of-work; memory-hard
Abstract :
[en] 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 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 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.
Disciplines :
Computer science
Finance
Author, co-author :
Biryukov, Alex ;  University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
Khovratovich, Dmitry ;  University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
External co-authors :
no
Language :
English
Title :
Equihash: asymmetric proof-of-work based on the Generalized Birthday problem
Publication date :
February 2016
Event name :
Network and Distributed System Security Symposium 2016
Event place :
San Diego, California, United States
Event date :
from 21-02-2016 to 24-02-2016
Audience :
International
Main work title :
Proceedings of NDSS 2016
Pages :
13
Peer reviewed :
Peer reviewed
Available on ORBilu :
since 27 October 2015

Statistics


Number of views
5330 (44 by Unilu)
Number of downloads
7514 (32 by Unilu)

Bibliography


Similar publications



Contact ORBilu