# Fractal Merkle Traversal

I am studying Fractal Merkle Tree Traversal algorithm in the book “Post Quantum Cryptography” (PDF). On 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.

Now, please look at Figure 4.1 of “Merkle-Tree Traversal Techniques” (PDF):

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?

Also, can someone explain the meaning of $A$ in the equation on page 55? $$A+[A/2]+[A/4]+\cdots+[A/2^h]$$

-
I think it should be $n_{23}$ since it has height 2. In fact Figure 4.3 confirms this. – Gustavo Salazar Torres Aug 13 '13 at 13:38
Why you think that this node is $n_{23}$? – juaninf Aug 13 '13 at 15:53

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 '13 at 15:46
Is $h=3$ in your example ? – juaninf Aug 26 '13 at 14:17
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 '13 at 9:34