How to build prefixed key for rocksdb

Question

I would like to know how can the key for the state System Events storage can be built for a given block hash/height

Answer 1

If you want to pull a specific storage item from rocksdb, it requires traversing the patricia trie in order to find the key that you want. This can become complicated quickly, and is generally a slow way to retrieve many keys. The code to do this within substrate can be seen here:

https://github.com/paritytech/substrate/blob/318dea38c9d8af7b526b35a619c393b08ad236ce/client/db/src/lib.rs#L145

https://github.com/paritytech/substrate/blob/318dea38c9d8af7b526b35a619c393b08ad236ce/primitives/state-machine/src/trie_backend_essence.rs#L80

Specifically in reference to RefTrackingState, TrieBackend and TrieBackendEssence.

The first step would be finding the root of the storage that you want, which should be provided as a hash in the block i.e the StateRoot.

From there you would need a way to traverse the patricia trie to get to the key you want to pull:

https://github.com/paritytech/substrate/blob/318dea38c9d8af7b526b35a619c393b08ad236ce/primitives/state-machine/src/trie_backend_essence.rs#L173

the reason this is slow is because of the time complexity of traversing a trie -- there is no other way to retrieve storage keys from rocksdb.

The actual traversal (implemented as a rust Iterator) is implemented by this crate in substrate: https://github.com/paritytech/substrate/blob/318dea38c9d8af7b526b35a619c393b08ad236ce/primitives/trie/src/lib.rs

Substrate has a bunch of traits/caching/syncing/performance optimizations built on top of this raw trie traversal which makes the code complicated to read into -- however it would be really cool if someone could distill this down into it's raw parts and demonstrate how to directly traverse storage keys for substrate rocksdb. I think it could lead to some interesting applications!

I'm not the most versed in this however I hope this gives you a starting point to begin exploring the topic -- or at least manipulating the substrate trait objects / structs to do your bidding

some reading on tries: https://en.wikipedia.org/wiki/Radix_tree

Answer 2

You may need to clarify your question, but these samples might help:

• A bit of an intro to constructing storage keys and obtaining storage entries from them via a node's RPC API:

  https://github.com/paritytech/polkadot-interaction-examples-rs/blob/main/src/bin/04_storage.rs

• How subxt constructs storage keys and uses them to get values back from the RPC API:

  https://github.com/paritytech/subxt/blob/master/subxt/src/storage.rs#L81

For the System Events storage, being a plain storage entry, it's quite easy:

1. Take the pallet name and storage name you're interested in as ASCII bytes , hash them using twox_128 and concatenate the results:

let mut prefix = Vec::new();
prefix.extend(sp_core::twox_128(b"System"));
prefix.extend(sp_core::twox_128(b"Events"));

2. Submit that to the "state_getStorage" RPC endpoint to get back the SCALE encoded bytes representing the events. This would be a call like:

{ 
  "jsonrpc": "2.0", 
  "method": "state_getStorage", 
  "params": [prefix_hex, block_hash]
}

Where the first param is the hex encoded prefix from (1) (for system event storage, "0x26aa394eea5630e07c48ae0c9558cef780d41e5e16056765bc8461851072c9d7"), and the second is the hex encoded block hash, or null if you want events from the latest block.

Bear in mind that your node will only keep storage from some set number of historic blocks; you'll need to run an archive node I believe to be able to query any block hash and get back the events from it.