Memory-hard function

In cryptography, a memory hard function (MHF) is a function that costs a significant amount of memory to evaluate. It is different from memory bound functions, the latter incurs cost by slowing down computation through memory latency. MHFs find their use as a form of proof-of-work.

Memory hard measure

There are different ways to measure the memory hardness of a function. A commonly seen measure is Cumulative Memory Complexity (CMC). In a parallel model, CMC measures memory hardness by summing up all the inputs on each step.

Another viable measure is integrating memory against physical time.

Yet another measure is the memory bandwidth consumption on a memory bus. This category of functions are also dubbed "Bandwidth-hard functions".

Motivation

There is a reason why MHFs cost a lot of memory instead of, say, CPU cycles.

Variants

Based on their evaluation patterns, MHFs can be put into two camps: data-dependent (dMHF) and data-independent (iMHF). Examples of dMHFs are scrypt, argon2d. Examples of iMHFs are argon2i, catena. Many of these MHFs are developed to be used as key derivation functions exactly because of their memory hardness.