Lili Tang
University of Chinese Academy of Sciences, Beijing, China; Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China

Rui Ding
University of Chinese Academy of Sciences, Beijing, China; Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China

Yao Sun
University of Chinese Academy of Sciences, Beijing, China; Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China

Xiaorui Gong
University of Chinese Academy of Sciences, Beijing, China; Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China

Keywords: Wagner’s Algorithm, Equihash, Generalized Birthday Problem

Abstract

The Generalized Birthday Problem (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 Equihash, a memory-hard proof-ofwork scheme constructed upon a single-list variant of Wagner’s algorithm. Due to its robust resistance to ASIC mining, 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 Equihash(200, 9) increases its theoretical time complexity by a factor of 224.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 Equihash parameters, with only an approximate twofold time penalty. For Equihash(144, 5), our optimized algorithm requires only 700 MB of memory, compared to approximately 2.5 GB in previous implementations.