Переслано оригинальное название 'Виталик подробно объясняет Биниус: эффективная система доказательств на основе бинарных полей'

Этот пост в первую очередь предназначен для читателей, хотя бы приблизительно знакомых с криптографией эпохи 2019 года, особенно SNARKs и STARKs. Если вы им не знакомы, рекомендую сначала прочитать эти статьи. Отдельная благодарность Джастину Дрейку, Джиму Посену, Бенджамину Даймонду и Ради Чойбасику за обратную связь и рецензирование.

За последние два года STARKs стали ключевой и незаменимой технологией для эффективного создания легко проверяемых криптографических доказательств очень сложных утверждений (например, доказательства того, что блок Ethereum является действительным). Одной из ключевых причин этого является малый размер поля: в то время как для обеспечения достаточной безопасности SNARKs на основе эллиптических кривых требуется работа с целыми числами длиной 256 бит, STARKs позволяют использовать гораздо меньшие размеры полей, которые более эффективны: сначала поле Goldilocks (64-битные целые числа), а затем Mersenne31 и BabyBear (оба по 31 бит). Благодаря этим выигрышам в эффективности, Plonky2, использующий Goldilocks, в сотни раз быстрее предыдущих версий при доказательстве многих видов вычислений.

Естественный вопрос, который задают, — можно ли довести эту тенденцию до логического завершения, создавая системы доказательств, работающие еще быстрее, работая напрямую с нулями и единицами? Именно это пытается сделать Binius, используя ряд математических трюков, которые делают его сильно отличающимся от SNARKs и STARKs трех лет назад. В этом посте рассматриваются причины, по которым генерация доказательств в малых полях более эффективна, почему бинарные поля уникально мощны и трюки, которые использует Binius для эффективной работы с доказательствами в бинарных полях.

Binius. К концу этого поста вы должны будете понять каждую часть этой диаграммы.

Резюме: конечные поля

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

Для выполнения сложной арифметики, сохраняя числа маленькими, криптографы обычно используют модульную арифметику. Мы выбираем некоторое простое «основание» p. Оператор % означает «взять остаток от деления»: 15 % 7=1, 53 % 10=3 и т.д. (обратите внимание, что ответ всегда неотрицателен, поэтому, например, −1 % 10=9).

Вы, вероятно, уже видели модулярную арифметику в контексте сложения и вычитания времени (например, какое время через четыре часа после 9:00?). Но здесь мы не просто складываем и вычитаем по модулю какого-то числа, мы также умножаем, делим и возводим в степень.

Мы переопределяем:

Вышеуказанные правила все самосогласованы. Например, если p=7, то:

5+3=1 (потому что 8%7=1)

1-3=5 (потому что -2%7=5)

2*5=3

3/5=2

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

Модулярная арифметика (или простые поля) является наиболее распространенным типом конечного поля, но существует также другой тип: расширенные поля. Вы, вероятно, уже видели расширенное поле: комплексные числа. Мы "представляем" новый элемент, который мы обозначаем как 𝑖, и объявляем, что он удовлетворяет 𝑖2=−1. Затем вы можете брать любую комбинацию обычных чисел и 𝑖, и производить с ними вычисления: (3𝑖+2)∗(2𝑖+4)= 6𝑖2+12𝑖+4𝑖+8=16𝑖+2. Мы также можем брать расширения простых полей. По мере того как мы начинаем работать над полями, которые являются более маленькими, расширения простых полей становятся все более важными для сохранения безопасности, а бинарные поля (которые использует Binius) полностью зависят от расширений для практической полезности.

Резюме: арифметизация

Способ, которым SNARK и STARK доказывают факты о компьютерных программах, заключается в арифметизации: вы преобразуете утверждение о программе, которую хотите доказать, в математическое уравнение, включающее многочлены. Допустимое решение уравнения соответствует допустимому выполнению программы.

Для того чтобы привести простой пример, предположим, что я вычислил 100-е число Фибоначчи, и я хочу доказать вам, что это так. Я создаю полиномиальное 𝐹, которое кодирует числа Фибоначчи: так что 𝐹(0)=𝐹(1)=1, 𝐹(2)=2, 𝐹(3)=3, 𝐹(4)=5 и так далее на 100 шагов. Условие, которое мне нужно доказать, заключается в том, что 𝐹(𝑥+2)=𝐹(𝑥)+𝐹(𝑥+1) в пределах диапазона 𝑥={0,1…98}. Я могу убедить вас в этом, предоставив вам частное:

где Z(x) = (x-0)(x-1) …(x-98). Если я могу доказать, что существуют F и H, удовлетворяющие этому уравнению, то F должна удовлетворять F(x+2)-F(x+1)-F(x) в диапазоне. Если я дополнительно проверю, что F удовлетворяет условию F(0)=F(1)=1, то F(100) действительно должна быть 100-м числом Фибоначчи.

