Starknet OS

The Starknet OS is a cairo program run by SHARP to prove Starknet's state transitions. Yes, that means that Starknet itself is written in Cairo! SHARP doesn't know anything about Starknet, all it takes as an input are base64 encoded Cairo PIE (Program Independent Execution) files which are yielded by the cairo runner.

The program hash of the Starknet OS is registered on the Starknet Core Contract which prevents one to prove a state transition with a different version of the OS.

I've decided to write this document to walk through the Starknet OS cairo program which is not studied enough. As we are finalizing the work on SHARP integration into Madara it is also a good opportunity to understand how one could tweak the Starknet OS for their own app chain and what would be the consequences of such changes.

The code

The full program can be found in the cairo-lang repository

Inputs loading

As every cairo program, it all starts with a main entrypoint.

// Reserve the initial range check for self validation.
// Note that this must point to the first range check used by the OS.
let initial_range_check_ptr = range_check_ptr;
let range_check_ptr = range_check_ptr + 1;

let (initial_carried_outputs: OsCarriedOutputs*) = alloc();
%{
    from starkware.starknet.core.os.os_input import StarknetOsInput

    os_input = StarknetOsInput.load(data=program_input)

    ids.initial_carried_outputs.messages_to_l1 = segments.add_temp_segment()
    ids.initial_carried_outputs.messages_to_l2 = segments.add_temp_segment()
%}

To begin with, the OS takes some input in the following form

@marshmallow_dataclass.dataclass(frozen=True)
class StarknetOsInput(ValidatedMarshmallowDataclass):
    contract_state_commitment_info: CommitmentInfo
    contract_class_commitment_info: CommitmentInfo
    deprecated_compiled_classes: Dict[int, DeprecatedCompiledClass] = field(
        metadata=fields.new_class_hash_dict_keys_metadata(
            values_schema=DeprecatedCompiledClass.Schema
        )
    )
    compiled_classes: Dict[int, CompiledClass] = field(
        metadata=fields.new_class_hash_dict_keys_metadata(values_schema=CompiledClass.Schema)
    )
    contracts: Dict[int, ContractState]
    class_hash_to_compiled_class_hash: Dict[int, int]
    general_config: StarknetGeneralConfig
    transactions: List[InternalTransaction]
    block_hash: int

As we can see the input consists of the block info, contracts deployed, declared, transactions. We will see after where do these input come from.

Then, we retrieve what is called the Block Context, we can picture this as the necessary information to execute the transactions within this block such as classes, block number/timestamp, sequencer address, chain_id, fee token address..

// Represents information that is the same throughout the block.
struct BlockContext {
    // Parameters for select_builtins.
    builtin_params: BuiltinParams*,

    // A list of (compiled_class_hash, compiled_class) with the classes that are executed
    // in this block.
    n_compiled_class_facts: felt,
    compiled_class_facts: CompiledClassFact*,

    // A list of (deprecated_compiled_class_hash, deprecated_compiled_class) with
    // the classes that are executed in this block.
    n_deprecated_compiled_class_facts: felt,
    deprecated_compiled_class_facts: DeprecatedCompiledClassFact*,

    // Information about the block.
    block_info: BlockInfo*,
    // StarknetOsConfig instance.
    starknet_os_config: StarknetOsConfig,
    // A function pointer to the 'execute_syscalls' function.
    execute_syscalls_ptr: felt*,
    // A function pointer to the 'execute_deprecated_syscalls' function.
    execute_deprecated_syscalls_ptr: felt*,
}

A few interesting lines we can zoom on

block_info=new BlockInfo(
    block_number=nondet %{ deprecated_syscall_handler.block_info.block_number %},
    block_timestamp=nondet %{ deprecated_syscall_handler.block_info.block_timestamp %},
    sequencer_address=nondet %{ os_input.general_config.sequencer_address %},
),
starknet_os_config=StarknetOsConfig(
    chain_id=nondet %{ os_input.general_config.chain_id.value %},
    fee_token_address=nondet %{ os_input.general_config.fee_token_address %},
),

