Теоретична реалізація та тестування першого етапу роботи протоколу ZK-STARK «Арифметизація»
DOI:
https://doi.org/10.26565/2304-6201-2024-63-01Ключові слова:
протокол, ZK-STARK, АРЕТМІТИЗАЦІЯ, моделювання, програма, реалізація, мова програмування C, тестування, блокчейн, ефективністьАнотація
Актуальність: З появою Інтернету світ почав стрімко змінюватися, до того ж темп змін постійно зростає, тому проблема збереження та обробки даних стає все більш актуальною. Протокол ZK-STARK - це новий криптографічний протокол, який ще не має масового застосування на практиці та дозволяє перевірити повідомлення чи транзакцію в мережі Блокчейн на достовірність, не відтворюючи її повністю. На даний момент, виявлені прогалини та проблеми, пов'язані з його застосуванням: обчислювальна складність, можлива погана сумісність з іншими протоколами, стійкість до атак з боку квантових компп’ютерів. Тому у роботі вирішено доповнити висвітлення проблеми, пов’язаної з обчислювальною складністю та запропонувати варіанти вирішення цієї проблеми.
Мета: на основі теоретичної реалізації першого етапу Arethmetization роботи протоколу ZK-STARK провести тестування його програмної реалізації задля надання рекомендацій щодо його найбільш обчислювально-ефективної версії.
Методи дослідження: математичні відомості з теорії інтерполювання, теорії груп, теорії чисел; відомості про числа Фібоначчі; відомості про функцію Ейлера; породжуючий елемент групи; циклічні групи; інтерполяційний поліном Лагранжа та послідовність обчислень, також середа програмування Visual Studio 2022, мова програмування C++, бібліотека NTL, Microsoft Excel.
Результати: результатом роботи є теоретична реалізація роботи першого етапу протоколу ZK-STARK та тестування на ефективність першого етапу, та надання рекомендацій щодо його найбільш ефективного версії.
Висновок: Тестування показало, що практичне впровадження Арифметизації на основі ШЗПФ має часову складність n*log(n), яка у (n^3)/(n*log(n)) разів менша, ніж часова складність Арифметизації на основі ЗМ та Г, що прискорює роботу етапу Арифметизація протоколу ZK-STARK.
Посилання
CONSENSYS, "Zero-Knowledge Proofs: STARKs vs SNARKs," BLOCKCHAIN EXPLAINED, [Online]. Available: https://consensys.net/blog/blockchain-explained/zero-knowledge-proofs-starks-vs-snarks/. [Accessed: 30-Apr-2023].
Bit2Me ACADEMY, "What are zk-STARKs?," [Online]. Available: https://academy.bit2me.com/en/what-are-zk-stark/. [Accessed: 30-Apr-2023].
Chainlink, "Understanding the Difference Between zk-SNARKs and zk-STARKS," [Online]. Available: https://chain.link/education-hub/zk-snarks-vs-zk-starks. [Accessed: 25-Apr-2024].
Ramses F., "STARKs vs SNARKs," Medium, [Online]. Available: https://medium.com/@ramsesfv/starks-vs-snarks-d2e09c4e6069. [Accessed: 25-Apr-2024].
"Throne of ZK: SNARK vs STARK," Medium, [Online]. Available: https://medium.com/nonce-classic/throne-of-zk-snark-vs-stark-e449984d5c36. [Accessed: 25-Apr-2024].
Techopedia, "Zero-Knowledge STARK (zkSTARK)," [Online]. Available: https://www.techopedia.com/definition/zero-knowledge-stark-zkstark. [Accessed: 25-Apr-2024].
Changelly Blog, "New Technology Explained: Zero-Knowledge Proof – Security Enhancing Protocol," [Online]. Available: https://changelly.com/blog/zero-knowledge-proof-explained/. [Accessed: 25-Apr-2024].
Hacken, "Comparing ZK-SNARKs & ZK-STARKs: Key Distinctions In Blockchain Privacy Protocols," [Online]. Available: https://hacken.io/discover/zk-snark-vs-zk-stark/. [Accessed: 25-Apr-2024].
Binance Academy, "zk-SNARKs and zk-STARKs Explained," [Online]. Available: https://academy.binance.com/en/articles/zk-snarks-and-zk-starks-explained. [Accessed: 30-Apr-2023].
Binance Academy, "zk-STARKs," [Online]. Available: https://academy.binance.com/en/glossary/zk-starks. [Accessed: 25-Apr-2024].
StarkWare, "Arithmetization I," Medium, [Online]. Available: https://medium.com/starkware/arithmetization-i-15c046390862. [Accessed: 25-Apr-2024].
Polygon Labs, "Introducing Plonky2," Polygon, [Online]. Available: https://polygon.technology/blog/introducing-plonky2. [Accessed: 25-Apr-2024].
StarkWare Team, "ethSTARK Documentation Version 1.1," IACR, [Online]. Available: https://eprint.iacr.org/2021/582.pdf. [Accessed: 25-Apr-2024].
H. P. William, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, Numerical Recipes in C++. The Art of Scientific Computing, 2nd ed: Cambridge University Press, Cambridge, 2003, 1004 с.
Державний університет "Житомирська політехніка", "Освітній портал," [Online]. Available: https://learn.ztu.edu.ua. [Accessed: 25-Apr-2024].
Р. М. Літнарович, Алгебра матриць: Курс лекцій, Рівне, Україна: МЕГУ, 2007, 112 с. [Online]. Available: https://core.ac.uk/download/pdf/14034615.pdf. [Accessed: 25-Apr-2024].
О. О. Кузнецов, "Конспект лекцій по математичним основам криптографічних доказів з нульовим розголошенням. Лекція №22: Дискретне перетворення Фур'є," PROXIMA LABS, 1501 Larkin Street, Suite 300, San Francisco, USA, 13 с.
"The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever?," Youtube, [Online]. Available: https://www.youtube.com/watch?v=h7apO7q16V0. [Accessed: 25-Apr-2024].
О. О. Кузнецов, "Конспект лекцій по математичним основам криптографічних доказів з нульовим розголошенням. Лекція №23: Дискретне перетворення Фур'є в кінцевих полях," PROXIMA LABS, 1501 Larkin Street, Suite 300, San Francisco, USA, 13 с.
