What are, quantitatively, the pros and cons of fixed versus variable memory access pattern in Password-Based Hashing, Entropy-Stretching Key Derivation functions, and Proof-of-Work applications?
Modern PBH, ESKDF, and PoW techniques all leverage memory as a way to increase the investment cost (perhaps operating cost?) of brute-force search/attack. Some, like Balloon, use a fixed memory access pattern, with that rationale:
Resistant to Cache Attacks. The memory access pattern of the Balloon hash function is independent of the password being hashed. Thus, an adversary who can observe the memory access patterns of a Balloon computation, e.g. via cache side-channels on a multi-user system, learns no information about the password being hashed.
Others, like Scrypt, make the indexes in memory strongly data-dependent. That can be as part of their argument of memory hardness, or/and with the rationale that it makes using cost-effective large but slow memory (or is it SIMD / GPU) less attractive to an attacker.
Argon2 has three variants: Argon2i, Argon2d, and Argon2id. Argon2d is faster and uses data-depending memory access, which makes it highly resistant against GPU cracking attacks and suitable for applications with no threats from side-channel timing attacks (eg. cryptocurrencies). Argon2i instead uses data-independent memory access, which is preferred for password hashing and password-based key derivation, but it is slower as it makes more passes over the memory to protect from tradeoff attacks. Argon2id is a hybrid of Argon2i and Argon2d, using a combination of data-depending and data-independent memory accesses, which gives some of Argon2i's resistance to side-channel cache timing attacks and much of Argon2d's resistance to GPU cracking attacks.