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

1. Вступ

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

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

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

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

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

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

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

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

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