Как работает установка доверия?

Перевод статьи https://vitalik.ca/general/2022/03/14/trustedsetup.html , формулы соетую свмотреть в оригинале статьи, увы.

От величайшего телеграмм канала https://t.me/gaserdblog

Необходимая подготовка: эллиптические кривые и сопряжения эллиптических кривых. См. также: Статья Данкрада Фейста о полиномиальных обязательствах KZG.

Особая благодарность Джастину Дрейку, Данкраду Фейсту и Чих-Ченг Лиангу за отзывы и рецензии.

Многие криптографические протоколы, особенно в области выборки доступности данных и ZK-SNARK, зависят от доверенных установок. Церемония установки доверия - это процедура, которая выполняется один раз для генерации части данных, которые затем должны использоваться каждый раз при запуске некоторого криптографического протокола. Для генерации этих данных требуется некоторая секретная информация; "доверие" возникает из-за того, что какой-то человек или какая-то группа людей должны сгенерировать эти секреты, использовать их для генерации данных, а затем опубликовать данные и забыть о секретах. Но как только данные сгенерированы, а секреты забыты, дальнейшего участия создателей церемонии не требуется.

Существует множество типов установки доверия. Самый ранний случай использования установки доверия в крупном протоколе - это Zcash в 2016 году. Эта работа была очень сложной и требовала много раундов общения, поэтому в ней могло быть только шесть участников. Каждый, кто использовал Zcash в тот момент, фактически доверял тому, что хотя бы один из шести участников был честным. В более современных протоколах обычно используется схема powers-of-tau, которая имеет модель доверия 1-of-N с типичным числом в сотни. То есть, сотни людей участвуют в совместной генерации данных, и только один из них должен быть честным и не публиковать свой секрет, чтобы конечный результат был безопасным. На практике такие хорошо выполненные установки часто считаются "достаточно близкими к недоверию".

В этой статье мы объясним, как работает установка KZG, почему она работает, а также будущее протоколов доверенных установок. Всем, кто хорошо разбирается в коде, стоит также проследить за реализацией этого кода: https://github.com/ethereum/research/blob/master/trusted_setup/trusted_setup.py.

Как выглядит power-of-tau?

Установка powers-of-tau состоит из двух серий точек эллиптической кривой, которые выглядят следующим образом:

G1 и G2 - стандартизированные точки генератора двух групп эллиптических кривых; в BLS12-381, G1 точки имеют длину (в сжатом виде) 48 байт, а G2 точки - 96 байт. n1 и n2 - длины сторон установки. Некоторые протоколы требуют , другие требуют n2 = 2, чтобы n1 и n2 были большими, а некоторые находятся посередине (например, выборка доступности данных в Ethereum в ее текущей форме требует n1 = 4096 и n2 = 16). s это секрет, который используется для генерации точек, и его нужно забыть.

Чтобы сделать KZG-обязательство для многочлена P(x)=∑icixi , мы просто берем линейную комбинацию ∑iciSi, где Si=G1∗si(точки эллиптической кривой в установке доверия). Точки G2 в установке используются для проверки оценок полиномов, которые мы берем на себя обязательства; я не буду рассматривать проверку здесь более подробно, хотя Данкрад сделал это в своем сообщении.

Интуитивно понятно, какую ценность предоставляет установка доверия?

It's worth understanding what is philosophically going on here, and why the trusted setup is providing value. A polynomial commitment is committing to a piece of size-N data with a size O(1) object (a single elliptic curve point). We could do this with a plain Pedersen commitment: just set the Si values to be N random elliptic curve points that have no known relationship with each other, and commit to polynomials with ∑iciSi as before. And in fact, this is exactly what IPA evaluation proofs do.

However, any IPA-based proofs take O(N) time to verify, and there's an unavoidable reason why: a commitment to a polynomial P(x) using the base points [S0,S1...Si...Sn−1] would commit to a different polynomial if we use the base points [S0,S1...(Si∗2)...Sn−1].

Стоит понять, что здесь происходит с философской точки зрения, и почему установка доверия обеспечивает ценность. Полиномиальное обязательство - это фиксация части данных размера N с объектом размера O(1) эллиптической кривой. Мы могли бы сделать это с помощью обычного обязательства Педерсена: просто задайте Si значения случайными N точками эллиптической кривой, которые не имеют никакой известной связи друг с другом, и зафиксируйте полиномиальные обязательства ∑iciSi, как и раньше. И на самом деле, это именно то, что делают оценочные доказательства на основе IPA.

