Масштабируемые zk-SNARK
- Страницы / Pages
- 34-41
Аннотация
Описан общий принцип работы (этапы, используемые параметры) схемы доказательства с нулевым разглашением zk-SNARK, возможность и перспективы его улучшения. Реализации zk-SNARK, которые известны на данный момент, имеют ограничения масштабируемости, обусловленные величиной доказываемого вычисления. Во-первых, размер доказывающего ключа по крайней мере линейно зависит от верхней границы структуры, в которой мы работаем. Во-вторых, при доказательстве требуется запись всех предыдущих шагов. В статье описывается алгоритм достижения новой реализации zk-SNARK с использованием криптографии на эллиптических кривых, особенностей структуры поля и цельности доказательств. Практически такая реализация является рекурсивной композицией доказательства, при этом генерация ключей для любых размеров вычислений несет постоянные расходы по памяти. В дальнейшем в процессе доказательства осуществляются только постоянные мультипликативные по времени и аддитивные по памяти расходы. Таким образом, описанная реализация zk-SNARK наделяется двумя важными свойствами: емкость и инкрементальная вычислимость.
Abstract
This article describes the General principle of operation (stages, parameters used) of the ZK-SNARK zero-knowledge proof scheme, the possibility and prospects for its improvement. Implementations of zk-SNARK that are currently 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 cryptography, field structure features, and proof integrity. In practice, this implementation is a recursive composition of the proof, while generating keys for any size of calculations carries constant memory costs. Subsequently, the entire process of proof is solely multiplicative constant costs overtime and additivecosts 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.