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

1 Вступ

Основною причиною низької ефективності 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, розмір поля, що використовується, повинен бути більшим за ступінь полінома; при зобов'язанні Меркле-дерева в STARKs необхідно виконати кодування Ріда-Соломона, розмір поля, що використовується, повинен бути більшим за розмір після розширення коду.

Binius запропонував інноваційне рішення для розв'язання обох цих проблем, представляючи ті ж дані двома різними способами: по-перше, використовуючи багатозмінний (, а саме багатолінійний ) багаточлен замість однозмінного багаточлена, представляючи весь обчислювальний шлях через його значення на "гіперкубах" ( hypercubes ); по-друге, оскільки довжина кожного виміру гіперкуба дорівнює 2, стандартне розширення Ріда-Соломона, як у STARKs, не може бути виконане, але гіперкуб можна розглядати як квадрат ( square ), на основі якого можна виконати розширення Ріда-Соломона. Цей підхід забезпечує безпеку, суттєво підвищуючи ефективність кодування та обчислювальну продуктивність.

2 Принципи аналізу

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

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

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

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

де «канонічний» означає унікальне та пряме представлення елемента в двійковій області. Наприклад, у найпростішому двійковому домені F2 будь-який k-бітовий рядок може бути відображений безпосередньо на k-бітний елемент двійкового домену. Це на відміну від поля простих чисел, яке не може забезпечити таке канонічне представлення в межах заданої позиції. Хоча 32-бітне поле простого числа може міститися в 32-розрядній системі, не кожен 32-бітовий рядок однозначно відповідає елементу домену, і двійкові поля мають зручність такого відображення один до одного. У простій області Fp поширені методи редукції включають редукцію Барретта, редукцію Монтгомері та спеціальні методи скорочення для конкретних скінченних полів, таких як Мерсенна-31 або Золотоволоски-64. У двійковій області F2k часто використовувані методи редукції включають спеціальні редукційні (, такі як використання ) в AES, Редукційні ( Монтгомері, такі як POLYVAL, використовують ), а рекурсивні редукційні ( такі як Tower). У статті "Дослідження простору проектування реалізації ECC-апаратного забезпечення простого поля проти двійкового поля" вказується, що двійковий домен не потребує введення перенесення як у додаванні, так і в множенні, і що квадратична операція двійкового домену дуже ефективна, оскільки вона слідує за (X + Y )2 = Х2 + У 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 також може продовжити обробку, дозволяючи розширення до будь-якого значення добутку.

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

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

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

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

• Упаковка: Цей метод оптимізує операцію, упаковуючи менші елементи, що знаходяться на сусідніх позиціях у словниковому порядку, в більші елементи. Оператор Pack працює з блоками розміром 2κ і об’єднує їх у високорозмірний простір.