Right, that's why you need ANTI-TMTO modifications in order to force a minimum amount of memory (to thwart botnet-mining).

TMTO works because scrypt writes the memory in-order from 0 to N-1 then reads them in a pseudorandom/unpredictable order; if you didn't save all the odd-numbered words you can recover any one of them on-demand by reading the word before it and doing the mixing operation.  If, on the other hand, you wrote those words in a pseudorandom/unpredictable order as well, TMTO wouldn't be possible (or at least pointlessly time-expensive).



Wow, this is really interesting!  Convenient timing too

So glad you actually wrote a whitepaper.  It's a huge pet peeve of mine when people make some big showy announcement about something and the only clear technical explanation is either their source code or a bunch of random postings scattered across reddit and some webforums .  Thank you for taking the time to do this.

I'm still going through the paper (should finish this weekend) but just one nitpick for now:


That can be true but it depends on the access pattern...  DRAMs have a lot of internal parallelism, so if you can blast reads/writes at a nice uniform stride that matches the bank size you can actually get more or less the whole thing running at once.  GPUs are designed around exploiting this.  The cycle time at the pins is way way way shorter than the cycle time of the internal arrays.  In fact as you move inward from the pins towards the capacitors each stage of circuitry has a longer cycle time than the previous one (sorta like a pyramid).

But yeah, what you say is true if you're doing serially-dependent reads and it's mostly true if the address pattern is pseudorandom.