Приветствуем! Впервые на сайте Zcash?
The Zcash network is young, but evolving quickly! Sign up and we'll be in touch with monthly highlights on ecosystem growth, network development and how to get started with Zcash!

Язык

BLS12-381: Новая схема эллиптической кривой zk-SNARK

Sean Bowe | Mar 11, 2017

Наша команда неустанно работает над повышением уровня безопасности, производительностью и юзабилити скрытых транзакций, сохраняющих конфиденциальными наши с вами личные данные. Как мы уже упомянули в нашем посте о ближайшем будущем, мы работаем над сетом криптографических усовершенствований для следующей версии Zcash, которая будет называться Sapling. Одна из наших целей - повысить производительность скрытых транзакций при этом снизив затраты памяти на их выполнение.

The BLS12-381 curve.

В прошлом месяце я некоторое время занимался разработкой и возможностью применения новой схемы построения эллиптической кривой, оптимальной для zk-SNARKs с уровнем безопасности 128 бит, которая также подходила бы для работы с криптографией спаривания. Такая конструкция позволит снизить затраты на выполнение и значительно повысит надежность и безопасность.

В скором времени выйдет публикация за авторством наших научных сотрудников, в которой будет более подробно описана сама конструкция и почему она была выбрана.

Кривые Баррето-Наерига

Кривые Баррето-Наерига (BN) - это класс используемых в криптографии спаривания эллиптических кривых над базисным полем \(\mathbb{F}_q\) порядка \(r\), где \(r \approx q\). На сегодняшний день мы используем конструкцию с \(q \approx 2^{254}\). В прошлом году Ким и Барбулеску представили измененный алгоритм метода решета числового поля. Согласно последней публикации этот алгоритм - вопреки консервативному мнению [1] - позволяет сохранить безопасность при уровне 110 бит.

Вопреки консервативной точки зрения, возможно построить новую эллиптическую кривую Баррето-Наерига для 128-битного уровня безопасности, если взять кривую ближе к \(q \approx 2^{384}\). Как бы то ни было, чем больше порядок элемента группы \(r\), тем хуже производительность мульти-экспоненцирования, скорость преобразования Фурье и прочих криптографических операций, которые необходимы для эффективной работы zk-SNARK и протокола конфиденциального вычисления. Кроме того, чем больше скалярное поле \(\mathbb{F}_r\), тем более массивными становятся ключи, что совсем некстати.

Кривые Баррето-Линн-Скотт

Кривые Баррето-Линн-Скотт (BLS) относятся к более старому классу эллиптических кривых, которые, как оказалось, больше подходят для достижения нужного нам уровня безопасности. Согласно текущим исследованиям, при \(q \approx 2^{384}\) и степени вложения равной 12 можно достичь 128-битного уровня безопасности. К тому же порядок элемента группы этих кривых \(r \approx 2^{256}\), что позволяет избежать потерь со стороны производительности и юзабилити, в отличие от больших скалярных полей.

BLS12-381

В схемах zk-SNARK приходится работать с довольно большими полиномами над скалярным полем \(\mathbb{F}_r\). Мы можем выполнять эффективное многоточечное вычисление/интерполяцию с помощью быстрых преобразований Фурье, при условии, что \(\mathbb{F}_r\) содержит большой \(2^s\) корень из единицы.

Как и обычно мы ориентируемся на подсемейство этих кривых, которое бы обладало оптимальными башнями расширения поля и простыми скрученными изоморфизмами. Чтобы обеспечить эффективность применения алгоритма Монтгомери и других аппроксимационных алгоритмов, мы ориентируемся на \(r \approx 2^{255}\), чтобы самый старший бит \(r\)\(q\)) возвращался к 64.

Как принято, чтобы оптимизировать операцию спаривания, необходимо убедиться, что параметризация кривой BLS обладает низким весом Хэмминга. Кривая, которую мы по итогу выбрали, называется BLS12-381 с \(q \approx 2^{381}\).

u = -0xd201000000010000
k = 12
q = 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687 629129015664037894272559787
r = 52435875175126190479447740508185965837690552500527637822603658699938581184513
E(Fq) := y^2 = x^3 + 4
Fq2 := Fq[i]/(x^2 + 1)
E'(Fq2) := y^2 = x^3 + 4(i + 1)

Применение языка Rust

Я начал работать над применением разрабатываемой схемы на языке Rust, что входит в мой проект для zk-SNARK, который называется bellman . Библиотека должна получиться мобильной, соответствовать стандартам и иметь высокую производительность. Из-за особенностей схем zk-SNARK сложно непрерывно эффективно создавать доказательства, и поэтому в настоящее время функционирование библиотеки не фокусируется на сопротивлении атакам по сторонним каналам.

В следующих постах мы расскажем о некоторых методах и инструментах использования эллиптических кривых, которые разработали наши ученые для оптимизации Zcash.

[1]Менезес, Саркар и Сингх (http://eprint.iacr.org/2016/1102.pdf) показывают, что 2^110 является консервативной оценкой размера пространства многочленов, которое нужно определить для полиномов с гладкой функцией. Однако для случая q=p^12, соответствующего для кривых BN, в настоящее время не существует эффективного метода определения этого пространства. (Проверка каждого полинома отдельно приведет к общему времени работы более 2^128). В настоящее время наиболее эффективным известным нам и полностью описанным алгоритмом для работы с кривой Zcash является ро-алгоритм Полларда, который задействует sqrt(q)~2^127. (Мы благодарим Палаша Санкара и Шашанка Сингха за то, что они помогли понять результат их работы).

cryptography, zkSNARKs | Просмотреть все тэги