Приветствуем! Впервые на сайте 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!

Язык

Выращивание деревца: Новые Крипто Инициативы

Sean Bowe | Jul 26, 2017

Следующее крупное обновление протокола Zcash, названное Sapling, включает большое количество улучшений производительности, безопасности и удобства для того, что мы называем скрытые транзакции. Это первая из серии статей в блоге, которые будут описывать прогресс в разработке Sapling.

BLS12-381: новая кривая zk-SNARK

zk-SNARK, используемые в Zcash, в настоящее время основываются на дружественных к парам конструкциям эллиптических кривых Баррето-Наерига, реализованных в libsnark, библиотеке, которая была разработана нашими иcследователями много лет назад. С тех пор была реализована оптимизация Кима-Барбулеску использующая общий метод решета числового поля и предположительно снижающая уровень безопасности до примерно 110 бит, хотя безопасность конкретной кривой, как показали наши исследования, остаётся около 128-бит, как и было первоначально.

В качестве дополнительной предосторожности, мы воспользовались возможностью обновить наши эллиптические кривые в обновлении Sapling. Ранее в том году, я презентовал новую кривую, которая называется BLS12-381. Эта кривая предназначается для 128-битной безопасности, использующей более консервативные рекомендации, предложенные в нескольких недавних работах.

Сейчас у нас есть написанное на языке Rust внедрение этой кривой. В нём появились усиленные гарантии безопасности памяти, поскольку не используются небезопасные{} оптимизации кода или сборок. Несмотря на то, что кривая стала больше, это новое внедрение более эффективно, чем та реализация BN254, которую мы в настоящий момент используем в Zcash.

измерения производительности

Ускорения особенно заметны в парах и \(\mathbb{G}_2\) вычислениях, что увеличивает производительность проверки и верификации zk-SNARK.

Новый алгоритм мультивозведения в степень

Самая дорогая часть создания доказательства zk-SNARK это оценка больших многочленов в группах эллиптических кривых \(\mathbb{G}_1\) and \(\mathbb{G}_2\). Она делается с помощью алгоритма так называемого "мультивозведения в степень" который вычисляет \(\prod_{i=0}^{n}{b_{i}^{s_i}}\) для некоторого большого количества порядков \(\vec{s}\) которые находятся в памяти, и большого количества оснований \(\vec{b}\) которые находятся на диске, в ключе проверки zk-SNARK.

В настоящее время мы используем в libsnark внедрение алгоритма Bos-Костера. В худшем случае, этот алгоритм использует столько же памяти как и основания над которыми производятся операции, и таким образом, единственный путь уменьшить использование памяти состоит в том, чтобы работать с меньшими количествами оснований за один раз. Например, Ариэль Габизон реализовал этот вид оптимизации как изменения в libsnark.

libsnark недавно внедрили вариант алгоритма Пиппенгера, разделяющего мультивозведение в степень на побитовые операторы в области экспоненты, накапливая основания и выполняя суммирование частями. Этот алгоритм не только более эффективный, чем алгоритм Боса-Костера, но также очень удобен в контексте нашего доказательства. Используя этот алгоритм, мы можем избежать загрузки ключа доказательства в память до того, как сконструировать доказательство, которое является основным источником использования памяти в нашей системе.

Новая система проверки

Конечно, выполнение меньшего количества возведений в степень могло бы стать хорошим способом улучшить производительность времени вычисления. Мы сильно полагаемся на то, что Новая система проверки zk-SNARK, разработанная Йенсом Гротом, позволит заменить PGHR (Пиноккио). Эта система проверки делает более сильные криптографические предположения, но имеет меньшие размеры доказательств и более быструю проверку/верификацию.

Кроме того, новая система доказательства Грота позволяет нам проектировать более дешевые вычисления для нескольких участников и другие действительно интересные особенности, о которых мы расскажем в следующих статьях для блога.

Следующие шаги

Хотя вышеупомянутые усилия объединили наши предложения по улучшению использования памяти и сокращению времени проверки, уменьшение размера нашей схемы zk-SNARK даст гораздо более заметный эффект. Мы построили большое количество новых криптографических примитивов поверх конструкции BLS12-381, что позволило нам сократить размеры арифметических схем, сократить размеры адресов Zcash, и упростить протокол.

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

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