
Краткий обзор системы проверки и показ того, как написать схему, которая вычисляет небольшую часть общей хеш-функции, которая значительно выигрывает от включения поиска вместе с арифметическими вентилями.
Введение
Plonkup — это новая система доказательства с нулевым разглашением, которая сочетает в себе Plonk с Plookup, позволяя арифметическим и пользовательским логическим элементам Plonk сосуществовать с логическими элементами поиска, включенными Plookup. Некоторые дорогостоящие компоненты схем zk-SNARK, такие как хеш-функции, можно выразить более эффективно, используя совместно поиск и арифметику. В этой статье я дам краткий обзор системы доказательства и покажу, как написать схему, которая вычисляет небольшую часть общей хеш-функции, которая значительно выигрывает от включения поиска вместе с арифметическими вентилями.
Plonk
Plonk — это система проверки от Gabizon, Williamson и Ciobotaru, впервые разработанная в 2019 году, которая обеспечивает универсальную, обновляемую доверенную настройку. Доверенная установка представляет собой общедоступные данные, созданные в ходе «церемонии» многосторонних вычислений, которые можно использовать для создания и проверки доказательств. Он называется доверенным, потому что установка может быть скомпрометирована, если все ее создатели вступят в сговор. (Если хотя бы один участник честен, значит, установка безопасна).
Универсальность означает, что одна церемония доверенной установки может использоваться любой цепью меньше определенного размера. Без этого свойства для каждого контура пришлось бы проводить новую церемонию.
Обновляемость означает, что существующая доверенная настройка может быть обновлена на новой церемонии, возможно, с новыми участниками, и она безопасна, если хотя бы один участник в любом обновлении был честен. .
Эти два свойства решают наиболее распространенные проблемы безопасности с доверенными настройками zk-SNARK и значительно затрудняют сговор.
Plonk, как и большинство других систем доказательства, использует арифметические схемы для представления вычислений. В арифметических схемах используются два вентиля + и × для выражения всех операций, выполняемых в схеме. Сложные вычисления требуют множества вентилей для их представления, а доказательство может занять довольно много времени. Некоторые операции, такие как побитовая арифметика, часто используемая в криптографических хэш-функциях, не могут быть эффективно выражены в виде арифметической схемы. Схемы, использующие несколько хэш-функций, могут вырасти до огромных размеров, и их проверка может занять несколько минут. (Это узкое место применимо к любой системе доказательства, использующей арифметические элементы, а не только к Plonk.)
Схема Plonk состоит из двух основных частей: арифметических вентилей и ограничений копирования. Арифметические элементы легко проверяются с помощью единственного полиномиального ограничения. Ограничения копирования, которые объединяют арифметические элементы, используются для построения полинома перестановки, который проверяет правильность всех ограничений копирования одновременно.
Plookup
Plookup — это собственная система доказательства от Gabizon и Williamson, которая очень похожа на Plonk, но не требует арифметической схемы и вместо этого может использоваться для доказательства того, что каждый элемент в списке запросов существует в общедоступной справочной таблице.
Plookup не использует арифметические элементы, но имеет собственный полином перестановки, который проверяет корректность запросов поиска.
Благодаря поискам операции, которые неэффективны в качестве арифметических схем, такие как проверка диапазона и побитовые операции, становятся намного более эффективными.
Зачем объединять два протокола?
Количество вентилей в схеме является основным фактором, определяющим время, необходимое для создания доказательства. Некоторые операции, которые мы, возможно, захотим использовать в схеме, могут быть написаны с использованием меньшего количества элементов в зависимости от метода.
Возьмем, к примеру, XOR. Многие криптографические хэш-функции, которые мы хотели бы смоделировать в схеме, например SHA или Blake, широко используют XOR. Чтобы показать, что три 8-битных значенияа,бисудовлетворитьа⊕б"="сиспользуя только арифметические вентили Plonk, вам сначала нужно будет ограничить каждый бит входных данных с помощью 16 вентилей, затем выполнить 8 однобитовых операций XOR с еще 8 вентилями и упаковать полученные биты обратно вместе с дополнительными 7 вентилями, для общего итога из 31 вентиля на XOR.
В этом случае немного лучше использовать систему ограничений ранга 1 (R1CS), поскольку благодаря неограниченному добавлению мы можем заменить последние 7 вентилей одним ограничением ранга 1, что дает всего 25 ограничений.
Однако с помощью Plookup и 8-битной таблицы поиска XOR это можно сделать в одиночном вентиле.
Некоторые другие операции, такие как сложение точек на встроенной эллиптической кривой, уже достаточно эффективны с использованием одних только арифметических элементов. Чтобы максимизировать эффективность, мы хотели бы использовать как справочные, так и арифметические элементы в одной схеме.
Схемы Plonkup
Провода — это векторы, содержащие частные входные данные проверяющего устройства. Провода можно рассматривать как столбцы большой матрицы. В этих примерах мы будем использовать три провода, которые назовем а,бис.
В этой матрице строка представляет собой кортеж частных входных данных, которые должны удовлетворять любым ограничениям, включенным для этой строки.
Селекторы — это векторы, которые включают или отключают ограничения для каждой строки. Единица с индексом 47 в селекторе умножения означает, что строка 47 должна удовлетворять ограничению умножения, например а47⋅б47"="с47.
Ограничения копирования — это простые уравнения, которые связывают значения записей в одной строке со значениями в другой, скажем с1"="а9например.
Наконец, таблица поиска представляет собой еще одну матрицу с тем же количеством столбцов, что и у прувера. Таблица поиска с тремя столбцами может моделировать функцию с двумя входами и одним выходом. Ряд(р,с,т)в справочной таблице, имитирующей функциюжЗначит этож(р,с)"="т.
Пример схемы
Давайте покажем, как построить небольшую схему Plonkup, которая делает что-то полезное. В хэше Blake2 32-битные слова объединяются с помощью операции XOR друг с другом, и полученные биты поворачиваются на некоторое количество мест. Это идеальная операция для использования в качестве небольшого примера схемы Plonkup.
Справочная таблица
Поскольку наша таблица имитирует XOR, допустимая строка таблицы поиска будет выглядеть так:(а,б,а⊕б). Нам нужно будет циклически перебрать все возможностиаиб. Еслиаиббыли бы по 32 бита каждый, у нас была бы таблица поиска с232×232ряды. В каждой строке есть три записи, и каждая запись представляет собой элемент скалярного поля для некоторой эллиптической кривой, обычно 256 бит или больше. Для 256-битных записей наша таблица будет представлять собой стройные, разумные и совершенно не ломающие вселенную размеры в 1,5 зебибайта.
Итак, нам нужно сделать нашу таблицу немного меньше. Давайте используем всего 8 бит дляаибдавая нам таблицу216строк и общий размер всего 6 мегабайт. Примером строки таблицы может быть(13,255,242)если для удобства мы используем десятичные целые числа вместо 256-битных элементов скалярного поля.
32-битное исключающее ИЛИ
Чтобы выполнить исключающее ИЛИ два 32-битных числа, мы разделяем каждое число на четыре 8-битных фрагмента и используем четыре справочных вентиля для вычисления исключающего ИЛИ. Затем нам нужно собрать четыре фрагмента обратно вместе, чтобы получить 32-битный результат. Давайте назовем наши два 32-битных входа Иксийи разделим их на четыре части каждую так, чтобыИкс"="Икс3∣Икс2∣Икс1∣Икс0ий"="й3∣й2∣й1∣й0. Мы вычисляем четыре XOR какя3"="Икс3⊕й3,я2"="Икс2⊕й2,я1"="Икс1⊕й1, ия0"="Икс0⊕й0. Тогда наши четыре вентиля XOR будут:
lookuр(Икс3,й3,я3)lookuр(Икс2,й2,я2)lookuр(Икс1,й1,я1)lookuр(Икс0,й0,я0)
Теперь нам нужно упаковать результаты XOR обратно в одно 32-битное значение. Мы соединим два верхних и два нижних фрагмента вместе, сдвинем влево старшие фрагменты каждой пары на 8 бит и добавим нижние фрагменты, чтобы получить два 16-битных значения. Затем мы повторяем 16-битный сдвиг и сложение, чтобы получить окончательный 32-битный результат.
Битовый сдвиг — это просто умножение на степень двойки, поэтому мы можем выполнить упаковку с помощью нескольких элементов сложения. Plonkup поддерживает скалярное умножение в элементе сложения, помещая скаляры в селекторы для левой, правой и выходных переменных. Дополнительные ворота типаadd((л,Икс),(р,й),(о,я))будет обеспечивать соблюдение ограничениялИкс+рй+оя"="0.
Наши элементы сложения битовой упаковки будут выглядеть так:
add((28,й3)(1,й2),(−1,ячi))add((28,й1)(1,й0),(−1,яlo))add((216,ячi)(1,яlo),(−1,я))
Ротация битов
Вращение бита можно рассматривать как «обмен». из двух блоков битов. Если мы будем осторожны, мы можем использовать элемент поля для представления каждого из двух фрагментов, а не разбивать их побитно. Этот обмен представляет собой вращение влево на любое количество битов в яup(или поворот вправо на количество битов вяdown).
я"="яup∣яdownш"="яdown∣яup
Операция, обозначаемая ∣, представляет собой объединение битовых представленийяupияdown, но мы можем использовать элементы поля для представленияяupияdownи вообще никогда не нужно возиться с битами. Используя элементы полей, мы можем выразить конкатенацию с помощью этих простых формул:
я"="2н−кяup+яdownш"="2кяdown+яup
Пока битовые представленияяupияdownна самом делекин−кбит соответственно, эти формулы правильно вычисляют вращение влево накбиты.
Последнее, что нужно сделать, это проверить разрядностьяupияdown. К сожалению, большую часть времени они будут иметь разную длину и потребуют двух дополнительных таблиц поиска диапазонов или некоторых дополнительных ограничений, чтобы адаптировать их для использования одной и той же дополнительной таблицы поиска диапазонов. Ни то, ни другое не идеально. К счастью, оказывается, что ограничение входных и выходных переменныхяишкнбиты также ограничиваютяupияdownдо их правильной длины в битах. Поскольку эти переменные имеют одинаковый размер, мы можем использовать одну и ту же таблицу поиска диапазонов для обеих. Кроме того, еслияявляется выходным сигналом предыдущего шага схемы, возможно, он уже ограничен по диапазону. Это именно тот случай, в котором мы окажемся, если последуем за XOR с вращением.
Поиск XOR обязательно ограничивает диапазон результатов, что является еще одной удачей. Мы можем повторно использовать таблицу поиска XOR в качестве таблицы поиска диапазонов для диапазонов, кратных 8 битам. Еслиаибоба меньше, чем28затем(а,б,а⊕б)будет строкой в таблице поиска. Мы можем проверить два элемента поля с помощью каждого элемента поиска XOR.
В одном из раундов Blake2s используется ротация на 7 бит. Предполагаяяограничен 32 битами предыдущими ограничениями, мы можем начать с двух элементов сложения.
Доказывающее вычисляетяupияdownтак чтоя"="яup∣яdownи так чтояupияdownправильное количество бит. Тогда наши элементы сложения будут:
add((225,яup),(1,яdown),(−1,я))add((27,яdown),(1,яup),(−1,ш))
Затем Доказывающее устройство вычисляет 8-битные фрагменты.ш3,…,ш0так чтош"="ш3∣ш2∣ш1∣ш0и вычисляет XORш3⊕ш2иш1⊕ш0. Затем у нас есть два шлюза поиска, показывающие, что все четыре фрагмента имеют длину менее 8 бит:
lookuр(ш3,ш2,ш3⊕ш2)lookuр(ш1,ш0,ш1⊕ш0)
Затем мы показываем, что 8-битные фрагменты были правильно вычислены с помощью еще трех элементов сложения:
add((28,ш3),(1,ш2),(−1,шчi))add((28,ш1),(1,ш0),(−1,шlo))add((216,шчi),(1,шlo),(−1,ш))
Собираем все вместе
Используя 8-битную таблицу поиска XOR (которая выполняет двойную функцию в качестве 8-битной таблицы диапазонов), мы можем выразитьш"="rot7(Икс⊕й)для 32-битной версииИкс,й,шиспользуя эти 14 ограничений:
lookuр(Икс3,й3,я3)lookuр(Икс2,й2,я2)lookuр(Икс1,й1,я1)lookuр(Икс0,й0,я0)add((28,й3)(1,й2),(−1,ячi))add((28,й1)(1,й0),(−1,яlo))add((216,ячi)(1,яlo),(−1,я))add((225,яup),(1,яdown),(−1,я))add((27,яdown),(1,яup),(−1,ш))lookuр(ш3,ш2,ш3⊕ш2)lookuр(ш1,ш0,ш1⊕ш0)add((28,ш3),(1,ш2),(−1,шчi))add((28,ш1),(1,ш0),(−1,шlo))add((216,шчi),(1,шlo),(−1,ш))
Сравнение с R1CS
Давайте сравним это с той же схемой, выраженной с использованием системы ограничений первого ранга, как в Groth16. R1CS имеет несколько преимуществ и несколько недостатков. Преимущество состоит в том, что R1CS допускает неограниченное сложение в одном ограничении, поэтому одно ограничение R1CS может заменить несколько ограничений сложения, которые мы использовали в нашей схеме на основе Plonkup. Недостатком является то, что R1CS не поддерживает поиск или эффективные вентили диапазона, поэтому операции XOR и проверки диапазона необходимо выполнять побитно. По моим подсчетам, версия той же схемы R1CS потребует 2 × 32-битных ограничения для проверки диапазона, 32-битных ограничения XOR и 1 ограничение вращения и упаковки битов. В целом версия этой схемы R1CS потребует почти в семь раз больше ограничений. Хотя ограничения R1CS не совсем сопоставимы с ограничениями Plonkup в отношении времени прувера, использование 1/7 количества вентилей, безусловно, будет серьезным улучшением.
Недостатки
Таблица поиска Plonkup увеличивает стоимость построения доказательства и его размер. Эта 8-битная таблица поиска XOR имеет216ряды, которые довольно велики. В большой и сложной схеме, где XOR используется много раз, таблица такого размера может оказаться полезной, но такая большая таблица явно расточительна для этого крошечного примера схемы. 4-битная таблица будет довольно маленькой, всего28строк, но примерно удвоит количество ограничений, необходимых в схеме, до 26, что все еще довольно мало.
Последние мысли
Plonk — это легко адаптируемая и гибкая система проверки, допускающая бесконечное количество пользовательских конфигураций, таких как Plonkup, которые могут значительно повысить производительность определенных операций. Вероятно, будет еще много итераций Plonk, которые устранят всевозможные мелкие недостатки или действительно эффективны для определенных специализированных схем. Далее появятся несколько режимов накопления доказательств, рекурсии и оптимизации схемы. Эти функции позволят Anoma стать максимально закрытым и масштабируемым протоколом.
Написано Джошуа Фицджеральдом, исследователем криптографии с нулевым разглашением и amp; разработчик протокола в Heliax, команде Anoma.
Если вас интересуют криптография с нулевым разглашением, передовые криптографические протоколы, языки для схем или инженерные должности в Rust, ознакомьтесь открытыми вакансиями в Heliax .