|
== Memory hard measure ==
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 |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>
Other viable measures areinclude 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 |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-11 |access-date=2023-01-11 |website=[[Cryptology ePrint Archive]]}}</ref>
== Motivation ==
MHFs wereare designed to useconsume alarge lotamounts of memory instead of a differentanother resource, suchon as CPUa cyclescomputer. [[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.
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 Memory-Hard Functions (dMHF) and data-independent Memory-Hard Functions (iMHF). dMHFs are MHFs where it is not clear which data is needed for the later steps of evaluating the function until the function is evaluated, while iMHFs are functions where there is no such ambiguity. <!-- this is probably a very confusing explanation, need to change! --> Examples of dMHFs are [[scrypt]] and [[Argon2]]d. Examples of iMHFs are [[Argon2]]i and [[catena (cryptography)|catena]]. Many of these MHFs are developed to be used as [[key derivation function|password hashing function]]s exactly because of their memory hardness.
A notable problem of dMHFs is that they are prone to [[side-channel attack]]s like cache timing. People tend toward iMHFs for this reason, especially for password hashing. However, iMHFs are 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>
|
