I'm trying to implement a merkle tree consistency algorithm with this paper:
However, I am kinda stuck on the consistency check, because I always land in an infinite loop when I execute the ConsProofSub part.
Example:
New tree has 8, old tree has 7 leaves.
Going through the previous function, I am obtaining m = 7, the leaves of my new tree as vector E and true as b.
The function goes through the recursive code flow, until we reach this situation:
E now has 2 elements, so n = 2.
m = 1, due to previous subtractions in the recursive call for m < k, as well as b = false.
We don't fall in the m = n && b = false if, as m and n are not equal.
k is now being calculated as, again, 2, because the ceiling is correcting the resulting 1/2 from log2(n)/2 to 1.
We fall into the m <= k case, and once again, we are recursively calling the function with the exact same parameters. Now we are in an infinite loop.
However, I can't seem to figure out what i am doing wrong. I feel like the ceiling in the k calculation is the problem. It basically makes it impossible to get out of the loop, because k will seemingly always be higher than m after some iterations.
Any advice / hint on my mistake here?
EDIT: What's interesting is the fact that the algorithm seems to work perfectly when n is an odd number. It only seems to fail for even numbers. I just tried it with a new tree of 7 leafs, and it works like a charm, delivering the correct nodes needed to prove consistency.
However, I'm still unable to figure out what changes would have to be made to make it work with even numbers.
There seems to be a mistake in the book. The case when
m = nandb = trueneeds to be handled separately. A bit more detailed description of the algorithm can be found in RFC 6962.Here is how you can fix it: