Memory-hard function: Difference between revisions

Revision as of 01:40, 21 August 2023

Revision as of 09:40, 25 August 2023

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 differs from a [[memory-bound function|memory-bound]] function, which incurs cost by slowing down computation through memory latency. MHFs can be used as [[proof of work]].

== Memory hard measure ==

Line 10:

== Motivation ==

MHFs are designed to consume large amounts of memory instead of another resource on a computer. [[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 ASICconstruct ASICs that could evaluate the hash function significantly faster than a CPU.

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.

Line 16:

== 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 is not clear whichspecific data is neededrequired for the later steps of evaluatinga thedMHF functiondepend untilon the functionresults isof evaluated,previous while iMHFs are functions where there is no such ambiguitysteps. <!-- this is probably a very confusing explanation, need to change! --> 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 because of their memory hardness.

A notable problem of 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==