Однако любые доказательства на основе IPA требуют O(N) времени для проверки, и на это есть неизбежная причина: обязательство многочлена P(x) с использованием базовых точек [S0,S1...Si...Sn−1] будет обязательством другого многочлена [S0,S1...(Si∗2)...Sn−1], если мы используем базовые точки.

Если мы хотим сделать доказательство на основе IPA для некоторого утверждения (скажем, что данный многочлен, оцененный в x = 10 равен 3826), то доказательство должно пройти с первым набором базовых точек и провалиться со вторым. Следовательно, какой бы ни была процедура проверки доказательства, она не может избежать того, чтобы каким-то образом учитывать каждое из Si значений, и поэтому неизбежно требует O(N) времени.

Но при надежной установке между точками существует скрытая математическая связь. Гарантируется Si+1=s∗Si , что между любыми двумя соседними точками будет одинаковый коэффициент. Если [S0,S1...Si...Sn−1] это достоверная установка, то "отредактированная установка" [S0,S1...(Si∗2)...Sn−1] также не может быть достоверной установкой. Следовательно, нам не нужны вычисления; вместо этого мы используем преимущества этой математической взаимосвязи для проверки всего, что нам нужно проверить, за постоянное время.

Однако математическая связь должна оставаться тайной: если она известна, то любой может придумать обязательство, обозначающее множество различных полиномов: если C обязательство касается P(x), то оно также касается P(x)∗x/s, или P(x)−x+s, или многих других. Это полностью разрушит все приложения полиномиальных обязательств. Следовательно, хотя в какой-то момент должен был существовать секрет, позволяющий установить математическую связь между значениями Si , обеспечивающую эффективную проверку, он также должен быть забыт.

Как работают установки с несколькими участниками?

Легко понять, как один участник может сгенерировать установку: просто выберите случайное число s, и сгенерируйте точки эллиптической кривой, используя s. Но доверенная установка с одним участником небезопасна: вы должны доверять одному конкретному человеку!

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

Возьмите существующую установку (обратите внимание, что вы не знаете s, вы просто знаете точки):

Теперь выберите свой собственный случайный секрет t. Вычислите:

Обратите внимание, что это эквивалентно:

То есть, вы создали действующую установку с секретом s∗t! Вы никогда не отдаете свой t предыдущим участникам, а предыдущие участники никогда не отдают вам свои секреты, которые вошли в s. И до тех пор, пока любой из участников честен и не раскрывает свою часть секрета, общий секрет не раскрывается. В частности, конечные поля обладают тем свойством, что если вы знаете , но не знаете , и надежно случайно сгенерированы, то вы ничего не знаете о s∗t!

Проверка настройки

Чтобы проверить, что каждый участник действительно участвовал, каждый участник может предоставить доказательство, состоящее из (i) точки G1∗s, которую он получил, и (ii) G2∗t , где t - секрет, который он вводит. Список этих доказательств может быть использован для проверки того, что окончательная установка объединяет все секреты (в отличие, скажем, от того, что последний участник просто забывает предыдущие значения и выводит установку только со своим собственным секретом, который он сохраняет, чтобы иметь возможность обманывать в любых протоколах, использующих эту установку).

Каждый участник должен раскрыть свое доказательство на каком-либо публично проверяемом носителе (например, личный сайт, транзакция с его .eth адреса, Twitter). Обратите внимание, что этот механизм не мешает кому-то утверждать, что он участвовал в каком-то индексе, где участвовал кто-то другой (при условии, что этот другой человек раскрыл свое доказательство), но обычно считается, что это не имеет значения: если кто-то готов солгать о своем участии, он также будет готов солгать о том, что удалил свой секрет. Пока хотя бы один из тех, кто публично заявляет о своем участии, честен, система безопасна.

В дополнение к вышеупомянутой проверке, мы также хотим убедиться, что все силы в настройке построены правильно (т.е. они являются силами одного и того же секрета). Для этого мы можем выполнить серию проверок сопряжения, проверяя, что e(Si+1,G2)=e(Si,T1) (где T1 - значение G2∗s в настройке) для каждого i. Это подтверждает, что коэффициент между каждым Si и Si+1 такой же, как коэффициент между T1 и G2. Затем мы можем сделать то же самое на стороне G2.

