Аналіз принципів Binius STARKs та їх оптимізаційні роздуми

1 Вступ

Основною причиною низької ефективності STARKs є те, що більшість чисел у реальних програмах є невеликими, але для забезпечення безпеки доказів, основаних на дереві Меркла, використання кодування Ріда-Соломона для розширення даних призводить до того, що багато додаткових зайвих значень займають цілу область, навіть якщо самі початкові значення є дуже малими. Для вирішення цієї проблеми зменшення розміру області стало ключовою стратегією.

Перший покоління 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, стандартне розширення Ріда-Соломона, як у STARKs, не може бути виконане, але гіперкуб можна розглядати як квадрат (square), на основі якого можна виконати розширення Ріда-Соломона. Цей підхід значно підвищує ефективність кодування та обчислювальну продуктивність, забезпечуючи при цьому безпеку.

2 Аналіз принципів

Поточна більшість систем SNARKs зазвичай складається з двох частин:

• Теорія інформації багаторазового інтерактивного oracle-доказу (Information-Theoretic Polynomial Interactive Oracle Proof, 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 адаптував перевірку добутків і перестановок HyperPlonk у своєму інтерактивному Oracle доказовому протоколі (PIOP), щоб забезпечити безпечну та ефективну перевірку узгодженості між змінними та їх перестановками. По-третє, протокол вводить нову багатолінійну зсувну перевірку, оптимізуючи ефективність перевірки багатолінійних відносин на малих полях. По-четверте, Binius використовує покращену Lasso перевірку, що надає гнучкість і потужну безпеку механізму пошуку. Нарешті, протокол використовує схему обіцянки малопольового многочлена (Small-Field PCS), що дозволяє йому реалізувати ефективну доказову систему на двійковому полі та зменшує витрати, зазвичай пов'язані з великими полями.

2.1 Обмежене поле: арифметика на основі веж бінарних полів

Тау-структура бінарних полів є ключем до реалізації швидких перевіряємих обчислень, що в основному зумовлено двома аспектами: ефективними обчисленнями та ефективною арифметикою. Бінарні поля за своєю сутністю підтримують надзвичайно ефективні арифметичні операції, що робить їх ідеальним вибором для криптографічних застосувань з чутливими до продуктивності вимогами. Крім того, структура бінарних полів підтримує спрощений арифметичний процес, тобто обчислення, виконувані в бінарному полі, можуть бути представлені у компактній та легкій для перевірки алгебраїчній формі. Ці характеристики, разом із здатністю максимально використовувати свої ієрархічні властивості через тау-структуру, роблять бінарні поля особливо підходящими для таких масштабованих систем доказів, як Binius.

Термін "canonical" означає унікальний та прямий спосіб представлення елементів у двійковому полі. Наприклад, у найосновнішому двійковому полі F2 будь-який k-бітний рядок може бути безпосередньо відображений на k-бітний елемент двійкового поля. Це відрізняється від простих полів, які не можуть надати таке нормативне представлення в заданій кількості бітів. Хоча 32-бітне просте поле може містити 32 біти, не кожен 32-бітний рядок може унікально відповідати елементу поля, тоді як двійкове поле має цю зручність однозначного відображення. У простому полі Fp поширеними методами редукції є редукція Барретта, редукція Монтгомері та спеціальні методи редукції для конкретних кінцевих полів, таких як Mersenne-31 або Goldilocks-64. У двійковому полі F2k звичайні методи редукції включають спеціальну редукцію (як у AES), редукцію Монтгомері (як у POLYVAL), а також рекурсивну редукцію (як у Tower). У статті "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" зазначається, що у двійковому полі не потрібно вводити переноси під час операцій додавання та множення, а обчислення квадратів у двійковому полі є дуже ефективним, оскільки воно підпорядковується спрощеному правилу (X + Y )2 = X2 + Y 2.

Як показано на малюнку 1, рядок довжиною 128 біт: цей рядок може бути інтерпретований різними способами в контексті бінарного поля. Його можна розглядати як унікальний елемент у 128-бітному бінарному полі або розбирати на два елементи 64-бітного поля, чотири елементи 32-бітного поля, 16 елементів 8-бітного поля або 128 елементів поля F2. Ця гнучкість представлення не потребує жодних обчислювальних витрат, а лише є перетворенням типу (typecast) бітового рядка, що є дуже цікавою та корисною властивістю. Водночас, елементи малих полів можуть бути упаковані в більші елементи полів без додаткових обчислювальних витрат. Протокол Binius використовує цю характеристику для підвищення обчислювальної ефективності. Крім того, у статті «On Efficient Inversion in Tower Fields of Characteristic Two» розглядається обчислювальна складність множення, піднесення до квадрату та обчислення обернених у n-бітних баштових бінарних полях (які можна розкладати на m-бітні підполя).

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 вдосконалено в трьох аспектах:

• Оптимізація ProductCheck: у HyperPlonk ProductCheck вимагає, щоб знаменник U у гіперкубі був скрізь ненульовим, і щоб добуток дорівнював певному значенню; Binius спростив цей процес перевірки, спеціалізувавши це значення на 1, тим самим зменшивши обчислювальну складність.

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

• Перемішування між стовпцями (PermutationCheck): HyperPlonk не має цієї функції; Binius підтримує проведення PermutationCheck між кількома стовпцями, що дозволяє Binius обробляти більш складні випадки розташування многочленів.

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

! Дослідження Bitlayer: Аналіз принципів Бініуса Старка та оптимізаційне мислення

2.3 PIOP: новий багатолінійний зсув аргумент------підходить для булевого гіперкуба

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

• Упаковка: цей метод працює шляхом об’єднання сусідніх менших елементів у словниковому порядку.