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

Ray Dillinger bear at sonic.net
Thu Jul 9 17:03:01 EDT 2015



On 07/06/2015 11:18 AM, Bill Cox wrote:
> Is it known whether Momentum and/or Cuckoo are memory-hard?  I don't think
> either are.
> 
> Both claim to be "memory-hard".  I would consider any algorithm that
> defeats the memory*time defense of a memory-hard algorithm like Scrypt to
> be a complete break, in the sense that we can no longer claim they are
> memory-hard.  Such algorithms are prone to effective custom-hardware
> attacks, and should probably be avoided as a PoW system which is trying to
> avoid ASIC implementations.

I tried to implement cuckoo cycle and momentum myself, but I was
unable to develop a "strong" construction for them.  It's easy to
develop problems that require resources FOO, but for all the problems
I developed, as soon as I thought deviously enough about ways to
solve them, FOO for problems as memory-hard as I can make them is
always expressible as the simple product of CPU and memory - double
one and you can halve the other.

Trying to come up with anything that valued memory *more* than CPU
(ie, FOO expressed as the product of CPU and some >1 power of
memory) I completely failed at.

I didn't go so far as to extend these observations into
published attacks on existing implementations - but I did examine
a few implementations and decided that none were suitable for
my purpose at the time because they valued memory the same as
CPU, rather than valuing it more than CPU.

Now that I've thought of explaining it, I'll probably organize
the arguments (and devious strategies for solution with smaller
memory and larger CPU) and put them in a blog post or something.

				Bear

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150709/8a4ccd5d/attachment.sig>


More information about the cryptography mailing list