Но это много пар и дорого. Вместо этого мы берем случайную линейную комбинацию L1=∑i=0n1-2riSi, и ту же линейную комбинацию, сдвинутую на единицу: L2=∑i=0n1-2riSi+1. Для проверки их соответствия мы используем единственную проверку на сопряженность: e(L2,G2)=e(L1,T1).

Мы можем даже объединить процесс для стороны G1 и стороны G2 вместе: в дополнение к вычислению L1 и L2, как указано выше, мы также вычисляем L3=∑i=0n2-2qiTi (qi - другой набор случайных коэффициентов) и L4=∑i=0n2-2qiTi+1, и проверяем e(L2,L3)=e(L1,L4).

Установки в форме Лагранжа

Во многих случаях вы не хотите работать с многочленами в форме коэффициентов (например, P(x)=3x3+8x2+2x+6), вы хотите работать с многочленами в форме оценки (например, P(x) - это многочлен, который оценивается в [19,146,9,187] на области [1,189,336,148] по модулю 337). Форма оценки имеет много преимуществ (например, вы можете умножать и иногда делить многочлены за время O(N)), и вы даже можете использовать ее для оценки за время O(N). В частности, выборка доступности данных ожидает, что блобы будут в форме оценки.

Чтобы работать с такими случаями, часто удобно преобразовать доверенную установку в форму оценок. Это позволит вам взять оценки ([19,146,9,187] в приведенном выше примере) и использовать их для вычисления обязательств напрямую.

Это проще всего сделать с помощью быстрого преобразования Фурье (БПФ), но передавая на вход не числа, а точки кривой. Я не буду повторять здесь подробное объяснение БПФ, но вот реализация; на самом деле это не так уж сложно.

Будущее установки доверия

Powers-of-tau - не единственный вид установки доверия. Некоторые другие заметные варианты (фактические или потенциальные) включают:

• Более сложные установки в старых протоколах ZK-SNARK (например, см. здесь), которые иногда все еще используются (в частности, Groth16), потому что проверка дешевле, чем PLONK.

• Некоторые криптографические протоколы (например, DARK) зависят от групп скрытого порядка - групп, в которых неизвестно, на какое число можно умножить элемент, чтобы получить нулевой элемент. Существуют полностью недоверенные версии этого метода (см.: группы классов), но, безусловно, наиболее эффективная версия использует группы RSA (мощности x mod n=pq, где p и q неизвестны). Доверенные установочные церемонии для этого с предположениями о доверии 1-of-n возможны, но очень сложны в реализации.
• Если/когда обфускация неразличимости станет жизнеспособной, многие протоколы, которые зависят от нее, будут включать в себя создание и публикацию обфусцированной программы, которая делает что-то со скрытым внутренним секретом. Это доверенная установка: создатель(и) должен обладать секретом, чтобы создать программу, и должен будет удалить ее после этого.

Криптография продолжает оставаться быстро развивающейся областью, и то, насколько важны доверенные установки, может легко измениться. Вполне возможно, что методы работы с IPA и идеями в стиле Halo улучшатся настолько, что KZG станет устаревшим и ненужным, или что квантовые компьютеры сделают все, что основано на эллиптических кривых, нежизнеспособным через десять лет, и мы застрянем, работая с протоколами на основе хэшей без доверенных настроек. Также возможно, что то, что мы можем сделать с помощью KZG, будет улучшаться еще быстрее, или появится новая область криптографии, которая будет зависеть от другого типа доверенной установки.

В той мере, в какой церемонии доверительной настройки необходимы, важно помнить, что не все доверительные настройки созданы одинаковыми. 176 участников лучше, чем 6, а 2000 было бы еще лучше. Церемония, которая достаточно мала, чтобы ее можно было запустить через браузер или приложение для телефона (например, установка ZKopru основана на веб-технологиях), может привлечь гораздо больше участников, чем та, которая требует запуска сложного программного пакета. В идеале в каждой церемонии должны участвовать участники, работающие с несколькими независимо созданными программными реализациями и под управлением различных операционных систем и сред, чтобы снизить риски сбоев в общем режиме. Церемонии, требующие только одного раунда взаимодействия для каждого участника (например, powers-of-tau), намного лучше многораундовых церемоний, как из-за возможности поддерживать гораздо большее количество участников, так и из-за большей простоты написания нескольких реализаций. Церемонии в идеале должны быть универсальными (результат одной церемонии должен поддерживать широкий спектр протоколов). Это все вещи, над которыми мы можем и должны продолжать работать, чтобы гарантировать, что доверенные установки могут быть настолько безопасными и надежными, насколько это возможно.