# Proof

The `Proof` operation in the MerklePatriciaTree provides a way to validate a specific \[key, value] pair's existence (or non-existence) without requiring the entire trie. This operation is especially useful in scenarios where a lightweight client wants to verify a particular data piece without downloading and storing the complete trie.

#### 🪜 Steps to Generate a Proof:

1. **Initialize Proof Data:**\
   Begin by creating an empty list to hold the nodes you'll traverse during the proof generation.
2. **Traverse the Trie:**\
   Navigate through the trie, following the path dictated by the key for which you want to generate a proof.
3. **Leaf Node Handling:**\
   If you encounter a leaf node:
   * Check if the leaf node's key matches the desired key.
   * If it matches, add the leaf node to the proof data list.
4. **Branch Node Handling:**\
   When encountering a branch node:
   * Add the entire branch node to the proof list, as it contains paths for multiple keys.
   * Continue the traversal following the path segment corresponding to the next nibble in the key.
5. **Extension Node Handling:**\
   Upon finding an extension node:
   * Add the extension node to the proof data list, as it represents a shared path among multiple keys.
   * Proceed down the path indicated by the extension node's nibbles.
6. **HashNode Encountered:**\
   If you come across a HashNode:
   * Fetch the actual node it refers to.
   * Continue with the normal proof generation process for the fetched node.
7. **Compile the Proof:**\
   Once traversal is complete, compile all the nodes you've added to the proof data list. This list represents the minimum set of nodes required to validate the \[key, value] pair's existence or non-existence.
8. **Return the Proof Data:**\
   The compiled list of nodes is the proof. It can be sent to any client wishing to verify a specific key's value within the trie.