4

The Runtime storage in Substrate is based on a tree structure rather than a flat structure. While this allows for efficient integrity verification, it incurs data retrieval overhead. According to the documentation:

Accessing trie data is costly. Each read operation takes O(log N) time, where N is the number of elements stored in the trie. To mitigate this, we use a key-value cache.

To optimize data retrieval, I'm interested in exploring alternative storage approaches. Specifically:

  • Is it possible to use a flat structure storage in the Runtime? If so, what are the necessary steps to implement it?
  • Are there any other recommended approaches or strategies to improve data retrieval performance in Substrate?

I appreciate any insights, recommendations, or references regarding alternative storage options and techniques to improve data retrieval efficiency in Substrate's Runtime storage.

3 Answers 3

0

Most of the merklized structures I can think of, are usually based on multiple nodes linked/hashed together with no cycle (tree, patricia trie, or mmr). Meaning that runtime like the ones produce by cumulus it will be difficult or a rather big change.

Note that some key value indexing for key value database are not flat but also log(N), eg for paritydb we got a hashmap like indexing (this one is flat but I don't know how to define a merkle proof for it), but also a btree indexing. One possibility to improve perf would be to attach the merklized info directly into the db indexing.

There may be some way to produce proof based on different crypto, but that is a lot out of my scope and I guess would be not straight forward to integrate with substrate (we use different merkle state structure at different chain height as a way to maintain history of state).

Edit: can also envision some head of chain direct key value db storage like ethereum snapshot, but it only cover part of the use case (read access when syncing).

0

Data Availability vs Data Querying

The Merkel Trie you’re referring to is simply the proof it’s a real (canonical) block. Blockchains use traditional storage (albeit optimised for compression, as many big blocks gets… big?) “under the hood”.

  • Each new block provides a reference of the previous, and will itself be referenced by the following block. This ensures a forkless series of “official” “next” “states” (blocks).
  • Why?! In a decentralised block production environment where anyone (with the necessary capital PoS, PoW) can produce blocks, consensus on the network of a singular, traceable lineage is therefore fundamental. If not; two or more blocks may be produced by two or more nodes simultaneously, causing the chain to fork, with X nodes following Block A and Y nodes following Block B.

Here’s a great explanation that’s less technical and more relatable in under a minute!; https://youtu.be/4DWsTh5HOWk?si=iQKw7S7kRYQ8OmMy

Recommended further reading; https://wiki.polkadot.network/docs/learn-consensus

0

The main main main reason why the storage is not flat (i.e. key -> value) is that a Merkle tree allows us to maintain a state root, and update it without needing to re-iterate all the other items in the database. Then, the same state root can also be used to generate state roots that are relatively compact.

Imagine a flat key value database. A light client only has the state root (i.e. Hash of all keys and values). How can we prove a small subset of the database to the light client? There is no way. But with a merkleized storage, if you send all the nodes from the value you want to prove, all the way to the root, the light can then verify it.

This is a good tradeoff example. Insertion and read is more inefficient in a "merkleized" storage, but maintaining a root is significantly easier.

This section of the corresponding Polkadot Blockchain Academy explains this concept.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.