Анализ принципов Binius STARKs и размышления об их оптимизации

1 Введение

В отличие от SNARKs, основанных на эллиптических кривых, STARKs можно рассматривать как SNARKs на основе хеширования. Одной из основных причин низкой эффективности STARKs в настоящее время является то, что большинство чисел в реальных программах довольно малы, такие как индексы в циклах for, логические значения, счетчики и т.д. Тем не менее, для обеспечения безопасности доказательства на основе дерева Меркла, при использовании кодирования Рида-Соломона для расширения данных многие дополнительные избыточные значения занимают весь диапазон, даже если оригинальные значения сами по себе очень малы. Для решения этой проблемы снижение размера диапазона стало ключевой стратегией.

Первое поколение STARKs имеет ширину кодирования 252 бита, второе поколение STARKs имеет ширину кодирования 64 бита, третье поколение STARKs имеет ширину кодирования 32 бита, но 32-битная ширина кодирования все еще имеет много неиспользуемого пространства. В сравнении, двоичное поле позволяет напрямую работать с битами, кодирование компактно и эффективно без произвольного неиспользуемого пространства, то есть четвертое поколение STARKs.

По сравнению с ограниченными полями, недавно обнаруженными в исследованиях Goldilocks, BabyBear, Mersenne31 и других за последние несколько лет, исследования бинарных полей восходят к 80-м годам прошлого века. В настоящее время бинарные поля широко применяются в криптографии, типичные примеры включают:

• Стандарт продвинутого шифрования (AES), основанный на поле F28;

• Galois сообщение аутентификации ( GMAC ), основанное на поле F2128;

• QR-код, использующий кодирование Рида-Соломона на основе F28;

• Исходный протокол FRI и zk-STARK, а также хэш-функция Grøstl, которая вышла в финал SHA-3 и основана на поле F28, является очень подходящим рекурсивным хэш-алгоритмом.

При использовании меньших полей операция расширения поля становится все более важной для обеспечения безопасности. А двоичное поле, используемое Binius, полностью зависит от расширения поля для обеспечения своей безопасности и практической применимости. Большинство многочленов, вовлеченных в вычисления Prover, не требуют перехода в расширенное поле и могут работать в базовом поле, что обеспечивает высокую эффективность в малом поле. Тем не менее, проверка случайных точек и вычисления FRI все еще требуют углубления в более широкое расширенное поле для обеспечения необходимой безопасности.

При построении системы доказательств на основе двоичных полей возникают 2 практические проблемы: при вычислении представления следа в STARKs размер поля должен быть больше степени многочлена; при обязательстве Merkle tree в STARKs необходимо использовать кодирование Рида-Соломона, при этом размер поля должен превышать размер после расширения кодирования.

Binius предложил инновационное решение для обработки этих двух проблем отдельно и реализовал это, представляя одни и те же данные двумя разными способами: во-первых, используя много переменные (, а именно много линейные ) многочлены вместо одномерных многочленов, представляя всю вычислительную траекторию через их значения на "гиперкубах" (hypercubes); во-вторых, поскольку длина каждого измерения гиперкуба равна 2, стандартное расширение Reed-Solomon не может быть выполнено, как в случае STARKs, но гиперкуб может быть рассмотрен как квадрат (square), на основе которого можно выполнить расширение Reed-Solomon. Этот метод значительно увеличивает эффективность кодирования и вычислительную производительность, обеспечивая при этом безопасность.

2 Принципиальный анализ

В настоящее время большинство систем SNARKs обычно состоит из двух частей:

