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
- 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)$
- Let $R$ be the single node stored on the stack: $R \leftarrow STACK.pop()$
- 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$.