Cryptography

Introduction

Starknet is built on advanced cryptographic primitives that enable scalable, trustless computation using STARK proofs. These include a custom prime field and elliptic curve and multiple hash functions optimized for zero-knowledge performance.

The STARK field

The STARK field is the finite field \(\mathbb{F}_P\), where:

\(P\) = \(2^{251} + 17\cdot2^{192} + 1\) = 3618502788666131213697322783095070105623107215331596699973092056135872020481

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

The STARK curve

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 \(G\) used in the ECDSA scheme is defined by:

  • \(G_x\) = 874739451078007766457464989774322083649278607533249481151382481072868806602

  • \(G_y\) = 152666792071518830868575557812948353041420400780739481342941381225525861407

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

Hash functions

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

Starknet Keccak

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

Pedersen hash

Starknet’s version of the Pedersen hash function 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 the Poseidon hash function 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.

Additional resources