<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Wed, Jul 8, 2015 at 10:11 AM, John Tromp <span dir="ltr"><<a href="mailto:john.tromp@gmail.com" target="_blank">john.tromp@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><span class="">> Is it known whether Momentum and/or Cuckoo are memory-hard?  I don't think<br>
> either are.<br>
<br>
</span>As author of Cuckoo Cycle, let me address your concerns.<br>
<span class=""><br>
> Both claim to be "memory-hard".<br>
<br>
</span>The Cuckoo Cycle project page at <a href="https://github.com/tromp/cuckoo" rel="noreferrer" target="_blank">https://github.com/tromp/cuckoo</a> in fact lists a<br>
<br>
"Linear Time-Memory Trade-Off Bounty<br>
<br>
$500 for an open source implementation that uses at most N/k bits<br>
while running up to 15 k times slower, for any k>=2.<br></blockquote><div><br></div><div>This bounty is for a memory-time trade-off.  I have not analyzed Cuckoo Cycle for TMTO resistance, and only lightly analyzed it for memory*time memory-hardness.  I've focused so far mainly on Momentum's memory-hardness.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">Both of these bounties require N ranging over {2^28,2^30,2^32} and<br>
#threads ranging over {1,2,4,8}, and further assume a high-end Intel<br>
Core i7 or Xeon and recent gcc compiler with regular flags as in my<br>
Makefile."<br>
<br>
The whitepaper at<br>
<a href="https://github.com/tromp/cuckoo/blob/master/cuckoo.pdf?raw=true" rel="noreferrer" target="_blank">https://github.com/tromp/cuckoo/blob/master/cuckoo.pdf?raw=true</a><br>
devotes a Section to Time-Memory Trade-Offs (TMTOs) that further<br>
details the memory hardness claims.<br>
<br>
Which you seem to conveniently ignore in your own notion of memory-hardness :-(<br></blockquote><div><br></div><div>Memory hardness is different than TMTO-resistance.  I use the definitions used by the Catena authors:</div><div><br></div><div><div>"Percival introduced the notion of sequential memory-hardness (SMH), which is satisfied by his introduced password scrambler scrypt. Bases on this notion, an algorithm is sequential memory-hard, if an adversary has no computational advantage in using multiple CPUs, i.e., using b cores requires b times the effort used for one core."</div><div><br></div><div>Your bounty requires that I use less total memory, which will make it hard to find cycles fast.  A proper bounty for sequential-memory-hardness would allow me to use N memory, and any number of CPUs to achieve a target speedup, preferably an unbounded speed-up as the number of CPUs grows.  This is achieved against Momentum with a parallel sorting machine.</div></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
Instead, what you're talking about is covered in the later Section<br>
"Parallelization", which show the gains achievable by using multiple threads. The algorithm you outline is also detailed in the earlier Section<br>
"Cuckoo Cyle basic algorithm" and is in fact what motivates the its name.<br>
<br>
It's almost as if you've gone out of your way to avoid reading the whitepaper:-)</blockquote><div><br></div><div>I read it, but I am focusing primarily on Momentum first, which is far simpler to analyze.  I see you have a mistake in your analysis of Momentum's memory-hardness:</div><div><br></div><div>"Since the extreme case of L = 2 is so special, there is likely to be a greater variety of algorithms that are more efficient than for the general case. While we haven’t found (and don’t know of) a improved main algorithm, we did find an improved BFS(L/2) TMTO algorithm (implemented in momentomatum.cpp) that cuts the memory usage in half, resulting in a slowdown of only 1.75—a lack of memory-hardness."</div><div><br></div><div>There is a trivial TMTO against Scrypt where for a large memory reduction factor N, the runtime is increased by only slightly more than N/4.  Attackers often make use of this.  However, since the memory*time cost is only reduced by at most a constant factor, Scrypt is still considered memory hard.  I am confident this is not the case for Momentum, but not because of your TMTO attack.</div><div><br></div><div>I also doubt Cuckoo Cycle is memory hard, though this needs further analysis.</div><div><br></div><div>Can we focus on Momentum first, and see if there is something special about Cuckoo Cycle that avoids Momentum's flaws?</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><span class=""><br>
> Cuckoo Cycle also claims to be memory-hard, but I don't buy it.  They're<br>
> looking for cycles of length L by building a forest of trees, and detecting<br>
> when loops form, and measuring the length.  If we do a parallel sort as<br>
> above, we can store entries in a Cuckoo hash table<br>
</span>> <<a href="https://en.wikipedia.org/wiki/Cuckoo_hashing" rel="noreferrer" target="_blank">https://en.wikipedia.org/wiki/Cuckoo_hashing</a>> rapidly in parallel.<br>
<br>
You don't need parallel sort for that; the parallel version of the<br>
basic algorithm already does it. But note that:<br>
<br>
1) it uses 32 times more memory than the Cuckoo Cycle reference algorithm<br>
2) the parallel memory accesses are going to form a latency bottleneck when<br>
    the number of threads runs into the hundreds.<br>
<br>
regards,<br>
-John<br>
</blockquote></div><br></div><div class="gmail_extra">My parallel sort algorithm uses the same amount of memory, and I already took into account the latency bottleneck when the number of parallel processing nodes runs into the thousands.</div><div class="gmail_extra"><br></div><div class="gmail_extra">Cuckoo Cycle is a very cool agorithm, as is Momentum, but let's focus on security against parallel attacks using custom ASICs, since this is what we're trying to prevent as a crypto-coin PoW.</div><div class="gmail_extra"><br></div><div class="gmail_extra">A major flaw I have not yet found any good solution for is the slowness of cryptographic hashing algorithms.  I checked the runtime of SHA256 using Intel's latest hardware instructions, and they just aren't fast enough (multiple cycles per byte rather than the other way around).  I think an ASIC attacker will gain a substantial advantage with far faster, lower-power implementations.  I have not seen a PoW system with fast verification yet that avoids this problem.  Until then, for ASIC resistance, I think it is safer to stick with algorithms like Scrypt, or even better, Yescrypt, and possibly Lyra2 or Argon2d.</div><div class="gmail_extra"><br></div><div class="gmail_extra">Bill</div></div>