Аналіз принципів 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 зазвичай складається з двох частин:

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

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

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

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

• Упаковка: цей метод полягає в тому, що