Виталик Бутерин через Блог Виталика Бутерина
Это зеркало поста на https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
Это третья часть серии статей, объясняющих, как работает технология zk-SNARK; предыдущие статьи о программы квадратичной арифметики и пары эллиптических кривых обязательны к прочтению, и эта статья предполагает знание обеих концепций. Также предполагаются базовые знания о том, что такое zk-SNARK и что они делают. Смотрите также Статья Кристиана Райтвисснера здесь для другого технического введения.
В предыдущих статьях мы представили программу квадратичной арифметики — способ представления любой вычислительной задачи с помощью полиномиального уравнения, которое гораздо лучше поддается различным формам математических ухищрений. Мы также представили пары эллиптических кривых, которые допускают очень ограниченную форму одностороннего гомоморфного шифрования, позволяющего выполнять проверку на равенство. Теперь мы собираемся начать с того места, на котором остановились, и использовать пары эллиптических кривых вместе с несколькими другими математическими трюками, чтобы позволить доказывающему доказать, что они знают решение для конкретного QAP, не раскрывая ничего больше о актуальное решение.
В этой статье речь пойдет о Протокол Пиноккио Парно, Джентри, Хауэлл и Райкова от 2013 г. (часто называемый PGHR13); существует несколько вариаций базового механизма, поэтому реализованная на практике схема zk-SNARK может работать немного иначе, но основные принципы в целом останутся прежними.
Для начала давайте углубимся в ключевое криптографическое предположение, лежащее в основе безопасности механизма, который мы собираемся использовать: *знание показателя* предположение.
По сути, если вы получаете пару точек � и �, где �⋅�=��, и вы получаете точку �, то невозможно придумать �⋅�, если только � не «выведено» из � каким-либо образом то, что ты знаешь. Это может показаться интуитивно очевидным, но на самом деле это предположение не может быть выведено из какого-либо другого предположения (например, твердости дискретного журнала), которое мы обычно используем при доказательстве безопасности протоколов на основе эллиптических кривых, и поэтому zk-SNARK фактически опираются на несколько более шаткая основа, чем криптография на основе эллиптических кривых в целом, хотя она все еще достаточно прочна, и большинство криптографов с ней согласны.
Теперь давайте разберемся, как это можно использовать. Предположим, что с неба падает пара точек (��,�), где �⋅�=��, но каково значение �, никто не знает. Теперь предположим, что я нашел пару точек (��,�), где �⋅�=��. Тогда предположение КоЭ подразумевает, что единственный способ получить эту пару точек — это взять � и � и умножить их на некоторый коэффициент r. что я лично знаю. Также обратите внимание, что благодаря магии пар эллиптических кривых проверка того, что �=�⋅�� на самом деле не требует знания � – вместо этого вы можете просто проверить, действительно ли �(��,�)=�(��,�).
Давайте займемся чем-нибудь более интересным. Предположим, что у нас с неба упало десять пар точек: (��1, �1),(��2,�2)…(��10,�10). Во всех случаях ��⋅��=��. Предположим, что я затем предоставляю вам пару точек (��,�), где �⋅�=��. Что ты знаешь сейчас? Вы знаете, что � — это некоторая линейная комбинация �1⋅�1+�2⋅�2+…+�10⋅�10, где мне известны коэффициенты �1, �2…�10. То есть единственный способ получить такую пару точек (��,�) — это взять несколько кратных �1,�2…�10, сложить их вместе и выполнить те же вычисления с �1,�2…� �10.
Обратите внимание, что, учитывая любой конкретный набор из «1…» 10 точек, для которых вы, возможно, захотите проверить линейные комбинации, вы на самом деле не можете создать сопутствующие «1…» 10 точек, не зная, что такое —, и если вы знаете, что такое �, то вы можете создать пару (��,�), где �⋅�=� для любого �, чего захотите, не утруждая себя созданием линейной комбинации. Следовательно, чтобы это работало, абсолютно необходимо, чтобы тот, кто создает эти точки, заслуживал доверия и фактически удалял — как только они создали десять точек. Отсюда и возникла концепция «доверенной установки»..
Помните, что решением QAP является набор полиномов (��,�,�) таких, что ��(��)⋅�(��)−��(��)=��(��)⋅�(��), где:
- � представляет собой линейную комбинацию набора многочленов {��1…��}
- � — линейная комбинация {��1…��} с теми же коэффициентами
- � представляет собой линейную комбинацию {��1…��} с теми же коэффициентами
Множества {��1…��},{��1…��} и {��1…��} и полином � являются частью постановки задачи.
Однако в большинстве реальных случаев �, � и � чрезвычайно велики; для чего-то со многими тысячами схемных элементов, таких как хеш-функция, полиномы (и коэффициенты для линейных комбинаций) могут состоять из многих тысяч членов. Следовательно, вместо того, чтобы заставлять доказывающего напрямую предоставлять линейные комбинации, мы собираемся использовать трюк, который мы представили выше, чтобы заставить доказывающего доказать, что они предоставляют что-то, что является линейной комбинацией, но не раскрывая ничего другого.
Возможно, вы заметили, что описанный выше трюк работает с точками эллиптической кривой, а не с полиномами. Следовательно, на самом деле мы добавляем следующие значения в доверенную настройку:
- �⋅�1(��), �⋅�1(��)⋅��
- �⋅�2(��), �⋅�2(��)⋅��
- ...
- �⋅�1(��), �⋅�1(��)⋅��
- �⋅�2(��), �⋅�2(��)⋅��
- ...
- �⋅�1(��), �⋅�1(��)⋅��
- �⋅�2(��), �⋅�2(��)⋅��
- ...
Вы можете думать о t как о «секретной точке», в которой вычисляется полином. � является «генератором» (некоторая случайная точка эллиптической кривой, которая указана как часть протокола), а �,��,�� и �� являются «токсичными отходами», числами, которые абсолютно необходимо удалить любой ценой, иначе тот, у кого они есть, сможет предоставить фальшивые доказательства. Теперь, если кто-то дает вам пару точек �, � такую, что �⋅��=� (напоминание: нам не нужно ��, чтобы проверить это, так как мы можем выполнить проверку на пары), то вы знаете, что они дают вам линейную комбинацию полиномов ��, оцененных в ��.
Следовательно, доказывающему необходимо дать:
- ��=��⋅�(��),��′=��⋅�(��)⋅��
- ��=��⋅�(��),��′=��⋅�(��)⋅��
- ��=��⋅�(��),��′=��⋅�(��)⋅��
Обратите внимание, что доказывающему на самом деле не нужно знать (и не должно знать!) ��,��,�� или �� для вычисления этих значений; скорее, проверяющий должен иметь возможность вычислить эти значения только на основе точек, которые мы добавляем в доверенную настройку.
Следующий шаг — убедиться, что все три линейные комбинации имеют одинаковые коэффициенты. Это можно сделать, добавив еще один набор значений в доверенную настройку: �⋅(��(��)+��(��)+��(��))⋅��, где � — еще одно число, которое следует считать «токсичным». отходы» и отбрасываются, как только доверенная установка будет завершена. Затем мы можем поручить доказывающему создать линейную комбинацию этих значений с теми же коэффициентами и использовать тот же прием спаривания, что и выше, чтобы убедиться, что это значение совпадает с предоставленным знаком �+�+�.
Наконец, нам нужно доказать, что ⋅�−��=��⋅��. Мы делаем это еще раз с проверкой сопряжения:
��(��,��)/��(��,��)?=��(��ℎ,�⋅�(��))
Где �ℎ=��⋅�(��). Если связь между этим уравнением и �⋅�−�=��⋅� не имеет для вас смысла, вернитесь и прочитайте статья о парах.
Выше мы видели, как преобразовать �, � и � в точки эллиптической кривой; � — это просто генератор (т. е. точка эллиптической кривой, эквивалентная номеру один). Мы можем добавить ⋅��(��) в доверенную настройку. � сложнее; � представляет собой просто полином, и мы очень мало заранее предсказываем, какими будут его коэффициенты для каждого отдельного решения QAP. Следовательно, нам нужно добавить еще больше данных в доверенную настройку; конкретно последовательность:
�, �⋅�, �⋅�2, �⋅�3, �⋅�4….
В доверенной настройке Zcash последовательность здесь достигает примерно 2 миллионов; именно столько степеней � вам нужно, чтобы быть уверенным, что вы всегда сможете вычислить �(��), по крайней мере, для конкретного экземпляра QAP, о котором они заботятся. При этом проверяющий может предоставить всю информацию проверяющему для проведения окончательной проверки.
Есть еще одна деталь, которую нам нужно обсудить. Большую часть времени мы не просто хотим абстрактно доказать, что существует какое-то решение для какой-то конкретной проблемы; скорее, мы хотим доказать либо правильность какого-то конкретного решения (например, доказать, что если вы возьмете слово «корова» и хешируете его по SHA3 миллион раз, конечный результат начнется с 0x73064fe5), или что решение существует, если вы ограничите некоторые параметры. Например, в реализации криптовалюты, где суммы транзакций и балансы счетов зашифрованы, вы хотите доказать, что вам известен некоторый ключ дешифрования k, такой, что:
decrypt(old_balance, k) >= decrypt(tx_value, k)
decrypt(old_balance, k) - decrypt(tx_value, k) = decrypt(new_balance, k)
Зашифрованный old_balance
, tx_value
и new_balance
должны быть указаны публично, поскольку это конкретные значения, которые мы хотим проверить в данный конкретный момент; только ключ дешифрования должен быть скрыт. Некоторые небольшие изменения в протоколе необходимы для создания «пользовательского ключа проверки», который соответствует некоторым конкретным ограничениям на входные данные.
Теперь давайте отойдем немного назад. Прежде всего, вот полный алгоритм проверки, любезно предоставленный Беном. Сассон, Тромер, Вирза и Кьеза:
Первая строка посвящена параметризации; по сути, вы можете думать о его функции как о создании «пользовательского ключа проверки». для конкретного случая проблемы где указаны некоторые аргументы. Вторая строка — это проверка линейной комбинации для �,� и �; третья строка — проверка того, что линейные комбинации имеют одинаковые коэффициенты, а четвертая строка — проверка произведения �⋅�−��=��⋅�.
В целом процесс проверки представляет собой несколько умножений эллиптических кривых (по одному для каждой «общедоступной» входной переменной) и пять проверок пар, одна из которых включает в себя дополнительное умножение пар. Доказательство содержит восемь точек эллиптической кривой: по паре точек для ��(��),�(��) и ��(��), точку �� для ��⋅(��(��)+��(��)+��(�� )) и точку ��ℎ для ��(��). Семь из этих точек находятся на кривой �� (по 32 байта каждая, так как координату �� можно сжать до одного бита), а в реализации Zcash одна точка (��) находится на скрученной кривой в ��2 (64 байт), поэтому общий размер доказательства составляет ~288 байт.
Двумя наиболее сложными в вычислительном отношении этапами создания доказательства являются:
- Деля (��⋅�−��)/�� для получения � (алгоритмы, основанные на Быстрое преобразование Фурье можно сделать это за субквадратичное время, но это все равно требует больших вычислительных ресурсов)
- Выполнение умножения и сложения эллиптической кривой для создания значений �(��),�(��),�(��) и �(��) и их соответствующих пар.
Основная причина, почему создать доказательство так сложно, заключается в том, что то, что было одним двоичным логическим элементом в исходном вычислении, превращается в операцию, которую необходимо криптографически обработать с помощью операций с эллиптической кривой, если мы делаем из нее доказательство с нулевым разглашением. . Этот факт, а также сверхлинейность быстрых преобразований Фурье, означает, что создание доказательства для транзакции Zcash занимает ~20–40 секунд.
Еще один очень важный вопрос: можем ли мы попытаться сделать доверенную настройку немного… менее требовательной к доверию? К сожалению, мы не можем сделать его полностью не заслуживающим доверия; само предположение КоЭ не позволяет создавать независимые пары (��,��⋅��), не зная, что такое ��. Однако мы можем значительно повысить безопасность, используя многосторонние вычисления, то есть создавая доверенную настройку между сторонами таким образом, что пока хотя бы один из участников удалил свои токсичные отходы, с вами все в порядке. .
Чтобы получить представление о том, как это сделать, вот простой алгоритм, позволяющий взять существующий набор (��, �⋅�, �⋅�2, �⋅�3…) и «добавить» свой собственный секрет. так что для обмана вам нужны и ваш секрет, и предыдущий секрет (или предыдущий набор секретов).
Выходной набор просто:
�,(��⋅�)⋅�,(��⋅�2)⋅�2,(��⋅�3)⋅�3…
Обратите внимание, что вы можете создать этот набор, зная только исходный набор и s, и новый набор функционирует так же, как и старый набор, за исключением того, что теперь в качестве «токсичных отходов» используется �⋅� вместо �. Пока вы и человек (или люди), создавшие предыдущий набор, не удалите свои токсичные отходы и позже не вступите в сговор, набор «безопасен».
Сделать это для полной доверенной настройки немного сложнее, поскольку здесь задействовано несколько значений, и алгоритм должен выполняться между сторонами в несколько раундов. Это область активных исследований, чтобы выяснить, можно ли еще больше упростить алгоритм многосторонних вычислений и сделать его более распараллеливаемым, поскольку чем больше вы можете это сделать, тем больше сторон становится возможным включить в процедуру доверенной установки. . Разумно понять, почему доверенная установка между шестью участниками, которые все знают и работают друг с другом, может вызывать у некоторых людей дискомфорт, но доверенная установка с тысячами участников будет почти неотличима от полного отсутствия доверия – и если вы действительно параноик , вы можете войти и поучаствовать в процедуре настройки самостоятельно, и быть уверенным, что вы лично удалили свое значение.
Другая область активных исследований — использование других подходов, которые не используют пары и ту же парадигму доверенной установки для достижения той же цели; видеть Недавняя презентация Эли бен Сассона для одной альтернативы (хотя имейте в виду, она по крайней мере столь же математически сложна, как и SNARK!)
Особая благодарность Ариэлю Габизону и Кристиану Райтвиснеру за рецензию.
- SEO-контент и PR-распределение. Получите усиление сегодня.
- PlatoData.Network Вертикальный генеративный ИИ. Расширьте возможности себя. Доступ здесь.
- ПлатонАйСтрим. Интеллект Web3. Расширение знаний. Доступ здесь.
- ПлатонЭСГ. Углерод, чистые технологии, Энергия, Окружающая среда, Солнечная, Управление отходами. Доступ здесь.
- ПлатонЗдоровье. Биотехнологии и клинические исследования. Доступ здесь.
- Смещения блоков. Модернизация права собственности на экологические компенсации. Доступ здесь.
- Источник: Платон Data Intelligence.