Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|improve this question
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

Your Answer


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

Browse other questions tagged or ask your own question.