Put

The Put operation in the Merkle Patricia Trie is designed to insert a [key, value] pair into the trie. This seemingly straightforward operation consists of several steps to ensure the trie's structure and properties are maintained. Here's a breakdown:

🪜Steps to Insert a New Node:

1. Convert Key to Nibble Sequence: Before any operations on the trie, convert the byte key into a sequence of nibbles for easier traversal and node handling.

2. Fetch the Current Root: Start the insertion process by fetching the current root hash of the trie if not exist.

3. Locate the Position: Traverse the trie using the nibble sequence to find the appropriate position for the new [key, value] pair.

4. Handle Existing Node:

   • If you encounter a node with the same key:

     • Update its value with the new provided value.

5. Leaf Node Insertion:

   • If the nibble sequence leads to a position without an existing node:

     • Insert a new leaf node using the remaining nibbles and value.

6. Branch Node Handling:

   • If the nibble sequence intersects with an existing path:

     • Insert a branch node at the point of intersection.

     • Adjust the existing nodes to maintain the trie's structure.

7. Extension Node Insertion:

   • If a segment of the nibble sequence is shared among multiple keys:

     • Insert an extension node to represent the shared nibble segment.

8. Handle HashNodes:

   • If during traversal you encounter a HashNode, load the actual node using its hash.

   • Continue the insertion process as you would with the loaded node.