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

1 Вступ

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

Як видно з таблиці 1, СТАРКИ першого покоління мають розмір 252 біти, СТАРКИ другого покоління – 64 біти, а СТАРКИ третього покоління – 32 біти. На противагу цьому, двійкова область дозволяє проводити операції прямого вирівнювання бітів і є компактною та ефективною в кодуванні без втрати простору, тобто STARK 4-го покоління.

Таблиця 1: Шляхи еволюції STARKS

| Особливість | 1 покоління STARK | 2 покоління STARK | 3 покоління STARK | 4 покоління STARKs(Binius) | |------|-------------|-------------|-------------|---------------------| | Бітова ширина коду | 252-розрядний | 64-розрядна версія | 32 біт | 1 біт | | Представницька система | СтаркВер | Плонки2 | Ведмідь | Біній |

У порівнянні з кінцевими доменами, відкритими в останні роки, такими як Goldilocks, BabyBear і Mersenne31, вивчення бінарних доменів можна простежити до 80-х років минулого століття. В даний час двійкові домени широко використовуються в криптографії, типові приклади включають:

• Advanced Encryption Standard (AES), заснований на доменах F28;

• Galois повідомлення аутентифікаційний код ( GMAC ), оснований на полі F2128;

• QR-код з використанням кодування Ріда-Соломона на основі F28;

• Оригінальні протоколи FRI і zk-STARK, а також хеш-функція Grøstl, що потрапила до фіналіста SHA-3, яка базується на домені F28 і є добре підходящим алгоритмом хешування для рекурсії.

При використанні невеликих доменів розширення доменних операцій стає все більш важливим для забезпечення безпеки. З іншого боку, двійковий домен, який використовується Binus, повинен повністю покладатися на розширення домену, щоб забезпечити його безпеку та фактичну доступність. Більшість многочленів, що беруть участь в розрахунках Провера, не потребують входу в розширену область, а повинні оперувати тільки під базовою областю, таким чином досягаючи високої ефективності в малих областях. Однак вибіркові перевірки точок і розрахунки FRI все одно повинні бути просвердлені в більшій зоні розширення, щоб забезпечити необхідну безпеку.

При побудові системи доведення на основі двійкових доменів виникають дві практичні проблеми: при розрахунку трасового представлення в СТАРКАХ розмір домену, що використовується, повинен бути більшим, ніж порядок многочлена; Коли дерево Меркла обіцяно в STARKs, його потрібно закодувати на мові Reed-Solomon, а розмір використовуваного домену повинен бути більшим, ніж розмір розширення кодування.

Бініус пропонує інноваційне рішення, яке розглядає ці дві проблеми окремо і робить це шляхом представлення одних і тих же даних двома різними способами: по-перше, використовуючи багатовимірні (зокрема, багатолінійні) многочлени замість одновимірних многочленів і представляючи всю обчислювальну траєкторію за її значенням на «гіперкубах»; По-друге, оскільки довжина кожного виміру гіперкуба дорівнює 2, неможливо виконати стандартне розширення Ріда-Соломона, як СТАРКа, але гіперкуб можна розглядати як квадрат на основі розширення Ріда-Соломона. Цей метод значно підвищує ефективність кодування та продуктивність обчислень, забезпечуючи при цьому безпеку.

2 Аналіз принципів

Побудова більшості сучасних систем СНАРК зазвичай складається з наступних двох частин:

• Інформаційно-теоретичне поліноміальне інтерактивне доведення оракула (PIOP) :P IOP як ядро системи доведення, перетворюючи обчислювальні співвідношення входів у перевірені поліноміальні рівняння. Різні протоколи PIOP дозволяють керівнику надсилати поліноми крок за кроком, взаємодіючи з валідатором, дозволяючи валідатору перевірити правильність обчислення, запитуючи результати оцінки невеликої кількості поліномів. Існуючі протоколи PIOP включають PLONK PIOP, Spartan PIP і HyperPlonk PIOP, всі з яких по-різному обробляють поліноміальні вирази, що впливає на продуктивність і ефективність всієї системи SNARK.

• Схема поліноміальних зобов'язань (PCS): Схема поліноміальних зобов'язань використовується для доказу того, чи є поліноміальне рівняння, породжене PIOP, істинним. PCS — це криптографічний інструмент, за допомогою якого дослідник може взяти на себе зобов'язання до певного многочлена, а потім перевірити результати оцінювання цього многочлена, приховуючи при цьому іншу інформацію про многочлен. Поширені поліноміальні схеми зобов'язань включають KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP) і Brakedown. Різні PCS мають різні сценарії продуктивності, безпеки та застосування.

Залежно від конкретних вимог, вибирайте різні PIOP і PCS, а також поєднуйте їх з відповідними скінченними полями або еліптичними кривими, можна побудувати системи доказів з різними атрибутами. Наприклад:

• Halo2: працює на базі PLONK PIOP у поєднанні з куленепробивними PCS і базується на кривих Pasta. Halo2 був розроблений з урахуванням масштабованості, а також з урахуванням видалення довіреного налаштування з протоколу ZCash.

