Вестник БФУ им. И. Канта

Текущий выпуск

Назад к списку Скачать статью

Масштабируемые zk-SNARK

Страницы / Pages
34-41

Аннотация

Описан общий принцип работы (этапы, используемые параметры) схемы доказательства с нулевым разглашением zk-SNARK, возможность и перспективы его улучшения. Реализации zk-SNARK, которые извест­ны на данный момент, имеют ограничения масштабируемости, обу­словленные величиной доказываемого вычисления. Во-первых, размер до­казывающего ключа по крайней мере линейно зависит от верхней грани­цы структуры, в которой мы работаем. Во-вторых, при доказатель­стве требуется запись всех предыдущих шагов. В статье описывается алгоритм достижения новой реализации zk-SNARK с использованием криптографии на эллиптических кривых, особенностей структуры по­ля и цельности доказательств. Практически такая реализация являет­ся рекурсивной композицией доказательства, при этом генерация клю­чей для любых размеров вычислений несет постоянные расходы по па­мяти. В дальнейшем в процессе доказательства осуществляются толь­ко постоянные мультипликативные по времени и аддитивные по па­мяти расходы. Таким образом, описанная реализация zk-SNARK наделя­ется двумя важными свойствами: емкость и инкрементальная вычис­лимость.

Abstract

This article describes the General principle of operation (stages, parame­ters used) of the ZK-SNARK zero-knowledge proof scheme, the possibility and prospects for its improvement. Implementations of zk-SNARK that are cur­rently known have scalability limitations that depend on the magnitude of the computation being proved. First, the size of the proving key depends at least linearly on the upper bound of the structure in which we work. Second, the proof requires a record of all previous steps. The article describes an algorithm for achieving a new implementation of zk-SNARK using elliptic curve cryp­tography, field structure features, and proof integrity. In practice, this imple­mentation is a recursive composition of the proof, while generating keys for any size of calculations carries constant memory costs. Subsequently, the en­tire process of proof is solely multiplicative constant costs overtime and addi­tivecosts in memory. Thus, the described implementation of zk-SNARK has two important properties: capacity and incremental computability.

Список литературы

1. Sasson E., Chiesa A., Tromer E., Virza M. Scalable Zero Knowledge via Cycles of Elliptic Curves // Algorithmica. 2017. № 79 (4). P. 1102—1160.

2. Что такое zk-SNARK? // Z.CASH.RU : офиц. сайт криптовалюты Zcash. URL: https://z.cash/ru/technology/zksnarks (дата обращения: 07.11.2020).

3. Что такое zk-SNARKs и zk-STARKs? // Binance Academy : [сайт]. URL: https://academy.binance.com/ru/articles/zk-snarks-and-zk-starks-explained (дата обраще­ния: 07.11.2020).

4. Мельничук Е. М., Новоселов С. А. Характеристические многочлены некото­рых гиперэллиптических кривых родов 2, 3 и p-ранга // Прикладная дискрет­ная математика. Приложение. 2019. № 12. С. 21—24.