Why do memory-hard functions rely on a time-space trade-off?

Question

I was reading about memory-hard functions recently. In those papers I read, they almost always introduce a time-space trade-off like this:

$$ S(n) \times T(n) \in \Omega(\mathrm{Poly}(n)) $$

I understand memory-hard functions are trying to impose heavy memory usage to counter ASIC attacks. But I don't understand why heavy memory usage must be measured with a time-space trade-off.

There are problems proven to be memory-heavy (at least the most memory-heavy in its class). Search PSPACE and EXPSPACE will return a list of results.

Computational complexity tells us that if a problem requires a lot of memory to run, then it also requires a lot of time to run. Wouldn't these problems be better used as memory-hard functions than those with a time-space trade-off?

Answer 1

In order to create such a function you fill up memory with results of some computation; the memory-hard function then reads these values to further the computation later on.

Rather than saving the values, one could theoretically re-calculate them when needed. So the memory is not really a hard requirement. The memory hard functions are however build in such a way that they require much more computation without memorization of the intermediate values. This is the time / memory trade off.

Answer 2

It is true that many memory-hard functions (MHFs) only give a time-space tradeoff. Take the example of scrypt, which was proven to have optimal cumulative memory complexity $\Omega(n^2)$ in:

Joël Alwen and Binyi Chen and Krzysztof Pietrzak and Leonid Reyzin and Stefano Tessaro: Scrypt is Maximally Memory-Hard. Eurocrypt 2017

Cumulative memory complexity only counts the sum of memory usage over the length of the algorithm. It does not preclude an algorithm taking $O(n^2)$ time but only $O(1)$ space, and indeed it is not hard to see that scrypt does have such an algorithm. From what I understand, this is how it is implemented by most ASICs, so the "optimal memory hardness" (paradoxically) does not prevent folks from evaluating it using basically no memory.

This odd situation is what has inspired more fine-grained definitions of memory-hardness, for example sustained memory complexity:

Joel Alwen and Jeremiah Blocki and Krzysztof Pietrzak: Sustained Space Complexity. Eurocrypt 2018.

Sustained complexity allows you to say things like "to evaluate this function you must use $\Omega(n/\log n)$ amount of memory for $\Omega(n)$ steps." So this is a step in the direction that you suggest.

To answer your specific question:

Computational complexity tells us that if a problem requires a lot of memory to run, then it also requires a lot of time to run. Wouldn't these problems be better used as memory-hard functions than those with a time-space trade-off?

This is more nontrivial than it seems. There is a difficult asymmetry in the requirements for a MHF:

• The honest algorithm is a sequential algorithm that uses $n$ time and $n$ memory
• No parallel algorithm uses significantly less than $n$ time, $n$ space (and ideally requires both simultaneously)

So you have to find a way to rule out speedups from parallelization. And it's actually worse than that, since you also want to rule out speedups from amortization (solving $k$ instances with less $\alpha n$ time and $\beta n$ memory for $\alpha \beta < k$).