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

1 Вступ

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

Перший покоління 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, розмір області має бути більшим за ступінь многочлена; під час зобов'язання Меркле-дерева в 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 у своєму інтерактивному протоколі доведення 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 елементів поля висотою 8 біт або 128 елементів поля F2. Гнучкість цього подання не вимагає жодних обчислювальних витрат, це лише зміна типу (typecast) бітового рядка, що є дуже цікавою та корисною властивістю. Крім того, елементи малого поля можуть бути упаковані в елементи більшого поля без додаткових обчислювальних витрат. Протокол Binius використовує цю властивість для підвищення обчислювальної ефективності. Крім того, стаття "On Efficient Inversion in Tower Fields of Characteristic Two" досліджує обчислювальну складність множення, піднесення до квадрату та обчислення обернених елементів у 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 вдосконалив у трьох аспектах:

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

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

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

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

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

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

• Упаковка: цей метод оптимізує операції, упаковуючи менші елементи, які знаходяться поруч у словниковому порядку, в більші елементи. Оператор Pack призначений для блокових операцій розміром 2κ і обробляє їх.