# 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](https://etherscan.io/address/0xc662c410C0ECf747543f5bA90660f6ABeBD9C8c4#readProxyContract) 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](https://github.com/keep-starknet-strange/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](https://github.com/starkware-libs/cairo-lang/blob/master/src/starkware/starknet/core/os/os.cairo) 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](https://github.com/starkware-libs/cairo-lang/blob/master/src/starkware/starknet/core/os/block_context.cairo) 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](https://medium.com/@pban/demystifying-cairo-white-paper-part-ii-9f9dc51886e9).
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](https://github.com/starkware-libs/cairo-lang/blob/master/src/starkware/starknet/core/os/constants.cairo#L47C10-L47C10)):

// 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](https://github.com/starkware-libs/cairo-lang/blob/master/src/starkware/starknet/core/os/syscall_handler.py#L1038) 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](https://github.com/starkware-libs/cairo-lang/blob/master/src/starkware/starknet/core/os/syscall_handler.py#L1098C13-L1098C13) 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](https://github.com/starkware-libs/cairo-lang/blob/master/src/starkware/starknet/storage/starknet_storage.py#L158) 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](https://github.com/starkware-libs/cairo-lang/blob/master/src/starkware/starknet/core/os/os.cairo#L18). If you're familiar with the [blockifier](https://github.com/starkware-libs/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](https://github.com/starkware-libs/cairo-lang/blob/master/src/starkware/starknet/core/os/execution/execute_transactions.cairo#L164C6-L164C32).
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](https://github.com/starkware-libs/blockifier/blob/main/crates/blockifier/src/transaction/account_transaction.rs#L711) 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](https://github.com/lambdaclass/cairo-vm/blob/main/vm/src/types/exec_scope.rs#L13) 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](https://docs.starknet.io/documentation/architecture_and_concepts/State/starknet-state/).

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](https://github.com/starkware-libs/cairo-lang/blob/27a157d761ae49b242026bcbe5fca6e60c1e98bd/src/starkware/cairo/common/merkle_multi_update.cairo#L68C15-L68C15) 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](https://github.com/starkware-libs/cairo-lang/blob/27a157d761ae49b242026bcbe5fca6e60c1e98bd/src/starkware/cairo/common/patricia.cairo#L418) 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](https://github.com/keep-starknet-strange/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](https://github.com/keep-starknet-strange/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.