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

1 Вступ

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

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

Таблиця 1: Шлях похідних STARKs

| Покоління | Ширина кодування | Представницька система | |------|----------|----------| | 1-е покоління | 252 біт | StarkWare STARKs | | Друге покоління | 64 біт | Plonky2 | | Третє покоління | 32 біти | BabyBear | | 4-те покоління | 1 біт | 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, розмір поля, що використовується, має бути більшим за степінь полінома; під час зобов'язання Меркле-дерева в 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 + двійкове поле. Конкретно, Binius включає п'ять ключових технологій для досягнення своєї ефективності та безпеки. По-перше, на основі веж двійкових полів (towers of binary fields) арифметика складає основу його обчислень, що дозволяє спростити обчислення в двійкових полях. По-друге, Binius у своєму інтерактивному Oracle-доказі (PIOP) адаптував перевірку добутку та перестановки HyperPlonk, що забезпечує безпечну та ефективну перевірку узгодженості між змінними та їх перестановками. По-третє, протокол вводить новий багатовимірний зсувний доказ, оптимізуючи ефективність перевірки багатовимірних відносин у малих полях. По-четверте, 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 елементів поля довжиною 8 біт або 128 елементів поля F2. Ця гнучкість представлення не потребує жодних обчислювальних витрат, це просто перетворення типу рядка бітів (typecast), що є дуже цікавою та корисною властивістю. Одночасно, елементи малих полів можуть бути упаковані в більші елементи полів без додаткових обчислювальних витрат. Протокол Binius використовує цю особливість для підвищення обчислювальної ефективності. Крім того, стаття "On Efficient Inversion in Tower Fields of Characteristic Two" досліджує обчислювальну складність множення, піднесення до квадрату та обернення у n-бітному вежовому бінарному полі (, що може бути розкладене на m-бітні підполя ).

Рисунок 1: Баштове двійкове поле

( 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: новий багаторазовий аргумент зсуву ------ застосовано