Re: scrypt time-memory tradeoff

[Solar Designer <solar@openwall.com>]

On Sat, Nov 17, 2012 at 05:20:54AM +0400, Solar Designer wrote:
[...]
> Thus, we have halved our memory needs (circuit area) and paid for this
> by only a 25% increase in processing time.
> 
> Now, if we want to reduce our memory needs a lot more, the situation is
> a lot better (for the defender).

Actually, unless I am mistaken, the area-time product is asymptotically
(by making extreme use of this trade-off) only 25% of what's expected in
the scrypt paper.

Without trade-off, it is 2*N time * N area = 2 * N^2.
With extreme trade-off, it is N+N*N/2 time * 1 area = ~ 0.5 * N^2

For e.g. a 100x reduction in memory, it is:

(100+100*101/2)/200/100 = 0.2575

> Yet for relatively low reduction in
> memory needs - like 2x or 4x - the trade-off favors the attacker.  So an
> attacker with an ASIC will want to use this, and will reduce the cost.

It appears that the trade-off always favors the ASIC-empowered attacker,
reducing the cost to 0.625 at 2x and further down to 0.25 at much higher
ratios.

Apparently, the only reason why GPU Litecoin miners are documented to be
optimal at 2x is that GPUs are not ASICs: they readily have some
resources available for use (including memory and bandwidth), which
would otherwise be partially idle.

> Am I missing something?  If not, does this possibly affect the dollar
> costs presented in the scrypt paper?  Should the dollar cost estimates
> for scrypt be multiplied by 0.5*1.25 = 0.625 (that is, reduced to 62.5%
> of what the paper says)?

Now I think the costs need to be divided by 4.

Alexander