Merkle Tree Traversal in Log Space and Time

We present a technique for Merkle tree traversal which requires only logarithmic space and time. For a tree with N leaves, our algorithm computes sequential tree leaves and authentication path data in time 2 log₂(N) and space less than 3 log₂(N), where the units of computation are hash function evaluations or leaf value computations, and the units of space are the number of node values stored. This result is an asymptotic improvement over all other previous results (for example, measuring cost=space*time). We also prove that the complexity of our algorithm is optimal: There can exist no Merkle tree traversal algorithm which consumes both less than O(log₂(N)) space and less than O(log₂(N)) time. Our algorithm is especially of practical interest when space efficiency is required.