• Информационно-теоретический полиномиальный интерактивный оракул, PIOP(: PIOP как основа системы доказательства преобразует входные вычислительные отношения в проверяемые полиномиальные равенства. Разные протоколы PIOP, взаимодействуя с проверяющим, позволяют доказателю последовательно отправлять полиномы, позволяя проверяющему проверять правильность вычислений, запрашивая лишь небольшое количество оценок полиномов. Существующие протоколы PIOP включают: PLONK PIOP, Spartan PIOP и HyperPlonk PIOP, которые по-разному обрабатывают полиномиальные выражения, что, в свою очередь, влияет на производительность и эффективность всей системы SNARK.

• Полиномиальная схема обязательств ) Polynomial Commitment Scheme, PCS (: Полиномиальная схема обязательств используется для доказательства того, является ли полиномиальное равенство, сгенерированное PIOP, истинным. PCS — это криптографический инструмент, с помощью которого доказатель может подтвердить определенный полином и позже проверить результаты его оценки, скрывая при этом другую информацию о полиноме. Распространенные схемы обязательств по полиномам включают KZG, Bulletproofs, FRI ) Fast Reed-Solomon IOPP ( и Brakedown и т. д. Разные PCS имеют разные характеристики, безопасность и области применения.

В зависимости от конкретных требований можно выбрать различные PIOP и PCS, а также комбинировать их с подходящими конечными полями или эллиптическими кривыми, чтобы создать доказательственную систему с различными свойствами. Например:

• Halo2: сочетание PLONK PIOP и Bulletproofs PCS, основанное на кривой Pasta. При проектировании Halo2 акцент сделан на масштабируемости и устранении доверенной настройки в протоколе ZCash.

• Plonky2: сочетает PLONK PIOP и FRI PCS, основан на области Goldilocks. Plonky2 разработан для достижения эффективной рекурсии. При проектировании этих систем выбранные PIOP и PCS должны соответствовать используемому конечному полю или эллиптической кривой, чтобы обеспечить правильность, производительность и безопасность системы. Выбор этих комбинаций влияет не только на размер доказательства SNARK и эффективность верификации, но также определяет, сможет ли система достичь прозрачности без необходимости доверенной настройки и поддерживать расширенные функции, такие как рекурсивные доказательства или агрегированные доказательства.

Binius: HyperPlonk PIOP + Brakedown PCS + бинарные поля. В частности, Binius включает в себя пять ключевых технологий, обеспечивающих его эффективность и безопасность. Во-первых, основанная на башенных бинарных полях )towers of binary fields( арифметика составляет основу его вычислений, позволяя выполнять упрощенные операции в бинарных полях. Во-вторых, Binius в своем интерактивном протоколе Oracle доказательства )PIOP( адаптировал проверку произведения и перестановок HyperPlonk, обеспечивая безопасную и эффективную проверку согласованности между переменными и их перестановками. В-третьих, протокол вводит новое многочленное смещение, оптимизируя эффективность проверки многочленных отношений на малых полях. В-четвертых, Binius использует улучшенный протокол поиска Lasso, обеспечивая гибкость и высокую безопасность механизма поиска. Наконец, протокол использует схему обязательств для многочленов на малых полях )Small-Field PCS(, что позволяет ему реализовать эффективную систему доказательств на бинарных полях и сократить затраты, обычно связанные с большими полями.

) 2.1有限域: основанная на арифметике башен двоичных полей

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

Термин "canonical" относится к уникальному и прямому представлению элементов в двоичном поле. Например, в самом простом двоичном поле F2 любая строка длиной k бит может быть непосредственно сопоставлена с элементом двоичного поля длиной k бит. Это отличается от полей с простым числом, которые не могут предоставить такое стандартное представление в заданной длине. Хотя поле с простым числом длиной 32 может содержать 32 бита, не каждая 32-битная строка может уникально соответствовать элементу поля, тогда как двоичное поле обладает удобством такого взаимно однозначного сопоставления. В поле с простым числом Fp распространенные методы редукции включают редукцию Барретта, редукцию Монтгомери и специальные методы редукции для определенных конечных полей, таких как Mersenne-31 или Goldilocks-64. В двоичном поле F2k часто используемые методы редукции включают специальную редукцию ###, используемую в AES (, редукцию Монтгомери ), используемую в POLYVAL (, и рекурсивную редукцию ), такую как Tower (. В статье "Изучение проектного пространства аппаратных реализаций ECC-полей с простым числом и двоичных полей" указывается, что в двоичном поле не требуется вводить перенос в операциях сложения и умножения, и что возведение в квадрат в двоичном поле очень эффективно, поскольку оно подчиняется упрощенному правилу )X + Y (2 = X2 + Y2.

