# LogSpace Merkle Traversal

I am studying LogSpace Merkle Tree Traversal algorithm in "Post Quantum Cryptography". I don't understand the Table 1 on page 58.

My question is: Why within of the $2^h$ rounds for $NEED_h$ exist only one $TAIL$, if tail in the page 42 is defined than intermediate nodes in $STACK_h$?

Algorithm 2.1 Treehash

Input: Height $H\ge2$
Output: Root of the Merkle tree

1. for $j = 0,…,2^H-1$ do
a) Compute the $j$th leaf: $NODE_1 \leftarrow LEAFCALC(j)$
b) While $NODE_1$ has the same height as the top node on $STACK$ do
i. Pop the top node from the stack: $NODE_2 \leftarrow STACK.pop$
ii. Compute theirparent node: $NODE_1 \leftarrow g(NODE_2||NODE_1)$
c) Push the parent node on the stack: $STACK.push(NODE_1)$
2. Let $R$ be the single node stored on the stack: $R \leftarrow STACK.pop()$
3. Return $R$

$STACK_h$ is defined to be an object which contains a stack of node values $STACK_h.initialize$ and $STACK_h.update$ will be methods to setup and incrementally execute treehash.The period starting from the time $STACK_h$ is created and ending at the time when the upcoming authentication node is required to be completed is denoted than $NEED_h$.

-
I suggest that you provide a self-contained definition of all mathematical notation and algorithms, in your question, so that people don't have to go look elsewhere to understand what is being asked. –  D.W. Aug 29 '13 at 20:24