Flattening state update storage

[Mirko-von-Leipzig]

Status Quo

State updates are currently stored as compressed json in a single table. This is because the only (current) usage of them is to serve starknet_getStateUpdate requests, which makes storing them exactly as required by this method convenient.

Motivation

All other state related methods query the state tree's to discover relevant information, such as when a contract was deployed, or what value a contract's nonce or storage has. This works because we currently store the state tree for every block. These tree's now comprise 2/3 of our storage requirements which is a lot. The flattening of state trees would let us move from querying state trees to querying the state update data directly instead. As such, this flattening is part of our larger goal of moving from storing all state trees to only the latest -- and thereby reducing our storage requirements.

State update data

A block's state update from the gateway contains:

// Blockchain related data -- not relevant to this discussion as this is already tracked elsewhere.
block_hash, new_root, old_root

// within .state_diff:
storage_diffs:          Vec<(ContractAddress, StorageAddress, StorageValue)>,
deployed_contracts:     Vec<(ContractAddress, ClassHash)>,
replaced_classes:       Vec<(ContractAddress, ClassHash)>,
old_declared_contracts: Vec<ClassHash>,
declared_classes:       Vec<(SierraHash, CasmHash)>,
nonces:                 Vec<(ContractAddress, ContractNonce)>,

RPC Usage

get_class_at, get_class_hash_at and get_nonce travel the global tree to get the state hash, which in turn is used to lookup the class, class hash or nonce.

get_storage_at travels both the global and contract tree's to retrieve the storage value.

get_state_update just reads the current compressed json as is.

get_proof travels both global and contract tree's to create the proof. This method will affected by this change. Options are:

1. restrict it to only support the latest N blocks
2. users can decide how often trees should be kept -- e.g. archive nodes can store every 50th tree fully, and this lets get_proof work at any block.

call, estimateFee, simulateTransaction all rely on state trees for:

1. contract discovery (i.e. does this contract exist at block i)
2. class discovery (i.e. does this class exist at block i)
3. storage value retrieval
4. nonce retrieval

Proposal

New tables:

contract's table (`deployed_contracts` and `replaced_classes`)
|--------------|------------------|------------|
| block number | contract address | class hash |
|--------------|------------------|------------|

nonce updates:
|--------------|------------------|------------|
| block number | contract address |    nonce   |
|--------------|------------------|------------|

storage updates:
|--------------|------------------|-------------|---------------|
| block number | contract address | storage key | storage value |
|--------------|------------------|-------------|---------------|

Contract address should probably be a reference to contract's table where possible i.e. intern it there. We can also intern storage key, if we decide that the space savings are worth it 🤷 Probably requires some stats to back up that decision -- although at that point maybe all hashes should just be interned into a single table -- or maybe there is some nice sqlite function somehow? (not really this proposals problem though).

We can also make replaced classes more obvious by adding a replaced: bool column -- this will make it easier to know if its a replaced class or a new deployment.

I think old_declared_contracts and declared_classes are already tracked? I haven't fully checked though, so maybe they need something similar, or an ammendment to what is there now.

[kkovaacs]

Overall I like the proposal. Just a few questions:

• Is block number a reference to a canonical block? If yes, how can we store state information for non-canonical blocks (p2p)? If no, how are reorgs handled?
• Personally I wouldn't add a replaced column unless we really need it (I think we don't).
• Efficient queries: since SQLite can use at most one index per table, how can we efficiently query values? (Like: storage value at key K for contract address A at block N.)
• We do currently track where a class was declared, but that information is is a block hash, so can't be directly used in queries like block_number <= N.

[kkovaacs]

I haven't thought it through 100%, but when would we need to store the non-canonical blocks? Shouldn't they only be canonical? The only exception I know of is during sync, for latest block the node should gossip and here we can either do:

We don't have to store data for gossip propagation, that's taken care of by libp2p. I was wondering how we'll handle forks (only until L1 checkpoints are available) though -- if we consider the longest chain the canonical one we'd definitely need that data. This can be a separate table (and/or representation too) which we apply to the canonical state?

The use-case is to trivially fill in replaced_classes for starknet_getStateUpdate and p2p. The alternative will then be to also do some distinct check somehow, but I don't know how / if that's possible or expensive..

Reconstructing a full state update structure for a block is a good question -- we should do some measurements if using a composite index for (contract address, block number) and then selecting at most two results ordered by the block number isn't fast enough. Anyway, this is something that we can optimize later I think, I don't expect these tables to be that large.

Yeah I'm not quite sure how to solve that effectively. That said, surely anything will be faster than multiple tree lookups?

Should be easy to check. We'd need something like a composite index of (contract_address, storage_key, block_number) so that block_number <= N can be evaluated using the index -- but it should be fine that way I think. We could also use some kind of compression for keys and values here, that might save some space.

Yeah I think we'll need to switch to block number instead of hashes -- just because of this.

Yes, but then we'll have to commit ourselves to only store canonical state this way -- and have a different solution for non-canonical data.

[Mirko-von-Leipzig]

Okay I think that sounds solid, providing we have duplicate tables for non-canonical data. And then some perf tests and index checks once we have tables to work with to make sure we are okay?

[CHr15F0x]

Okay I think that sounds solid, providing we have duplicate tables for non-canonical data. And then some perf tests and index checks once we have tables to work with to make sure we are okay?

LGTM, I like this proposal 🕵️

I'm curious how forks will be stored, ie iiuc only the longest chain would be stored as canonical, others would not be stored and then if some fork turns out to be longer than it'd "just" be a reorg (which hopefully will be automatic due to on delete cascade) and then we resume sync on that fork?

[Mirko-von-Leipzig]

Forks depend on the consensus algorithm in use and how we want to interpret it. So still too early to say with certainty, but yes I think the simplest (and fastest for querying) is to have separate tables for canonical data and fork data (which is hopefully temporary).

[Mirko-von-Leipzig]

Fork data can also be stored "raw" since we don't need to query it -- so it can be json or whatever we want really that is efficient.

[Mirko-von-Leipzig]

Implemented :)