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

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

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

• Інформаційно-теоретичні поліноміальні інтерактивні оракульні докази (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP як основа доказової системи перетворює вхідні обчислювальні зв'язки на перевіряємi поліноміальні рівняння. Різні протоколи 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-бітовий рядок може унікально відповідати елементу поля, тоді як бінарне поле має цю зручність однозначного відображення. У просторовому полі 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-бітні підполя).

! Дослідження 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 обробляти більш складні випадки перестановки多项式.

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

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

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

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

• Упаковка：