First, we can see the use of the keyword nondet, which implies some non determinism.
To quote Lior on this keyword:

"nondet" is just a way to inline a hint. In this case, it's a way to populate the OS inputs into Cairo structs. It's non-deterministic from the point of view of the verifier as the verifier doesn't know where these values come from and whether they are "correct" in any sense, until there's actual (non-hint) Cairo code that deals with them

Then, we observe that some parameters are given through deprecated syscalls while others come directly from a hint variable os_input.
It's set when loading the program input as part of the 1st hint, the program input is given to the cairo runner.

The OS will then initialize the state changes

let (
    contract_state_changes: DictAccess*, contract_class_changes: DictAccess*
) = initialize_state_changes();

This merely initializes some dictionaries given the fact that we know from the hint variable os_input which contracts were interacted with in this block.

Interestingly, we also see that dict_new constructor seems to use the initial_dict scope variable under the hood.

// Initializes state changes dictionaries.
func initialize_state_changes() -> (
    contract_state_changes: DictAccess*, contract_class_changes: DictAccess*
) {
    %{
        from starkware.python.utils import from_bytes

        initial_dict = {
            address: segments.gen_arg(
                (from_bytes(contract.contract_hash), segments.add(), contract.nonce))
            for address, contract in os_input.contracts.items()
        }
    %}
    // A dictionary from contract address to a dict of storage changes of type StateEntry.
    let (contract_state_changes: DictAccess*) = dict_new();

    %{ initial_dict = os_input.class_hash_to_compiled_class_hash %}
    // A dictionary from class hash to compiled class hash (Casm).
    let (contract_class_changes: DictAccess*) = dict_new();

    return (
        contract_state_changes=contract_state_changes, contract_class_changes=contract_class_changes
    );
}

Block Preprocessing

Now, it's time for some pre-processing!

// Pre-process block.
with contract_state_changes {
    write_block_number_to_block_hash_mapping(block_context=block_context);
}

Here is the full source code which we will explain step by step

// Writes the hash of the (current_block_number - buffer) block under its block number in the
// dedicated contract state, where buffer=STORED_BLOCK_HASH_BUFFER.
func write_block_number_to_block_hash_mapping{range_check_ptr, contract_state_changes: DictAccess*}(
    block_context: BlockContext*
) {
    alloc_locals;
    tempvar old_block_number = block_context.block_info.block_number - STORED_BLOCK_HASH_BUFFER;
    let is_old_block_number_non_negative = is_nn(old_block_number);
    if (is_old_block_number_non_negative == FALSE) {
        // Not enough blocks in the system - nothing to write.
        return ();
    }

    // Fetch the (block number -> block hash) mapping contract state.
    local state_entry: StateEntry*;
    %{
        ids.state_entry = __dict_manager.get_dict(ids.contract_state_changes)[
            ids.BLOCK_HASH_CONTRACT_ADDRESS
        ]
    %}

    // Currently, the block hash mapping is not enforced by the OS.
    local old_block_hash;
    %{
        (
            old_block_number, old_block_hash
        ) = execution_helper.get_old_block_number_and_hash()
        assert old_block_number == ids.old_block_number,(
            "Inconsistent block number. "
            "The constant STORED_BLOCK_HASH_BUFFER is probably out of sync."
        )
        ids.old_block_hash = old_block_hash
    %}

    // Update mapping.
    assert state_entry.class_hash = 0;
    assert state_entry.nonce = 0;
    tempvar storage_ptr = state_entry.storage_ptr;
    assert [storage_ptr] = DictAccess(key=old_block_number, prev_value=0, new_value=old_block_hash);
    let storage_ptr = storage_ptr + DictAccess.SIZE;
    %{
        storage = execution_helper.storage_by_address[ids.BLOCK_HASH_CONTRACT_ADDRESS]
        storage.write(key=ids.old_block_number, value=ids.old_block_hash)
    %}

    // Update contract state.
    tempvar new_state_entry = new StateEntry(class_hash=0, storage_ptr=storage_ptr, nonce=0);
    dict_update{dict_ptr=contract_state_changes}(
        key=BLOCK_HASH_CONTRACT_ADDRESS,
        prev_value=cast(state_entry, felt),
        new_value=cast(new_state_entry, felt),
    );
    return ();
}

