Обмен электронных валют по самому выгодному курсу!
 


Kurbetsoft
Доступно в Google PlayО технологии Bulletproofs, об ускорении Rangeproofs и не только

 

В 2015 году мы анонсировали «конфиденциальные транзакции» (Confidential Transactions) в качестве главной особенности сайдчейна Elements Alpha. Данная функция заменяет суммы транзакций «обязательствами Педерсена» (Pedersen commitments) — криптографическим инструментом, который скрывает сумму сделки, при этом оставляя возможность кому угодно проверять совпадение сумм на входе и выходе любой отдельной транзакции.

Основная проблема конфиденциальных транзакций заключалась в том, что они увеличивали размер транзакций и замедляли проверку, поскольку требовалось, чтобы выход каждой транзакции содержал «доказательство диапазона» (Rangeproof) — один из видов доказательства с нулевым разглашением, который подтверждает, что суммы слишком малы для того, чтобы образовалась очередь. В то время как длина обычной цифровой подписи составляет менее 100 байт, а время подтверждения занимает меньше 100 микросекунд, доказательства диапазона по размеру достигали нескольких килобайт, а время подтверждения измерялось миллисекундами. Фактически, доказательства диапазона составляли основную часть данных любой транзакции, в которой они использовались.

Несмотря на то, что наши доказательства диапазона, основанные на кольцевой подписи, работающей по принципу колец Борромео, были быстрейшими и наименьшими из всех известных, для требуемых размеров диапазона и без «доверенной установки» они были все еще довольно велики.

После 2015 были предприняты попытки повысить эффективность доказательств диапазона. В начале 2017 Адам Бэк (Adam Back) нашел способ уменьшить размер доказательства диапазона на 24%, но без повышения эффективности проверки. Примерно в то же время мы обратились с этой проблемой к нашим друзьям и коллегам-криптографам Дэну Боне (Dan Boneh) и Бенедикту Бюнцу (Benedikt Bunz) из Стэнфордского университета, которые были убеждены в том, что технологию можно улучшить.

Мы были поражены тем, к чему они в итоге пришли.

Меньше, Быстрее, Сильнее

Технология Bulletproofs, берущая свое начало из работ Джонатана Бутла (Jonathan Bootle) и других от 2016 года, посвященных повышению эффективности использования дискретного логарифмирования, лежащего в основе доказательства с нулевым разглашением, представляет собой более эффективную форму этого самого доказательства. Для наших целей важно то, что Bulletproofs имеет встроенную поддержку обязательств Педерсена и открытых ключей. Это дает нам возможность реализовать доказательства диапазона на общих принципах нулевого разглашения без осуществления тяжелых машинных расчетов эллиптических кривых.

Меньше. Для уменьшения размера транзакций наши прежние доказательства диапазона ограничивали выходы до значения 232. Это уменьшало выходы примерно до 43 BTC, но это значение можно было увеличить, уменьшив точность доказательств с 1 сатоши до 10 или 100 или сделав минимально возможное значение отличным от нуля. Подобные корректировки были возможны, но использование конкретных сумм снижает уровень конфиденциальности, которую обеспечивает система.

Изначально 32-битные доказательства диапазона достигали примерно 2.5 кибибайт. В результате оптимизации, проведенной Адамом, их размер должен был уменьшиться до 2 КиБ. С помощью Bulletproofs они бы достигли 610 байт. Благодаря таким скромным размерам мы бы могли удвоить диапазон до 64 бит, избавившись от необходимости любых корректировок. Это бы означало увеличить размер с ничтожных 610 байт до 1220, правильно? Нет. На самом деле, с технологией Bulletproofs размер 64-битных доказательств диапазона составляет всего лишь 674 байта.

Сильнее. Причина, по которой мы смогли удвоить диапазон, добавив только 64 байта к размеру доказательства, состоит в том, что их размер растет логарифмически. Делается это с использованием одного из вариантов аргумента скалярного произведения, взятого из доклада Бутла и других от 2016 года (Джонатан Бутл также помогал Бенедикту и Дэну в разработке Bulletproofs). В частности, логарифмический размер аргумента, описанного в докладе, в технологии Bulletproofs сократился еще сильнее, со значения 6log(N) точек кривой до 2log(N).

Этот же трюк позволяет объединить несколько доказательств диапазона внутри транзакции воедино, при этом лишь незначительно увеличив ее размер. Таким образом, совокупность двух доказательств диапазона будет иметь размер 738 байт, четырех — 802, восьми — 866. Без Bulletproofs восемь 64-битных доказательств диапазона имели бы размер больше 40000 байт!

