Minimizing Redundant Hash and Witness Operations in Merkle Hash Trees

Reusing cached data is a widely adopted technique for improving network and system performance. Future Internet architectures such as Named Data Networking (NDN) leverage intermediate nodes—such as proxy servers and routers—to cache and deliver data, reducing latency and alleviating load on original data sources. However, a fundamental challenge of this approach is the lack of trust in intermediate nodes, as users cannot reliably identify and verify them. To address this issue, many systems adopt data-oriented verification rather than sender authentication, using Merkle Hash Trees (MHTs) to enable users to verify both the integrity and authenticity of received data. Despite its advantages, MHT-based authentication incurs significant redundancy: identical hash values are often recomputed, and witness data are repeatedly transmitted for each segment. These redundancies lead to increased computational and communication overhead, particularly in large-scale data publishing scenarios. This paper proposes a novel scheme to reduce such inefficiencies by enabling the reuse of previously verified node values, especially transmitted witnesses. The proposed scheme improves both computational and transmission efficiency by eliminating redundant computation arising from repeated calculation of identical node values. To achieve this, it stores and reuses received witness values. As a result, when verifying 2n segments (n > 8), the proposed method achieves more than an 80% reduction in total hash operations compared to the standard MHT. Moreover, our method preserves the security guarantees of the MHT while significantly optimizing its performance in terms of both computation and transmission costs.