1. The code starts by retrieving the old_block_number, this is computed by substracting the block_number of the current context (which we retrieved earlier!) and some buffer.
   We also learn more about the buffer meaning

// The block number -> block hash mapping is written for the current block number minus this number.
const STORED_BLOCK_HASH_BUFFER = 10;

This buffer is chosen such that there is enough time to do all this computation client side. In Madara, we tried to do the state root computation synchronously (at the end of every block) but that was just taking too long especially as the state was growing. With this buffer we make sure we have enough time, only drawback is that syscalls can only give you info about the block 10 blocks behind (?).

2. From the first dictionary we initialized earlier (contract_state_changes), we fetch the StateEntry storage changes dictionary as specified in the comment // A dictionary from contract address to a dict of storage changes of type StateEntry.

Here we learn that 1 contracts address is reserved for the OS (source):

// OS reserved contract addresses.

// This contract stores the block number -> block hash mapping.
const BLOCK_HASH_CONTRACT_ADDRESS = 1;

This contract is not deployed per se but given as part of the input. As per lior, it's not an actual contract, it's just a storage that contains the block hashes block[i] = block_hash.

3. Let's then introduce the execution_helper hint variable. As the python code states its role is to maintain the information needed for executing transactions in the OS. In this hint, we use it to fetch the old block number and hash.

def get_old_block_number_and_hash(self) -> Tuple[int, int]:
    """
    Returns the block number and block hash of the
    (current_block_number - stored_block_hash_buffer) block.
    """
    assert (
        self.old_block_number_and_hash is not None
    ), f"Block number is probably < {constants.STORED_BLOCK_HASH_BUFFER}."

    return self.old_block_number_and_hash

Here again, we find our buffer constant, in fact it will only return a value if we are at a block past that buffer. If we look closely at the create method from the OsExecutionHelper, we see that it fetches this information from the updated state which was written by the Batcher.

Finally assert old_block_number == ids.old_block_number makes sure that the old_block_hash that was returned by get_old_block_number_and_hash is in fact the current_block - STORED_BLOCK_HASH_BUFFER.

4. The last part of the function is quite straightforward, we need to update the content of our StateEntry dict such that it reflects the storage change from our block_number to block_hash mapping inside our contract (you know the one reserved for the OS).
   We again ask some help to the OsExecutionHelper hint variable to write in the storage :

storage = execution_helper.storage_by_address[ids.BLOCK_HASH_CONTRACT_ADDRESS]
storage.write(key=ids.old_block_number, value=ids.old_block_hash)

Specifically, we get the storage of our super contract thanks to the Mapping[int, OsSingleStarknetStorage].
This class represents a single contract storage and it is used by the Starknet OS run in the GpsAmbassador.
It also exposes read/write functions to ongoing storage changes.
As per Lior, the GpsAmbassador is the service responsible for running the OS and sending the run to SHARP to be proven. In Madara this refers to the sharp worker run in a separate thread in the node.

5. Last step, we update our contract_state_changes dictionary with our new StateEntry constructed with our new storage!

Transactions Execution

After we've pre-processed the block and updated our block number -> block hash mapping, we can execute the transactions within the block.

// Execute transactions.
let outputs = initial_carried_outputs;
with contract_state_changes, contract_class_changes, outputs {
    let (local reserved_range_checks_end) = execute_transactions(block_context=block_context);
}
let final_carried_outputs = outputs;

Let's dive into the internal of the execute_transactions function. If you're familiar with the blockifier, you will see some similar logic but written in Cairo instead of Rust.

The comments help us understand the global flow

// Executes the transactions in the hint variable os_input.transactions.
//
// Returns:
// reserved_range_checks_end - end pointer for the reserved range checks.
//
// Assumptions:
//   The caller verifies that the memory range [range_check_ptr, reserved_range_checks_end)
//   corresponds to valid range check instances.
//   Note that if the assumption above does not hold it might be the case that
//   the returned range_check_ptr is smaller then reserved_range_checks_end.

