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

1 Вступ

На відміну від SNARK-ів, що базуються на еліптичних кривих, STARK-и можуть розглядатися як SNARK-и на основі хешування. Однією з основних причин низької ефективності STARK-ів є те, що більшість чисел у реальних програмах є дуже маленькими, такими як індекси в циклах 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 зазвичай складається з двох частин:

• Інформаційна теорія поліноміальних інтерактивних 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 акцент робиться на масштабованості та усуненні довіреного налаштування в протоколі 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 використовує цю особливість для підвищення обчислювальної ефективності. Крім того, у статті "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, але й закладають основу для майбутніх систем доказів на основі бінарних полів.

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

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

• Упаковка: цей метод працює шляхом взяття менших сусідніх позицій у словниковому порядку