Memory hard function (MHF) is a family of functions 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 popular 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".
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