Memory-bound function (often abbreviated MBF) is a class of computational functions whose execution time is deliberately limited primarily by the latency and bandwidth of a system’s main memory rather than by the speed of the central processing unit (CPU). By making the dominant cost of evaluating the function the time required to perform memory accesses, an MBF achieves a runtime that is relatively invariant across processors with differing clock speeds or instruction‑level performance.
Definition
An MBF is designed so that:
- The algorithm requires a large number of memory reads or writes that cannot be effectively cached or pre‑fetched.
- The amount of computation per memory access is small, ensuring that CPU cycles are not the bottleneck.
- The total runtime scales with the characteristics of the memory subsystem (e.g., latency, bandwidth, cache hierarchy) rather than with raw CPU speed.
Consequently, MBFs are considered memory‑bound as opposed to CPU‑bound functions, whose performance is dictated mainly by processor capabilities.
Design Principles
| Principle | Description |
|---|---|
| Large Working Set | The function accesses a data set that exceeds the size of typical CPU caches, forcing frequent main‑memory accesses. |
| Low Computational Intensity | Each memory operation performs minimal arithmetic or logical work, keeping CPU utilization low. |
| Deterministic Access Pattern | The pattern of memory accesses is either fixed or derived from the input in a way that cannot be predicted to allow pre‑fetching. |
| Uniform Cost Across Architectures | Because memory latency is less variable than CPU speed across platforms, the function’s runtime remains comparable on diverse hardware. |
Applications
| Domain | Use of MBFs |
|---|---|
| Proof‑of‑Work (PoW) Systems | MBFs have been employed in client‑puzzle schemes to mitigate denial‑of‑service attacks, where the cost to solve a puzzle is tied to memory latency, limiting advantages of powerful CPUs. |
| Spam Mitigation | Early anti‑spam proposals used MBFs to require senders to perform a memory‑intensive computation before accepting an email, deterring mass spamming. |
| Password Hashing and Key Derivation | Functions such as scrypt and Argon2 are classified as memory‑hard (a superset of memory‑bound) to resist GPU and ASIC attacks; they incorporate MBF‑like characteristics. |
| Cryptographic Protocols | Some key‑exchange and commitment schemes incorporate MBFs to balance computational effort across participants. |
Notable Examples
- Laurie–Zwick MBF (1999) – Introduced by Ben Laurie and Geoffrey Zwick as a proof‑of‑work function where the evaluator must repeatedly access a large pseudo‑random data table stored in main memory. |
- scrypt – A password‑based key derivation function that requires a configurable amount of memory, making it memory‑bound for typical parameter choices. |
- Argon2 – The winner of the Password Hashing Competition (PHC) includes Argon2d (data‑dependent memory accesses) and Argon2i (data‑independent accesses), both exhibiting strong memory‑bound properties. |
Security and Performance Considerations
- Resistance to Parallelism – Because the function’s critical path is memory latency, parallel execution on many cores or GPUs yields limited speedup, unlike CPU‑bound hashes.
- Parameter Selection – The security of an MBF depends on the size of the memory region and the number of accesses; insufficient parameters can render the function vulnerable to optimization.
- Hardware Variability – While MBFs aim for platform‑independent cost, extreme differences in memory hierarchy (e.g., embedded devices with very low‑latency memory) can affect absolute runtime.
See also
- Memory‑hard function
- Proof‑of‑work
- Cache‑timing attacks
- Computational complexity (memory‑bound vs. CPU‑bound)
References
- Laurie, B., & Zwick, G. (1999). Memory‑Bound Functions. Proceedings of the 1999 USENIX Security Symposium.
- Percival, C. (2009). Stronger Key Derivation via scrypt. International Conference on Network and Distributed System Security (NDSS).
- Biryukov, A., Dinu, D., & Khovratovich, D. (2016). Argon2: the memory‑hard function for password hashing and proof‑of‑work. Password Hashing Competition.
This entry reflects the consensus of peer‑reviewed literature and authoritative technical reports up to the knowledge cutoff date.
