Теоретична реалізація та тестування першого етапу роботи протоколу ZK-STARK «Арифметизація»

Анотація

Актуальність: З появою Інтернету світ почав стрімко змінюватися, до того ж темп змін постійно зростає, тому проблема збереження та обробки даних стає все більш актуальною. Протокол ZK-STARK - це новий криптографічний протокол, який ще не має масового застосування на практиці та дозволяє перевірити повідомлення чи транзакцію в мережі Блокчейн на достовірність, не відтворюючи її повністю. На даний момент, виявлені прогалини та проблеми, пов'язані з його застосуванням: обчислювальна складність, можлива погана сумісність з іншими протоколами, стійкість до атак з боку квантових компп’ютерів. Тому у роботі вирішено доповнити висвітлення проблеми, пов’язаної з обчислювальною складністю та запропонувати варіанти вирішення цієї проблеми.

Мета: на основі теоретичної реалізації першого етапу Arethmetization роботи протоколу ZK-STARK провести  тестування його програмної реалізації задля надання рекомендацій щодо його найбільш обчислювально-ефективної версії.

Методи дослідження: математичні відомості з теорії інтерполювання, теорії груп, теорії чисел; відомості про числа Фібоначчі; відомості про функцію Ейлера; породжуючий елемент групи; циклічні групи; інтерполяційний поліном Лагранжа та послідовність обчислень, також середа програмування Visual Studio 2022, мова програмування C++, бібліотека NTL, Microsoft Excel.

Результати: результатом роботи є теоретична реалізація роботи першого етапу протоколу ZK-STARK та тестування на ефективність першого етапу, та надання рекомендацій щодо його найбільш ефективного версії.

Висновок: Тестування показало, що практичне впровадження Арифметизації на основі ШЗПФ має часову складність n*log⁡(n), яка у (n^3)/(n*log⁡(n)) разів менша, ніж часова складність Арифметизації на основі ЗМ та Г, що прискорює роботу етапу Арифметизація протоколу ZK-STARK.