STARK-Friendly Hash

The primary design goal is to drastically reduce the number of multiplication gates in the arithmetic circuit representation. Unlike traditional hashes like SHA-256 which rely on bitwise Boolean operations that are expensive to represent algebraically, STARK-friendly hashes use operations native to large finite fields (e.g., 256-bit fields).

• Poseidon uses a sponge construction with a round function composed of field additions, exponentiations (typically x^5), and linear mixing layers.
• Rescue-Prime employs a similar strategy with alternating S-box layers and affine transformations.
• This design choice directly translates to faster prover times and smaller proof sizes.

These hash functions are constructed to have a low algebraic degree when evaluated as a polynomial. A low-degree round function means the constraint system representing the hash is simpler and requires fewer intermediate variables.

• The S-box (substitution box) is typically a power map like x^3, x^5, or x^{-1} over the field.
• This avoids high-degree polynomial evaluation which would blow up the number of constraints.
• The linear layer is a simple matrix multiplication over the field, which translates to cheap addition gates in the circuit.

STARK-friendly hashes operate directly on elements of the same large finite field used by the zkSTARK protocol itself. This eliminates the costly overhead of bit-decomposition and field emulation required when using traditional hashes.

• Traditional hashes operate on bits and bytes, requiring the circuit to decompose field elements into binary representations.
• A native field hash like Poseidon treats each input word as a single field element, applying operations directly.
• This field-native property is the single biggest factor in the efficiency gap between STARK-friendly and traditional hashes in a ZKP context.

Most STARK-friendly hashes, including Poseidon, are built on the sponge construction, which absorbs input and squeezes output at variable lengths. This provides a flexible cryptographic primitive that can serve as a hash function, a PRF, or a commitment scheme within the same circuit.

• The absorb phase ingests field elements into an internal state.
• The squeeze phase extracts the hash digest.
• This unified design reduces the number of distinct cryptographic gadgets needed in a zkSTARK prover, simplifying the overall circuit architecture.

Despite their structural simplicity, STARK-friendly hashes are designed to resist algebraic cryptanalysis, including Gröbner basis attacks and interpolation attacks. The security analysis focuses on the difficulty of solving the low-degree equations that define the hash.

• The wide trail strategy is adapted for the field setting to ensure diffusion.
• A sufficient number of rounds is chosen to thwart statistical saturation attacks.
• Formal security proofs often reduce the hash's collision resistance to hard problems like the Permuted Kernel Problem or rely on the sponge construction's indifferentiability from a random oracle.

Two leading families illustrate different design philosophies within the STARK-friendly paradigm.

• Poseidon: Optimized for minimal multiplications per round. Uses a dense linear layer and a low-degree S-box (x^5). It is the most widely deployed in production zkEVM rollups.
• Rescue-Prime: Uses an alternating key schedule and a different S-box strategy (often x^3 and x^{-1}) to achieve a higher security margin against algebraic attacks at the cost of slightly more constraints.
• The choice between them depends on the specific circuit size vs. security margin trade-off required by the application.