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

1 Вступ

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

Перший покоління 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 акцент робився на масштабованості та усуненні trusted setup у протоколі ZCash.

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

Binius: HyperPlonk PIOP + Brakedown PCS + двійкове поле. Конкретно, Binius включає п'ять ключових технологій для забезпечення своєї ефективності та безпеки. По-перше, арифметика на основі веж двійкових полів є основою його обчислень, що дозволяє виконувати спрощені обчислення у двійковому полі. По-друге, 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 + Y2.

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

Як показано на малюнку 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：новий multilinear shift аргумент------придатний для boolean hypercube

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

• Упаковка: цей метод оптимізує операцію, упаковуючи сусідні елементи з меншими значеннями у словниковому порядку в більші елементи. Оператор Pack націлений на блоки розміром 2κ і об'єднує їх в один елемент у високорозмірному просторі. Через багатолінійне розширення.