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

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

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 конструкція та обробка віртуальних多项式 є однією з ключових технологій, яка може ефективно генерувати та оперувати多项式, що походять з вхідних дескрипторів або інших віртуальних多项式. Ось два ключових методи:

• Упаковка: цей метод шляхом об'єднання сусідніх менших елементів у словниковому порядку