Аналіз принципів 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 розмір області повинен бути більшим за ступінь полінома; під час комітету дерева Меркла в 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 було розроблено з акцентом на масштабованість і усунення trusted setup у протоколі ZCash.

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

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

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

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

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

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

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

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