Paper 2025/2141

Memory Optimizations of Wagner's Algorithm with Applications to Equihash

Abstract

The Generalized Birthday Problem ($\textsf{GBP}$) serves as a cornerstone for a broad spectrum of cryptanalytic research. The classical solution, Wagner's $k$-tree algorithm (CRYPTO’02), is characterized by inherently high memory complexity. Subsequently, Biryukov and Khovratovich (NDSS'16) introduced $\textsf{Equihash}$, a memory-hard proof-of-work scheme constructed upon a single-list variant of Wagner's algorithm. Due to its robust resistance to ASIC mining, $\textsf{Equihash}$ has emerged as one of the most widely adopted proof-of-work schemes in blockchain. Memory optimization for Wagner-type algorithms remains a persistent challenge in cryptographic research. Conventional approaches primarily focus on reducing list size to lower memory consumption, yet this strategy typically incurs a prohibitive time penalty. For instance, halving the memory usage of the mining algorithm for $\textsf{Equihash}(200, 9)$ increases its theoretical time complexity by a factor of $2^{24.6}$. In this work, we explore a new optimization direction: List Item Reduction (LIR), which facilitates practical and fine-grained memory-time trade-offs. We systematize existing LIR techniques and propose novel optimization methods integrated into a new hybrid framework. While our approach does not improve asymptotic memory complexity, it achieves a near-linear trade-off in practice, offering substantial benefits for the concrete design of efficient Wagner-style algorithms. Specifically, our techniques reduce peak memory usage by more than 50% (from $> 2nN$ to $nN$ bits) across all $\textsf{Equihash}$ parameters, with only an approximate twofold time penalty. For $\textsf{Equihash}(144,5)$, our optimized algorithm requires only 700 MB of memory, compared to approximately 2.5 GB in previous implementations.