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

Як показано на малюнку 1, рядок довжиною 128 біт: цей рядок можна інтерпретувати кількома способами в контексті бінарної області. Його можна розглядати як унікальний елемент у 128-бітовій бінарній області або розглядати як два елементи області висоти 64 біти, чотири елементи області висоти 32 біти, 16 елементів області висоти 8 біт або 128 елементів області F2. Ця гнучкість представлення не вимагає жодних обчислювальних витрат, це просто перетворення типу (typecast) рядка бітів, що є дуже цікавою та корисною властивістю. Водночас, малі елементи області можуть бути упаковані в більші елементи області без додаткових обчислювальних витрат. Протокол Binius використовує цю особливість для підвищення обчислювальної ефективності. Крім того, стаття "On Efficient Inversion in Tower Fields of Characteristic Two" досліджує обчислювальну складність множення, піднесення до квадрату та обернення в n-бітових областях висоти бінарної області (які можуть бути розкладені на m-бітові підобласті).

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

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

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

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

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

• Упаковка：