АЛГОРИТМІЧНЕ ЗАБЕЗПЕЧЕННЯ КОНТРОЛЮ ЦІЛІСНОСТІ ДАНИХ НА ОСНОВІ ДЕРЕВА МЕРКЛА

Анотація

У статті досліджено алгоритмічні та криптографічні аспекти забезпечення цілісності даних із використанням ієрархічної хеш-структури типу дерева Меркла. Обґрунтовано актуальність застосування таких структур у сучасних інформаційних системах, зокрема в умовах обробки великих масивів даних, функціонування хмарних сервісів та розподілених реєстрів. Проаналізовано традиційні підходи до контролю цілісності, включаючи контрольні суми, плоске та блокове хешування, а також механізми автентифікаційних кодів повідомлень, і визначено їхні обмеження щодо масштабованості та ефективності перевірки окремих фрагментів даних. Наведено формалізований опис дерева Меркла як повного двійкового дерева, у вузлах якого зберігаються криптографічні хеш-значення, а кореневий хеш слугує компактним представленням усього набору даних. Виконано аналітичну оцінку часової та просторової складності основних операцій – побудови структури, перевірки окремого блоку та його оновлення. Показано, що побудова дерева характеризується лінійною складністю O(n), тоді як операції перевірки та оновлення одного елемента мають логарифмічну складність O(log n), що забезпечує ефективність роботи зі зростанням обсягу даних. Реалізовано програмну модель динамічного двійкового дерева мовою C++ з можливістю використання різних криптографічних хеш-функцій. Проведено експериментальне дослідження продуктивності із застосуванням SHA-256 та національної хеш-функції «Купина-256» відповідно до ДСТУ 7564:2014. Отримані результати підтвердили теоретичні оцінки складності та продемонстрували збереження характеру залежностей при збільшенні обсягу даних до кількох гігабайтів. Встановлено, що використання «Купини» призводить до збільшення часу виконання приблизно на 25–30 % порівняно з SHA-256 без зміни масштабованості алгоритму. Наукова новизна роботи полягає у систематизованому аналітичному дослідженні алгоритмічних характеристик дерева Меркла, експериментальному підтвердженні логарифмічної залежності часу перевірки від розміру даних у реальних умовах та оцінюванні практичної доцільності використання національної хеш-функції у структурі контролю цілісності. Отримані результати можуть бути використані під час проєктування безпечних розподілених файлових систем, хмарних сервісів та блокчейн-орієнтованих застосувань.