Memory-hard function: Difference between revisions

Revision as of 04:17, 12 January 2023

Latest revision as of 20:22, 12 May 2025

(13 intermediate revisions by 6 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" />

{{short description|Computer algorithm that requires a lot of memory}}

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

== Introduction ==

In [[cryptography]], a '''memory-hard function''' (MHF) is a function that costs a significant amount of [[random-access memory|memory]] to evaluate. It differs from a [[memory-bound function]], which incurs cost by slowing down computation through memory latency. MHFs can be used as [[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 ==

MHFs were designed to use a lot of memory instead of a different resource, such as CPU cycles. [[Bitcoin]]'s proof-of-work useduses 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 circuit]]scircuits (ASICs) designed for Bitcoin mining, can computeuse these30,000 hashestimes upless toenergy 100,000per timeshash fasterthan [[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 wanted to designutilised hash functions for which it was difficult to ASICconstruct 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, and a commonly seen measure is Cumulative Memory Complexity (CMC). In a parallel model, CMC is the sum of the memory required to compute a function 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 |last1=Alwen |first1=Joel |last2=Blocki |first2=Jeremiah |last3=Pietrzak |first3=Krzysztof |date=2017-07-07 |title=Sustained Space Complexity |class=cs.CR |eprint=1705.05313 }}</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" />

Other viable measures are 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>, and measuring 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> Functions requiring high memory bandwidth are sometimes referred to as "bandwidth-hard functions."<ref>{{Cite web |last=Blocki |first=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-11 |access-date=2023-01-11 |website=[[Cryptology ePrint Archive]]}}</ref>

== Measuring memory hardness ==

== Motivation ==

There are differentvarious ways to measure the memory hardness of a function,. and aOne commonly seen measure is Cumulativecumulative Memorymemory Complexitycomplexity (CMC). In a parallel model, CMC is the sum of the memory required to compute a function 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 |last1eprint=Alwen1705.05313 |class=cs.CR |first1=Joel |last2last1=BlockiAlwen |first2=Jeremiah |last3last2=PietrzakBlocki |first3title=KrzysztofSustained Space Complexity |date=2017-07-07 |titlelast3=Sustained Space ComplexityPietrzak |classfirst3=cs.CR |eprint=1705.05313 Krzysztof}}</ref>

MHFs were designed to use a lot of memory instead of a different resource, such as CPU cycles. [[Bitcoin]]'s proof-of-work used repeated evaluation of the [[SHA-2]] 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 circuit]]s (ASICs) designed for Bitcoin mining can compute these hashes up to 100,000 times faster. This led to concerns about the centralization of mining for Bitcoin and other cryptocurrencies. Because of this inequality between miners using ASICs and miners using CPUs or off-the shelf hardware, designers of later proof-of-work systems wanted to design hash functions for which it was difficult to ASIC that could evaluate the hash function significantly faster than a CPU.

Other viable measures areinclude integrating memory usage 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>, and measuring 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> Functions requiring high memory bandwidth are sometimes referred to as "bandwidth-hard functions.".<ref>{{Cite web |lastlast1=Blocki |firstfirst1=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-1112 |access-date=2023-01-11 |website=[[Cryptology ePrint Archive]]}}</ref>

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.

== Variants ==

MHFs can be categorized into two different groups based on their evaluation patterns: data-dependent Memorymemory-Hardhard Functionsfunctions (dMHF) and data-independent Memorymemory-Hardhard Functionsfunctions (iMHF). dMHFsAs areopposed MHFsto whereiMHFs, itthe ismemory notaccess clearpattern whichof dataa isdMHF neededdepends foron the laterfunction stepsinput, ofsuch evaluatingas the functionpassword untilprovided theto a key derivation function.<ref>{{Cite isbook evaluated,|last1=Blocki while|first1=Jeremiah iMHFs|last2=Harsha are|first2=Ben functions|last3=Kang where|first3=Siteng there|last4=Lee is|first4=Seunghoon no|last5=Xing such|first5=Lu ambiguity.|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 [[Argon2]]d., Exampleswhile examples of iMHFs are [[Argon2]]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.

A notable problem ofwith dMHFs is that they are prone to [[side-channel attack]]s likesuch as cache timing. PeopleThis tendhas towardresulted iMHFsin fora thispreference reason,for especiallyusing foriMHFs passwordwhen 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>

==References==