Gotta Hash 'Em All! Speeding Up Hash Functions for Zero-Knowledge Proof Applications

• URL: http://arxiv.org/abs/2501.18780v2
• Date: Sun, 14 Sep 2025 03:19:40 GMT
• Title: Gotta Hash 'Em All! Speeding Up Hash Functions for Zero-Knowledge Proof Applications
• Authors: Nojan Sheybani, Tengkai Gong, Anees Ahmed, Nges Brian Njungle, Michel Kinsy, Farinaz Koushanfar,
• Abstract summary: HashEmAll is a novel collection of FPGA-based realizations for ZK-friendly hash functions.<n>Our evaluation shows that latency-optimized HashEmAll designs outperform CPU implementations by at least $10 times$.<n>This highlights the suitability of HashEmAll for real-world ZKP applications involving large-scale data authentication.
• Score: 9.853088551679969
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Collision-resistant cryptographic hash functions (CRHs) are crucial for security, particularly for message authentication in Zero-knowledge Proof (ZKP) applications. However, traditional CRHs like SHA-2 or SHA-3, while optimized for CPUs, generate large circuits, rendering them inefficient in the ZK domain. Conversely, ZK-friendly hashes are designed for circuit efficiency but struggle on conventional hardware, often orders of magnitude slower than standard hashes due to their reliance on expensive finite field arithmetic. To bridge this performance gap, we present HashEmAll, a novel collection of FPGA-based realizations for three prominent ZK-friendly hashes: Griffin, Rescue-Prime, and Reinforced Concrete. Each offers distinct optimization profiles, with both area-optimized and latency-optimized variants available, allowing users to tailor hardware selection to specific application constraints regarding resource utilization and performance. Our extensive evaluation shows that latency-optimized HashEmAll designs outperform CPU implementations by at least $10 \times$, with the leading design achieving a $23 \times$ speedup. These gains are coupled with lower power consumption and compatibility with accessible FPGAs. Importantly, the highly parallel and pipelined architecture of HashEmAll enables significantly better practical scaling than CPU-based approaches towards building real-world ZKP applications, such as data commitments with Merkle Trees, by mitigating the hashing bottleneck for large trees. This highlights the suitability of HashEmAll for real-world ZKP applications involving large-scale data authentication. We also highlight the ability to translate the HashEmAll methodology to various ZK-friendly hash functions and different field sizes.

Related papers

• Spotlight Attention: Towards Efficient LLM Generation via Non-linear Hashing-based KV Cache Retrieval [67.21678698740267]
  We introduce Spotlight Attention, a novel method that employs non-linear hashing functions to optimize the embedding distribution of queries and keys.<n>We also develop a lightweight, stable training framework using a Bradley-Terry ranking-based loss.
  arXiv  Detail & Related papers  (2025-08-27T10:11:27Z)
• EFFACT: A Highly Efficient Full-Stack FHE Acceleration Platform [15.3973190088728]
  EFFACT is a highly efficient full-stack FHE acceleration platform with a compiler that provides comprehensive optimizations and vector-friendly hardware.<n>For generality, EFFACT is also equipped with an ISA and a compiler backend that can support several FHE schemes like CKKS, BGV, and BFV.
  arXiv  Detail & Related papers  (2025-04-22T12:01:20Z)
• HashAttention: Semantic Sparsity for Faster Inference [91.54218318798603]
  HashAttention is a principled approach casting pivotal token identification as a recommendation problem.<n>It efficiently identifies pivotal tokens for a given query in this Hamming space using bitwise operations.<n>It can reduce the number of tokens used by a factor of $1/32times$ for the Llama-3.1-8B model with LongBench.
  arXiv  Detail & Related papers  (2024-12-19T02:34:15Z)
• if-ZKP: Intel FPGA-Based Acceleration of Zero Knowledge Proofs [3.0009885036586725]
  We present a novel scalable architecture that is suitable for accelerating the zk-SNARK prover compute on FPGAs.<n>We focus on the multi-scalar multiplication (MSM) that accounts for the majority of time spent in zk-SNARK systems.<n>Our implementation runs 110x-150x faster compared to reference software library.
  arXiv  Detail & Related papers  (2024-12-17T02:35:32Z)
• AMAZE: Accelerated MiMC Hardware Architecture for Zero-Knowledge Applications on the Edge [10.803274987172035]
  cryptographic hash (CRH) functions have long been an integral part of providing security and privacy in modern systems. Certain constructions of zero-knowledge proof (ZKP) protocols aim to utilize CRH functions to perform cryptographic hashing. Standard CRH functions, such as SHA2, are inefficient when employed in the ZKP domain. Most mature ZK-friendly hash, MiMC, presents a block cipher and hash function with a simple algebraic structure.
  arXiv  Detail & Related papers  (2024-11-10T03:55:08Z)
