Hash functions

Domain and range

All hashes outputs are eventually mapped to elements in \(\mathbb{F}_P\), where \(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. For Starknet Keccak, Keccak256 is augmented in order to fit into a field element.

Pedersen hash

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

For more information, see STARK curve.

Poseidon hash

Poseidon is a family of hash functions designed to be very efficient as algebraic circuits. As such, they can be very useful in ZK-proving systems such as STARKs.

Poseidon is a sponge construction based on the Hades permutation. Starknet’s version of Poseidon is based on a three-element state permutation.

A Poseidon hash of up to 2 elements is defined as follows.

\[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

Additional 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}\]

For an implementation of the above in Python, see poseidon_hash.py, and for an equivalent Cairo implementation, see poseidon.cairo in the cairo-lang GitHub repository.