Если вы хотите доказать что-то более сложное, замените «простое» отношение 𝐹(𝑥+2)=𝐹(𝑥)+𝐹(𝑥+1) более сложным уравнением, которое по сути означает «𝐹(𝑥+1) - это результат инициализации виртуальной машины со состоянием 𝐹(𝑥) и выполнения одного вычислительного шага». Вы также можете заменить число 100 на большее число, например 100000000, чтобы выполнить больше шагов.

Все SNARKs и STARKs основаны на этой идее использования простого уравнения над многочленами (или иногда векторами и матрицами) для представления большого количества отношений между отдельными значениями. Не все включают проверку эквивалентности между смежными вычислительными шагами таким же образом, как в приведенном выше примере: PLONK не делает этого, например, и то же самое касается R1CS. Но многие из самых эффективных делают это, потому что наложение той же проверки (или нескольких одинаковых проверок) много раз облегчает минимизацию накладных расходов.

Plonky2: от 256-битных SNARK и STARK до 64-битных... только STARK

Пять лет назад разумным резюме различных типов доказательств нулевого знания было следующее. Существуют два типа доказательств: (на основе эллиптических кривых) SNARK и (на основе хэш-функций) STARK. Технически STARK - это тип SNARK, но на практике обычно используется термин "SNARK" только для доказательств, основанных на эллиптических кривых, и "STARK" для хэш-функций. SNARK маленькие, поэтому их можно быстро проверить и легко поместить на цепь. STARK большие, но для них не требуются доверенные настройки, и они устойчивы к квантовым вычислениям.

STARKs работают, обрабатывая данные как полином, вычисляя значения этого полинома во множестве точек и используя Merkle root этого расширенного набора данных в качестве "полиномиального обязательства"

Важным моментом истории является то, что сначала широкое распространение получили SNARK, основанные на эллиптических кривых: приблизительно до 2018 года STARK стали достаточно эффективными для использования благодаря FRI, а к тому времени Zcash уже работал более года. У SNARK, основанных на эллиптических кривых, есть ключевое ограничение: если вы хотите использовать SNARK, основанные на эллиптических кривых, то арифметика в этих уравнениях должна выполняться с использованием целых чисел по модулю числа точек на эллиптической кривой. Это большое число, обычно близкое к 2256: например, для кривой bn128 это 21888242871839275222246405745257275088548364400416034343698204186575808495617. Но фактические вычисления выполняются с использованием малых чисел: если представить себе "реальную" программу на вашем любимом языке, то большинство операций в ней выполняются счетчиками, индексами в циклах, позициями в программе, отдельными битами, представляющими Истину или Ложь, и другими вещами, которые почти всегда будут состоять всего из нескольких разрядов.

Даже если ваши «оригинальные» данные состоят из «маленьких» чисел, процесс доказательства требует вычисления частных, расширений, случайных линейных комбинаций и других преобразований данных, которые приводят к равному или большему количеству объектов, в среднем такого же размера, как полный размер вашего поля. Это создает ключевую неэффективность: для доказательства вычислений над n малыми значениями вам придется выполнить еще больше вычислений над n намного большими значениями. Сначала STARK унаследовали привычку использовать поля из 256 бит из SNARK, и поэтому столкнулись с той же неэффективностью.

Расширение Рида-Соломона некоторых оценок полинома. Несмотря на то, что исходные значения небольшие, все дополнительные значения увеличиваются до полного размера поля (в данном случае 2 в степени 31 -1)

В 2022 году был выпущен Plonky2. Основным новшеством Plonky2 было выполнение арифметики по модулю меньшего простого числа: 2⁶⁴−2³²+1=18446744069414584321. Теперь каждое сложение или умножение всегда можно выполнить всего в нескольких инструкциях на ЦП, и хэширование всех данных вместе происходит в 4 раза быстрее, чем раньше. Но это имеет свои подводные камни: этот подход подходит только для STARK. Если вы попытаетесь использовать SNARK с эллиптической кривой такого небольшого размера, эллиптическая кривая становится небезопасной.