Q: Add details (?)

What's the most interesting for us is the execute_transactions_inner function.
Given a block context and a number of transactions it will execute them sequentially.

// Guess the current transaction's type.
%{
    tx = next(transactions)
    tx_type_bytes = tx.tx_type.name.encode("ascii")
    ids.tx_type = int.from_bytes(tx_type_bytes, "big")
%}

This first hint is used to retrieve the type of the transaction (declare/deploy/invoke/l1_handler).
Then the OS will call the function corresponding to the transaction's type e.g execute_invoke_function_transaction.

We will only dive into the invoke function but feel free to explore the code by yourself to understand the other entrypoints. We can do the parallel with the blockifier code which follows the same flow as the OS.

1. Validate Transaction Version
2. Compute Transaction Hash
3. Check and increment nonce
4. Run __validate__ entrypoint responsible for signature verification
5. Execute only non-reverted transactions
6. Charge fees

Right before we run the transaction validation, we find this mysterious hint

%{
    tx_info_ptr = ids.tx_execution_context.deprecated_tx_info.address_
    execution_helper.start_tx(tx_info_ptr=tx_info_ptr)
%}

This is described in the python comments

"""
Called when starting the execution of a transaction.

'tx_info_ptr' is a pointer to the TxInfo struct corresponding to said transaction.
"""

In simpler words, it just tells the OS where to look for the transaction info during execution.

struct TxInfo {
    // The version of the transaction. It is fixed (currently, 1) in the OS, and should be
    // signed by the account contract.
    // This field allows invalidating old transactions, whenever the meaning of the other
    // transaction fields is changed (in the OS).
    version: felt,

    // The account contract from which this transaction originates.
    account_contract_address: felt,

    // The max_fee field of the transaction.
    max_fee: felt,

    // The signature of the transaction.
    signature_len: felt,
    signature: felt*,

    // The hash of the transaction.
    transaction_hash: felt,

    // The identifier of the chain.
    // This field can be used to prevent replay of testnet transactions on mainnet.
    chain_id: felt,

    // The transaction's nonce.
    nonce: felt,
}

VM Scope

Before we look at the code responsible for computing state updates and commitments. I wanted to highlight one specific hint used throughout the OS.

%{ vm_enter_scope(...) %} and %{ vm_exit_scope() %}

It has been implemented within the rust Cairo VM here which we can probably leverage. It's a very simple struct that just holds scopes defined as HashMap<String, Box<dyn Any>>. Within one scope you can access the local variables and the variables from upper scopes.

State Update

%{
    # This hint shouldn't be whitelisted.
    vm_enter_scope(dict(
        commitment_info_by_address=execution_helper.compute_storage_commitments(),
        os_input=os_input,
    ))
    ids.initial_state_updates_ptr = segments.add_temp_segment()
%}

This hint creates the scope that will be used by the next hint, mainly we make accessible to the vm the os input and the storage commitments.

let state_updates_ptr = initial_state_updates_ptr;

with state_updates_ptr {
    let (state_update_output) = state_update{hash_ptr=pedersen_ptr}(
        contract_state_changes_start=contract_state_changes_start,
        contract_state_changes_end=contract_state_changes,
        contract_class_changes_start=contract_class_changes_start,
        contract_class_changes_end=contract_class_changes,
    );
}

The state_update function does a few things but mostly it updates the different commitment trees which will be used to update and validate the global state.
It outputs both the initial_root and the final_root.

For more information about how Starknet stores its own state please refer to the official documentation.

The state update is performed in 3 main steps:

1. Updates contract state trie: contract_state_update
2. Updates contract class trie: contract_class_update
3. Compute the initial and final roots of the global state: calculate_global_state_root

Q: Why is the initial root not passed through a hint ?

The 2 first steps are quite similar so we'll only take a close look at the contract_state_update.

The function starts by setting up everything so the merkle trie updates can happen smoothly. Mostly doing some dictionary allocation, hashing the state changes and storing the number of actual state changes.

