Аналіз принципів 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, розмір поля має бути більшим за ступінь многочлена; під час зобов'язання Merkle tree в STARKs потрібно виконати кодування Ріда-Соломона, розмір поля має бути більшим за розмір після розширення коду.

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

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

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

• Інформаційно-теоретичний полінономіальний інтерактивний oracle proof ( 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.

Термін "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 використовує цю особливість для підвищення обчислювальної ефективності. Крім того, у статті "On Efficient Inversion in Tower Fields of Characteristic Two" розглядається обчислювальна складність операцій множення, піднесення до квадрату та обернення в n-бітних площинних двійкових полях (, що можуть бути розкладені на m-бітні підполя ).

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

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 обробляти більш складні ситуації з перестановкою многочленів.

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

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

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

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