We prove upper and lower bounds for computing Merkle tree
traversals, and display optimal trade-offs between time
and space complexity of that problem.

more >>>

We consider the problem of traversing skew (unbalanced) Merkle
trees and design an algorithm for traversing a skew Merkle tree
in time O(log n/log t) and space O(log n (t/log t)), for any choice
of parameter t\geq 2.
This algorithm can be of special interest in situations when
more >>>