The main hint of this function is the following:

 %{
    ids.initial_root = os_input.contract_state_commitment_info.previous_root
    ids.final_root = os_input.contract_state_commitment_info.updated_root
    preimage = {
        int(root): children
        for root, children in os_input.contract_state_commitment_info.commitment_facts.items()
    }
    assert os_input.contract_state_commitment_info.tree_height == ids.MERKLE_HEIGHT
%}

We set the initial and final roots by retrieving the state commitments from the input (remember the beginning).

Then we set the preimage by looking at the commitment facts, this preimage will then be used by the merkle_multi_update function.

Finally we set the MERKLE_HEIGHT value of the outer scope to the correct trie height (251).

Now that we have everything, we can perform the actual trie update

patricia_update_using_update_constants(
    patricia_update_constants=patricia_update_constants,
    update_ptr=hashed_state_changes,
    n_updates=n_contract_state_changes,
    height=MERKLE_HEIGHT,
    prev_root=initial_root,
    new_root=final_root,
);

One interesting trick used here is to pass the powers of 2 as pre-computed constants to the function which saves us a ton of computation.

Merkle Patricia Trie

As we've seen in the previous section, the Starknet OS uses merkle patricia tries with pedersen or poseidon depending on the trie.

from starkware.cairo.common.patricia import (
    patricia_update_constants_new,
    patricia_update_using_update_constants,
)
from starkware.cairo.common.patricia_utils import PatriciaUpdateConstants
from starkware.cairo.common.patricia_with_poseidon import (
    patricia_update_using_update_constants as patricia_update_using_update_constants_with_poseidon,
)

For instance let's look at the first major hint

%{
    from starkware.cairo.common.patricia_utils import canonic, patricia_guess_descents
    from starkware.python.merkle_tree import build_update_tree

    # Build modifications list.
    modifications = []
    DictAccess_key = ids.DictAccess.key
    DictAccess_new_value = ids.DictAccess.new_value
    DictAccess_SIZE = ids.DictAccess.SIZE
    for i in range(ids.n_updates):
        curr_update_ptr = ids.update_ptr.address_ + i * DictAccess_SIZE
        modifications.append((
            memory[curr_update_ptr + DictAccess_key],
            memory[curr_update_ptr + DictAccess_new_value]))

    node = build_update_tree(ids.height, modifications)
    descent_map = patricia_guess_descents(
        ids.height, node, preimage, ids.prev_root, ids.new_root)
    del modifications
    __patricia_skip_validation_runner = globals().get(
        '__patricia_skip_validation_runner')

    common_args = dict(
        preimage=preimage, descent_map=descent_map,
        __patricia_skip_validation_runner=__patricia_skip_validation_runner)
    common_args['common_args'] = common_args
%}

This shouldn't be necessary difficult as it ends up mostly translating python code to rust and we can probably gain performance from this too. However it will need extensive testing for each of these against their respective python implementations which are battle-tested.

Conclusion

This post is still a draft and doesn't aim to be fully exhaustive. It's here to give an overview in the inner workings of the Starknet OS and help during the development of the SNOS rust library.

Here are a few interesting tweaks that could ba applied to the OS in the context of an app-chain:

• Blocks batching: as we've seen the OS cairo program operates on one block. In order to support low block time app-chains it should run on multiple blocks at once. In that case, we would only pay for state updates between the initial and final state.
• State Representation: the OS uses merkle patricia tries to represent the different state tries. If you're building a permissionned app-chain or have a limited state growth then it could be interesting to change these to simpler and more efficient binary tries. Poseidon should also be used everywhere probably.
• Fee Model: the fee charging logic could be changed to integrate a paymaster protocol at the OS level and thus making the whole chain gas-less.

There are probably a ton of other changes that could be made to tailor the Starknet OS to your specific use case. If you have ideas please create an issue on the SNOS repository.

Credits

Thank you to everyone contributing and reviewing this document.

Lior Goldberg from Starkware, Ben from Starkware, Abdel from Starkware, Apoorv from Pragma.