Rescue Hash

Rescue Hash is a zk-friendly cryptographic hash function, meaning it is optimized for efficiency within zero-knowledge proof (ZKP) and validity proof systems like STARKs and SNARKs. Unlike traditional hash functions such as SHA-256, its mathematical operations are designed to be easily representable as arithmetic circuits, which drastically reduces the computational overhead of generating proofs about hashed data. This makes it a core primitive for blockchain scalability solutions like zkRollups and privacy-preserving applications.

The function is built upon the Rescue-Prime algorithm, a sponge construction that operates over a prime field. Its design uses a set of carefully chosen operations—including non-linear S-boxes and linear layers—that are efficient in fields commonly used in ZK proofs (e.g., the Goldilocks field). This contrasts with hash functions that rely on binary operations, which are notoriously expensive to prove in ZK. The result is a hash that is both provably secure against known cryptanalytic attacks and orders of magnitude faster to use within a proving system.

A primary application of Rescue Hash is in STARK-based systems, such as those developed by StarkWare. Here, it functions as the Merkle tree hash for committing to large batches of transactions in a zkRollup, enabling high-throughput and low-cost settlements on a layer 1 blockchain like Ethereum. Its efficiency is critical for keeping proof generation times and costs manageable, which is essential for the practical deployment of layer 2 scaling solutions.

When comparing hash functions, Poseidon is another major zk-friendly alternative. While both are designed for similar use cases, they differ in their underlying mathematical approaches and parameter choices. The selection between Rescue, Poseidon, or other functions often depends on the specific proof system, the chosen elliptic curve, and the required balance between proof generation speed, verification cost, and security parameters within a given protocol's architecture.

The Rescue hash function is a zk-friendly cryptographic primitive built on the Sponge construction, similar to SHA-3, but optimized for operations in finite fields used by zero-knowledge proof (ZKP) systems like STARKs. Its core innovation is using non-linear operations that are efficient to compute and verify within the constraints of an arithmetic circuit, making it significantly faster than traditional hash functions like SHA-256 in a ZKP context. This efficiency is critical for applications such as ZK-Rollups and private transactions, where proof generation speed directly impacts scalability and cost.

At its heart, Rescue operates over a prime field and employs a series of rounds, each consisting of a non-linear layer and a linear layer. The non-linear layer uses power maps (like x^α) that are carefully chosen to be invertible and efficient in the target field. The linear layer applies an MDS (Maximum Distance Separable) matrix to provide diffusion, ensuring that a small change in the input propagates throughout the entire state. This combination creates a secure permutation that is resistant to cryptanalysis while remaining arithmetization-friendly.

The design parameters of Rescue, such as the alpha exponent, state size, and number of rounds, are selected based on security proofs and performance requirements for a given field. For instance, a common instantiation uses a state of 12 field elements and α=5. Its security is analyzed in the algebraic group model, providing confidence in its resilience against attacks like Gröbner basis analysis, which are particularly relevant in the ZKP setting where adversaries can exploit the algebraic structure.

In practice, Rescue enables the efficient construction of Merkle trees and commitment schemes within ZKPs. For example, a STARK-based rollup might use a Rescue-based Merkle tree to commit to a batch of transactions. The prover can then generate a proof that they know a valid Merkle path without revealing the underlying data. Compared to using a Pedersen hash or Poseidon, Rescue often provides a different trade-off between constraint count and security, making it a versatile tool in the cryptographer's toolkit for designing scalable blockchain protocols.

The Rescue hash function is a cryptographic primitive specifically designed for zero-knowledge proof (ZKP) and STARK systems, prioritizing efficiency in arithmetic circuits over traditional binary fields. Unlike SHA-256 or Keccak, which are optimized for software and hardware on binary data, Rescue operates directly over prime fields (like the STARK-friendly prime field), making its operations—addition, multiplication, and inversion—native to the proof system's arithmetic. This design eliminates the need for costly bitwise operations within a proof, dramatically reducing the number of constraints and computational overhead during proof generation and verification.

Its core security and efficiency stem from a sponge construction and a permutation built from a set of low-degree power maps (e.g., x^α and x^{1/α}) and MDS matrices. The carefully chosen alpha exponent (commonly 3 or 5) and its inverse create a permutation that is both algebraically simple—keeping the constraint count low—and cryptographically robust, providing resistance against known attacks like Gröbner basis analysis. The use of an MDS matrix ensures strong diffusion, spreading the influence of each input bit across the entire state. This combination results in a function that is ZK-friendly, meaning it minimizes the prover's work while maintaining the required security guarantees for applications like Merkle tree commitments and digital signatures within ZK rollups.

The arithmetization of Rescue—translating its algorithm into a set of polynomial constraints for a proof system—is exceptionally clean. Each round of the permutation translates into a fixed set of arithmetic operations (additions and multiplications) that map directly to R1CS or AIR constraints without complex decompositions. This property makes Rescue a prime example of algebraic hash function design, where the entire cryptographic specification is expressed in the language of finite field arithmetic that proof systems natively understand. Its performance is benchmarked by metrics such as constraint count and multiplicative complexity, where it consistently outperforms adaptations of traditional hashes in ZK contexts.

In practical deployment, Rescue is often instantiated with parameters like Rescue-Prime, which fine-tunes the round count and constants for a specific security level and field. It forms the backbone of several production systems, including the zkSync rollup and the StarkWare ecosystem, where it hashes transaction data and state roots. Its design rationale represents a paradigm shift: instead of adapting general-purpose cryptography to ZK, it builds cryptography from the ground up with the proof system's arithmetic circuit as the primary computational model, optimizing for the prover's most expensive operations.