Memory-hard function: Difference between revisions

Revision as of 23:34, 15 October 2020

Latest revision as of 20:22, 12 May 2025

(25 intermediate revisions by 15 users not shown)

Line 1:

{{short description|Type of cryptographic algorithm}}In [[cryptography]], a '''memory-hard function''' ('''MHF''') is a function that costs a significant amount of [[random-access memory|memory]] to efficiently evaluate.<ref name=":0">{{Cite thesis |title=Memory-Hard Functions: When Theory Meets Practice |url=https://escholarship.org/uc/item/7x4630qv |publisher=UC Santa Barbara |date=2019 |language=en |first=Binyi |last=Chen}}</ref> It differs from a [[memory-bound function]], which incurs cost by slowing down computation through memory latency.<ref>{{Cite book |last1=Dwork |first1=Cynthia |last2=Goldberg |first2=Andrew |last3=Naor |first3=Moni |date=2003 |editor-last=Boneh |editor-first=Dan |chapter=On Memory-Bound Functions for Fighting Spam |title=Advances in Cryptology - CRYPTO 2003 |series=Lecture Notes in Computer Science |language=en |___location=Berlin, Heidelberg |publisher=Springer |pages=426–444 |doi=10.1007/978-3-540-45146-4_25 |isbn=978-3-540-45146-4|doi-access=free }}</ref> MHFs have found use in [[key stretching]] and [[proof of work]] as their increased memory requirements significantly reduce the computational efficiency advantage of custom hardware over general-purpose hardware compared to non-MHFs.<ref name=":1">{{Cite web |last=LIU |first=ALEC |date=2013-11-29 |title=Beyond Bitcoin: A Guide to the Most Promising Cryptocurrencies |url=https://www.vice.com/en/article/beyond-bitcoin-a-guide-to-the-most-promising-cryptocurrencies/ |access-date=2023-09-30 |website=Vice |language=en}}</ref><ref name=":0" />

{{Multiple issues|{{refimprove|date=December 2019}}{{original research|date=December 2019}}}}

== Introduction ==

In [[cryptography]], a '''memory hard function''' (MHF) is a function that costs 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]].

MHFs are designed to consume large amounts of memory on a computer in order to reduce the effectiveness of [[parallel computing]]. In order to evaluate the function using less memory, a significant time penalty is incurred. As each MHF computation requires a large amount of memory, the number of function computations that can occur simultaneously is limited by the amount of available memory. This reduces the efficiency of specialised hardware, such as [[application-specific integrated circuit]]s and [[Graphics processing unit|graphics processing units]], which utilise parallelisation, in computing a MHF for a large number of inputs, such as when [[Brute-force attack|brute-forcing]] password hashes or [[Cryptocurrency|mining cryptocurrency]].<ref name=":0" /><ref name=":2">{{Cite book |last1=Biryukov |first1=Alex |last2=Khovratovich |first2=Dmitry |date=2015 |editor-last=Iwata |editor-first=Tetsu |editor2-last=Cheon |editor2-first=Jung Hee |chapter=Tradeoff Cryptanalysis of Memory-Hard Functions |title=Advances in Cryptology – ASIACRYPT 2015 |series=Lecture Notes in Computer Science |language=en |___location=Berlin, Heidelberg |publisher=Springer |pages=633–657 |doi=10.1007/978-3-662-48800-3_26 |isbn=978-3-662-48800-3|doi-access=free }}</ref>

== MemoryMotivation hardand measureexamples ==

[[Bitcoin]]'s proof-of-work uses repeated evaluation of the [[SHA-2|SHA-256]] function, but modern general-purpose processors, such as off-the-shelf [[central processing unit|CPUs]], are inefficient when computing a fixed function many times over. Specialized hardware, such as application-specific integrated circuits (ASICs) designed for Bitcoin mining, can use 30,000 times less energy per hash than [[x86]] CPUs whilst having much greater hash rates.<ref name=":2" /> This led to concerns about the centralization of mining for Bitcoin and other cryptocurrencies.<ref name=":2" /> Because of this inequality between miners using ASICs and miners using CPUs or off-the shelf hardware, designers of later proof-of-work systems utilised hash functions for which it was difficult to construct ASICs that could evaluate the hash function significantly faster than a CPU.<ref name=":1" />

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. <ref>(AS15) Alwen, Serbineko, [https://eprint.iacr.org/2014/238.pdf ''High Parallel Complexity Graphs and Memory-Hard Functions''], 2015</ref>

As memory cost is platform-independent,<ref name=":0" /> MHFs have found use in cryptocurrency mining, such as for [[Litecoin]], which uses [[scrypt]] as its hash function.<ref name=":1" /> 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 without significantly increasing the computation time for legitimate users.<ref name=":0" />

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>

== Measuring memory hardness ==

Yet another measure is the memory 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> This category of functions are also dubbed "Bandwidth-hard functions".

There are differentvarious ways to measure the memory hardness of a function. AOne commonly seen measure is Cumulativecumulative Memorymemory Complexitycomplexity (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 arXiv |eprint=1705.05313 |class=cs.CR |first1=Joel |last1=Alwen |first2=Jeremiah |last2=Blocki |title=Sustained Space Complexity |date=2017-07-07 |last3=Pietrzak |first3=Krzysztof}}</ref>

