Аналіз принципів 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 зазвичай містить дві частини:

• Інформаційно-теоретичні поліно́мні інтерактивні ора́кульні докази ( Information-Theoretic Polynomial Interactive Oracle Proof, PIOP ): PIOP як основа системи доведення перетворює вхідні обчислювальні зв'язки в поліно́мні рівності, які можна перевірити. Різні протоколи PIOP через взаємодію з перевіряючим дозволяють доказувачу поступово надсилати поліно́ми, таким чином перевіряючий може перевірити правильність обчислень, запитуючи результати оцінки лише невеликої кількості поліно́мів. Існуючі протоколи PIOP включають: PLONK PIOP, Spartan PIOP та HyperPlonk PIOP, які по-різному обробляють поліно́мні вирази, що впливає на продуктивність і ефективність усієї системи SNARK.

• Поліноміальні зобов'язання ( Поліноміальна схема зобов'язань, 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 включає п'ять ключових технологій для досягнення своєї ефективності та безпеки. По-перше, базова арифметика на основі веж двійкових полів (towers of binary fields) становить основу його обчислень, що дозволяє спростити обчислення в двійкових полях. По-друге, Binius адаптував HyperPlonk перевірку добутків та перестановок у своєму інтерактивному Oracle доказовому протоколі (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 використовує цю особливість для підвищення обчислювальної ефективності. Крім того, у статті "Про ефективне обернення в області висоти з характеристикою два" розглядається обчислювальна складність операцій множення, піднесення до квадрату та обернення в 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 вимога до знаменника U полягає в тому, щоб він був ненульовим у всіх точках гіперкуба, і добуток повинен дорівнювати певному значенню; Binius спростив цей процес перевірки, спеціалізуючи це значення на 1, зменшуючи тим самим обчислювальну складність.

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

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

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

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

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

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

• Упаковка: цей метод через