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

1 Вступ

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

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

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

| Покоління | Ширина | Особливості | |------|------|------| | 1-ше покоління | 252 біти | Велике поле, велике витрачання простору | | 2-ге покоління | 64 біт | середнє поле, велике витрачання простору | | 3-е покоління | 32 біт | Малий простір, все ще є невикористані площі | | 4-е покоління | 1 біт | двійкова область, без витрат простору |

На відміну від 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 як основа системи доказів перетворює вхідні обчислювальні відношення в перевіряємi поліноміальні рівності. Різні протоколи PIOP, взаємодіючи з перевіряючим, дозволяють доводячому поступово надсилати поліноми, що дає змогу перевіряючому верифікувати правильність обчислення, запитуючи результати оцінки невеликої кількості поліномів. Існуючі протоколи PIOP включають: PLONK PIOP, Spartan PIOP та HyperPlonk PIOP, які по-різному обробляють поліноміальні вирази, що впливає на продуктивність та ефективність всієї системи SNARK.

• Поліноміальні зобов'язання ( Поліноміальна схема зобов'язань, PCS ): Поліноміальна схема зобов'язань використовується для доведення того, чи є поліноміальне рівняння, згенероване PIOP, істинним. PCS є криптографічним інструментом, за допомогою якого доказувач може зобов'язатися певним поліномом і пізніше перевірити результати оцінки цього полінома, приховуючи при цьому іншу інформацію про поліном. Загальноприйняті поліноміальні схеми зобов'язань включають KZG, Bulletproofs, FRI ( Швидкий Рід-Соломон 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 + Binary Domain. Зокрема, Binius включає п'ять ключових технологій для досягнення його ефективності та безпеки. По-перше, арифметика на основі баштового двійкового домену (towers двійкового fields) становить основу його обчислення, що дозволяє реалізувати спрощені операції в двійковій області. По-друге, у своєму інтерактивному протоколі Oracle proof (PIOP) Binius адаптує продукт HyperPlonk та перевірку перестановок, щоб забезпечити безпечну та ефективну перевірку узгодженості між змінними та їх перестановками. По-третє, протокол вводить новий аргумент мультилінійного зсуву для оптимізації ефективності перевірки багатолінійного зв'язку на невеликій області. По-четверте, Бініус використовує покращену версію аргументу пошуку Лассо, яка забезпечує гнучкість і надійну безпеку механізму пошуку. Нарешті, протокол використовує схему зобов'язань малого поля полінома 019283746574839201Small-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-бітні підполя ).

( 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, але й для невизначених