Аналіз принципів 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 розмір області, що використовується, має бути більшим за ступінь многочлена; під час зобов'язання Merkle tree в STARKs необхідно виконати кодування Ріда-Соломона, розмір області, що використовується, має бути більшим за розмір, що розширюється в результаті кодування.

Binius запропонував інноваційне рішення, яке окремо обробляє ці дві проблеми та реалізує їх за допомогою двох різних способів представлення однакових даних: по-перше, використовуючи багатозмінні (зокрема, багатолінійні) поліноми замість однозмінних поліномів, представляючи всю обчислювальну траєкторію через їх значення в "гиперкубах"; по-друге, оскільки довжина кожного виміру гиперкуба становить 2, то неможливо виконати стандартне розширення Ріда-Соломона, як у STARKs, але можна розглядати гиперкуб як квадрат, базуючись на якому здійснити розширення Ріда-Соломона. Цей метод значно підвищує ефективність кодування та обчислювальну продуктивність, забезпечуючи при цьому безпеку.

2. Аналіз принципу

Поточна більшість систем SNARKs зазвичай складається з двох частин:

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

Як показано на рисунку 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 може продовжувати обробку, дозволяючи розширення на будь-яке значення добутку.

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

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

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

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

• Упаковка：