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

[John Tromp]

> Is it known whether Momentum and/or Cuckoo are memory-hard?  I don't think
> either are.

As author of Cuckoo Cycle, let me address your concerns.

> Both claim to be "memory-hard".

The Cuckoo Cycle project page at https://github.com/tromp/cuckoo in fact lists a

"Linear Time-Memory Trade-Off Bounty

$500 for an open source implementation that uses at most N/k bits
while running up to 15 k times slower, for any k>=2.

Both of these bounties require N ranging over {2^28,2^30,2^32} and
#threads ranging over {1,2,4,8}, and further assume a high-end Intel
Core i7 or Xeon and recent gcc compiler with regular flags as in my
Makefile."

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 :-(

Instead, what you're talking about is covered in the later Section
"Parallelization",
which show the gains achievable by using multiple threads.
The algorithm you outline is also detailed in the earlier Section
"Cuckoo Cyle basic algorithm"
and is in fact what motivates the its name.

It's almost as if you've gone out of your way to avoid reading the whitepaper:-)

> Cuckoo Cycle also claims to be memory-hard, but I don't buy it.  They're
> looking for cycles of length L by building a forest of trees, and detecting
> when loops form, and measuring the length.  If we do a parallel sort as
> above, we can store entries in a Cuckoo hash table
> <https://en.wikipedia.org/wiki/Cuckoo_hashing> rapidly in parallel.

You don't need parallel sort for that; the parallel version of the
basic algorithm
already does it. But note that:

1) it uses 32 times more memory than the Cuckoo Cycle reference algorithm
2) the parallel memory accesses are going to form a latency bottleneck when
    the number of threads runs into the hundreds.

regards,
-John