How to store storage trie in leveldb?

Question

I want to know the structure of storage trie and its data structure in leveldb, and I read solidity storage.

I still have questions?

1. In the yellow paper, it says that storage root is a mapping between 256-bit integer and 256-bit integer, is this key value pair store in leveldb?

2. If we want to store one value V in the storage trie of one contract. Following solidity storage, I count the key K for V, and insert V using K in the storage trie (just like K is the account address and V is the account state in the state trie). Then update the storage root just like state trie. Am I right?

3. If question 1 is right, what's the real key we use to store V in leveldb, is it K or K and something after SHA3? How can we get the parent hash of some leaf value nodes, just use SHA3(value1, value2, ...)?

Answer 1

I am not an expert, but let me share my understanding. Also, please check this question: Ethereum Merkle Patricia Trie and Hashes

1. The trie is stored as key value pairs in levelDB. Each hash (256-bit integer) allows you to access a node. The value corresponds to a RLP encoded node (see Appendix D in yellow paper for different node types).
2. If you want to store a new Value v, you encode the value in RLP and determine the key as explained in getStorageAt. Then you insert a new leaf node or update an existing one. Of course, all depending higher-level node hashes until the root must be updated.
3. As explained in solidity storage, the real key is SHA3 hash based on the storage index of the variable that you are storing (for static data the storage index, for mappings it is keccak256(k . p))

I recommend looking at the following links, too:

References: https://easythereentropy.wordpress.com/2014/06/04/understanding-the-ethereum-trie/ https://wanderer.github.io/ethereum/nodejs/code/2014/05/21/using-ethereums-tries-with-node/ https://github.com/medvedev1088/ethereum-merkle-patricia-trie-example https://medium.com/cybermiles/diving-into-ethereums-world-state-c893102030ed