Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
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
    
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 '13 at 13:19
    
Is $h=3$ in your example ? –  juaninf Aug 26 '13 at 14:17
    
"...and assume this tree of height 3 is our exist subtree." Yes, h=3 –  mephisto Aug 27 '13 at 11:29
1  
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

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

share|improve this answer
1  
Why you think that this node is $n_{23}$? –  juaninf Aug 13 '13 at 15:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.