Как показано на рисунке 1, строка длиной 128 бит: эта строка может быть интерпретирована несколькими способами в контексте двоичного поля. Она может рассматриваться как уникальный элемент в 128-битном двоичном поле или быть разобрана на два элемента 64-битного башенного поля, четыре элемента 32-битного башенного поля, 16 элементов 8-битного башенного поля или 128 элементов поля F2. Эта гибкость представления не требует никаких вычислительных затрат, а лишь преобразования типов строк )typecast(, что является очень интересным и полезным свойством. Кроме того, малые элементы поля могут быть упакованы в более крупные элементы поля без дополнительных вычислительных затрат. Протокол Binius использует эту особенность для повышения вычислительной эффективности. Кроме того, статья «О эффективном обращении в башенных полях характеристик два» исследует вычислительную сложность операций умножения, возведения в квадрат и обращения в n-битных башенных двоичных полях ), которые могут быть разложены на m-битные подполя (.

! [Исследование битlayer: анализ принципов и оптимизационное мышление Binius STARKs])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(

) 2.2 PIOP: переработанная версия HyperPlonk Product и PermutationCheck------ подходит для двоичного поля

Дизайн PIOP в протоколе Binius заимствовал HyperPlonk и использует ряд основных проверочных механизмов для проверки корректности полиномов и многомерных множеств. Эти основные проверки включают:

1. GateCheck: Проверка, удовлетворяют ли конфиденциальное свидетельство ω и открытый ввод x вычислительным отношениям C###x,ω(=0, чтобы гарантировать правильную работу схемы.

2. PermutationCheck: Проверка того, являются ли результаты вычисления двух многомерных многочленов f и g на булевом гиперкубе соотношением перестановки f)x( = f)π(x(), чтобы обеспечить согласованность перестановок между переменными многочлена.

3. LookupCheck: проверка, находится ли вычисление многочлена в заданной таблице поиска, то есть f)Bµ( ⊆ T)Bµ(, чтобы убедиться, что некоторые значения находятся в заданном диапазоне.

4. MultisetCheck: Проверка на равенство двух многомножества, а именно {)x1,i,x2,(}i∈H={)y1,i,y2,(}i∈H, гарантируя согласованность между несколькими множествами.

5. ProductCheck: Проверка того, равно ли значение многочлена на булевом гиперкубе заявленному значению ∏x∈Hµ f)x( = s, чтобы обеспечить правильность произведения многочлена.

6. ZeroCheck: Проверка того, является ли многочлен с несколькими переменными нулем в любой точке булевого гиперквадрата ∏x∈Hµ f)x( = 0, ∀x ∈ Bµ, чтобы гарантировать распределение нулей многочлена.

7. SumCheck: Проверка того, является ли сумма значений многочлена с несколькими переменными заявленным значением ∑x∈Hµ f)x( = s. Путем преобразования задачи оценки многочлена с несколькими переменными в задачу оценки одночленного многочлена, уменьшается вычислительная сложность для проверяющей стороны. Кроме того, SumCheck также позволяет пакетную обработку, вводя случайные числа, чтобы построить линейные комбинации для обработки нескольких экземпляров проверки суммы.

8. BatchCheck: основанный на SumCheck, проверяет правильность оценки нескольких многомерных многочленов для повышения эффективности протокола.

Хотя у Binius и HyperPlonk есть много схожего в проектировании протокола, Binius улучшил следующие 3 аспекта:

• Оптимизация ProductCheck: в HyperPlonk ProductCheck требует, чтобы знаменатель U был ненулевым на всем гиперкубе, и произведение должно быть равно определенному значению; Binius упростил этот процесс проверки, специфицировав это значение как 1, что снизило вычислительную сложность.

• Обработка проблемы деления на ноль: HyperPlonk не смог должным образом обработать случаи деления на ноль, что привело к невозможности утверждать о ненулевом значении U в гиперкубе; Binius правильно обработал эту проблему, даже при нулевом знаменателе ProductCheck от Binius может продолжать обработку, позволяя обобщение на произвольные значения произведения.

• Перекрестная проверка перестановки: HyperPlonk не поддерживает эту функцию; Binius поддерживает проверку перестановки между несколькими столбцами, что позволяет Binius обрабатывать более сложные случаи перестановки многочленов.

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

) 2.3 PIOP: Новый многофункциональный сдвиг аргумента------применимо к булеву гиперкубу

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

• Упаковка: Этот метод работает за счет того, что меньший из соседних элементов в словаре.