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

1 Вступ

Основною причиною низької ефективності STARK є те, що більшість чисел у фактичних програмах є відносно малими, такими як індекси у циклі 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 розмір області має бути більшим за ступінь багаточлена; під час зобов'язання дерева Меркла в STARKs необхідно виконати кодування Ріда-Соломона, розмір області має бути більшим за розмір після розширення коду.

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

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 у своєму інтерактивному 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-бітні підполя ).

( 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: Аналіз принципів Бініуса Старка та оптимізаційне мислення

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

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

• Упаковка: цей метод через