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

Bill Cox waywardgeek at gmail.com
Wed Jul 8 16:37:20 EDT 2015

On Wed, Jul 8, 2015 at 12:13 PM, John Tromp <john.tromp at gmail.com> wrote:

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

For consistency with existing terminology as used to describe Scrypt and
other "sequential-memory-hard" password hashing schemes, why don't we call
this a "memory-intensive TMTO-resistant PoW with fast verification"?

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

I was trying to show that an ASIC based miner doing Momentum computations
would have essentially an unfair advantage vs CPUs, leading to an
inevitable switch to ASIC based mining if Momentum were used as the PoW for
a PoW mining based crypto-currency.  Parallel sorting is enough to work out
well enough for the proof, I think.

Now that I've been pointed to faster the parallel Pollard rho-algorithm
<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=> for
finding hash collisions (thanks for the link, Jonathan!), I think Momentum
can be sped up linearly with the number of processors.  Momentum does not
seem parallelization-hardened

> 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
> _______________________________________________
> The cryptography mailing list
> cryptography at metzdowd.com
> http://www.metzdowd.com/mailman/listinfo/cryptography

I am more interested in massively parallel attacks.  If I'm not mistaken,
using lots of memory had providing good defense against parallel attacks is
what we need to defend against ASIC based mining.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150708/5f4eff57/attachment.html>

More information about the cryptography mailing list