What is a merkle proof of inclusion?

I have a Merkle Tree but what do I do with it?

As described in the previous section a Merkle Tree provides an efficient way to verify the integrity of a set of data as well as see whether or not a certain piece of data is included within. How exactly is this done though? This section will explain in detail how once can prove that tree contains a piece of data pertaining to them.

Reinvent the wheel (Merkle Root)

Let's say that you have a Merkle Tree containing a set up numbers and you'd like to prove that your number (64) is contained within. To do this you will want to reconstruct the merkle root as it represents the highest level of the data set and is representative of all values below it. That may seem like quite the challenge at first but it is actually quite simple. All that needs to be provided is the value you wish to prove inclusion for and all the sibling leafs up to the root.

Your number is 64 and you need to prove it is contained within the tree

When all of that data has been provided then we can begin reconstructing the root. To do so we traverse up the tree. We start by hashing the value you have provided and then hashing that value with the sibling leaf. That operation produces the parent and then the resultant hash for the parent is hashed with the next sibling leaf provided. This process will repeat n times where n is the depth of the tree.

Once the tree has been traversed to the top you will now have the computed root. All that needs to be determined is that it is equivalent to the existing root. If it is then one can know for certain that your data is contained within the tree!