# What does “sequential memory-hard” mean?

I found this term in Scrypt's paper. I have several questions about its meaning, ranging from how to parse it, to theoretical bounds:

### Q1: How to parse it?

• Is it read (sequential memory)-hard?
• Or sequential (memory-hard)?

### Q2: What does it mean?

• Does it mean that as space is linearly reduced, then penalty is that is exponentially increased?
• Can we tell what is that exponent? Or does suffice to simply be an exponent, regardless of which exponent?
• In current practice, can we say something more specific about what that exponent for state-of-art functions beyond just "it's exponential"? I think it is within reach to make more specific claims.
• Ideally, is there any theorem that shows an upper bound for this exponent? E.g. can we say, for every reduced single unit of memory, amount of computation performed doubles? Tripples? Quadruples? ...?

### Q3: Any better name?

• Is the name used in Scrypt's paper still the most accurate name?
• Is there a better name for it that the cool kids like to use nowadays more? In Argon2's paper, as well as Here, it seems to be called memory-hard. Does it mean that memory-hard is the better name to adopt? E.g. what do the coolest gurus in top cryptographic journals tend to use?
• Optional: any reason the Scrypt paper didn't call it memory-hard? Or was it just the randomness of life?

### Appendix

I did look at previous related answers, and I found these:

• This only asks about such functions in relation to another function. Thus doesn't dig deep into what such functions are in themselves.
• This only asks about the motivations of such functions.
• This asks whether his function is a good one among such functions.

The Scrypt paper here defines memory-hard and sequential memory hard, and accordingly explains why one was used over the other.

Definition 1. A memory-hard algorithm on a Random Access Machine is an algorithm which uses $$S(n)$$ space and $$T(n)$$ operations, where $$S(n) \in \Omega (T(n)^{1-\epsilon})$$

Definition 2. A sequential memory-hard function is a function which

(a) can be computed by a memory-hard algorithm on a Random Access Machine in $$T(n)$$ operations; and
(b) cannot be computed on a Parallel Random Access Machine with $$S∗(n)$$ processors and $$S ∗(n)$$ space in expected time $$T∗(n)$$ where $$S∗(n)T∗(n) =\mathcal{O}(T(n)^{2-x})$$ for any $$x > 0$$.

Put another way, a sequential memory-hard function is one where not only the fastest sequential algorithm is memory-hard, but additionally where it is impossible for a parallel algorithm to asymptotically achieve a significantly lower cost. Since memory-hard algorithms asymptotically come close to using the most space possible given their running time, and memory is the computationally usable resource general-purpose computers have which is most expensive to reproduce in hardware , we believe that, for any given running time on a sequential general-purpose computer, functions which are sequential memory-hard come close to being the most expensive possible functions to compute in hardware.

• What does $1- \epsilon$ do? Couldn't find it in paper. – caveman Jan 5 at 21:07
• Is Argon2 not sequential memory hard? But just memory hard? Any reason Argon2 didn't do it like Scrypt? – caveman Jan 5 at 21:16
• Good question, I've asked it here. – Modal Nest Jan 5 at 21:44
• Just to help others understand what I'm lacking: I read those quotes from the Scrypt paper, but I'm not sure if I understood them correctly, and historically I tent to misunderstand things, so I'm too wary to trust my thoughts. Hence I'd really appreciate if someone could specifically answer my sub-questions under my questions. Specifically, the 4 questions under Q2. (side note: thanks a lot for posting that question. It helps me a lot.) – caveman Jan 7 at 20:02
• @caveman I'll probably ask a follow-up to that as it appears difficult to answer. I've edited the answer to include the fuller explanation. I think your Q2 is answered as it's sub-questions rely on a meaning not defined in the paper. It might be better to ask another question that gets to the crux of your question, and is self-contained. – Modal Nest Jan 8 at 10:14