ALGORITHMIC SUPPORT FOR DATA INTEGRITY CONTROL BASED ON THE MERKLE TREE

Abstract

The article examines algorithmic and cryptographic aspects of data integrity assurance using a hierarchical hash structure known as a Merkle tree. The relevance of such structures in modern information systems is substantiated, particularly in the context of large-scale data processing, cloud services, and distributed ledgers. Traditional integrity control approaches, including checksums, flat and block hashing, as well as message authentication codes, are analyzed, and their limitations in terms of scalability and efficiency of partial verification are identified. A formalized description of the Merkle tree as a complete binary tree is presented, where nodes store cryptographic hash values and the root hash serves as a compact representation of the entire dataset. An analytical evaluation of time and space complexity for the main operations–tree construction, single-block verification, and update–is performed. It is shown that construction has linear complexity O(n), while verification and update of a single element exhibit logarithmic complexity O(log n), ensuring efficiency as the data volume increases. A dynamic binary tree implementation in C++ was developed with support for interchangeable cryptographic hash functions. An experimental performance study was conducted using SHA-256 and the national hash function Kupyna-256 in accordance with DSTU 7564:2014. The results confirmed the theoretical complexity estimates and demonstrated stable scalability behavior for datasets up to several gigabytes. It was established that the use of Kupyna increases execution time by approximately 25–30 % compared to SHA-256 without affecting the overall scalability pattern. The scientific novelty of the work consists in a systematic analytical study of the algorithmic characteristics of the Merkle tree, experimental confirmation of the logarithmic dependence of verification time on data size under practical conditions, and assessment of the practical applicability of a national hash function within an integrity control structure. The obtained results may be applied in the design of secure distributed file systems, cloud services, and blockchain-oriented applications.