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

1 Вступ

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

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

Таблиця 1: Шлях похідних STARKs

| Алгебра | Ширина шини | Домен | |------|------|------| | Перше покоління | 252bit | Поле простих чисел | | 2-е покоління | 64bit | Goldilocks | | 3-є покоління | 32 біт | просторове поле | | 4-те покоління | 1 біт | двійкова область |

В порівнянні з недавніми дослідженнями обмежених полів, такими як Goldilocks, BabyBear, Mersenne31, що з'явилися в останні роки, дослідження двійкових полів можна віднести до 80-х років минулого століття. На сьогоднішній день двійкові поля широко застосовуються в криптографії, типові приклади включають:

• Стандарт високої криптографії (AES), заснований на полі F28;

• Galois повідомлення автентифікації ( GMAC ), на основі поля F2128;

• QR-код, використовуючи кодування Ріда-Соломона на основі F28;

• Первоначальні протоколи FRI та zk-STARK, а також хеш-функція Grøstl, яка потрапила до фіналу SHA-3, заснована на полі F28, є дуже підходящою для рекурсії хеш-алгоритмом.

Коли використовуються менші поля, операція розширення поля стає все більш важливою для забезпечення безпеки. А двійкове поле, яке використовує Binius, повністю покладається на розширення поля для забезпечення його безпеки та практичної придатності. Більшість поліномів, що беруть участь у обчисленнях Prover, не потребують переходу в розширене поле, а лише працюють у базовому полі, що забезпечує високу ефективність у малих полях. Однак випадкові перевірки точок і обчислення FRI все ще потребують заглиблення в більше розширене поле для забезпечення необхідного рівня безпеки.

При побудові системи доказів на основі бінарних полів існує дві практичні проблеми: під час обчислення відстеження в 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.

• Поліноміальні зобов'язання ( Поліноміальна схема зобов'язань, 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 + Binary Domain. Зокрема, Binius включає п'ять ключових технологій для досягнення його ефективності та безпеки. По-перше, арифметика на основі баштового двійкового домену (towers двійкового fields) становить основу його обчислення, що дозволяє реалізувати спрощені операції в двійковій області. По-друге, у своєму інтерактивному протоколі Oracle proof (PIOP) Binius адаптує продукт HyperPlonk та перевірку перестановок, щоб забезпечити безпечну та ефективну перевірку узгодженості між змінними та їх перестановками. По-третє, протокол вводить новий аргумент мультилінійного зсуву для оптимізації ефективності перевірки багатолінійного зв'язку на невеликій області. По-четверте, Бініус використовує покращену версію аргументу пошуку Лассо, яка забезпечує гнучкість і надійну безпеку механізму пошуку. Нарешті, протокол використовує схему зобов'язань малого поля полінома 019283746574839201Small-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-бітні підобласті (.

! [Двійковий домен вежі])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 покращився в трьох наступних аспектах:

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

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

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

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

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

У протоколі Binius конструкція та обробка віртуальних поліномів є ключовими.