[Cover Photo by Quangpraha]

Last time in part 2, we want on an adventure in discovering how we build up a Merkle tree from its children nodes all the way to the root. Now, we have the ever-so-fun task of generating the proof for the tree structure, so that we may then prove whether or not an element is contained in the set. Recall that in my code, I included a special data structure called a HashMap with the Node struct. Each node is linked to their neighbors with this mapping as one another’s K:V pairs.

The first step of this algorithm is to take the leaf node and search its key against the mapping to retrieve its neighbor. Then, we can match against the result and check whether the value produced is Some or None. If we match against the first arm, given the index of the leaf as an argument, we will then hash the data in the appropriate order.

Once we hash together these two elements, then we can push it to the proof hashes vector (later returned as part of the Option enum). From here, we set the loop up for the next iteration by setting the current hash equal to the parent hash we recently reconstructed and divide the index variable by 2. We then repeat this process until the lookup result of the mapping matches against the latter match arm and break the loop. Once the loop is broken, we can determine if we are sending back None or the vector of proof hashes, where the former case occurs when the vector’s length is 0.

The main strategy of this algorithm is to exploit the O(1) lookup of mappings to locate neighbors without extra steps. If neighbors are linked together, we can always get the parent node, no matter where we are in the tree. However, if we are searching depth first, then we need to rely on the pointers to our children nodes, contained within the Node struct. This is a reconstruction strategy, where, beginning at the leaf we want to prove, we find the elements necessary for the proof until we arrive at the root.

Once we generate our proof, we can then move onto the verification algorithm. The verification algorithm itself is the lightest component of the bunch and resembles the proof generation algorithm we just reviewed. The major difference is that we will rely expressly on the leaf provided as an argument and the supplied intermediate hashes.

We take the current proof element and hash it with the current node. We then check whether or not this hash is the Merkle root we are searching for. If it is, we can break the loop and return true. Otherwise, we’ll do a length check to ensure that we do not do any superfluous looping. If this is the case that breaks the loop, we will return false. The big difference between this algorithm and the last is that we are checking against the Merkle root to ensure the validity of the leaf node and most importantly we are travelling up the tree with the proof hashes supplied rather than those we can find in the mapping. As such, we do not need the full data set to actually prove whether or not an element is contained within the set of leaf nodes.

For the full code, please visit my repository on GitHub.

Follow me on Twitter @Raisin_Labs!