• Benchmarking ZK-Friendly Hash Functions and SNARK Proving Systems for EVM-compatible Blockchains [7.520993886306112]
  We benchmarked three SNARK proving systems and five ZK-friendly hash functions, including our self-developed circuit templates for Poseidon2, Neptune, and GMiMC. Our work provides a benchmark for ZK-friendly hash functions and ZK tools, while also exploring cost efficiency and compliance in ZKP-based privacy-preserving transaction protocols.
  arXiv  Detail & Related papers  (2024-09-03T15:19:47Z)
• Performance Evaluation of Hashing Algorithms on Commodity Hardware [0.0]
  This report presents a performance evaluation of three popular hashing algorithms Blake3, SHA-256, and SHA-512. These hashing algorithms are widely used in various applications, such as digital signatures, message authentication, and password storage. The results of the evaluation show Blake3 generally outperforms both SHA-256 and SHA-512 in terms of throughput and latency.
  arXiv  Detail & Related papers  (2024-07-11T08:31:02Z)
• Extreme Compression of Large Language Models via Additive Quantization [59.3122859349777]
  Our algorithm, called AQLM, generalizes the classic Additive Quantization (AQ) approach for information retrieval. We provide fast GPU and CPU implementations of AQLM for token generation, which enable us to match or outperform optimized FP16 implementations for speed.
  arXiv  Detail & Related papers  (2024-01-11T18:54:44Z)
• Large-Scale Distributed Learning via Private On-Device Locality-Sensitive Hashing [11.885388917784804]
  We develop one of the first private, personalized, and memory-efficient on-device LSH frameworks. Our framework enables privacy and personalization by allowing each device to generate hash tables, without the help of a central host. We prove several statistical and sensitivity properties of our hash functions, and experimentally demonstrate that our framework is competitive in training large-scale recommender networks.
  arXiv  Detail & Related papers  (2023-06-05T03:33:26Z)
• A Lower Bound of Hash Codes' Performance [122.88252443695492]
  In this paper, we prove that inter-class distinctiveness and intra-class compactness among hash codes determine the lower bound of hash codes' performance. We then propose a surrogate model to fully exploit the above objective by estimating the posterior of hash codes and controlling it, which results in a low-bias optimization. By testing on a series of hash-models, we obtain performance improvements among all of them, with an up to $26.5%$ increase in mean Average Precision and an up to $20.5%$ increase in accuracy.
  arXiv  Detail & Related papers  (2022-10-12T03:30:56Z)
• Asymmetric Scalable Cross-modal Hashing [51.309905690367835]
  Cross-modal hashing is a successful method to solve large-scale multimedia retrieval issue. We propose a novel Asymmetric Scalable Cross-Modal Hashing (ASCMH) to address these issues. Our ASCMH outperforms the state-of-the-art cross-modal hashing methods in terms of accuracy and efficiency.
  arXiv  Detail & Related papers  (2022-07-26T04:38:47Z)
• ASH: A Modern Framework for Parallel Spatial Hashing in 3D Perception [91.24236600199542]
  ASH is a modern and high-performance framework for parallel spatial hashing on GPU. ASH achieves higher performance, supports richer functionality, and requires fewer lines of code. ASH and its example applications are open sourced in Open3D.
  arXiv  Detail & Related papers  (2021-10-01T16:25:40Z)
• Quantum collision finding for homomorphic hash functions [0.0]
  We present concrete attack examples to provable hash functions, including a preimage attack to $oplus$-linear hash functions. Hash functions which are additive or multiplicative are vulnerable to a quantum attack using the hidden subgroup problem algorithm for quantum computers.
  arXiv  Detail & Related papers  (2021-07-30T23:01:02Z)
• SMYRF: Efficient Attention using Asymmetric Clustering [103.47647577048782]
  We propose a novel type of balanced clustering algorithm to approximate attention. SMYRF can be used as a drop-in replacement for dense attention layers without any retraining. We show that SMYRF can be used interchangeably with dense attention before and after training.
  arXiv  Detail & Related papers  (2020-10-11T18:49:17Z)
• Faster Secure Data Mining via Distributed Homomorphic Encryption [108.77460689459247]
  Homomorphic Encryption (HE) is receiving more and more attention recently for its capability to do computations over the encrypted field. We propose a novel general distributed HE-based data mining framework towards one step of solving the scaling problem. We verify the efficiency and effectiveness of our new framework by testing over various data mining algorithms and benchmark data-sets.
  arXiv  Detail & Related papers  (2020-06-17T18:14:30Z)
• Hashing-based Non-Maximum Suppression for Crowded Object Detection [63.761451382081844]
  We propose an algorithm, named hashing-based non-maximum suppression (HNMS) to efficiently suppress the non-maximum boxes for object detection. For two-stage detectors, we replace NMS in region proposal network with HNMS, and observe significant speed-up with comparable accuracy. Experiments are conducted on CARPK, SKU-110K, CrowdHuman datasets to demonstrate the efficiency and effectiveness of HNMS.
  arXiv  Detail & Related papers  (2020-05-22T23:45:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.