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

• Plonky2: використовує PLONK PIOP та FRI PCS у поєднанні, основане на області Goldilocks. Plonky2 створено для досягнення ефективної рекурсії. При проектуванні цих систем вибір PIOP та PCS повинен відповідати використаній скінченній області або еліптичній кривій, щоб забезпечити коректність, продуктивність та безпеку системи. Ці комбінації впливають не лише на розмір доказу SNARK та ефективність перевірки, але й визначають, чи може система досягти прозорості без надійних налаштувань, чи може підтримувати рекурсивні докази або агреговані докази та інші розширені функції.

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

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