Для сохранения безопасности Plonky2 также необходимо было ввести расширенные поля. Ключевой техникой при проверке арифметических уравнений является "выборка в случайной точке": если вы хотите проверить, действительно ли 𝐻(𝑥)∗𝑍(𝑥) равно 𝐹(𝑥+2)−𝐹(𝑥+1)−𝐹(𝑥), вы можете выбрать некоторую случайную координату 𝑟, предоставить доказательства открытия полиномиального обязательства, доказывающие 𝐻(𝑟), 𝑍(𝑟), 𝐹(𝑟), 𝐹(𝑟+1) и 𝐹(𝑟+2), а затем фактически проверить, равно ли 𝐻(𝑟)∗𝑍(𝑟) 𝐹(𝑟+2)−𝐹(𝑟+1)−𝐹(𝑟). Если злоумышленник может предугадать координату заранее, он может обмануть систему доказательства - вот почему она должна быть случайной. Но это также означает, что координата должна быть выбрана из набора достаточно большого, чтобы злоумышленник не мог угадать ее случайно. Если модуль близок к 2²⁵⁶, это явно так. Но с модулем 2⁶⁴−2³²+1, мы еще не совсем там, и если мы опустимся до 2³¹−1, это определенно не так. Попытка подделать доказательство два миллиарда раз, пока удача улыбнется, абсолютно в пределах возможностей атакующего.

Для прекращения этого мы выбираем 𝑟 из расширенного поля. Например, вы можете определить 𝑦, где 𝑦³=5, и берут комбинации 1, 𝑦 и 𝑦². Это увеличивает общее количество координат примерно до 2⁹³Большинство полиномов, вычисляемых доказывающим лицом, не входят в это расширенное поле; они просто используют целые числа по модулю 2³¹−1, и поэтому вы все равно получаете все преимущества от использования небольшого поля. Но случайная проверка точки и вычисление FRI выполняются в этом большем поле, чтобы обеспечить необходимую безопасность.

От небольших простых чисел до двоичного

Компьютеры выполняют арифметические операции, представляя большие числа в виде последовательностей нулей и единиц, и строя "схемы" на основе этих битов для вычисления таких вещей, как сложение и умножение. Компьютеры оптимизированы для выполнения вычислений с 16-битными, 32-битными и 64-битными целыми числами. Модули, такие как 2⁶⁴−2³²+1 и 2³¹-1 выбраны не только потому, что они укладываются в эти границы, но и потому, что они хорошо соответствуют этим границам: вы можете выполнять умножение по модулю 2⁶⁴−2³²+1, выполняя обычное 32-разрядное умножение, и сдвигая и копируя выходы битовым образом в нескольких местах; в этой статье хорошо объясняются некоторые приемы.

Однако было бы еще лучше, если бы вычисления выполнялись непосредственно в двоичном коде. Что, если бы сложение было "просто" XOR, без необходимости "переносить" переполнение от добавления 1 + 1 в одной битовой позиции к следующей битовой позиции? Что, если бы умножение можно было бы распараллеливать таким же образом? И все эти преимущества будут заключаться в том, что вы сможете представлять значения True/False с помощью всего одного бита.

Захват этих преимуществ прямого выполнения бинарных вычислений именно то, что пытается сделать Binius. Таблица из презентации команды Binius на zkSummit показывает прирост эффективности:

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

От одномерных многочленов до гиперкубов

Предположим, что мы убеждены этим рассуждением и хотим делать все через биты (нули и единицы). Как мы на самом деле привязываемся к полиному, представляющему миллиард битов?

Здесь мы сталкиваемся с двумя практическими проблемами:

1. Для того чтобы многочлен представлял множество значений, эти значения должны быть доступны при оценке многочлена: в нашем примере чисел Фибоначчи выше, 𝐹(0), 𝐹(1) … 𝐹(100), и в более крупных вычислениях индексы могут достигать миллионов. И используемое нами поле должно содержать числа, увеличивающиеся до такого размера.

2. Чтобы доказать что-либо о значении, которое мы фиксируем в дереве Меркла (как это делают все STARK), требуется кодировка Рида-Соломона: расширение n значений в, например. 8n, используя избыточность, чтобы предотвратить мошенничество злонамеренного проверяющего, подделывая одно значение в середине вычисления. Для этого также необходимо иметь достаточно большое поле: чтобы расширить миллион значений до 8 миллионов, вам нужно 8 миллионов различных точек, в которых будет вычисляться полином.

Ключевая идея в Binius заключается в том, чтобы решать эти две проблемы отдельно, делая это путем представления одних и тех же данных двумя различными способами. Во-первых, сам полином. SNARK, основанный на эллиптических кривых, STARK эпохи 2019 года, Plonky2 и другие системы, как правило, работают с полиномами по одной переменной: 𝐹(𝑥). Binius, с другой стороны, черпает вдохновение из протокола Spartan и работает с многомерными полиномами: 𝐹(𝑥1,𝑥2…𝑥𝑘). Фактически, мы представляем весь вычислительный след на «гиперкубе» оценок, где каждый 𝑥𝑖 равен либо 0, либо 1. Например, если бы мы хотели представить последовательность чисел Фибоначчи, и мы все еще использовали достаточно большое поле, чтобы их представить, мы могли бы визуализировать первые шестнадцать из них как что-то вроде этого:

То есть, F(0,0,0,0) будет равно 1, F(1,0,0,0) также будет 1, F(0,1,0,0) будет равно 2 и так далее, пока мы не дойдем до F(1,1,1,1)=987. При таком гиперкубе оценок существует ровно один многолинейный (степень 1 в каждой переменной) полином, который производит эти оценки. Таким образом, мы можем думать об этом наборе вычислений как о представлении полинома; На самом деле нам никогда не нужно утруждать себя вычислением коэффициентов.

Этот пример, конечно, просто для иллюстрации: на практике весь смысл перехода к гиперкубу заключается в том, чтобы позволить нам работать с отдельными битами. "Родной для Binius" способ подсчета чисел Фибоначчи заключается в использовании более высокомерного куба, используя каждый набор, например, 16 бит, чтобы сохранить число. Для реализации целочисленного сложения поверх битов требуется некоторая хитрость, но с Binius это не слишком сложно.

Теперь перейдем к стирающему кодированию. Принцип работы STARK таков: вы берете n значений, Рид-Соломон расширяет их на большее количество значений (часто 8n, обычно между 2n и 32n), а затем случайным образом выбираете несколько ветвей Меркла из расширения и выполняете какую-то проверку их. Гиперкуб имеет длину 2 в каждом измерении. Следовательно, непрактично расширять его напрямую: не хватает «места» для выборки ветвей Меркла из 16 значений. Так что же нам делать вместо этого? Мы притворяемся, что гиперкуб — это квадрат!

Простой Биниус - пример

Смотреть здесьдля реализации этого протокола на python.

Давайте рассмотрим пример, используя обычные целые числа в качестве нашего поля для удобства (в реальной реализации это будут элементы бинарного поля). Сначала мы берем гиперкуб, к которому хотим привязаться, и кодируем его как квадрат:

Теперь мы расширяем квадрат Рида-Соломона. То есть мы рассматриваем каждую строку как многочлен степени 3, вычисленный при x = {0, 1, 2, 3}, и вычисляем тот же многочлен при x = {4, 5, 6, 7}:

Обратите внимание, что числа быстро взрываются! Поэтому в реальной реализации мы всегда используем конечное поле для этого, вместо обычных целых чисел: если бы мы использовали целые числа по модулю 11, например, расширение первой строки было бы просто [3, 10, 0, 6].

Если вы хотите поиграть с увеличением и проверить числа здесь сами, вы можете использовать мой простой код расширения Рида-Соломона здесь.

Затем мы рассматриваем это расширение как столбцы и создаем дерево Меркля из столбцов. Корень дерева Меркля - наше обязательство.

Предположим, что доказывающему лицу нужно доказать вычисление этого многочлена в некоторой точке 𝑟={𝑟0,𝑟1,𝑟2,𝑟3}. В Binius есть одна тонкость, которая делает его несколько слабее, чем другие схемы обязательства многочленов: доказывающему лицу не следует знать, или иметь возможность угадать, 𝑠, пока они не обязались к корню Меркля (другими словами, 𝑟 должно быть псевдослучайным значением, которое зависит от корня Меркля). Это делает схему бесполезной для «поиска по базе данных» (например, «хорошо, ты дал мне корень Меркля, теперь докажи мне 𝑃(0,0,1,0)!»). Но фактические протоколы доказательства в нуле, которые мы обычно используем, не требуют «поиска по базе данных»; им просто нужно проверить многочлен в случайной точке вычисления. Следовательно, эти ограничения приемлемы для наших целей.

Предположим, мы выбираем 𝑟={1,2,3,4} (в этот момент полином оценивается как −137; вы можете подтвердить этос этим кодом). Теперь мы переходим к процессу непосредственного создания доказательства. Мы разбиваем 𝑟 на две части: первая часть {1,2}, представляющая собой линейную комбинацию столбцов в пределах строки, и вторая часть {3,4}, представляющая собой линейную комбинацию строк. Мы вычисляем "тензорное произведение", как для части столбца:

И для части строки:

Это означает: список всех возможных продуктов одного значения из каждого набора. В случае строки мы получаем:

[(1-r2)(1-r3), (1-r3), (1-r2)r3, r2*r3]

Используйте r={1,2,3,4} (так что r2=3 и r3=4):

[(1-3)(1-4), 3(1-4),(1-3)4,34] = [6, -9 -8 -12]

Теперь мы вычисляем новую «строку» 𝑡′, взяв эту линейную комбинацию существующих строк. То есть, мы берем:

Вы можете рассматривать происходящее здесь как частичную оценку. Если мы умножим полное тензорное произведение ⨂𝑖=03(1−𝑟𝑖,𝑟𝑖) на полный вектор всех значений, то получим оценку 𝑃(1,2,3,4)=−137. Здесь мы умножаем частичное тензорное произведение, которое использует только половину координат оценки, и уменьшаем сетку из 𝑁 значений до строки из 𝑁 значений. Если вы передадите эту строку кому-то еще, то они смогут использовать тензорное произведение другой половины координат оценки, чтобы завершить остальные вычисления.

Доказатель предоставляет проверяющему этот новый ряд, 𝑡′, а также доказательства Меркля некоторых случайно выбранных столбцов. Это 𝑂(𝑁) данных. В нашем иллюстративном примере доказатель предоставит только последний столбец; в реальной жизни доказатель должен будет предоставить несколько десятков столбцов для достижения достаточной безопасности.

Теперь мы воспользуемся линейностью кодов Рида-Соломона. Ключевое свойство, которое мы используем, заключается в том, что линейная комбинация расширения Рида-Соломона дает тот же результат, что и расширение Рида-Соломона линейной комбинации. Такого рода «независимость от порядка» часто возникает, когда у вас есть две операции, которые обе являются линейными.

Верификатор делает именно это. Они вычисляют расширение 𝑡′, и они вычисляют ту же линейную комбинацию столбцов, которую прувер вычислил ранее (но только для столбцов, предоставленных прувером), и проверяют, что эти две процедуры дают одинаковый ответ.

В этом случае, расширяя t′ и вычисляя одну и ту же линейную комбинацию ([6,−9,−8,12]) столбца, оба дают один и тот же ответ: −10746. Это доказывает, что корень Меркла был построен «добросовестно» (или, по крайней мере, «достаточно близко»), и он соответствует t': по крайней мере, подавляющее большинство столбцов совместимы друг с другом и с t′.

Но проверяющему все еще нужно проверить еще одну вещь: фактически проверить оценку полинома в {𝑟0..𝑟3}. До сих пор ни один из шагов проверяющего фактически не зависел от значения, которое заявил доказатель. Вот как мы это проверяем. Мы берем тензорное произведение того, что мы обозначили как "часть столбца" точки оценки:

В нашем примере, где r={1,2,3,4}, так что половина выбранного столбца - {1,2}), это равно:

Итак, теперь мы берем эту линейную комбинацию 𝑡′:

Что именно равняется ответу, который вы получите, если вы оцените полином непосредственно.

Выше приведено довольно полное описание «простого» протокола Binius. У него уже есть несколько интересных преимуществ: например, потому что данные разделены на строки и столбцы, вам нужно только поле половины размера. Но это далеко не приближается к реализации всех преимуществ вычислений в двоичном формате. Для этого нам понадобится полный протокол Binius. Но сначала давайте более глубоко понимать бинарные поля.

Бинарное поле

Наименьшее возможное поле - арифметика по модулю 2, настолько маленькое, что мы можем записать его таблицы сложения и умножения:

Мы можем создавать более крупные бинарные поля, взяв расширения: если мы начнем с 𝐹2 (целые числа по модулю 2), а затем определим 𝑥, где 𝑥2=𝑥+1, мы получим следующую таблицу сложения и умножения:

Оказывается, мы можем расширить двоичное поле до произвольно больших размеров, повторяя эту конструкцию. В отличие от комплексных чисел над вещественными, где вы можете добавить один новый элемент 𝑖, но больше нельзя добавить ничего (кватернионы существуют, но математически странны, например, 𝑎𝑏≠𝑏𝑎), с конечными полями вы можете бесконечно добавлять новые расширения. Конкретно, мы определяем элементы следующим образом:

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

Мы можем представить эти числа в виде списка битов, например, 1100101010001111. Первый бит представляет кратные 1, второй бит представляет кратные 𝑥0, затем последующие биты представляют кратные: 𝑥1, 𝑥1∗𝑥0, 𝑥2, 𝑥2∗𝑥0 и так далее. Это кодирование хорошо, потому что вы можете его разложить:

Это довольно необычная нотация, но мне нравится представлять элементы двоичного поля как целые числа, принимая битовое представление, где более значимые биты находятся справа. То есть, 1=1, 𝑥₀=01=2, 1+𝑥₀=11=3, 1+𝑥₀+𝑥₂=11001000=19, и так далее. 1100101010001111 - это, в этом представлении, 61779.

Сложение в двоичном поле - это просто исключающее ИЛИ (кстати, то же самое касается и вычитания); обратите внимание, что это означает, что x+x=0 для любого x. Чтобы умножить два элемента x*y, существует очень простой рекурсивный алгоритм: разделите каждое число пополам:

Затем разделите умножение:

