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.