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.
Where \([\cdot]_j\) denotes taking the j’th coordinate of a tuple
Useful resources:
-
The exact parameters defining the permutation used in Starknet
-
A reference implementation (in c and assembly) of the above by CryptoExperts
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:
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: