Memory-hard function
In cryptography, a memory hard function (MHF) is a function that costs a significant amount of memory to evaluate. It is different from memory bound functions, the latter incurs cost by slowing down computation through memory latency. MHFs find their use as a form of proof-of-work.
Memory hard measure
There are different ways to measure the memory hardness of a function. A commonly seen measure is Cumulative Memory Complexity (CMC). In a parallel model, CMC measures memory hardness by summing up all the inputs on each step. [1]
Another viable measure is integrating memory against physical time.[2]
Yet another measure is the memory bandwidth consumption on a memory bus.[3] This category of functions are also dubbed "Bandwidth-hard functions".
Motivation
There is a reason why MHFs cost a lot of memory instead of, say, CPU cycles. Bitcoin used repeated evaluation of SHA function as proof of work, but it turned out that modern general purpose processors, i.e. off-the-shelf CPUs are very inefficient when tasked to compute a fixed function over and over. Miners adopted application-specific integrated circuits, ASICs, and achieved 10^16 speedup. While this is fine for what bitcoin is good for, we want a more "egalitarian" hardness measure. That is, there is no short-cuts like ASICs, we want everyone to be equally inefficient to make sure we don't have to make the function too hard for most CPU users to defend against short-cut takers.
Over time, it has been recognized that memory cost remains fairly equal across the board. Hence MHF.
Variants
Based on their evaluation patterns, MHFs can be put into two camps: data-dependent (dMHF) and data-independent (iMHF). dMHFs are that which sometimes you don't know which pieces of information you would still need for later calculations, and iMHFs are ones that there's no such ambiguity. Examples of dMHFs are scrypt, argon2d. Examples of iMHFs are argon2i, catena. Many of these MHFs are developed to be used as password hashing functions exactly because of their memory hardness.
dMHFs have the glaring problem that they are prone to side channel attacks like cache timing. People tend towards iMHFs for this reason, especially when you are doing password hashing. However iMHFs are mathematically proven to have weaker memory hardness properties than dMHFs.
Construction
- depth-robust graph
- scrypt
- brg
References
- ^ (AS15) Alwen, Serbineko, High Parallel Complexity Graphs and Memory-Hard Functions, 2015
- ^ (MO16) Moran, Orlov, Simple Proofs of Space-Time and Rational Proofs of Storage, 2016
- ^ (BR18) Blocki, Ren, Bandwidth-Hard Functions: Reductions and Lower Bounds, 2018