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.
Another popular measure is integrating memory against physical time.[1]
Yet another measure is the memory bandwidth consumption on a memory bus.[2]
References
- ^ (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