Моделювання та програмна реалізація тестування низького ступеня у криптографічних протоколах доказу з нульовим розголошенням

Abstract

У роботі проведено моделювання та тестування низького ступеня у криптографічних протоколах доказу із нульовим розголошенням шляхом програмної реалізації першого етапу «Арифметизація» роботи протоколу ZK-STARK. Створено програмну реалізацію першого етапу роботи протоколу STARK «Арифметизація» шляхом написання двох програм КПСІВРП STARK-01 та КПСІВРП-STARK-02 на мові програмування C++ на «домашньому комп’ютері». Програма КПСІВРП-STARK-01 використовує метод Гауса для пошуку коренів інтерполяційного полінома. Програма КПСИВРП-STARK-02, яка використовує метод обернених матриць для пошуку коренів інтерполяційного полінома. Тестування першого етапу «Арифметизація» протоколу ZK-STARK для оцінки тривалості роботи програми від розміру матриці пошуку коренів інтерполяційного поліному виявило, що Програма КПСІВРП-STARK-01 потребує меншого об’єму пам’яті, ніж програма КПСІВРП-STARK-02. Апроксимація за вхідними даними обох програм в Mathcad виявила що: залежність об’єму пам’яті, яку потребують обидві програми при роботі, від розміру матриці пошуку коренів інтерполяційного полінома має нелінійний характер. Ефективність створених Програм з урахуванням можливостей «домашнього комп’ютеру» та міжнародного досвіду вирішення СЛАР з великою кількістю невідомих та рівнянь, показало, що залежність часу роботи Програми КПСІВРП-STARK-01 та КПСІВРП-STARK-02 від розміру матриці пошуку коренів інтерполяційного полінома має поліноміальний характер, який можна виразити якісною залежністю f(x) = x3. Залежність об’єму пам’яті, які потребують дві програми при роботі, від розміру матриці пошуку коренів інтерполяційного полінома має також нелінійний характер. Залежність об’єму пам’яті, яку потребує матриця пошуку коренів інтерполяційного полінома від її розміру насить також нелінійний характер. Більшу частину часу роботи першого етапу «Арифметизація» протоколу ZK STARK займає саме розрахунок коренів інтерполяційного поліному. Вирішення СЛАР з великою кількістю невідомих та рівнянь – це дуже складна обчислювальна задача. Тому, якщо діяльність протоколу STARK зумовлює рішення СЛАР, такого розміру, які наведені у таблицях чи більшого розміру, то, наразі, має сенс розподілити обчислення між комп’ютерами обчислювальної мережі задля прискорення роботи першого етапу роботи протоколу або збільшити потужність окремих вузлів мережі. Для більш швидкої реалізації протоколу слід використовувати метод Гауса для пошуку коренів інтерполяційного полінома, ніж метод обернених матриць. Для оброблення дуже великих обсягів даних, протокол STARK має бути реалізований на обладнанні, яке значно потужніше, ніж те, на якому було проведене тестування протоколу, наприклад, на квантовому комп’ютері чи мережі звичайних комп’ютерів, бо залежність часу роботи протоколу та обсягу пам’яті, яку він займає при роботі від розміру матриці пошуку коренів інтерполяційного поліному носить нелінійний характер.In this work, we have modeled and tested a low degree of proof in cryptographic protocols with zero disclosure by software implementation of the first stage «Arithmetization» of the ZK-STARK protocol. A software implementation of the first stage of the STARK protocol «Arithmetization» was created by writing two programs KPSIVRP-STARK-01 and KPSIVRP-STARK-02 in the C++ programming language on a «home computer». The program KPSIVRP-STARK-01 uses the Gauss method to find the roots of an interpolation polynomial. Program KPSIVRP-STARK-02, which uses the method of inverse matrices to find the roots of an interpolation polynomial. Testing of the first stage «Arithmetization» of the ZK-STARK protocol to estimate the duration of the program operation depending on the size of the matrix for finding the roots of the interpolation polynomial revealed that the program KPSIWRP-STARK-01 requires less memory than the program KPSIWRP STARK-02. The approximation by the input data of both programs in Mathcad revealed that: the dependence of the amount of memory required by both programs on the size of the matrix for finding the roots of the interpolation polynomial is nonlinear. The effectiveness of the created programs, taking into account the capabilities of a «home computer» and international experience in solving SLARs with a large number of unknowns and equations, showed that the dependence of the operating time of the KPSIVRP-STARK-01 and KPSIVRP-STARK-02 programs on the size of the interpolation polynomial root search matrix is polynomial in nature, which can be expressed by the quality dependence f(x) = x3. The dependence of the amount of memory required by two programs during operation on the size of the root search matrix of an interpolation polynomial is also nonlinear. The dependence of the amount of memory required by the matrix for finding the roots of an interpolation polynomial on its size is also nonlinear. The calculation of the roots of the interpolation polynomial takes up most of the time of the first stage of the ZK-STARK protocol, Arithmetization. Solving a PDE with a large number of unknowns and equations is a very complex computational task. Therefore, if the activity of the STARK protocol leads to the solution of SLARs of the size shown in the tables or larger, then it makes sense to distribute the computation between computers in the computer network to speed up the first stage of the protocol or to increase the power of individual network nodes. For faster protocol implementation, the Gaussian method should be used to find the roots of the interpolation polynomial rather than the inverse matrix method. To process very large amounts of data, the STARK protocol should be implemented on hardware that is much more powerful than the one on which the protocol was tested, for example, on a quantum computer or a network of ordinary computers, since the dependence of the protocol's running time and the amount of memory it occupies during operation on the size of the interpolation polynomial root search matrix is nonlinear.