3

I'm trying to implement a merkle tree consistency algorithm with this paper:

https://books.google.de/books?id=CokSDQAAQBAJ&lpg=PA147&dq=merkle%20consistency%20proof&hl=de&pg=PA148#v=onepage&q&f=false

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.

Sossenbinder
  • 4,852
  • 5
  • 35
  • 78

1 Answers1

2

There seems to be a mistake in the book. The case when m = n and b = true needs 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:

enter image description here

Community
  • 1
  • 1
Anton
  • 3,113
  • 14
  • 12
  • That's the perfect solution. Note that I also added an edit to your answer, because I noticed something else which is just wrong in the books algorithm. – Sossenbinder Jan 17 '17 at 08:42
  • 1
    @Sossenbinder In your edit you write: _"I would like to add, that the calculation of k is not correct as displayed in this book. If this formula is used, and we come to a situation where n=9, k will be 4 instead of 8."_ I don't think this is true. `n = 9` ⇒ `log(n/2) = log(4.5) ≈ 2.17` ⇒ `⌈log(n/2)⌉ = 3` ⇒ `2^⌈log(n/2)⌉ = 8`. `⌈x⌉` is the notation for the [ceiling function](https://en.wikipedia.org/wiki/Floor_and_ceiling_functions). – Anton Jan 17 '17 at 11:09
  • Indeed, I must have done something wrong with my calculation. I used ceiling, but I might have screwed up with parentheses placement or something. – Sossenbinder Jan 17 '17 at 12:47