Efficient hash chain traversal based on binary tree inorder traversal

摘要

This paper presents an algorithm to improve the time and space complexity of reverse hash chain traversal. Mapping the traversing of a reverse hash chain to the inorder traversing of a binary tree, the proposed algorithm chooses auxiliary nodes saved by stack dynamically with the help of the binomial tree model, and achieves low time and space complexity for the traversing of a reverse hash chain with any length. Analyzing the time and space complexity with the help of the binomial tree model, the result shows that the proposed algorithm requires only ⌈ log2n ⌉ / 2 hash operations per chain link traversal and ⌈ log2n ⌉ + 1 chain links to be save at the same time, where n is the length of the reverse hash chain. Compared to other algorithms, our algorithm can be applied to hash chain with any length without the limitation that the length must be of 2 integer-th power, and the proof is more exact.