I would like to know what best steps are there in finding differences between a high order amount of merkle tree's or if a better associative structure should be used.

I ask this questions because while i have found on comparing two trees for differences i have not found any specifics on comparing n amount at the same time (100-200 for ex).

While i would imagine a sequential validation process from one tree to the next, my question would be if there are any general way to do so.


While I originally looked into what would require the use of some Tree Topology or use of Bloom Filters, I asked a friend on this problem. He gave me a more practical solution:

  1. Sort each Tree by Leaves Seperately
  2. Then you put each result in heaps - sort of like a merge step of the quick sort algorithm.
  3. You then take the First Heap from the first tree and compare it with the first heaps from the other trees.

    • If all heaps match, pop all the heaps and you have a leaf present in all of the trees

    • If the first heap is larger than any given heap, pop it - it doesn't match all the trees. Continue popping from that heap until you find a matching heap, or...

    • If the first heap is smaller than any given heap, pop all of the previously checked heaps - all of them contain a leaf that is not present in all of the trees

    • Repeat until one of the heaps is empty

This solution has a linear complexity - you will compare each leaf about 1 time.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.