Memory-hard function

This article has multiple issues. Please help or discuss these issues on the . (Learn how and when to remove these template messages) This article needs additional citations for verification. Please help by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources:  –  ·  ·  · scholar · JSTOR (December 2019) (Learn how and when to remove this template message) This article possibly contains original research. Please by verifying the claims made and adding inline citations. Statements consisting only of original research should be removed. (December 2019) (Learn how and when to remove this template message) This article's tone or style may not reflect the encyclopedic tone used on Wikipedia. See Wikipedia's guide to writing better articles for suggestions. (January 2021) (Learn how and when to remove this template message) (Learn how and when to remove this template message)

In cryptography, a memory-hard function (MHF) is a function that costs significant amount of memory to evaluate. It is different from a memory-bound function; 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. ^[1]

Another viable measure is integrating memory against physical time.^[2]

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

Motivation[]

There is a reason why MHFs cost a lot of memory instead of, for example, CPU cycles. Bitcoin used repeated evaluation of SHA-2 function as proof of work, but it turned out that modern general-purpose processors, i.e. off-the-shelf CPUs, are inefficient when tasked to compute a fixed function many times over. For example, miners adopted application-specific integrated circuits (ASICs) and achieved 10^16 speedup. While this is fine for what Bitcoin is good for, a more "egalitarian" hardness measure was needed. In other words, they wanted everyone to be equally inefficient in computing the function even if they have an ASIC. Because if some people can evaluate the function efficiently and some can't, then in order to make the function relatively hard for the short-cut takers, the made the function too hard for a regular user. If everyone is inefficient, then everyone can evaluate a moderately-hard function.

Over time, it has been recognized that memory cost remains fairly equal across the board. Hence MHF.

Variants[]

Based on their evaluation patterns, MHFs can be put into two camps: data-dependent (dMHF) and data-independent (iMHF). dMHFs are MHFs that don't know which pieces of information are needed for later calculations, and iMHFs are ones where there is no such ambiguity. Examples of dMHFs are scrypt and Argon2d. Examples of iMHFs are Argon2i and catena. Many of these MHFs are developed to be used as password hashing functions exactly because of their memory hardness.

dMHFs have the glaring problem that they are prone to side-channel attacks like cache timing. People tend toward iMHFs for this reason, especially for password hashing. However, iMHFs are mathematically proven to have weaker memory hardness properties than dMHFs.

Construction[]

depth-robust graph[]

For iMHFs in the parallel random oracle model (pROM), it is a known fact that the cumulative pebbling complexity is lower-bounded and upper-bounded by the depth-robustness of a graph.

scrypt[]

bit-reversal-graph[]

References[]