Аналіз принципів 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, неможливо провести стандартне розширення Ріда-Соломона, як це робиться у STARKs, але можна розглядати гіперкуб як квадрат (square), на основі якого проводити розширення Ріда-Соломона. Цей метод забезпечує безпеку та значно підвищує ефективність кодування та обчислювальні характеристики.

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

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

• Інформаційно-теоретичне поліно взаємодії Oracle Proof (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 акцент зроблено на масштабованість та усунення trusted setup з протоколу 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 восьмибітних елементів вежі або 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 конструкція та обробка віртуальних поліномів є однією з ключових технологій, яка здатна ефективно генерувати та маніпулювати поліномами, що походять з вхідних ручок або інших віртуальних поліномів. Нижче наведено два ключових методи:

• Упаковка: цей метод шляхом