Memory-hard function: Difference between revisions

Revision as of 01:30, 22 December 2021

Revision as of 17:36, 30 October 2022

Line 2:

{{Multiple issues|{{More citations needed|date=December 2019}}{{original research|date=December 2019}}{{tone|date=January 2021}}}}

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 a [[memory-bound function]];, the latterwhich incurs cost by slowing down computation through memory latency. MHFs findare theirsometimes useused as a form ofin [[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 measuresis memorythe hardnesssum byof summingthe upmemory allrequired theto inputscompute ona eachfunction over every time step. of the computation.<ref>(AS15) Alwen, Serbineko, [https://eprint.iacr.org/2014/238.pdf ''High Parallel Complexity Graphs and Memory-Hard Functions''], 2015</ref><ref>{{Cite journal |last=Alwen |first=Joel |last2=Blocki |first2=Jeremiah |last3=Pietrzak |first3=Krzysztof |date=2017-07-07 |title=Sustained Space Complexity |url=http://arxiv.org/abs/1705.05313 |journal=arXiv:1705.05313 [cs]}}</ref>

Another viable measure is integrating memory against physical time.<ref>(MO16) Moran, Orlov, [https://eprint.iacr.org/2016/035.pdf ''Simple Proofs of Space-Time and Rational Proofs of Storage''], 2016</ref>

Yet another measure is the memory [[bandwidth (computing)|bandwidth]] consumption on a memory bus.<ref>(BR18) Blocki, Ren, [https://eprint.iacr.org/2018/221.pdf ''Bandwidth-Hard Functions: Reductions and Lower Bounds''], 2018</ref> ThisFunctions categorythat ofrequire functionshigh memory bandwidth are also dubbedcalled "bandwidth-hard functions".

== Motivation ==

ThereMHFs iswere adesigned reasonto why MHFs costuse a lot of memory instead of, fora exampledifferent resource, such as CPU cycles. [[Bitcoin]]'s proof-of-work used repeated evaluation of the [[SHA-2]] function as proof of work, but it turned out that modern general-purpose processors, i.e.such as off-the-shelf [[central processing unit|CPUs]], are inefficient when tasked to computecomputing a fixed function many times over. ForSpecialized examplehardware, minerssuch adoptedas [[application-specific integrated circuit]]s (ASICs) and achieved 10^16 speedup. While this is finedesigned for what Bitcoin ismining goodcan for,compute athese morehashes "egalitarian"up hardnessto measure100,000 wastimes neededfaster. InThis other words, they wanted everyoneled to beconcerns equallyabout inefficientthe incentralization computingof themining functionfor evenBitcoin ifand theyother have an ASICcryptocurrencies. Because ifof somethis peopleinequality canbetween evaluateminers theusing function efficientlyASICs and someminers can't,using thenCPUs inor orderoff-the toshelf makehardware, thedesigners functionof relativelylater hardproof-of-work forsystems thewanted short-cutto takers,design thehash madefunctions thefor functionwhich tooit hardwas fordifficult ato regularASIC user.that Ifcould everyoneevaluate isthe inefficient,hash thenfunction everyonesignificantly canfaster evaluatethan a moderately-hard functionCPU.

Over time, it has been demonstrated that memory costs remains relatively constant between CPUs and more specialized hardware, which is why MHFs have found use in cryptocurrency mining. They are also useful in password hashing, because they significantly increase the cost of trying many possible passwords against a leaked database of hashed passwords.

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 putcategorized into two campsdifferent groups based on their evaluation patterns: data-dependent Memory-Hard Functions (dMHF) and data-independent Memory-Hard Functions (iMHF). dMHFs are MHFs thatwhere don'tit knowis whichnot piecesclear ofwhich informationdata areis needed for the later calculationssteps of evaluating the function until the function is evaluated, andwhile iMHFs are onesfunctions where there is no such ambiguity. <!-- this is probably a very confusing explanation, need to change! --> Examples of dMHFs are [[scrypt]] and [[Argon2]]d. Examples of iMHFs are [[Argon2]]i and [[catena (cryptography)|catena]]. Many of these MHFs are developed to be used as [[key derivation function|password hashing function]]s exactly because of their memory hardness.

dMHFsA havenotable theproblem glaringof problemdMHFs is that they are prone to [[side-channel attack]]s 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==