1
$\begingroup$

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.
$\endgroup$
4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ What does $1- \epsilon$ do? Couldn't find it in paper. $\endgroup$
    – caveman
    Jan 5 at 21:07
  • $\begingroup$ Is Argon2 not sequential memory hard? But just memory hard? Any reason Argon2 didn't do it like Scrypt? $\endgroup$
    – caveman
    Jan 5 at 21:16
  • 1
    $\begingroup$ Good question, I've asked it here. $\endgroup$
    – Modal Nest
    Jan 5 at 21:44
  • $\begingroup$ 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.) $\endgroup$
    – caveman
    Jan 7 at 20:02
  • $\begingroup$ @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. $\endgroup$
    – Modal Nest
    Jan 8 at 10:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.