<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Mon, Jul 27, 2015 at 12:46 PM, 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:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">On Mon, Jul 27, 2015 at 2:29 PM, Bill Cox <<a href="mailto:waywardgeek@gmail.com">waywardgeek@gmail.com</a>> wrote:<br>
> A problem with Momentum as currently implemented is that it can be run with<br>
</span>> reduced memory, enabling efficient GPU attacks.<br>
<br>
Dave Andersen's latest remarks on his GPU code:<br>
<a href="https://bitcointalk.org/index.php?topic=826901.msg11944049#msg11944049" rel="noreferrer" target="_blank">https://bitcointalk.org/index.php?topic=826901.msg11944049#msg11944049</a><br>
You can ask him what he thinks is a faster implementation.<br>
<br>
Fore reduced memory, you can find all collisions in 8MB,<br>
using Cuckoo Cycle's algorithm for finding 2 cycles in bipartite graphs.<br>
<span class=""><br>
>  I think we can get around<br>
> this problem simply by changing the parameters it uses.<br>
<br>
</span><span class="">> If instead, we run with n == 26, and Hb's output also being 26 bits, then we<br>
> get around 2^26 collisions.<br>
<br>
</span>To me, that's a completely different beast.<br>
I would no longer call that Momentum...<br>
<span class="HOEnZb"><font color="#888888"><br>
-John<br>
</font></span></blockquote></div><br></div><div class="gmail_extra">Well, it certainly seems different, at least in terms of optimizations and attacks.  With input/output of Hb set to the same width, I _think_ it is more GPU resistant.  I could be wrong.  I think we can not compute the collisions efficiently in less than around 2^27 bytes, though there's the obvious TMTO option, as usual in Momentum.</div><div class="gmail_extra"><br></div><div class="gmail_extra">If this works as I think it does, without any attacks I'm missing, then I would prefer this version, since it forces an ASIC to use more memory.  I think the main ASIC defense for Momentum is total memory bandwidth.  The latency defense is overcome with buffered radix-sort, but the data still has to be written and read once.</div><div class="gmail_extra"><br></div><div class="gmail_extra">Bill</div></div>