Аналіз принципів 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 запропонував інноваційне рішення для вирішення цих двох проблем, представляючи однакові дані двома різними способами: по-перше, використовуючи багатозмінні (зокрема, багатолінійні) многочлени замість однозмінних многочленів, представляючи всю обчислювальну траєкторію за їх значеннями на "гіперкубах" (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 включає п'ять ключових технологій для досягнення своєї ефективності та безпеки. По-перше, на основі баштових двійкових полів арифметика стала основою його обчислень, що дозволяє виконувати спрощені обчислення в двійковому полі. По-друге, Binius у своєму інтерактивному протоколі доказів Oracle (PIOP) адаптував HyperPlonk для перевірки добутків та перестановок, що забезпечує безпечну та ефективну перевірку узгодженості між змінними та їх перестановками. По-третє, протокол вводить новий доказ мульти-лінійного зсуву, оптимізуючи ефективність перевірки мульти-лінійних зв'язків у малих полях. По-четверте, 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 + Y2.

! Дослідження Bitlayer: Аналіз принципів Бініуса Старка та оптимізаційне мислення

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

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