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

1 Вступ

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

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

| Час | STARKs | Ширина кодування | |------|--------|----------| | 2018 | Перше покоління | 252bit | | 2021 | 2-е покоління | 64bit | | 2022 | Третє покоління | 32bit | | 2023 | Четверте покоління | 1bit |

Таблиця 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, розмір використаного поля має бути більшим за ступінь полінома; під час зобов'язання Меркле-дерева в STARKs необхідно виконати кодування Ріда-Соломона, розмір використаного поля має бути більшим за розмір, отриманий після розширення коду.

Binius запропонував інноваційне рішення, яке окремо вирішує ці дві проблеми, і реалізує їх шляхом представлення однакових даних двома різними способами: по-перше, використовуючи багатозмінний (, а саме, багатолінійний )многочлен замість однозмінного многочлена, представляючи всю обчислювальну траєкторію через його значення на "гиперкубах" (hypercubes); по-друге, оскільки довжина кожного виміру гиперкуба дорівнює 2, неможливо проводити стандартне розширення Ріда-Соломона, як у STARKs, але можна розглядати гиперкуб як квадрат (square), на основі якого проводити розширення Ріда-Соломона. Цей метод, забезпечуючи безпеку, значно підвищує ефективність кодування та обчислювальну продуктивність.

2 Принципи解析

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

• Інформаційно-теоретичні полігональні інтерактивні Oracle-докази (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP як основа системи доказів перетворює вхідні обчислювальні відношення на перевіряємi полігональні рівняння. Різні протоколи 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 у своєму інтерактивному 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-бітні підполя (.

! [Двійковий домен вежі])https://img-cdn.gateio.im/social/moments-a5d031be4711f29ef910057f444a118(

Рисунок 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: новий багатолінійний зсувний аргумент------придатний для булевого гіперкутника

У протоколі Binius побудова та обробка віртуальних багаторазових поліномів є важливою