Cryptography

The STARK field

The felt252 type in Cairo refers to elements of the STARK field.

The STARK field is the finite field \(\mathbb{F}_P\), where \(P\) is a prime number defined by:

\[P = 2^{251} + 17*2^{192} + 1\]

The STARK curve

The STARK curve is commonly used in smart contracts but not distinguished by the Starknet protocol.

The STARK curve is an elliptic curve defined over the STARK field by:

\[y^2 \equiv x^3 + \alpha \cdot x + \beta \pmod{P}\]

where:

  • \(\alpha = 1\)

  • \(\beta = 3141592653589793238462643383279502884197169399375105820974944592307816406665\) and the generator point used in the ECDSA scheme is defined by:

  • \(G_x = 874739451078007766457464989774322083649278607533249481151382481072868806602\)

  • \(G_y = 152666792071518830868575557812948353041420400780739481342941381225525861407\)

Hash functions

There are three hash functions used throughout Starknet’s specifications that map inputs to elements in the STARK field.

Starknet Keccak

Starknet Keccak, commonly denoted by \(\text{sn_keccak}\), is defined as the first 250 bits of Ethereum’s keccak256.

Pedersen hash

Pedersen hash is then defined by:

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

where:

  • \(a_{low}\) and \(b_{low}\) are the 248 low of \(a\) and \(b\), respectively

  • \(a_{high}\) and \(b_{high}\) are the 4 high bits of \(a\) and \(b\), respectively

  • The values of the constants \(\text{shift_point}, P_0, P_1, P_2, P_3\) can be found in fast_pedersen_hash.py

  • \([P]_x\) denotes the \(x\) coordinate of point \(P\)

Array hashing

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

Starknet’s version of Poseidon is based on a three-element state Hades permutation and defined of up to 2 elements by:

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

Where \([\cdot]_j\) denotes taking the \(j\)'th coordinate of a tuple.

Array hashing

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 \(\text{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 reference implementations of the above see poseidon_hash.py and poseidon.cairo in the cairo-lang GitHub repository.