Последний кусок - единственный слегка сложный, потому что вам нужно применить правило уменьшения и заменить 𝑅𝑥∗𝑅𝑦∗𝑥𝑘2 на 𝑅𝑥∗𝑅𝑦∗(𝑥𝑘−1∗𝑥𝑘+1). Существуют более эффективные способы умножения, аналоги алгоритма Карацубы и быстрые преобразования Фурье, но я оставлю это упражнением для заинтересованного читателя разобраться в этом.

Деление в двоичных полях выполняется путем комбинирования умножения и инверсии. "Простой, но медленный" способ выполнения инверсии - это применение обобщенной малой теоремы Ферма. Существует также более сложный, но более эффективный алгоритм инверсии, который вы можете найти здесь. Вы можете использовать код здесьиграть с бинарным сложением, умножением и делением самостоятельно.

Слева: таблица сложения для элементов четырехразрядного бинарного поля (т.е. элементов, состоящих только из комбинаций 1, 𝑥₀，𝑥₁и 𝑥₀𝑥₁).

Правильно: таблица умножения для элементов четырехразрядного бинарного поля.

Прекрасное в этом типе бинарного поля заключается в том, что оно объединяет некоторые из лучших частей «обычных» целых чисел и модулярной арифметики. Как и обычные целые числа, элементы бинарного поля неограничены: вы можете продолжать расширять их настолько, насколько захотите. Но, как и в модулярной арифметике, если вы выполняете операции над значениями в пределах определенного размера, все ваши ответы также остаются в том же диапазоне. Например, если вы берете последовательные степени числа 42, вы получите:

После 255 шагов ты вернулся к 42²⁵⁵ = 1. Так же, как положительные целые числа и модульная арифметика, они следуют обычным математическим законам: аb=ba, a(b+c)=a b+a*c, есть даже некоторые странные новые законы.

Наконец, двоичные поля упрощают работу с битами: если вы выполняете математические операции с числами, которые соответствуют 2^k бит, тогда весь ваш вывод также подойдет под 2 к бит. Это избегает смущения. В EIP-4844 Ethereum каждый «блок» блоба должен быть цифровым модулем 52435875175126190479447740508185965837690552500527637822603658699938581184513, поэтому кодирование бинарных данных требует выбрасывания некоторого пространства и выполнения дополнительной проверки, чтобы гарантировать, что каждый элемент хранит значение менее 2²⁴⁸. Это также означает, что бинарные операции с полями выполняются очень быстро на компьютерах - как на ЦП, так и в теоретически оптимальных конструкциях ФПГА и АСИС.

Все это означает, что мы можем сделать что-то вроде кодирования Рида-Соломона, которое мы сделали выше, таким образом, чтобы полностью избежать «взрыва» целых чисел, как мы видели в нашем примере, и очень «взрывающимся» способом. «Родной» способ, тот вид вычислений, в котором хорошо разбираются компьютеры. Атрибут "split" бинарных полей - как мы это делаем 1100101010001111=11001010+10001111*x₃и затем разделить его в соответствии с нашими потребностями также крайне важно для достижения большой гибкости.

Полный Биниус

Смотри здесьдля реализации этого протокола на Python.

Теперь мы можем перейти к "полному Биниусу", который настраивает "простой Биниус" так, чтобы (i) работать над бинарными полями и (ii) позволять нам фиксировать отдельные биты. Этот протокол сложен для понимания, потому что он постоянно переключается между различными способами просмотра матрицы битов; Конечно, мне потребовалось больше времени, чтобы понять, чем обычно требуется для понимания криптографического протокола. Но как только вы поймете, что такое бинарные поля, хорошая новость заключается в том, что не существует никакой «более сложной математики», от которой зависит Binius. Это не эллиптические пары кривых, где есть все более и более глубокие кроличьи норы алгебраической геометрии, в которые нужно спуститься; Здесь двоичные поля — это все, что вам нужно.

Давайте еще раз взглянем на полную диаграмму:

К настоящему времени вам должны быть знакомы большинство компонентов. Идея «сплющивания» гиперкуба в сетку, идея вычисления комбинации строк и комбинации столбцов как тензорных произведений точки оценки, и идея проверки эквивалентности между «расширением Рида-Соломона, затем вычислением комбинации строк», и «вычислением комбинации строк, затем расширением Рида-Соломона», все были в простом Binius.

Что нового в «полном Binius»? В основном три вещи:

• Индивидуальные значения в гиперкубе и в квадрате должны быть битами (0 или 1)
• Процесс расширения увеличивает биты в более крупные биты, группируя их в столбцы и временно притворяясь, что они являются более крупными элементами поля
• После шага комбинации строк есть шаг разложения на элементы "разложение на биты", который преобразует расширение обратно в биты

