# 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).

## 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.