# Hash functions

## Domain and range

All hashes outputs are eventually mapped to elements in $$\mathbb{F}_p$$ with $$p=2^{251}+17\cdot 2^{192}+1$$.

There are three hash functions used throughout Starknet’s specifications:

• $$sn\_keccak: \{0,1\}^* \rightarrow \mathbb{F}_p$$

• $$pedersen: \mathbb{F}_p^2\rightarrow\mathbb{F}_p$$

• $$poseidon: \mathbb{F}_p^*\rightarrow \mathbb{F}_p$$

## Starknet Keccak

Starknet keccak, usually denoted by $$sn\_keccak$$, is defined as the first 250 bits of the Keccak256 hash (this is just Keccak256 augmented in order to fit into a field element).

## Pedersen hash

### STARK curve

Pedersen hash makes use of the following STARK friendly elliptic curve over $$\mathbb{F}_p$$:

$y^2=x^3+\alpha x +\beta$

where

• $$\alpha=1$$

• $$\beta = 3141592653589793238462643383279502884197169399375105820974944592307816406665$$

### Definition

Given an input $$(a,b)\in\mathbb{F}_p^2$$, we begin by breaking it into $$a_{low}, a_{high}, b_{low}, b_{high}$$, where the low part consists of the low 248 bits of the element and the high part consists of the high 4 bits of the element. Our Pedersen hash is then defined by:

$h(a,b) = \left[shift\_point + a_{low} \cdot P_0 + a_{high} \cdot P1 + b_{low} \cdot P2 + b_{high} \cdot P3\right]_x$

where the values of the constants $$shift\_point, P_0, P_1, P_2, P_3$$ can be found in fast_pedersen_hash.py, and $$[P]_x$$ denotes the $$x$$ coordinate of the point $$P$$.

## Poseidon hash

Poseidon is a family of hash functions designed for being very efficient as algebraic circuits. As such, they may be very useful in ZK proving systems such as STARKs and others.

Poseidon is a sponge construction based on the Hades permutation. Starknet’s version of Poseidon is based on a three element state permutation (see exact parameters below).

We define the Poseidon hash of up to 2 elements below, see below the arbitrary number of inputs version.

$poseidon_1(x) := \left[\text{hades_permutation}(x,0,1)\right]_0$
$poseidon_2(x,y) := \left[\text{hades_permutation}(x,y,2)\right]_0$

Where $$[\cdot]_j$$ denotes taking the j’th coordinate of a tuple

Useful resources:

## Array hashing

### Pedersen

Let $$h$$ denote the pedersen hash function, then given an array $$a_1,...,a_n$$ of $$n$$ field elements we define $$h(a_1,...,a_n)$$ to be:

$h(...h(h(0, a_1),a_2),...,a_n),n)$

### Poseidon

Let $$\text{hades}:\mathbb{F}_p^3\rightarrow\mathbb{F}_p^3$$ denote the Hades permutation (with Starknet’s parameters), then given an array $$a_1,...,a_n$$ of $$n$$ field elements we define $$poseidon(a_1,...,a_n)$$ to be the first coordinate of $$H(a_1,...,a_n;0,0,0)$$, where:

$H(a_1,...,a_n;s_1,s_2,s_3)=\begin{cases} H\big(a_3,...,a_n;\text{hades}(s_1+a_1, s_2+a_2, s_3)\big), & \text{if } n\ge 2 \\ \text{hades}(s_1+a_1,s_2+1,s_3), & \text{if } n=1 \\ \text{hades}(s_1+1,s_2,s_3), & \text{if } n=0 \\ \end{cases}$

You can find an implementation of the above in Python here, and an equivalent Cairo implementation here.