Мы рассмотрим оба по очереди. Во-первых, новая процедура расширения. Код Рида-Соломона имеет фундаментальное ограничение, что если вы расширяете 𝑛 значений до 𝑘∗𝑛 значений, вам нужно работать в поле, которое имеет 𝑘∗𝑛 различных значений, которые вы можете использовать в качестве координат. С 𝐹₂(т. е. биты), вы не можете это сделать. Итак, что мы делаем, так это «упаковываем» смежные 𝐹₂элементы вместе в большие значения. В данном примере мы упаковываем по два бита за раз в элементы в {0,1,2,3}, потому что в нашем расширении всего четыре точки оценки, и этого достаточно для нас. В «реальном» доказательстве мы, вероятно, объединяли бы 16 бит за раз. Затем мы выполняем код Рида-Соломона над этими упакованными значениями и снова распаковываем их в биты.

Теперь комбинация строк. Чтобы сделать проверку "оценить в случайной точке" криптографически безопасной, нам нужно, чтобы эта точка была выбрана из довольно большого пространства, намного большего, чем сам гиперкуб. Поэтому, в то время как точки внутри гиперкуба являются битами, оценки за пределами гиперкуба будут намного больше. В нашем примере выше, "комбинация строк" в конечном итоге оказывается [11,4,6,1].

Это представляет проблему: мы знаем, как объединять пары битов в более крупное значение, а затем выполнять расширение Рида-Соломона на нем, но как это сделать с парами значительно больших значений?

Хитрость в Binius заключается в выполнении операций побитово: мы рассматриваем отдельные биты каждого значения (например, для того, что мы обозначили как "11", это [1,1,0,1]), а затем мы расширяем по строкам. То есть мы выполняем процедуру расширения на 1 строке каждого элемента, затем на строке 𝑥0, затем на "𝑥"₁«строку, затем на 𝑥₀∗𝑥₁строка и так далее (ну, в нашем игрушечном примере мы останавливаемся здесь, но в реальной реализации мы бы продолжили до 128 строк (последняя из которых будет 𝑥₆∗ …∗ 𝑥₀)),

Повторение:

• Мы берем биты в гиперкубе и преобразуем их в сетку
• Затем мы рассматриваем смежные группы битов в каждой строке как более крупные элементы поля и выполняем арифметические операции с ними для расширения строк методом Рида-Соломона
• Затем мы берем комбинацию строк каждого столбца битов и получаем (для квадратов больше 4x4, значительно меньших) столбец битов для каждой строки в качестве выходных данных
• Затем мы рассматриваем выходные данные как матрицу и снова обрабатываем биты как строки

Почему это работает? В «обычной» математике возможность (часто) выполнять линейные операции в любом порядке и получать тот же результат перестает работать, если начать разбивать число на цифры. Например, если я начну с числа 345 и умножу его на 8, а затем на 3, я получу 8280, и если сделаю эти две операции в обратном порядке, я также получу 8280. Но если вставить операцию «разделить по цифрам» между двумя шагами, все ломается: если сначала умножить на 8, а затем на 3, вы получите:

Но если сделать 3х, а потом 8х, то получится:

Но в двоичном поле, построенном с башенной структурой, этот подход работает. Причина заключается в их разделимости: если умножить большое значение на маленькое значение, то то, что происходит на каждом сегменте, остается на каждом сегменте. Если мы умножим 1100101010001111 на 11, это то же самое, что и первая факторизация 1100101010001111, которая

И затем умножить каждый компонент отдельно на 11.

Собираем все вместе

В общем, системы доказательства нулевого знания работают, делая утверждения о многочленах, которые одновременно представляют утверждения о базовых оценках: как мы видели в примере с числами Фибоначчи, 𝐹(𝑋+2)−𝐹(𝑋+1)−𝐹(𝑋)=𝑍(𝑋)∗𝐻(𝑋) одновременно проверяет все шаги вычисления чисел Фибоначчи. Мы проверяем утверждения о многочленах, доказывая оценки в случайной точке. Эта проверка в случайной точке заменяет проверку всего многочлена: если многочленное уравнение не совпадает, вероятность того, что оно совпадет в конкретной случайной координате, крайне мала.

На практике основным источником неэффективности является тот факт, что в реальных программах большинство чисел, с которыми мы работаем, являются маленькими: индексы в циклах, значения True/False, счетчики и подобные вещи. Но когда мы «расширяем» данные с использованием кодирования Рида-Соломона, чтобы обеспечить им необходимую избыточность для обеспечения безопасности проверок на основе доказательства Меркля, большинство «дополнительных» значений оказываются занимающими полный размер поля, даже если исходные значения малы.

