Paper 2017/497

Time-Memory Tradeoff Attacks on the MTP Proof-of-Work Scheme

Itai Dinur and Niv Nadler

Abstract

Proof-of-work (PoW) schemes are cryptographic primitives with numerous applications, and in particular, they play a crucial role in maintaining consensus in cryptocurrency networks. Ideally, a cryptocurrency PoW scheme should have several desired properties, including efficient verification on one hand, and high memory consumption of the prover's algorithm on the other hand, making the scheme less attractive for implementation on dedicated hardware. At the USENIX Security Symposium 2016, Biryukov and Khovratovich presented a new promising PoW scheme called MTP (Merkle Tree Proof) that achieves essentially all desired PoW properties. As a result, MTP has received substantial attention from the cryptocurrency community. The scheme uses a Merkle hash tree construction over a large array of blocks computed by a memory consuming (memory-hard) function. Despite the fact that only a small fraction of the memory is verified by the efficient verification algorithm, the designers claim that a cheating prover that uses a small amount of memory will suffer from a significant computational penalty. In this paper, we devise a sub-linear computation-memory tradeoff attack on MTP. We apply our attack to the concrete instance proposed by the designers which uses the memory-hard function Argon2d and computes a proof by allocating 2 gigabytes of memory. The attack computes arbitrary malicious proofs using less than a megabyte of memory (about 1/3000 of the honest prover's memory) at a relatively mild penalty of 170 in computation. This is more than 55,000 times faster than what is claimed by the designers. The attack requires a one-time precomputation step of complexity $2^{64}$, but its online cost is only increased by a factor which is less than 2 when spending $2^{48}$ precomputation time. The main idea of the attack is to exploit the fact that Argon2d accesses its memory in a way which is determined by its previous computations. This allows to inject a small fraction of carefully selected memory blocks that manipulate Argon2d's memory access patterns, significantly weakening its memory-hardness.

Note: Main difference: added another simple attack and countermeasure in Section 4.1.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in CRYPTO 2017
Contact author(s)
dinuri @ cs bgu ac il
History
2017-06-15: last of 2 revisions
2017-06-01: received
See all versions
Short URL
https://ia.cr/2017/497
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/497,
      author = {Itai Dinur and Niv Nadler},
      title = {Time-Memory Tradeoff Attacks on the MTP Proof-of-Work Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2017/497},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/497}},
      url = {https://eprint.iacr.org/2017/497}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.