Memory-hard function: Difference between revisions

Revision as of 08:03, 30 September 2023

Revision as of 02:59, 1 October 2023

Line 1:

{{short description|ComputerType algorithmof thatcryptographic requires a lot of memoryalgorithm}}

{{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 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 journal |last=Dwork |first=Cynthia |last2=Goldberg |first2=Andrew |last3=Naor |first3=Moni |date=2003 |editor-last=Boneh |editor-first=Dan |title=On Memory-Bound Functions for Fighting Spam |url=https://link.springer.com/chapter/10.1007/978-3-540-45146-4_25 |journal=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}}</ref> MHFs canhave befound useduse asin [[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/4x3ywn/beyond-bitcoin-a-guide-to-the-most-promising-cryptocurrencies |access-date=2023-09-30 |website=Vice |language=en}}</ref><ref name=":0" />

== Introduction ==

Line 8:

== Motivation and examples ==

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

== 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 (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-12 |access-date=2023-01-11 |website=[[Cryptology ePrint Archive]]}}</ref>

== Variants ==