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

1 Вступ

Основною причиною низької ефективності STARKs є те, що більшість чисел у реальних програмах є маленькими, такими як індекси у циклах for, логічні значення, лічильники тощо. Однак, щоб забезпечити безпеку доказів на основі дерев Меркла, під час розширення даних за допомогою кодування Ріда-Соломона багато додаткових надмірних значень займають весь простір, навіть якщо самі початкові значення дуже маленькі. Щоб вирішити цю проблему, зменшення розміру поля стало ключовою стратегією.

Як показано в таблиці 1, ширина кодування STARKs першого покоління становить 252 біти, ширина кодування STARKs другого покоління становить 64 біти, ширина кодування STARKs третього покоління становить 32 біти, але 32-бітна ширина кодування все ще має величезні втрати простору. У порівнянні з цим, бінарна область дозволяє безпосередньо виконувати операції з бітами, кодування компактне та ефективне без будь-яких втрат простору, тобто STARKs четвертого покоління.

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

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 спроектовано з акцентом на масштабованість і усунення 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 + Y2.

Як показано на малюнку 1, 128-бітний рядок: цей рядок можна інтерпретувати кількома способами в контексті бінарної області. Його можна розглядати як унікальний елемент у 128-бітній бінарній області або розглядати як два елементи 64-бітної вежі, чотири елементи 32-бітної вежі, 16 елементів 8-бітної вежі або 128 елементів області F2. Ця гнучкість представлення не вимагає жодних обчислювальних витрат, лише перетворення типу рядка бітів (typecast), що є дуже цікавою та корисною властивістю. Водночас, малі елементи області можуть бути упаковані в більші елементи області без додаткових обчислювальних витрат. Протокол Binius використовує цю особливість для підвищення обчислювальної ефективності. Крім того, стаття "On Efficient Inversion in Tower Fields of Characteristic Two" досліджує обчислювальну складність множення, піднесення до квадрату та обернення в n-бітній вежі бінарної області (, розкладеної на m-бітні підобласті ).

Рисунок 1: Вежа бінарних полів

( 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 вдосконалив наступні 3 аспекти:

• Оптимізація ProductCheck: в HyperPlonk ProductCheck вимагає, щоб знаменник U був ненульовим на всьому гіперкубі, і щоб добуток дорівнював певному значенню; Binius спростив цей процес перевірки, спеціалізуючи це значення на 1, що знижує обчислювальну складність.

• Обробка проблеми ділення на нуль: HyperPlonk не зміг належним чином обробити випадки ділення на нуль, що призвело до неможливості стверджувати, що U є ненульовим на гіперкубі; Binius правильно вирішив цю проблему, навіть у випадках, коли знаменник дорівнює нулю, ProductCheck Binius може продовжити обробку, дозволяючи розширення до будь-якого значення добутку.

• Перевірка перестановки між стовпцями: HyperPlonk не має цієї функції; Binius підтримує перевірку перестановки між кількома стовпцями, що дозволяє Binius обробляти більш складні ситуації перестановки багаторазових поліномів.

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

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