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

1. Вступ

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

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

| Алгебра | Ширина кодування | Типове впровадження | |------|----------|----------| | 1-е покоління | 252 біти | StarkWare | | 2-е покоління | 64bit | Plonky2 | | 3-є покоління | 32bit | Plonky3 | | 4-е покоління | 1 біт | Binius |

Порівняно з такими нещодавніми дослідженнями обмежених полів, як Goldilocks, BabyBear, Mersenne31, дослідження двійкових полів можна простежити до 80-х років минулого століття. Наразі двійкові поля вже широко використовуються в криптографії,典型例子包括:

• Стандарт високої криптографії (AES), оснований на полі F2^8
• Galois повідомлення автентифікації ( GMAC ), на основі F2^128 області
• QR-код, використовуючи кодування Ріда-Соломона на основі F2^8
• Початкові протоколи FRI та zk-STARK, а також хеш-функція Grøstl, яка потрапила до фіналу SHA-3, заснована на полі F2^8, є дуже підходящим рекурсивним хеш-алгоритмом.

Коли використовуються менші поля, операція розширення полів стає дедалі важливішою для забезпечення безпеки. А бінарне поле, яке використовує 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 акцент робився на масштабованість, а також на усунення 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.

Термін "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 = X^2 + Y^2.

Як показано на малюнку 1, 128-бітний рядок: цей рядок може бути інтерпретований кількома способами в контексті бінарної області. Його можна розглядати як унікальний елемент у 128-бітній бінарній області або розглядати як два 64-бітних елементи областей веж, чотири 32-бітних елементи областей веж, 16 8-бітних елементів областей або 128 елементів області F2. Ця гнучкість представлення не потребує жодних обчислювальних витрат, лише перетворення типу рядка бітів (typecast), що є дуже цікавою та корисною властивістю. У той же час, елементи малих областей можуть бути упаковані в більш великі елементи областей без додаткових обчислювальних витрат. Протокол Binius використовує цю особливість для підвищення обчислювальної ефективності. Крім того, стаття «Про ефективне обернення у вежах полів характеристик два» досліджує обчислювальну складність операцій множення, піднесення до квадрата та обернення в 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 вдосконалив наступні 3 аспекти:

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

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

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

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

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

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