Аналіз принципів Binius STARKs та їх оптимізаційні роздуми

1 Вступ

Основною причиною низької ефективності STARKs є те, що більшість чисел у фактичних програмах є досить малими, такими як індекси в циклах for, булеві значення, лічильники тощо. Проте, щоб забезпечити безпеку доказів на основі дерева Меркла, під час розширення даних з використанням кодування Ріда-Соломона багато додаткових надмірних значень займають ціле поле, навіть якщо оригінальне значення само по собі дуже маленьке. Для вирішення цієї проблеми зменшення розміру поля стало ключовою стратегією.

Як показано в таблиці 1, ширина кодування STARKs першого покоління становить 252 біт, ширина кодування STARKs другого покоління становить 64 біти, ширина кодування STARKs третього покоління становить 32 біти, але 32-бітна ширина кодування все ще має значну кількість невикористаного простору. У порівнянні з цим, двійкове поле дозволяє виконувати операції безпосередньо над бітами, забезпечуючи компактне та ефективне кодування без будь-якого невикористаного простору, тобто STARKs четвертого покоління.

Таблиця 1: Шлях еволюції STARKs

| Алгебра | Ширина кодування | Представницька система | |------|----------|----------| | Перше покоління | 252bit | StarkWare | | Друге покоління | 64bit | Plonky2 | | Третє покоління | 32bit | BabyBear | | 4 покоління | двійкова область | Binius |

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

• Поліноміальні зобов'язання ( Поліноміальна схема зобов'язань, PCS ): Поліноміальна схема зобов'язань використовується для доведення того, чи є вірними поліноміальні рівності, згенеровані PIOP. PCS є криптографічним інструментом, за допомогою якого доведувач може зобов'язатися певним поліномом і пізніше перевірити результати оцінки цього полінома, одночасно приховуючи іншу інформацію про поліном. Звичайні схеми поліноміальних зобов'язань включають KZG, Bulletproofs, FRI ( Швидкий Рід-Соломон 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 адаптував перевірку продукції та заміни 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 + Y2.

Як показано на рисунку 1, 128-бітний рядок: цей рядок може бути інтерпретований у контексті бінарного поля різними способами. Він може розглядатися як унікальний елемент у 128-бітному бінарному полі або бути розкладеним на два 64-бітних елементи поля, чотири 32-бітних елементи поля, 16 восьмибітних елементів поля або 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 ProductCheck вимагає, щоб знаменник U був ненульовим на всьому гіперкубі, а добуток мав дорівнювати певному значенню; Binius спростив цей процес перевірки, спеціалізуючи це значення на 1, тим самим зменшуючи обчислювальну складність.

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

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

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

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

У протоколі Binius, віртуальний