4
$\begingroup$

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):

screenshot

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] $$

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

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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$. $\endgroup$
    – juaninf
    Aug 25 '13 at 15:46
  • $\begingroup$ 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. $\endgroup$
    – mephisto
    Aug 26 '13 at 13:19
  • $\begingroup$ Is $h=3$ in your example ? $\endgroup$
    – juaninf
    Aug 26 '13 at 14:17
  • $\begingroup$ "...and assume this tree of height 3 is our exist subtree." Yes, h=3 $\endgroup$
    – mephisto
    Aug 27 '13 at 11:29
  • 1
    $\begingroup$ 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. $\endgroup$
    – mephisto
    Aug 28 '13 at 9:34

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.