Storage Trie

In Ethereum, the storage trie is a type of Merkle Patricia Trie that stores the state of smart contracts. The storage trie is used to persistently store the key-value pairs that make up the internal state of a contract.

The structure of the storage trie is similar to the state trie. Each node in the storage trie contains a hash of its child nodes and a key-value pair. The key is the 256-bit storage slot address, and the value is the 256-bit value stored in that slot.

When a smart contract needs to read or modify a value in storage, it first calculates the storage slot address based on the key-value pair that it wants to access. It then traverses the storage trie to find the node containing that key-value pair.

Once the node is found, the contract can read or modify the value in the storage slot by updating the value in the key-value pair and then updating the node's hash and the hashes of all its parent nodes up to the root of the storage trie.

When the contract modifies the value of a storage slot, a new key-value pair is created, and the old key-value pair is marked as deleted. This is because the storage trie is an immutable data structure, and it's not possible to directly modify a node in the trie.

Overall, the storage trie is an efficient and secure way to persistently store the internal state of smart contracts in Ethereum.

                   +-- (k: "01", v: "hello")
              +----|---- (k: "012", v: "world")
              |    +-- (k: "02", v: "foo")
              |
(root node)---+-- (k: "1a", v: "bar")
              |
              |    +-- (k: "123", v: "baz")
              +----|---- (k: "13", v: "qux")
                   +-- (k: "2", v: "abc")

In this example, the root node has six children nodes, each representing a key-value pair stored in the storage trie. The key is represented as a sequence of nibbles (half-bytes), and the value can be any arbitrary data.

To search for a value associated with a particular key, you start at the root node and follow the appropriate branch for each nibble in the key until you reach a leaf node. If the leaf node has the same key as the one you are searching for, then you have found the corresponding value. If the leaf node has a different key, then the key you are searching for is not present in the storage trie.