Theoretical implementation and testing of the first stage of the ZK-STARK protocol “Arithmetisation”

Abstract

Relevance:  Starting with the invention of the Internet, the world began to change rapidly, and the pace of change is increasing, so the problem of data storage and processing is becoming more and more relevant. The ZK-STARK protocol is a new cryptographic zero-knowledge proof protocol that is not yet widely used in practice and allows you to check a message or a transaction on the blockchain network for authenticity without reproducing it completely. At the moment, gaps and problems related to this protocol are identified: computational complexity, possible poor compatibility with other protocols, and resistance to attacks from quantum computers. Therefore, the paper aims to supplement the coverage of the problem associated with computational complexity and to propose solutions to this problem.

Purpose: on the basis of the theoretical implementation of the first stage named Arithmetization of the ZK-STARK protocol, to test its software implementation in order to provide recommendations on its most computationally efficient version.

Research methods: mathematical statements on interpolation theory, group theory, number theory; information on Fibonacci numbers; information on the Euler function; generating element of a group; cyclic groups; Lagrange interpolation polynomial and the sequence of calculations of Arithmetization; Visual Studio 2022 programming environment, C⁺⁺ programming language, NTL library, Microsoft Excel.

Results of work: The result of the work is the theoretical implementation of the first stage of the ZK-STARK protocol and the effectiveness testing of the first stage, and providing recommendations for its most effective version. 

Conclusion: Testing has shown that the practical implementation of the Arithmetization based on the inverse fast Fourier transform has a time complexity , that is in  times less than the time complexity of the Arithmetization based on  inverse matrices method and Gaussian method for interpolation, that speeds up the work of Arithmetization of  the ZK-STARK protocol.