Other viable measures include integrating memory usage against time and measuring memory [[bandwidth (computing)|bandwidth]] consumption on a memory bus. Functions requiring high memory bandwidth are sometimes referred to as "bandwidth-hard functions".<ref>{{Cite web |last1=Blocki |first1=Jeremiah |last2=Liu |first2=Peiyuan |last3=Ren |first3=Ling |last4=Zhou |first4=Samson |date=2022 |title=Bandwidth-Hard Functions: Reductions and Lower Bounds |url=https://eprint.iacr.org/2018/221.pdf |url-status=live |archive-url=https://web.archive.org/web/20230112040047/https://eprint.iacr.org/2018/221.pdf |archive-date=2023-01-12 |access-date=2023-01-11 |website=[[Cryptology ePrint Archive]]}}</ref>

== 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 [[Central processing unit|CPUs]] are very inefficient when tasked to compute a fixed function over and over. Miners adopted [[Application-specific integrated circuit|application-specific integrated circuits]], ASICs, and achieved 10^16 speedup. While this is fine for what bitcoin is good for, we want a more "egalitarian" hardness measure. In other words, we want 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, we will make 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 putcategorized into two campsdifferent groups based on their evaluation patterns: data-dependent memory-hard functions (dMHF) and data-independent memory-hard functions (iMHF). dMHFsAs areopposed thatto whichiMHFs, sometimesthe youmemory don'taccess know which piecespattern of informationa youdMHF woulddepends stillon needthe forfunction later calculationsinput, andsuch iMHFsas arethe onespassword thatprovided there'sto noa suchkey ambiguity.derivation function.<!ref>{{Cite book |last1=Blocki |first1=Jeremiah |last2=Harsha |first2=Ben |last3=Kang |first3=Siteng |last4=Lee |first4=Seunghoon |last5=Xing |first5=Lu |last6=Zhou |first6=Samson |date=2019 |editor-last=Boldyreva |editor-first=Alexandra this|editor2-last=Micciancio is|editor2-first=Daniele probably|chapter=Data-Independent aMemory veryHard confusingFunctions: explanation,New needAttacks toand change!Stronger Constructions |chapter-url=https://link.springer.com/chapter/10.1007/978-3-030-26951-7_20 |title=Advances in Cryptology – CRYPTO 2019 |series=Lecture Notes in Computer Science |language=en |___location=Cham |publisher=Springer International Publishing |pages=573–607 |doi=10.1007/978-3-030-26951-7_20 |isbn=978-3-030-26951-7}}</ref> Examples of dMHFs are [[scrypt]], and [[argon2Argon2]]d., Exampleswhile examples of iMHFs are [[argon2Argon2]]i, and [[Catenacatena (cryptography)|catena]]. Many of these MHFs arehave been developeddesigned to be used as [[key derivation function|password hashing function]]s exactly because of their memory hardness.

dMHFs have the glaring problem that they are prone to side channel attacks like cache timing. People tend towards iMHFs for this reason, especially when you are doing 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===

A notable problem with dMHFs is that they are prone to [[side-channel attack]]s such as cache timing. This has resulted in a preference for using iMHFs when hashing passwords. However, iMHFs have been mathematically proven to have weaker memory hardness properties than dMHFs.<ref>Alwen, J., Blocki, J. (2016). [https://doi.org/10.1007/978-3-662-53008-5_9''Efficiently Computing Data-Independent Memory-Hard Functions.'']</ref>

== References ==

<references />

== References ==

{{Reflist}}

[[Category:Cryptography]]