<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">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>You wrote in the paper:</div><div><br></div><div>"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."</div><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>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?</div><div><br></div><div>Thanks,</div><div>Bill</div></div></div></div>