[Cryptography] Are Momentum and Cuckoo Cycle PoW algorithms broken?
waywardgeek at gmail.com
Wed Jul 8 14:51:17 EDT 2015
On Wed, Jul 8, 2015 at 10:11 AM, John Tromp <john.tromp at gmail.com> wrote:
> The whitepaper at
> 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?
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the cryptography