# Memory-hard function

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Memory-hard_function
> Markdown URL: https://mediated.wiki/source/Memory-hard_function.md
> Source: https://en.wikipedia.org/wiki/Memory-hard_function
> Source revision: 1290098532
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{short description|Type of cryptographic algorithm}}In [cryptography](/source/cryptography), a '''memory-hard function''' ('''MHF''') is a function that costs a significant amount of [memory](/source/random-access_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](/source/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](/source/key_stretching) and [proof of work](/source/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" />

== Introduction ==
MHFs are designed to consume large amounts of memory on a computer in order to reduce the effectiveness of [parallel computing](/source/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](/source/application-specific_integrated_circuit)s and [graphics processing units](/source/Graphics_processing_unit), which utilise parallelisation, in computing a MHF for a large number of inputs, such as when [brute-forcing](/source/Brute-force_attack) password hashes or [mining cryptocurrency](/source/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>

== Motivation and examples ==
[Bitcoin](/source/Bitcoin)'s proof-of-work uses repeated evaluation of the [SHA-256](/source/SHA-2) function, but modern general-purpose processors, such as off-the-shelf [CPUs](/source/central_processing_unit), 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](/source/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](/source/Litecoin), which uses [scrypt](/source/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" />

== Measuring memory hardness ==
There are various ways to measure the memory hardness of a function. One 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 |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](/source/bandwidth_(computing)) 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](/source/Cryptology_ePrint_Archive)}}</ref>

== Variants ==

MHFs can be categorized into two different 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](/source/scrypt) and [Argon2](/source/Argon2)d, while examples of iMHFs are [Argon2](/source/Argon2)i and [catena](/source/catena_(cryptography)). Many of these MHFs have been designed to be used as [password hashing function](/source/key_derivation_function)s because of their memory hardness.

A notable problem with dMHFs is that they are prone to [side-channel attack](/source/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==
{{Reflist}}

Category:Cryptography

---
Adapted from the Wikipedia article [Memory-hard function](https://en.wikipedia.org/wiki/Memory-hard_function) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Memory-hard_function?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.