Аналіз принципів 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, розмір області має бути більшим за ступінь多项式; під час зобов'язання Merkle tree в STARKs необхідно виконати кодування Ріда-Соломона, розмір області має бути більшим за розмір після розширення коду.

Binius запропонував інноваційне рішення, яке окремо вирішує ці дві проблеми, і реалізує їх через два різних способи представлення однакових даних: по-перше, використовуючи багатозмінний (, а саме багатолінійний ) многочлен замість однозмінного многочлена, шляхом його значень на "гіперкубах" (hypercubes) для представлення всієї обчислювальної траєкторії; по-друге, оскільки довжина кожного виміру гіперкуба дорівнює 2, то не можна виконати стандартне розширення Reed-Solomon, як це роблять STARKs, але можна розглядати гіперкуб як квадрат (square), на основі якого виконати розширення Reed-Solomon. Цей підхід забезпечує безпеку, одночасно значно підвищуючи ефективність кодування та обчислювальну продуктивність.

2. Аналіз принципу

Поточна більшість систем SNARKs зазвичай складається з двох частин:

• Інформаційно-теоретичні поліно-масивні інтерактивні оракульні докази ( 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 у своєму інтерактивному Oracle доказовому протоколі (PIOP) адаптував HyperPlonk перевірки добутків та перестановок, забезпечуючи безпечну та ефективну перевірку узгодженості між змінними та їх перестановками. По-третє, протокол вводить новий мульти-лінійний зсувний доказ, оптимізуючи ефективність перевірки мульти-лінійних зв'язків у малих полях. По-четверте, 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-бітні підполя (.

! [Дослідження 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κ і об'єднує їх у великі.