Аналіз принципів 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 зазвичай складається з двох частин:

• Інформаційно-теоретичні поліноміальні інтерактивні oracle докази ( 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 було спроектовано з акцентом на масштабованість та усунення довірчої установки з протоколу 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-розрядні підобласті (.

! [Дослідження Bitlayer: Аналіз принципів Бініуса Старка та оптимізаційне мислення])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(

) 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κ і об'єднує їх у високі виміри.