Lili Tang, Rui Ding, Yao Sun, Xiaorui Gong

Memory Optimizations of Wagner’s Algorithm with Applications to Equihash

Introduction

Memory optimizations of wagner’s algorithm with applications to equihash. Optimize Wagner's algorithm for Equihash, a blockchain PoW. Our LIR method reduces peak memory over 50% with minimal time impact, significantly boosting cryptographic efficiency.

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.

Full Text

Comments

You need to be logged in to post a comment.