19.02.2004

In this paper we describe optimal trade-offs between time and space complexity of Merkle tree traversals along with their associated authentication paths, improving on the previous results of Jakobsson, Leighton, Micali and Szydlo (2003) and Szydlo (2004). In particular we show that our algorithm requires 2 log n/log⁽³⁾ n hash function evaluations and storage for less than (log n/log⁽³⁾ n)log log n + 2 log n hash values, where n is the number of leaves in the Merkle tree. We also prove that these trade-offs are optimal, i.e. there is no algorithm that requires less than \Theta(log n/log t) time and less than \Theta(t log n/ log t) space for any choice of parameter t. Our algorithm could be of special use in the case when both time and space are simultaneously limited.