Get

The Get operation in the Merkle Patricia Trie retrieves the value associated with a given key. Although the primary goal is to fetch a value, the retrieval process requires a systematic traversal of the trie structure based on the given key.

🪜 Steps to Retrieve a Value:

1. Convert Key to Nibble Sequence: First and foremost, transform the byte key into a sequence of nibbles. This will guide the traversal through the trie.

2. Fetch the Current Root: Begin the retrieval process from the current root of the trie if not exist.

3. Initiate Traversal: Using the nibble sequence, navigate through the trie to locate the desired value.

4. Handle HashNodes:

   • If you encounter a HashNode during traversal:

     • Load the actual node using its hash.

     • Continue the retrieval process with the loaded node.

5. Encounter Branch Node:

   • If the current node is a branch node:

     • Use the next nibble in the sequence to decide which child to continue traversal with.

     • If you've reached the end of the nibble sequence and the current branch node has a value, then you've found the desired value. Otherwise, continue traversal.

6. Encounter Leaf Node:

   • If the current node is a leaf node:

     • Compare its key with the remaining nibble sequence.

     • If they match, you've found the value. If not, the key doesn't exist in the trie.

7. Encounter Extension Node:

   • If the current node is an extension node:

     • Check if the extension's nibble sequence matches the beginning of the remaining nibble sequence for the key.

     • If it matches, continue traversal with the next segment of the nibble sequence. Otherwise, the key doesn't exist in the trie.

8. Value Not Found:

   • If you reach the end of the nibble sequence without finding a matching leaf node or without exhausting the entire key, the key doesn't exist in the trie.