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

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

• Інформаційно-теоретичне поліно-інтерактивне 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 акцент робився на масштабованості та усуненні довіреного налаштування в протоколі 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 + Y 2.

Як показано на рисунку 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κ і обробляє їх