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

[John Tromp]

> 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.

I would prefer to call that parallelization hardness.
Memory hardness should ideally be about the suffering caused by having less
than the designated amount of memory available.

> 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?

This is already implemented and results are shown in the section
called "Parallelization". I don't understand why you need sorting though.

Unfortunately, I have no access to a working Xeon Phi
multicore cpu that would allow me to try more than 40 threads.
I do expect the parallel speedup to flatten out at around a hundred threads.
For AMD Opteron based servers, it already flattened at 30.

regards,
-John