Starknet state

The state of Starknet consists of:

  • Contract classes: a mapping between class hash and the class definition

  • Contract instances: a mapping between addresses (251-bit field elements) and the contract’s state.

A contract state consists of:

  • Class hash: defines the functionality of the contract

  • Contract storage: a key-value mapping where the key/values are field elements

  • Contract nonce: the number of transactions sent from this contract

With the above definition, we can provide a brief sketch of Starknet’s transition function. A transaction \(tx\) transitions the system from state \(S\) to state \(S'\) if:

  • \(tx\) is an invoke transaction, and the storage of \(S'\) is the result of executing the target contract code with respect to the previous state \(S\) (the arguments, contract address, and the specific entry point are part of the transaction)

  • \(tx\) is a deploy_account transaction, and \(S'\) contains the new contract’s state at the contract’s address. Additionally, the storage of \(S\) is updated according to the execution of the contract’s constructor.

  • \(tx\) is a declare transaction, and \(S'\) contains the class hash and definition in the contract classes mapping

State commitment

The state commitment is a digest which uniquely (up to hash collisions) encodes the state. In Starknet, the commitment combines the roots of two binary Merkle-Patricia trees of height 251 in the following manner:

state_commitment = ℎ(
    "STARKNET_STATE_V0",
    contracts_tree_root,
    classes_tree_root
)

Where:

  • \(h\) is the Poseidon hash function

  • STARKNET_STATE_V0 is a constant prefix string encoded in ASCII (and represented as a field element).

  • contracts_tree_root is the root of the Merkle-Patricia tree whose leaves are the contracts states, see below

  • classes_tree_root is the root of the Merkle-Patricia tree whose leaves are the compiled class hashes, see below

The contracts tree

Like Ethereum, this is a 2-level structure where the contract address determines the path from the root to the leaf encoding the contract state. The information stored in the leaf is:

\[h(h(h(\text{class_hash}, \text{storage_root}), \text{nonce}),0)\]

Where:

  • \(h\) is the Pedersen hash function.

  • \(\text{class_hash}\) is the hash of the contract’s definition discussed here

  • \(\text{storage_root}\) is the root of another Merkle-Patricia tree of height 251 that is constructed from the contract’s storage

  • \(\text{nonce}\) is the current nonce of the contract

The classes tree

The classes tree encodes the information about the existing classes in the state of Starknet. It maps (Cairo 1.0) class hashes to their compiled class hashes. The value of a leaf at a path corresponding to some class hash is given by:

ℎ(CONTRACT_CLASS_LEAF_V0, compiled_class_hash)

Where:

  • \(h\) is the Poseidon hash function

  • CONTRACT_CLASS_LEAF_V0 is a constant prefix string encoded in ASCII (and represented as a field element).

  • compiled_class_hash is the hash of the Cairo assembly resulting from compiling the given class via the Sierra→Casm compiler

Cairo 1.0 classes that are part of the commitment are defined with Sierra, an intermediate representation between Cairo 1.0 and Cairo assembly (see here for more information).

However, the prover only deals with Cairo assembly. This means that unless we want the compilation from Sierra to Casm to be part of every block in which the class is used, the commitment must have some information about the associated Cairo assembly.

Today, the user signs the compiled_class_hash as part of a declare v2 transaction. If the transaction was included in a block, then this compiled_class_hash becomes part of the commitment. In the future, when Sierra→Casm compilation becomes part of the Starknet OS, this value may be updated via a proof of the Sierra→Casm compiler execution, showing that compiling the same class with a newer compiler version results in some new compiled class hash.

Merkle-Patricia tree

Specifications

As mentioned above, our commitment scheme uses a binary Merkle-Patricia tree with the Pedersen hash function. Each node in the tree is represented by a triplet \((length, path, bottom)\).

The actual data is placed in the leaves, and a leaf node with data \(x\) is encoded by the triplet \((0,0,x)\). Empty nodes (leaves or internal) are encoded by the zero triplet \((0,0,0)\). A subtree rooted at a node \((length, path, bottom)\) has a single non-empty subtree, rooted at the node obtained by following the path specified by \(path\).

\(path\) is an integer in \([0, 2^{length}-1]\), and the binary expansion of \(path\) indicates how should we proceed along the tree, where the first step is indicated by the most significant bit, and \(0,1\) are interpreted as left, right correspondingly.

The reason that length is specified and cannot be deduced from \(path\) is that we’re dealing with field elements of fixed size (251 bits each).

For a node with \(length>0\), following \(path\) leads the highest node whose both right and left child are none empty.

The following rules specify how the tree is constructed from a given set of leaves:

The hash of a node \(N =(length, path, bottom)\), denoted by \(H(N)\), is:

\[H(N)=\begin{cases} bottom, & \text{if } length = 0 \\ h(bottom, path) + length, & \text{otherwise} \end{cases}\]

Note that any arithmetic operations in the above are done in our field.

We can now proceed to recursively define the nodes in the tree. The triplet represents the parent of the nodes \(left=(\ell_L, p_L, b_L)\), \(right=(\ell_R, p_R, b_R)\) is given by:

\[parent= \begin{cases} (0,0,0), & \text{if } left=right=(0,0,0)\\ (\ell_L + 1, p_L, b_L), & \text{if } right=(0,0,0) \text{ and } left \neq (0,0,0)\\ (\ell_R + 1, p_R + 2^{\ell_R}, b_R), & \text{if } right\neq (0,0,0) \text{ and } left = (0,0,0)\\ (0, 0, h(H(left), H(right))), & \text{otherwise} \end{cases}\]

Example trie

We now show an example of the construction of a height 3 Merkle-Patricia tree from the leaves \([0,0,1,0,0,1,0,0]\):

trie

Where \(r=h(H(2,2,1),H((2,1,1))\). Note that in our example there is no skipping from the root (length is zero), so the final commitment to the tree will be \(H((0,0,r))=r\).

Suppose that we want to prove, with respect to the commitment we have just computed, that the value of the leaf whose path is given by \(101\) is \(1\). In a standard Merkle tree, the proof would have consisted of data from three nodes (siblings along the path to the root).

Here, since the tree is sparse, we only need to send the two children of the root \((2,2,1), (2,1,1)\). This suffices to reproduce the commitment \(r\), and since the height of the tree, \(3\), is known and fixed, we know that the path \(01\) of length \(2\) specified by the right child \((2,1,1)\) leads us to the desired leaf.

Special addresses

Starknet uses special contract addresses to provide distinct capabilities beyond regular contract deployment.

Two such addresses are 0x0 and 0x1. These addresses are reserved for specific purposes and are characterized by their unique behavior in comparison to traditional contract addresses.

0x0 address

Address 0x0 functions as the default caller_address for external calls, including interactions with the L1Handler or deprecated Deploy transactions. Unlike regular contracts, address 0x0 does not possess a storage structure and does not accommodate storage mapping.

0x1 address

Address 0x1 is another special contract address within Starknet’s architecture. It functions as a storage space for mapping block numbers to their corresponding block hashes. The storage structure at this address is organized as follows:

Keys

Block numbers between the first_v0_12_0_block and the current block minus 10.

Values

Corresponding block hashes for the specified blocks.

Default Values

For all other block numbers, the values are set to 0.

The storage organization of address 0x1 supports the efficient retrieval of block hashes based on block numbers within a defined range and is also used by the get_block_hash system call.