Memory-hard function: Difference between revisions

Revision as of 20:35, 25 November 2019

Latest revision as of 20:22, 12 May 2025

(42 intermediate revisions by 21 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" />

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 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 measureIntroduction ==

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>

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>

== Motivation and examples ==

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>

[[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" />

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" />

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".

== Measuring memory hardness ==

== Motivation ==

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>

There is a reason why MHFs cost a lot of memory instead of, say, CPU cycles. Bitcoin used repeated evaluation of SHA function as proof of work, but it turned out that modern general purpose processors, i.e. off-the-shelf CPUs are very inefficient when tasked to compute a fixed function over and over. Miners adopted Application Specific Integrated Circuits, ASICs, and achieve 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.

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>

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). As opposed to iMHFs, the memory access pattern of a dMHF depends on the function input, such as the password provided to a key 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 |editor2-last=Micciancio |editor2-first=Daniele |chapter=Data-Independent Memory Hard Functions: New Attacks and 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 [[catena (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.

dMHFsA havenotable theproblem glaringwith problemdMHFs is that they are prone to [[side -channel attacksattack]]s such likeas cache timing. PeopleThis tendhas towardsresulted iMHFsin fora thispreference reason,for especiallyusing iMHFs when you are doing password hashing passwords. However, iMHFs arehave 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>

== Construction References==

{{Reflist}}

*depth-robust graph

[[Category:Cryptography]]

== References ==