Быстрее. Такая экономия пространства — это замечательно, но наш предварительный анализ данного метода показал, что проверка будет происходить медленнее в сравнении с прежними доказательствами диапазона. Это обусловлено тем, что проверка одного 64-битного доказательства потребует более 200 скалярных умножений, каждое из которых занимает 50 микросекунд, в то время как прежним доказательствам диапазона требовалось 128 умножений.

Однако после дополнительных анализов нам удалось объединить значительную часть умножений, уменьшив их общее число до 147. Но более важно достигнутое нами осознание того, что в отличие от прежних доказательств диапазона, все умножения происходят независимо друг от друга, следовательно, мы могли бы собрать их в один большой пакет данных. В ходе нашей работы над агрегированием подписей мы узнали, как сделать групповое умножение очень быстрым. Питер Вайли (Pieter Wuille), Грег Максвелл (Greg Maxwell), Джонас Ник (Jonas Nick), Питер Деттман (Peter Dettman) и я провели несколько месяцев в работе над этой проблемой и смогли уменьшить скорость каждого из 147 умножений до 15,5 микросекунд, получив общее время проверки по технологии Bulletproof равное 2,3 мс, вместо прежних 5,8 мс.

Это уже более чем двукратное увеличение скорости, но, поскольку наше пакетное умножение начинает происходить быстрее с ростом числа заданных точек на эллиптической кривой, показатели агрегирования выглядят даже более впечатляюще. Так, объединение восьми 64-битных доказательств Bulletproofs может быть проверено всего лишь за 10,7 мс, тогда как для прежних доказательств этот показатель равнялся 46,5 мс — более чем четырехкратное ускорение.

Но может быть еще лучше. Технология Bulletproofs поддерживает чрезвычайно эффективную форму пакетной проверки. Из 147 необходимых нам умножений, 130 используют одинаковые точки в каждом «пуленепробиваемом» доказательстве, это значит, что в ходе группового подтверждения эти 130 умножений могут быть объединены, в результате чего останется лишь 17. Более того, предельный показатель растет логарифмически: при объединении двух диапазонов каждое дополнительное доказательство потребует 19 дополнительных точек, при объединении четырех — 21 дополнительную точку.

Отметим, что мы представили два похожих, но самостоятельных понятия: агрегирование обозначает объединение «доказывающей стороной» (Prover) множества доказательств диапазона в одно целое, в то время как пакетирование означает проверку «подтверждающей стороной» (Verifier) множества отдельных доказательств одновременно.

Таким образом, подтверждение двух 64-битных доказательств диапазона займет менее 2,7 мс, или 1,3 мс на каждый диапазон. Подтверждение тысячи доказательств диапазона — 239 мс, или 0,24 мс на диапазон, что является 23-х кратным улучшением по сравнению с прежними доказательствами. Но из-за агрегирования показатели улучшаются еще сильнее. Тысяча восьмикратных объединений (8000 диапазонов в итоге) может быть подтверждена за 588 мс, или 74 микросекунды на каждый диапазон, что в 78 раз лучше по сравнению с прежними доказательствами диапазона.

В конечном итоге этот эффект достигает максимума при объединении 64 доказательств, так как в этот момент возрастающая эффективность умножения скалярных точек перестает оказывать решающее воздействие. На этом этапе мы можем проводить пакетную проверку менее чем за 49 микросекунд на каждый диапазон, что соответствует 120-кратному повышению эффективности. Для справки, подпись по принципу алгоритма цифровой подписи на основе эллиптических кривых (ECDSA) занимает примерно 49 микросекунд, поэтому на данном уровне агрегирования доказательство диапазона уже не играет определяющую роль в подтверждении транзакций. Конечно, мы вряд ли увидим большое количество 64-выходных транзакций в блокчейне, но такую скорость, безусловно, можно достигнуть и в неблокчейновых условиях, таких как Provisions.

Такая проверка также эффективно использует память, требуя меньше 100 КиБ для подтверждения одного доказательства диапазона и линейно изменяя масштаб по мере увеличения размера.

Можно доказать всё, что угодно (если это правда)