Чтобы избежать этого, мы хотим сделать поле как можно меньшим. Plonky2 снизил нас с чисел 256 бит до чисел 64 бит, а затем Plonky3 пошел еще дальше и дошел до 31 бита. Но даже это неоптимально. С бинарными полями мы можем работать с отдельными битами. Это делает кодирование «плотным»: если у ваших фактических базовых данных n бит, то ваше кодирование также будет иметь n бит, и расширение будет состоять из 8 * n битов, без дополнительных накладных расходов.

Теперь давайте посмотрим на диаграмму в третий раз:

В Binius мы обязуемся соблюдать мультилинейный многочлен: гиперкуб 𝑃(x₀,x₁,…x_к) , где индивидуальные оценки 𝑃(0,0…0), 𝑃(0,0…1) до 𝑃(1,1,…1) содержат данные, которые нас интересуют. Чтобы доказать оценку в точке, мы «переинтерпретируем» те же данные как квадрат. Затем мы расширяем каждую строку, используя кодирование Рида-Соломона над группами битов, чтобы обеспечить данным необходимую избыточность для обеспечения безопасности случайных запросов ветвей Меркла. Затем мы вычисляем случайное линейное комбинацию строк, с коэффициентами, спроектированными так, чтобы новая объединенная строка фактически содержала оценку, которая нас интересует. Как эту вновь созданную строку (которая переинтерпретируется как 128 строк битов), так и несколько случайно выбранных столбцов с ветвями Меркла передают проверяющему.

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

Чего мы не охватили?

• Эффективные алгоритмы для расширения строк, которые необходимы для фактического повышения вычислительной эффективности верификатора. Мы используем быстрые преобразования Фурье над бинарными полями, описанныездесь(хотя конкретная реализация будет отличаться, потому что в этом посте используется менее эффективная конструкция, не основанная на рекурсивном расширении).
• Арифметизация. Одночлены удобны, потому что можно делать вещи вроде F(X+2)-F(X+1)-F(X) = Z(X)*H(X), чтобы связать смежные шаги в вычислении. В гиперкубе "следующий шаг" гораздо менее интерпретируем, чем "X+1". Можно было бы использовать X+k, степени k, но такое поведение приведет к потере многих ключевых преимуществ Binius. Решение представлено в Биниус бумага(См. Раздел 4.3), но это само по себе глубокая кроличья нора.
• Как фактически безопасно выполнять проверки конкретных значений. В примере с числами Фибоначчи требуется проверка граничных условий ключа: F(0)=F(1)=1 и значения F(100). Но с использованием "сырых" биниусов небезопасно проверять на известных точках оценки. Существуют довольно простые способы преобразования проверки известной оценки в проверку неизвестной оценки с использованием так называемых протоколов суммарной проверки; но мы не будем вдаваться в них здесь.
• Протоколы поиска, еще одна технология, которая недавно начала использоваться как способ создания ультраэффективных систем доказательств. Binius может быть объединен с протоколами поиска для многих приложений.
• Превышение времени проверки квадратного корня. Квадратный корень дорогой: доказательство Binius из битов длиной около 11 МБ. Вы можете исправить это, используя другую систему доказательств для создания «доказательства доказательства Binius», тем самым получив как эффективность Binius в доказательстве основного утверждения, так и небольшой размер доказательства. Другой вариант - намного более сложный протокол FRI-Binius, который создает доказательство полилогарифмического размера (как обычный FRI).
• Как Binius влияет на то, что считается «дружелюбным к SNARK». Основное заключение заключается в том, что, если вы используете Binius, вам уже не нужно слишком беспокоиться о том, чтобы сделать вычисление «арифметически дружественным»: «обычные» хеши больше не эффективнее традиционных арифметических хешей, умножение по модулю или по модулю больше не является большой головной болью по сравнению с умножением по модулю , и так далее. Но это сложная тема; многое меняется, когда все делается в двоичном виде.

Я ожидаю еще множество улучшений в техниках, основанных на бинарных полях, в следующие месяцы.

Отказ от ответственности：

1. Эта статья перепечатана с [Panews]. Пересылка оригинального заголовка «Vitalik обьясняет Binius: эффективная система доказательств на основе двоичных полей». Все авторские права принадлежат оригинальному автору [Виталик Бутерин*]. Если есть возражения по поводу этой перепечатки, пожалуйста, свяжитесь с Gate Learnкоманда, и они оперативно решат эту проблему.
2. Отказ от ответственности: Взгляды и мнения, выраженные в этой статье, являются исключительно мнением автора и не являются инвестиционными советами.
3. Переводы статьи на другие языки выполняются командой Gate Learn. Если не указано иное, копирование, распространение или плагиат переведенных статей запрещены.