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

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

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

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

• Інформаційно-теоретичні поліноomialні інтерактивні oracle докази (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP як основа системи доказів перетворює вхідні обчислювальні відношення у поліноomialні рівняння, які можна перевірити. Різні PIOP протоколи через взаємодію з перевіряючим дозволяють доказувачу поетапно надсилати поліноomialи, що дозволяє перевіряючому перевіряти правильність обчислень, запитуючи лише невелику кількість оцінок поліноomialів. Існуючі PIOP протоколи включають: PLONK PIOP, Spartan PIOP і HyperPlonk PIOP тощо, які по-різному обробляють поліноomialні вирази, що впливає на загальну продуктивність і ефективність системи 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.

Термін "канонічний" відноситься до унікального та безпосереднього способу подання елементів у бінарному полі. Наприклад, у найпростіше бінарному полі F2 будь-який k-бітний рядок може бути безпосередньо відображений на k-бітний елемент бінарного поля. Це відрізняється від просторових полів, які не можуть забезпечити таке нормативне подання в заданій кількості біт. Хоча 32-бітне просторове поле може бути вміщене в 32 біти, не кожен 32-бітний рядок може унікально відповідати елементу поля, тоді як бінарне поле має цю зручність однозначного відображення. У просторовому полі Fp звичайні методи редукції включають редукцію Барретта, редукцію Монтгомері, а також спеціальні методи редукції для певних скінченних полів, таких як Mersenne-31 або Goldilocks-64. У бінарному полі F2k звичайні методи редукції включають спеціальну редукцію (, як у AES, редукцію Монтгомері ), як у POLYVAL, і рекурсивну редукцію (, як у Tower ). У статті "Дослідження простору дизайну ECC-апаратних реалізацій простого поля та бінарного поля" зазначається, що в бінарному полі під час виконання операцій додавання та множення не потрібно вводити перенесення, і квадратна операція у бінарному полі є дуже ефективною, оскільки вона слідує спрощеному правилу (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 Research: Аналіз принципів Binius STARKs та їх оптимізаційні роздуми])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, але й закладають основу для майбутніх систем доказів, основаних на бінарних полях.

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

) 2.3 PIOP: новий багатолінійний зсув аргумент------підходить для булевого гіперкуба

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

• Packing: Цей метод упакує менші елементи, що знаходяться поряд у лексикографічному порядку, в більші.