Доказательства Bulletproofs представлены в гораздо более общем виде, нежели доказательства диапазона. Они могут использоваться для доказательства произвольных утверждений с нулевым знанием. По своей эффективности технология сопоставима с zk-SNARKs или zk-STARKs, но имеет встроенную поддержку открытых ключей на эллиптической кривой и обязательств Педерсена (поэтому, как правило, отсутствует необходимость осуществлять вычисления эллиптической кривой внутри проверенной программы). Также, в отличие от zk-SNARKs, доказательства Bulletproofs имеют полный 128-битный уровень криптостойкости в соответствии со стандартными предположениями без использования «доверенной установки». И, в отличие от zk-STARKs, они достаточно быстры, чтобы можно было доказывать и проверять разумные по масштабу задачи на обычном вычислительном оборудовании.

В качестве примера рассмотрим один пробег функции сжатия SHA-2. Нашему «доказывающему» требуется менее 30 МиБ памяти и примерно 13 секунд, чтобы доказать знание прообраза функции SHA-2. Для проверки требуется приблизительно 23 МиБ памяти и 435 мс, но мы можем провести пакетную проверку дополнительных доказательств примерно за 28 мс, и на каждый уйдет по 13,4 КиБ. В результате размер доказательства составляет всего лишь 1379 байт.

Наш «доказывающий» более эффективно потребляет память, нежели zk-SNARKs: на одной и той же системе SNARK-доказательство для SHA-2 занимает только 4 секунды, но при этом 75 МиБ памяти. Тогда подтверждение, требующее единоразово провести объемное предварительное вычисление для каждой цепи (описание утверждения, которое подлежит доказать), займет лишь 3-5 секунд и совсем немного памяти для проверки. Эти показатели не увеличиваются с ростом размера цепи, поэтому при нескольких тысячах «гейтов» SNARKs выйдет явным победителем даже против нашей пакетной проверки. К сожалению, это происходит за счет «доверенной установки» и новых криптографических предположений.

По-прежнему остаются значительные возможности для дополнительной оптимизации технологии Bulletproofs как на доказывающей стороне, так и на проверяющей.

Право доказывать произвольные утверждения — будь то путем Bulletproofs, zk-SNARKs или zk-STARKs — имеет множество применений. Может использоваться для реализации простых электронных подписей, включая (прослеживаемые) кольцевые подписи и пороговые подписи — которые для больших колец, по всей видимости, являются более эффективными, чем традиционные схемы, как по времени проверки, так и по размеру доказательства — но все не ограничивается только этим. Оно может использоваться для решения проблем ненадежной торговли с помощью задач Судоку. Может применяться в многосторонних расчетах для доказательства того, что каждая сторона действовала честно, даже с конфиденциальной информацией (в частности, при использовании схем мультиподписей, наподобие MuSig, позволяет осуществить генерацию детерминированных одноразовых кодов, не требуя от подписавшегося лица поддерживать состояние, чтобы не быть подверженным атакам с повторным использованием кода). Может использоваться для подтверждения прообраза хеш-функции.

Прообразы хеш-функций представляют особенный интерес, поскольку они могут использоваться для создания доказательств Меркла с нулевым разглашением, которые эффективны при охвате огромного массива данных (состоящего из миллиона или миллиарда элементов). Мы рассмотрим их более подробно в одной из будущих статей.

Заключение

  • В основе технологии Bulletproofs лежат общие принципы доказательства с нулевым разглашением (как и в zk-SNARKs);
  • Технология может использоваться для расширения многосторонних протоколов, таких как мультиподписи или условные платежи с нулевым знанием;
  • Bulletproofs предоставляет гораздо более эффективную версию доказательств диапазона конфиденциальных транзакций (при использовании пакетной верификации скорость проверки увеличивается более чем в 23 раза);
  • Такие доказательства диапазона могут быть объединены внутри транзакции, при этом её размер будет расти логарифмически;
  • При должном агрегировании, таком как Provisions, пакетная верификация дает более чем 120-кратный прирост скорости, по сравнению с прежними доказательствами.

Мы бы хотели поблагодарить Джонатана Бутла и всех тех, кто с ним работал над созданием аргумента скалярного произведения, который позволил добиться всего этого, а также Бенедикта Бюнца и Дэна Боне, наших соавторов, которые проделали большую часть изобретательской работы. Кроме того, хотели бы поблагодарить Шона Буе и Дайру Хопвуд за их исследования по оптимизации арифметических цепей.

Все вычисления производились на одном ядре процессора Intel i7-6820HQ с тактовой частотой 2.7 ГГц.

Источник

 

 

 

 




[vkontakte] [facebook] [twitter] [odnoklassniki] [mail.ru] [livejournal]

Каталог сайтов