Memory-hard function: Difference between revisions

Revision as of 20:36, 25 November 2019

Revision as of 20:38, 25 November 2019

Line 1:

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

== Memory hard measure ==

Line 9:

== Motivation ==

There is a reason why MHFs cost a lot of memory instead of, say, CPU cycles. [[Bitcoin]] used repeated evaluation of [[SHA-2|SHA]] function as proof of work, but it turned out that modern general purpose processors, i.e. off-the-shelf CPUs[[Central processing unit|CPU]]<nowiki/>s are very inefficient when tasked to compute a fixed function over and over. Miners adopted [[Application-specific Specificintegrated circuit|application-specific Integratedintegrated Circuitscircuits]], ASICs, and achieved 10^16 speedup. While this is fine for what bitcoin is good for, we want a more "egalitarian" hardness measure. That is, there is no short-cuts like ASICs, we want everyone to be equally inefficient to make sure we don't have to make the function too hard for most CPU users to defend against short-cut takers.

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