​
Overview

Starknet’s state is composed of contract classes and instances and tracks any changes to them. Its commitment uses a cryptographic structure optimized for zero-knowledge proofs, enabling efficient proof generation of state updates and forming the backbone of Starknet’s scalability and security.

​
State structure

Starknet’s state consists of:
  • A mapping between the hashes of contract classes and their definitions
  • A mapping between the addresses of contract instances and their states

​
Contract instance state

A contract instance state consists of:
  • A class hash, which defines the functionality of the contract
  • A key-value mapping (where the key and values are field elements), which comprises the contract’s storage
  • A nonce, which tracks the number of transactions sent from this contract

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

​
Address 0x0

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

​
Address 0x1

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:
KeysBlock numbers between first_v0_12_0_block\texttt{first\_v0\_12\_0\_block} and current_block−10\texttt{current\_block} - 10.
ValuesCorresponding block hashes for the specified blocks.
Default ValuesFor 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.

​
State transition

A transaction txt x transitions the system from state SS to state S′S^{'} if:
  • txt x is an INVOKE transaction, and the storage of S′S^{'} is the result of executing the target contract code with respect to the previous state SS. The arguments, contract instance’s address, and the specific function entry point are part of the transaction.
  • txt x is a DEPLOY_ACCOUNT transaction, and S′S^{'} contains the new contract instance’s state at the contract instance’s address. Additionally, the storage of SS is updated according to the execution of the contract instance’s constructor.
  • txt x is a DECLARE transaction, and S′S^{'} contains the class hash and definition in the contract class’s mapping

​
State commitment

The state commitment is a digest that represents the state. In Starknet, the state commitment combines the roots of two binary Merkle-Patricia tries of height 251 in the following manner: 
state_commitment = hPos(
    "STARKNET_STATE_V0",
    contract_trie_root,
    class_trie_root
)
Where:
  • hPos is the Poseidon hash function.
  • STARKNET_STATE_V0 is a constant prefix string encoded in ASCII (and represented as a field element).
  • contract_trie_root is the root of the contract trie, a Merkle-Patricia trie whose leaves are the contracts’ states.
  • class_trie_root is the root of the class trie, a Merkle-Patricia trie whose leaves are the compiled class hashes.

​
The contract trie

As with Ethereum, this trie is a two-level structure, whose leaves correspond to distinct contracts. The address of each contract determines the path from the trie’s root to its corresponding leaf, whose content encodes the contract’s state. The information stored in the leaf is as follows: 
hPed(
  hPed(
    hPed(
      class_hash,
      storage_root
    ),
    nonce
  ),
  0
)
Where:
  • hPed is the Pedersen hash function.
  • class_hash is the hash of the contract’s definition.
  • storage_root is the root of another Merkle-Patricia trie of height 251 that is constructed from the contract’s storage.
  • nonce is the current nonce of the contract.

​
The class trie

The class trie encodes the information about all existing classes in Starknet’s state. This trie maps class hashes to their compiled class hashes. The information stored in a leaf at a path corresponding to some class hash is as follows: 
hPos(
    CONTRACT_CLASS_LEAF_V0,
    compiled_class_hash
)
Where:
  • hPos 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-to-Casm compiler.
Compiled class hashThe compiled class hash identifies the output of a specific Casm compilation as unique.Cairo classes that are part of the state commitment are defined with Sierra, an intermediate representation between Cairo and Cairo assembly (Casm). However, the prover only works with Casm.So in order to prevent needing to compile from Sierra to Casm in every block in which the class is used, the state commitment must have some information about the corresponding Cairo assembly. The compiled class hash provides this information.For more information, see the Cairo Book.The party that declares the contract signs the compiled class hash, which they obtain using an SDK, as part of the DECLARE transaction. If the transaction is included in a block, then the compiled class hash becomes part of the state commitment.In the future, when Sierra-to-Casm compilation becomes part of the Starknet OS, this value might be updated via a proof of the Sierra-to-Casm compiler execution, showing that compiling the same class with a newer compiler version results in some new compiled class hash.

​
Merkle-Patricia trie

The state commitment scheme uses a binary Merkle-Patricia trie with the Pedersen hash function.

​
About nodes

Each node in the trie is represented by a triplet (length,path,value)\left(\right. l e n g t h , p a t h , v a l u e \left.\right), where:
lengthl e n g t his the length of the path, measured in nodes.
pathp a t his the path from the current node to its unique non-empty subtrie.

pathp a t h is an integer in the set {0,…,2length−1}\{0, \ldots, 2^{\mathit{length}} - 1\}, and the binary expansion of pathp a t h indicates how to proceed along the trie, as follows:

1. Expand pathp a t h to its binary representation.

2. Starting with the most significant bit, representing the root of the trie, traverse the tree node by node, where the bit values 00 and 11 indicate left and right, respectively.
valuev a l u eis the value of the node, which can be either data, or the hash of two non-empty child nodes.
An empty node is one whose triplet values are (0,0,0)\left(\right. 0 , 0 , 0 \left.\right). Leaf nodes and internal nodes can be empty. A subtrie rooted at a node (length,path,value)\left(\right. l e n g t h , p a t h , v a l u e \left.\right) has a single non-empty subtrie, rooted at the node obtained by following the path specified by pathp a t h.
Length is specified, and cannot be deduced from pathp a t h, because the numbers in the triplet (length,path,value)\left(\right. l e n g t h , p a t h , v a l u e \left.\right) are field elements of fixed size, 251 bits each.For a node where length>0l e n g t h > 0, pathp a t h leads to the highest node whose left and right children are not empty.

​
Trie construction

The following rules specify how the trie is constructed from a given set of leaves: The hash of a node N=(length,path,value)N = \left(\right. l e n g t h , p a t h , v a l u e \left.\right), denoted by H(N)H \left(\right. N \left.\right), is: H(N)={value,if length=0hred(value,path)+length,otherwiseH(N) = \begin{cases} \mathit{value}, & \text{if } \mathit{length} = 0 \\ h_{\mathit{red}}(\mathit{value}, \mathit{path}) + \mathit{length}, & \text{otherwise} \end{cases}
All arithmetic operations in the above description of HH are done in the STARK field, as described in The STARK field.

​
Mathematical definition of the nodes in the trie

The triplet representing the parent of the nodes left=(ℓL,pL,vL)l e f t = \left(\right. ℓ_{L} , p_{L} , v_{L} \left.\right), right=(ℓR,pR,vR)r i g h t = \left(\right. ℓ_{R} , p_{R} , v_{R} \left.\right) is defined as follows: parent={(0,0,0),if left=right=(0,0,0)(ℓL+1,pL,vL),if right=(0,0,0) and left≠(0,0,0)(ℓR+1,pR+2ℓR,vR),if right≠(0,0,0) and left=(0,0,0)(0,0,hred(H(left),H(right))),otherwise\mathit{parent} = \begin{cases} (0, 0, 0), & \text{if } \mathit{left} = \mathit{right} = (0, 0, 0) \\ (\ell_L + 1, p_L, v_L), & \text{if } \mathit{right} = (0, 0, 0) \text{ and } \mathit{left} \neq (0, 0, 0) \\ (\ell_R + 1, p_R + 2^{\ell_R}, v_R), & \text{if } \mathit{right} \neq (0, 0, 0) \text{ and } \mathit{left} = (0, 0, 0) \\ (0, 0, h_{\mathit{red}}(H(\mathit{left}), H(\mathit{right}))), & \text{otherwise} \end{cases}

​
Example trie

The diagram A three-level Merkle-Patricia trie illustrates the construction of a three-level-high Merkle-Patricia trie from the leaves whose values are (0,0,1,0,0,1,0,0)\left(\right. 0 , 0 , 1 , 0 , 0 , 1 , 0 , 0 \left.\right):

Figure 1. A three-level Merkle-Patricia trie

Where r=hPed(H(2,2,1),H((2,1,1))r = h_{P e d} \left(\right. H \left(\right. 2 , 2 , 1 \left.\right) , H \left(\right. \left(\right. 2 , 1 , 1 \left.\right) \left.\right). Notice that the example does not skip from the root, whose length is zero, so the final state commitment to the trie is H((0,0,r))=rH \left(\right. \left(\right. 0 , 0 , r \left.\right) \left.\right) = r. Suppose that you want to prove, with respect to the state commitment just computed, that the value of the leaf whose path is given by 101101 is 11. In a standard Merkle trie, the proof would consist of data from three nodes, which are siblings along the path to the root. In a Merkle-Patricia trie, because the trie is sparse, you only need to send the two children of the root, which are (2,2,1)\left(\right. 2 , 2 , 1 \left.\right) and (2,1,1)\left(\right. 2 , 1 , 1 \left.\right). These two children are enough to reproduce the state commitment rr, and because you know that the height of the trie is three, and that it is fixed, you know that the path 0101 of length 22 specified by the right-hand child, (2,1,1)\left(\right. 2 , 1 , 1 \left.\right), leads to the desired leaf.