Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-118 | 21st December 2004 00:00

A Note on Traversing Skew Merkle Trees

RSS-Feed




TR04-118
Authors: Marek Karpinski, Yakov Nekrich
Publication: 21st December 2004 16:24
Downloads: 1810
Keywords: 


Abstract:

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
the exact number of items to be identified is not known in advance.



ISSN 1433-8092 | Imprint