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

• Інформаційно-теоретичні поліноніальні інтерактивні оракульні докази ( 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 розроблений з акцентом на масштабованість та усунення довіреного налаштування в протоколі ZCash.

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

Binius: HyperPlonk PIOP + Brakedown PCS + двійкове поле. Конкретно, Binius включає п'ять ключових технологій для досягнення своєї ефективності та безпеки. По-перше, аритметична структура на основі веж двійкових полів (towers of binary fields) стала основою для його обчислень, що дозволяє спростити обчислення в двійковому полі. По-друге, Binius адаптував перевірки добутку та перестановки в своєму інтерактивному протоколі Oracle доказів (PIOP), забезпечуючи безпечну та ефективну перевірку узгодженості між змінними та їх перестановками. По-третє, протокол вводить новий доказ багатолінійного зсуву, оптимізуючи ефективність перевірки багатолінійних зв'язків на малих полях. По-четверте, Binius використовує вдосконалену версію доказу пошуку Lasso, що надає механізму пошуку гнучкість і потужну безпеку. Нарешті, протокол використовує схему зобов'язань поліномів малих полів (Small-Field PCS), що дозволяє реалізувати ефективну систему доказів на двійкових полях та зменшує витрати, які зазвичай пов'язані з великими полями.

2.1 Обмежене поле: арифметика на основі веж бінарних полів

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

Термін "канонічний" стосується єдиного та прямого способу представлення елементів у бінарному полі. Наприклад, у найосновнішому бінарному полі F2 будь-який рядок з k бітів може бути безпосередньо відображений на елемент bінарного поля з 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 восьмибітних елементів вежі або 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 покращився в наступних 3 аспектах:

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

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

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

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

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

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

• Упаковка: цей метод оптимізує операції, упаковуючи сусідні менші елементи в більші елементи у лексикографічному порядку. Оператор Pack орієнтований на блоки розміром 2κ і об'єднує їх у високовимірному просторі.