# Fractal Merkle Traversal

I am studying Fractal Merkle Tree Traversal algorithm in this book. In the [pag. 54] I don't understand this paragraph:

We may determine the number of pebbles returned at these times by observing that a leaf is returned every single round, a pebble at height $ih + 1$ every two rounds, one at height $ih + 2$ every four rounds, etc.

Please look at Figure 4.1. In round 1 is true that leaf $n_0$ no longer needed. Now in paragraph says "pebble at height $ih + 1$ every two rounds, ... " then for the second round, in the case of $i = 1$ and $h = 1$, we see that in the height $i*h+1=2$ should have a node that is no longer required. Which would be in this example that node?

And also, What's means $A$ in the Equation $$A+[A/2]+[A/4]+\cdots+[A/2^h]$$ of the page 55 in 1?

-

First, the passage you refer to is on page 55, 2nd paragraph. And it would also be great if you'd announce that figure 4.1 is actually in a different document ;-) took me quite a while to figure this out. Now to your question.

So, I assume you understand the paragraph? You have to note that a round here corresponds to $2^{(i-1)h}$ "whole tree rounds". Now, the paragraph only says that every "round" a new node on level $ih$ is not required anymore, every two rounds one at level $ih+1$, and so on. Figure 4.1 is a bad example because the root of a subtree is never stored and hence there is no node on the second internal level of the subtree to discard. However, ignore everything green and red in the picture and assume this tree of height 3 is our exist subtree. Then, in the first round node $n_1$ is not needed anymore. In the second round, node $n_0$ and node $n_{23}$ can be discarded. So, Gustavo was right.

Regarding the $A$... it is simply $a$, I assume this is simply a typo, occured when harmonizing the notation of the different papers. You see, in round $a$ you discarded $a$ pebbles at level $ih$, $\lfloor a/2\rfloor$ pebbles at level $ih+1$, and so on.

-
thanks by your reply, In the second round, node $n_{23}$ is at height $1$ and the paragraph say : "a pebble at height $ih+1$ every two rounds" in the example $i = 1$ and $h=1$ then $ih+1=2$. and $n_{23}$ is at height $1$. –  juaninf Aug 25 at 15:46
That's right, but the root nodes of subtrees are never computed as they are leaves of the next subtree (See p.49 - "Static view"). That's why I choose a different example. –  mephisto Aug 26 at 13:19
Is $h=3$ in your example ? –  juaninf Aug 26 at 14:17
"...and assume this tree of height 3 is our exist subtree." Yes, h=3 –  mephisto Aug 27 at 11:29
The $ih$ is the offset of the subtree, i.e. $ih+0$ are the leaves of the subtree, $ih+1$ are the nodes on level $1$ in the subtree, and so on. –  mephisto Aug 28 at 9:34
show 1 more comment

I think it should be $n_{23}$ since it has height 2.
In fact Figure 4.3 confirms this.

-
Why you think that this node is $n_{23}$? –  juaninf Aug 13 at 15:53