• Plonky2: поєднує PLONK PIOP з FRI PCS і базується на домені Goldilocks. Plonky2 призначений для ефективної рекурсії. При проектуванні цих систем вибрані PIOP і PCS повинні відповідати скінченній області або еліптичній кривій, що використовуються для забезпечення правильності, продуктивності та безпеки системи. Вибір цих комбінацій не тільки впливає на розмір доказу та ефективність перевірки SNARK, але й визначає, чи зможе система досягти прозорості без потреби в надійних налаштуваннях, і чи може вона підтримувати розширені функції, такі як рекурсивні докази або агреговані докази.

Binius: HyperPlonk PIOP + Brakedown PCS + Binary Domain. Зокрема, Binius включає п'ять ключових технологій для досягнення його ефективності та безпеки. Перш за все, арифметика на основі веж двійкових полів становить основу її обчислень, в якій можна реалізувати спрощені операції в двійкових полях. По-друге, у своєму інтерактивному протоколі Oracle Proof Protocol (PIOP) Binius адаптував продукт HyperPlonk та перевірку перестановок, щоб забезпечити безпечну та ефективну перевірку узгодженості між змінними та їх перестановками. По-третє, протокол вводить новий аргумент мультилінійного зсуву для оптимізації ефективності перевірки багатолінійного зв'язку на невеликій області. По-четверте, Бініус використовує покращену версію аргументу пошуку Лассо, яка забезпечує гнучкість і надійну безпеку механізму пошуку. Нарешті, протокол використовує схему зобов'язань малого поля полінома (Small-Field PCS), що дозволяє йому реалізувати ефективну систему доведення на двійковій області та зменшити накладні витрати, які зазвичай пов'язані з великими доменами.

2.1 Скінченні поля: арифметика на основі веж двійкових полів

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

де «канонічний» означає унікальне та пряме представлення елемента в двійковій області. Наприклад, у найпростішому двійковому домені F2 будь-який k-бітовий рядок може бути відображений безпосередньо на k-бітний елемент двійкового домену. Це на відміну від поля простих чисел, яке не може забезпечити таке канонічне представлення в межах заданої позиції. Хоча 32-бітне поле простого числа може міститися в 32-розрядній системі, не кожен 32-бітовий рядок однозначно відповідає елементу домену, і двійкові поля мають зручність такого відображення один до одного. У простій області Fp поширені методи редукції включають редукцію Барретта, редукцію Монтгомері та спеціальні методи скорочення для конкретних скінченних полів, таких як Мерсенна-31 або Золотоволоски-64. У двійковій області F2k часто використовувані методи редукції включають спеціальну редукцію (наприклад, використовується в AES), редукцію Монтгомері (наприклад, використовується в POLYVAL) і рекурсивну редукцію (наприклад, Tower). У статті "Дослідження простору проектування реалізації ECC-апаратного забезпечення простого поля проти двійкового поля" вказується, що двійковий домен не потребує введення перенесення як у додаванні, так і в множенні, і що квадратична операція двійкового домену дуже ефективна, оскільки вона слідує за (X + Y )2 = Х2 + У 2.

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

Як показано на рисунку 1, 128-бітний рядок: цей рядок може бути інтерпретований різними способами в контексті двійкового домену. Він може розглядатися як унікальний елемент у 128-бітному двійковому домені, або він може бути вирішений як два 64-бітні баштові елементи, чотири 32-бітні баштові елементи, 16 8-бітних баштових елементів або 128 елементів домену F2. Гнучкість цього представлення не вимагає жодних обчислювальних витрат, лише набір побітових рядків, що є дуже цікавою та корисною властивістю. У той же час малі елементи домену можуть бути упаковані в більші доменні елементи без додаткових обчислювальних витрат. Протокол Binius використовує цю функцію для підвищення обчислювальної ефективності. Крім того, стаття "Про ефективну інверсію в полях вежі характеристики два" досліджує обчислювальну складність операцій множення, квадратного кільця та інверсії в n-бітній двійковій області, яка може бути розкладена на m-бітові субдомени.

2.2 PIOP: адаптована версія HyperPlonk Product та PermutationCheck------для бінарного поля

Дизайн PIOP в протоколі Binius запозичений у HyperPlonk і використовує серію механізмів перевірки ядра для перевірки правильності поліномів і багатовимірних множин. Ці основні тести включають:

1. GateCheck: Перевірте, чи конфіденційний свідок ω і публічний вхід x задовольняють відношення роботи схеми C(x, ω)=0, щоб забезпечити правильну роботу схеми.

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

• Обробка задачі ділення на нуль: HyperPlonk не може адекватно обробляти випадок ділення нуля, що призводить до неможливості стверджувати ненульову проблему U на гіперкубі; Binius обробляє це правильно, а ProductCheck від Binius продовжує обробляти навіть тоді, коли знаменник дорівнює нулю, дозволяючи узагальнювати довільні значення продукту.

• PermutationCheck: Ця функція недоступна в HyperPlonk; Binius підтримує перевірку перестановок між кількома стовпцями, що дозволяє Binius обробляти більш складні поліноміальні перестановки.

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