[Cryptography] Are Momentum and Cuckoo Cycle PoW algorithms broken?

[Bill Cox]

On Wed, Jul 8, 2015 at 10:11 AM, John Tromp <john.tromp at gmail.com> wrote:

> The whitepaper at
> https://github.com/tromp/cuckoo/blob/master/cuckoo.pdf?raw=true
> devotes a Section to Time-Memory Trade-Offs (TMTOs) that further
> details the memory hardness claims.
>
> Which you seem to conveniently ignore in your own notion of
> memory-hardness :-(
>

You wrote in the paper:

"David Andersen also suggested an alternative method of trimming that
avoids storing a bit per edge. Expanding on that idea led to the algorithm
implemented in tomato miner.h, which, unlike the main algorithm, can
trade-off memory directly for runtime. On the downside, to even achieve
memory parity with the main algorithm, it already incurs a big slowdown. To
the extent that this slowdown is unavoidable, it can be called the memory
hardness of the proof-of-work."

This is an incorrect notion of memory-hardness.  Specifically, the goal is
to defeat attackers who have a huge number of cheap parallel cores, whether
they are using a GPU, FPGA, or ASIC attack.  Scrypt's notiion of
memory-hardness where multiple computing cores provides no more than a
constant advantage in memory-use * runtime is the proper definition.

Momentum certainly runs faster when using N memory locations when trying to
find a collision over N nounces.  That makes it memory intensive, but not
sequential memory-hard.  Parallel sorting algorithms will be devastatingly
more efficient at mining any crypto-currency based on Momentum.

If I just implement an actual Cuckoo hash table using a parallel sorting
machine, and do the on-average constant time insertions mostly in parallel,
wont I detect all the Cuckoo cycles?  How much faster is your
implementation than this basic algorithm?

Thanks,
Bill
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150708/04e6606f/attachment.html>