Merkle trees underpin diverse cryptographic systems, from hash-based signatures (e.g., LMS, XMSS) to blockchain (e.g., Bitcoin, Ethereum), post-quantum cryptography (e.g., SPHINCS+), and zero-knowledge protocols. Their strength lies in providing efficient verification with compact authentication paths, making them a fundamental primitive in modern cryptographic systems. Existing acceleration of Merkle trees primarily focuses on assigning parallel processing units (e.g., PEs or CUDA cores) to leaf nodes. However, due to the inherent reduction structure, the number of active computations decreases by half at each upper level, leading to progressively lower hardware utilization, especially for trees with greater depth. Furthermore, existing resource allocation strategies for Merkle tree computations rely on heuristic theoretical approximations, which tend to converge to suboptimal configurations. To address these challenges, we propose MARS, a general GPU-based optimization framework1, and use the Merkle tree–intensive FORS (Forest of Random Subset) component in SPHINCS+as a representative case study. MARS leverages the fixed parameters of FORS as guidance to increase the computational load of individual warps, accelerates the tree-reduction process by minimizing shared memory usage and utilizing registers more effectively, and finally, inspired by automated tuning, applies profiling-guided parallel optimization across multiple Merkle trees to achieve architecture-portable configurations. Compared to the latest GPU-optimized FORS signature generation on RTX4090, MARS achieves signature generation throughput improvements of 2.52×, 2.39× and 2.33× under three different f-parameter sets.

SPHINCS+is a stateless hash-based signature scheme known for its strong post-quantum security, but it suffers from slow signature speed due to the heavy use of hash operations. The parallel architecture of GPUs offers a potential advantage for accelerating the computation of SPHINCS+signatures. However, existing GPU-based optimization efforts for SPHINCS+ either do not fully exploit the inherent parallelism of its Merkle Tree-based structure, or lack fine-grained, compilerlevel customization tailored to its diverse computational kernels. This paper proposes HERO-Sign, which adopts hierarchical tuning methodologies and efficient compiler-time GPU optimizations for SPHINCS+. HERO-Sign rethinks the parallelization potential arising from data independence in SPHINCS+, components, including FORS (Forest of Random Subsets), MSS (Merkle Signature Scheme, and WOTS+(Winternitz One-Time Signature Plus). First, it introduces a Tree Fusion strategy for FORS, whose structure contains a large number of branches. Our FORS Fusion strategy is supported by an automated Tree Tuning search algorithm, allowing it to adapt and optimize fusion schemes across various GPU platforms. To further enhance performance, HERO-Sign adopts an adaptive compilation strategy that accounts for the varying effectiveness of compiler optimizations across different SPHINCS+component kernels (FORS_Sign, TREE_Sign, WOTS+_Sign). This strategy automatically selects between PTX and native branches during the compilation phase to maximize efficiency. For multiple batches of message signatures, HERO-Sign focuses on optimizing kernel-level overlapping and employs a Task Graph-based construction strategy to minimize multi-stream idle time and reduce kernel launch overhead. Compared to state-of-the-art GPU implementations, under the SPHINCS+-128f, SPHINCS+-192f and SPHINCS+256f parameter sets, HERO-Sign demonstrates an enhanced throughput of$\mathbf{1. 2 8} \times \mathbf{- 3. 1 3} \times \mathbf{, ~} \mathbf{1. 2 8} \times \mathbf{- 2. 9 2} \times$, and$\mathbf{1. 2 4} \times \mathbf{- 2. 6 0} \times$on RTX 4090. Similar performance improvements have also been achieved on other architectures, including the A100, H100, and GTX 2080. HERO-Sign also achieves a two-order-of-magnitude reduction in kernel launch latency.