1. Вступ

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

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

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

У порівнянні з кінцевими полями, такими як Золотоволоска, BabyBear і Mersenne31, які останнім часом привернули увагу, бінарні польові дослідження датуються 1980-ми роками. Сьогодні двійкові поля широко використовуються в криптографії, яскравими прикладами яких є:

• Стандарт шифрування AES (Advanced Encryption Standard), заснований на
• 𝐹28
• поле;
• Код автентифікації повідомлення Галуа (GMAC), заснований на
• Ф2128
• поле;
• QR-коди, що використовують кодування Ріда-Соломона на основі
• 𝐹28
• поле;
• Оригінальні протоколи FRI та zk-STARK, а також хеш-функція Grøstl, фіналіст в конкурсі SHA-3, який базується на
• 𝐹28
• поле і добре підходить для рекурсивних хеш-алгоритмів.

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

При побудові системи доведення на основі бінарних полів існують дві практичні проблеми: по-перше, розмір поля, що використовується для представлення сліду в STARKs, повинен бути більшим, ніж степінь полінома. По-друге, розмір поля, яке використовується для зобов'язання дерева Меркля в STARKs, повинен бути більшим, ніж розмір після розширення кодування Ріда-Соломона.

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

2. Принципи Binius

Будівництво більшості сучасних систем SNARK зазвичай складається з наступних двох компонентів:

• Інформаційно-теоретичне інтерактивне доказ оракулу поліномів (PIOP): Як ядро системи доказу, PIOP перетворює обчислювальні відносини з вводу в перевірні поліноміальні рівняння. Різні протоколи PIOP дозволяють доведу відсилати поліноми інкрементально через взаємодії з перевірювачем. Це дозволяє перевірювачу підтвердити правильність обчислення шляхом запиту лише невеликої кількості оцінок поліномів. Різні протоколи PIOP, такі як PLONK PIOP, Spartan PIOP і HyperPlonk PIOP, різними чином обробляють поліноміальні вирази, що впливає на продуктивність та ефективність загальної системи SNARK.
• Схема комітменту полінома (PCS): PCS - це криптографічний інструмент, який використовується для доведення правильності поліноміальних рівнянь, створених PIOP. Вона дозволяє доведенцю зобов'язатися до полінома та перевіряти його оцінки, не розкриваючи додаткової інформації про поліном. Загальні схеми PCS включають KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP) та Brakedown, кожна з яких пропонує відмінні характеристики продуктивності, гарантії безпеки та застосовні сценарії.

Вибираючи різні схеми PIOPs та PCS, і поєднуючи їх з відповідними скінченними полями або еліптичними кривими, можна побудувати системи доведення з різними властивостями. Наприклад:

• Halo2: Поєднує PLONK PIOP з куленепробивними PCS і працює на кривій Pasta. Halo2 розроблений з урахуванням масштабованості та усуває довірені налаштування, які раніше використовувалися в протоколі ZCash.
• Plonky2: поєднує PLONK PIOP з FRI PCS та базується на полі Goldilocks. Plonky2 оптимізований для ефективної рекурсії.

При проектуванні цих систем велике значення має сумісність між обраними PIOP, PCS та скінченним полем або еліптичною кривою для забезпечення коректності, продуктивності та безпеки. Ці комбінації впливають на розмір SNARK-доказу, ефективність перевірки та визначають, чи може система досягнути прозорості без довіреної настройки, а також підтримувати передові функції, такі як рекурсивні докази або агрегація доказів.

Binius поєднує HyperPlonk PIOP з Brakedown PCS та працює в двійковому полі. Конкретно, Binius включає п'ять ключових технологій, щоб досягти як ефективності, так і безпеки:

1. Арифметика на основі веж бінарних полів: це становить обчислювальну основу Binius, що дозволяє спрощені операції в межах бінарного поля.
2. Перевірки продукту та перестановки HyperPlonk: Binius адаптує перевірки продукту та перестановки HyperPlonk у своєму PIOP, щоб забезпечити безпеку та ефективність узгодженості між змінними та їх перестановками.
3. Новий аргумент мультілінійного зсуву: Ця оптимізація поліпшує перевірку мультілінійних залежностей в малих полях, підвищуючи загальну ефективність.
4. Покращений аргумент пошуку Lasso: протокол включає більш гнучкий та безпечний механізм пошуку з цим вдосконаленим аргументом.
5. Схема зобов'язання до малого поля поліномів (PCS): Binius використовує PCS, спеціально призначену для малих полів, що зменшує накладні витрати, що зазвичай пов'язані з більшими полями, та дозволяє ефективну систему доведення в бінарному полі.

Ці інновації дозволяють Binius пропонувати компактну, високопродуктивну систему SNARK, оптимізовану для бінарних полів з відтриманням надійної безпеки та масштабованості.

2.1 Кінцеві поля: арифметика на основі веж бінарних полів

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

Термін "канонічний" відноситься до унікального та прямого представлення елементів у бінарному полі. Наприклад, у найпростішому бінарному полі $\mathbb{F}2

, анік-бітстрінґканбедіректлымаппедтоак-бітбинарифіельделемент. Цейдифферсфромпримефіельдконфігураційнумберофбітс. Альтхоугха32-бітпримефіельдканфітвітхін32бітс, нотеверы32-бітстрінґкануніквуелыcorrespondspondтоафіелделемент, деереасбинарифіельдспровідетьсятілонемаппінг. Інпримефіельдс

\mathbb{F}_p$, у загальних методах зменшення зустрічаються методи Барретта, Монтгомері та спеціалізовані методи зменшення для певних кінцевих полів, таких як Mersenne-31 або Goldilocks-64. У двійкових полях $\mathbb{F}{2^k}$, загальними методами зменшення є спеціальне зменшення (як у AES), метод Монтгомері (як використовується в POLYVAL) та рекурсивне зменшення (як використовується в Tower-полях). Стаття Дослідження простору проектування реалізацій Prime Field та Binary Field ECC-апаратнихзауважте, що бінарні поля не потребують перенесення в додаванні або множенні, а піднесення до квадрата в бінарних полях вельми ефективне завдяки правилу спрощення

(𝑋+𝑌)2=𝑋2+𝑌2

.

Рисунок 1. Вежі Бінарного Поля

Як показано на рисунку 1, 128-бітний рядок можна тлумачити декількома способами в контексті двійкового поля. Він може бути розглянутий як унікальний елемент у 128-бітному двійковому полі, або його можна розібрати на два елементи поля вежі з 64 бітами, чотири елементи поля вежі з 32 бітами, шістнадцять елементів поля вежі з 8 бітами або 128 елементів поля вежі.

𝐹2

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

𝑛

-бітова вежа двійкових полів (розкладна на

𝑚

-бітні підполя).

2.2 PIOP: Адаптований продукт HyperPlonk та перевірка перестановки - підходить для бінарних полів

Дизайн PIOP в протоколі Binius бере натхнення від HyperPlonk та включає ряд основних перевірок для перевірки правильності поліномів та багатозначних множин. Ці перевірки є необхідними для забезпечення цілісності обчислень у системі доказів, особливо при роботі з двійковими полями. Ключові перевірки включають:

1. gateCheck: Забезпечує, що приватний свідок
2. 𝜔
3. і публічного введення
4. 𝑥
5. задовольняють відношення роботи схеми
6. 𝐶(𝑥,𝜔)=0
7. , перевірка правильного виконання схеми.
8. PermutationCheck: Перевіряє, що результати оцінки двох багатозмінних поліномів
9. 𝑓
10. і
11. 𝑔
12. на булевому гіперкубі утворюють перестановочний зв'язок
13. 𝑓(𝑥)=𝑓(𝜋(𝑥))
14. , забезпечуючи консистентність між поліноміальними змінними.
15. LookupCheck: Перевіряє, чи оцінка полінома знаходиться в заданій таблиці пошуку, тобто
16. 𝑓(𝐵𝜇)⊆𝑇(𝐵𝜇)
17. , забезпечуючи, що певні значення потрапляють у визначений діапазон.
18. MultisetCheck: Підтверджує, чи два багатовимірні набори рівні, тобто ${(x{1,i},x{2,i})}{i \in H} = {(y{1,i},y{2,i})}{i \in H}$, забезпечуючи послідовність між різними множинами.
19. ProductCheck: Забезпечує, що оцінка раціонального полінома на булевому гіперкубі дорівнює заявленому значенню, тобто
20. ∏𝑥∈𝐻𝜇𝑓(𝑥)=𝑠
21. , підтверджуючи правильність многочленового добутку.
22. ZeroCheck: Перевіряє, чи багатовимірний поліном дорівнює нулю в будь-якій точці на булевому гіперкубі, тобто
23. ∏x∈Hμf(x)=0
24. для всіх
25. 𝑥∈𝐵𝜇
26. , забезпечуючи правильне розподіл нулів у поліномі.
27. SumCheck: Підтверджує, чи дорівнює сума оцінок мультіваріативного полінома заявленому значенню, тобто
28. ∑𝑥∈𝐻𝜇𝑓(𝑥)=𝑠
29. . Зводячи обчислення багатовимірних многочленів до одновимірного обчислення многочленів, це знижує обчислювальну складність верифікатора. SumCheck також дозволяє пакетування, яке будує лінійні комбінації з використанням випадкових чисел для пакетної обробки кількох екземплярів.
30. BatchCheck: Розширення SumCheck, яке перевіряє правильність кількох багатозмінних оцінок поліномів, збільшуючи ефективність протоколу.

Поки Бініус та ГіперПлонк мають кілька схожостей у своїх дизайнах протоколів, Бініус вводить наступні ключові покращення:

1. Оптимізація ProductCheck: у HyperPlonk, ProductCheck потребує знаменника
2. 𝑈
3. щоб було ненульовим по всьому гіперкубу і що добуток відповідає певному значенню. Binius спрощує цю перевірку, встановлюючи значення добутку рівним 1, зменшуючи загальну обчислювальну складність.
4. Обробка проблеми ділення на нуль: HyperPlonk не ефективно вирішує проблеми ділення на нуль, що ускладнює гарантію, що
5. 𝑈
6. залишається ненульовим над гіперкубом. Binius вирішує це, правильно обробляючи сценарії ділення на нуль, що дозволяє функціонувати ProductCheck навіть тоді, коли знаменник дорівнює нулю, що дозволяє розширення до довільних значень продукту.
7. Перевірка перестановки крос-колонки: HyperPlonk не підтримує перевірку перестановки крос-колонки. Binius вирішує це обмеження, вводячи підтримку перевірки перестановки крос-колонки, що дозволяє протоколу керувати більш складними поліноміальними перестановками в кількох колонках.

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

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

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

• Упаковка: Метод упаковки оптимізує обробку менших елементів, групуючи їх разом в більшу область. Зокрема, елементи, що розташовані поруч у лексикографічному порядку, упаковуються в більші блоки, зазвичай розміром
• 2𝜅
• . Шляхом використання мультилінійного розширення (MLE) упаковані елементи перетворюються на новий віртуальний поліном, який потім може бути оцінений та оброблений ефективно. Цей метод покращує продуктивність операцій на булевому гіперкубі шляхом перебудови функції
• 𝑡
• в обчислювально ефективну форму.
• Оператор зсуву: Оператор зсуву переставляє елементи в межах блоку, циклічно зсуваючи їх на підставі заданого зсуву
• 𝑜
• . Цей зсув застосовується до блоків розміру
• 2𝑏
• , забезпечуючи, що всі елементи в блоку рівномірно зсуваються відповідно до передбаченого зсуву. Цей оператор особливо корисний при роботі з віртуальними поліномами в просторах високої розмірності, оскільки його складність лінійно зростає з розміром блоку, що робить його ідеальною технікою для великих наборів даних або складних обчислень на булевому гіперкубі.

2.4 PIOP: Адаптований аргумент пошуку Lasso - застосовний до бінарних полів

Протокол Lasso в Binius пропонує високоефективний метод доведення того, що елементи у векторі

𝑎∈𝐹𝑚

містяться в заздалегідь визначеній таблиці

𝑡∈𝐹𝑛

. Цей аргумент пошуку вводить концепцію "Одномоментного пошуку" і добре підходить для схем зобов'язання багатовимірних поліномів. Ефективність Lasso підкреслена в двох основних аспектах:

• Ефективність доказів: При проведенні
• 𝑚
• пошуків у таблиці розміром
• 𝑛
• , доказувачу потрібно лише зобов'язатися
• 𝑚+𝑛
• невеликі елементи поля, розмір поля вибирається зі множини
• 0,…,𝑚
• У криптографічних схемах, що ґрунтуються на піднесенні до степеня, вартість доводу для довіреної сторони є
• 𝑂(𝑚+𝑛)
• операції груп (наприклад, додавання точок еліптичної кривої). Ця ефективність додається до вартості перевірки того, чи співпадає багатолінійний поліноміал, обчислений на булевому нескінченному просторі, з елементом таблиці.
• Відсутність зобов'язання стосовно великих таблиць : Якщо таблиця
• 𝑡
• Структурований, Lasso не потребує прямого зобов'язання до таблиці, що дозволяє обробляти дуже великі таблиці (наприклад,
• 2128
• або більше). Час виконання перевірки залежить лише від конкретних записів, до яких звертається в таблиці. Для будь-якого цілочисельного параметра
• 𝑐>1
• , основна вартість пов'язана з розміром підтвердження, який зростає, якщо
• 3⋅𝑐⋅𝑚+𝑐⋅𝑛1/𝑐
• елементи полів, які знаходяться. Ці елементи також є невеликими, взятими з множини
• 0,…,max𝑚,𝑛1/𝑐,𝑞−1
• , де
• 𝑞
• є найбільшим значенням у векторі
• 𝑎
• .

Протокол Lasso складається з трьох основних компонентів:

1. Віртуальна поліноміальна абстракція великих таблиць: Протокол Lasso поєднує віртуальні поліноми для забезпечення ефективного пошуку та операцій на великих таблицях, забезпечуючи масштабованість без погіршення продуктивності.
2. Small Table Lookup : В основі Lasso лежить пошук в невеликій таблиці, який перевіряє, чи є віртуальний поліном, обчислений на булевому гіперкубі, підмножиною оцінок іншого віртуального полінома. Цей процес схожий на виявлення пам'яті в автономному режимі і зводиться до задачі виявлення мультизету.
3. Багатомножинна перевірка: Протокол також включає віртуальний механізм для виконання багатомножинних перевірок, гарантуючи, що два набори елементів або збігаються, або відповідають заздалегідь визначеним умовам.

Протокол Binius адаптує Lasso для операцій з бінарними полями, припускаючи, що поточне поле є простим полем з великою характеристикою (набагато більшою, ніж довжина стовпця, що шукається). Бініус представляє мультиплікативну версію протоколу Лассо, вимагаючи від організатора та верифікатора збільшити операцію «лічильника пам'яті» протоколу не просто додаванням 1, а збільшенням за допомогою мультиплікативного генератора в двійковому полі. Однак ця мультиплікативна адаптація вносить додаткову складність: на відміну від адитивного приросту, мультиплікативний генератор не збільшується у всіх випадках, натомість має єдину орбіту на рівні 0, що може представляти вектор атаки. Щоб пом'якшити цю потенційну атаку, виконавець повинен взяти на себе зобов'язання щодо вектора лічильника зчитування, який є ненульовим скрізь, щоб забезпечити безпеку протоколу.

2.5 PCS: Адаптований PCS з гальмуванням — застосовується для невеликих полів

Основна ідея конструювання Binius PCS (Polynomial Commitment Scheme) - упаковка. У статті Binius пропонується дві схеми Brakedown PCS, які базуються на бінарних полях: одна інстанціюється за допомогою конкатенованих кодів, а інша використовує кодування на рівні блоку, яке підтримує самостійне використання кодів Ріда-Соломона. Друга схема Brakedown PCS спрощує процес доведення та верифікації, але породжує трохи більший розмір доведення, ніж перша; однак цей компроміс є вартий завдяки спрощенню та перевагам реалізації.

Зобов'язання многочлена Бініуса в основному використовує зобов'язання малого поля з оцінками в розширеному полі, універсальну конструкцію малого поля та кодування на рівні блоку з методами кодування Ріда-Соломона.

Зобов'язання з поліноміальним зобов'язанням з невеликим полем з розширеною оцінкою поля. У протоколі Binius зобов'язання з поліноміальним зобов'язанням виконуються над невеликим полем

K

, з оцінками, що відбуваються у розширеному полі

𝐿/𝐾

Ця техніка забезпечує те, що мультилінійний поліноміальний

𝑡(𝑋0,…,𝑋ℓ−1)

належить до домену

𝐾[𝑋0,…,𝑋ℓ−1]

, поки оцінювальні бали знаходяться в більшому полі

𝐿

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

Конструкція універсальної малих полів В цій конструкції визначаються ключові параметри, такі як поле

𝐾

, його розмір

ℓ

, та пов'язаний з ним лінійний блочний код

𝐶

, забезпечуючи при цьому розширене поле

𝐿

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

Кодування на блочному рівні з кодами Ріда-Соломона Для поліномів, визначених у малих полях, таких як $\mathbb{F}2

,theBiniusprotocolbusblock−levelencodingusingReed−Solomoncodes.Ця схема дозволяє ефективно зобов'язаннямалих−поліномів полів за допомогою кодування їхрядка−by−rowintolargerfields(наприклад,

\mathbb{F}{2^{16}}$ ), використовуючи ефективність та властивості максимальної віддальної роздільності кодів Ріда-Соломона. Після кодування ці рядки фіксуються за допомогою дерева Меркла, що спрощує операційну складність фіксацій поліномів у невеликих полях. Цей підхід дозволяє ефективно обробляти поліноми в невеликих полях без обчислювального бременя, яке зазвичай пов'язане з більшими полями.

3. Оптимізації Binius

Для подальшого покращення продуктивності Binius впроваджує чотири основні оптимізації:

1. PIOP на основі GKR : Протокол GKR (Goldreich-Kalai-Rothblum) використовується для заміни алгоритму пошуку Лассо при множенні двійкового поля, значно зменшуючи накладні витрати в процесі зобов'язання.
2. Оптимізація ZeroCheck PIOP: Ця оптимізація стосується балансу між обчислювальними витратами доведувача та перевіряючого, що робить операцію ZeroCheck більш ефективною шляхом більш ефективного розподілу навантаження.
3. Оптимізація Sumcheck PIOP: Шляхом оптимізації процесу Sumcheck невеликого поля Binius зменшує загальне обчислювальне навантаження при роботі над невеликими полями.
4. Оптимізація PCS : Використовуючи оптимізацію FRI-Binius (Fast Reed-Solomon Interactive Oracle Proofs of Proximity), Binius зменшує розмір доказу та підвищує продуктивність протоколу, підвищуючи загальну ефективність як генерації доказів, так і перевірки.

3.1 GKR-заснована PIOP: Множення бінарного поля за допомогою GKR

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

Основна ідея протоколу GKR (Goldwasser-Kalai-Rothblum) полягає в досягненні згоди між Prover (P) і Verifier (V) за шаровою арифметичною схемою на скінченному полі

𝐹

. Кожен вузол в цій схемі має два входи для обчислення необхідної функції. Щоб зменшити обчислювальну складність верифікатора, протокол використовує протокол SumCheck, який поступово зводить заяви про значення вихідного вентиля схеми до значень вентилів нижчого рівня, в кінцевому підсумку спрощуючи претензії до тверджень про входи. Таким чином, верифікатору потрібно лише перевірити правильність входів схеми.

ВоротаАлгоритм множення цілих чисел на основі GKRу Binius перетворює перевірку на те, чи два 32-бітних цілих числа

𝐴

і

𝐵

задовольнити

𝐴⋅𝐵=?𝐶

в перевірці чи

(𝑔𝐴)𝐵=?𝑔𝐶

утримує

𝐹264∗

. Це перетворення в поєднанні з протоколом GKR значно зменшує накладні витрати, пов'язані з поліноміальними зобов'язаннями. У порівнянні з попередньою схемою пошуку на основі Бініуса, підхід множення на основі GKR вимагає лише одного допоміжного зобов'язання та знижує вартість SumChecks, роблячи алгоритм більш ефективним, особливо у випадках, коли SumChecks є більш економічними, ніж додаткові зобов'язання. Цей метод стає перспективним рішенням для мінімізації витрат на поліноміальні зобов'язання двійкового поля в міру оптимізації Бініуса.

3.2 Оптимізація ZeroCheck PIOP: Збалансування обчислювальних витрат між доводником та перевірником

Папір Деякі поліпшення для PIOP для ZeroCheckпропонує стратегії збалансувати обчислювальні витрати між доведенням (P) та перевіркою (V), зосереджуючись на зменшенні передачі даних та обчислювальної складності. Нижче наведено ключові техніки оптимізації:

• Зменшення передачі даних довідника

Передаче частини обчислювального навантаження на Верифікатора, можна мінімізувати передавання даних Prover. Наприклад, на раунде

𝑖

, Проповідник посилає

𝑣𝑖+1(𝑋)

для

𝑋=0,…,𝑑+1

, а Перевірник перевіряє, чи

𝑣𝑖=𝑣𝑖+1(0)+𝑣𝑖+1(1)

володіє.

Оптимізація: Доказувач може уникнути відправлення

vi+1(1)

, так як перевірник може обчислити його як

𝑣𝑖+1(1)=𝑣𝑖−𝑣𝑖+1(0)

.

У початковому раунді Доводчик відправляє

𝑣1(0)=𝑣1(1)=0

, що дозволяє уникнути деяких розрахунків оцінки, що зменшує обчислювальні та передавальні витрати до

d2n−1CF+(d+1)2n−1CG

.

• Зменшення кількості оцінкових точок для довідника

Під час раунду

я

, Професіонал повинен надіслати

𝑣𝑖+1(𝑋)

, обчислений як

𝑣𝑖+1(𝑋)=∑𝑥∈𝐻𝑛−𝑖−1𝛿^𝑛(𝛼,(𝑟,𝑋,𝑥))𝐶(𝑟,𝑋,𝑥)

.

Оптимізація: Натомість, Prover може надсилати

𝑣𝑖+1′(𝑋)=∑𝑥∈𝐻𝑛−𝑖−1𝛿^𝑛(𝛼𝑖+1,…,𝛼𝑛−1,𝑥)𝐶(𝑟,𝑋,𝑥),

де $v_i(X) = v_i’(X) \cdot \hat{\delta}{i+1}((\alpha_0, \dots, \alpha_i), (r, X))

.AstheVerifierhasaccessto

\alpha

𝑎𝑛𝑑

r

,𝑡ℑ𝑒𝑑𝑒𝑔𝑟𝑒𝑒𝑜𝑓

v_i’(X)

𝑖𝑠𝑙𝑜𝑤𝑒𝑟𝑡ℎ𝑎𝑛𝑡ℎ𝑎𝑡𝑜𝑓

v_i(X)

, 𝑠𝑗𝑎𝑛𝑢𝑗𝑢𝑐𝑡𝑖𝑛𝑔𝑡ℎ𝑒𝑟𝑒𝑞𝑢𝑖𝑟𝑒𝑑𝑒𝑣𝑎𝑙𝑢𝑎𝑡𝑖𝑜𝑛𝑝𝑜𝑖𝑛𝑡𝑠. 𝑇ℎ𝑒𝑖𝑛𝑡𝑒𝑟−𝑟𝑜𝑢𝑛𝑑𝑐ℎ𝑒𝑐𝑘𝑐𝑎𝑛𝑡ℎ𝑒𝑛𝑏𝑒𝑠𝑖𝑚𝑝𝑙𝑖𝑓𝑖𝑒𝑑𝑎𝑠

(1 - \alphai)v{i+1}'(0) + \alpha_i v{i+1}’(1) = v_i’(X),

𝑡ℎ𝑒𝑟𝑒𝑏𝑦𝑙𝑜𝑤𝑒𝑟𝑖𝑛𝑔𝑑𝑎𝑡𝑎𝑡𝑟𝑎𝑛𝑠𝑚𝑖𝑠𝑠𝑖𝑜𝑛𝑛𝑒𝑒𝑑𝑠𝑎𝑛𝑑𝑒𝑛ℎ𝑎𝑛𝑐𝑖𝑛𝑔𝑒𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑐𝑦.𝑊𝑖𝑡ℎ𝑡ℎ𝑒𝑠𝑒𝑖𝑚𝑝𝑟𝑜𝑣𝑒𝑚𝑒𝑛𝑡𝑠,𝑡ℎ𝑒𝑜𝑣𝑒𝑟𝑎𝑙𝑙𝑐𝑜𝑠𝑡𝑖𝑠𝑎𝑝𝑝𝑟𝑜𝑥𝑖𝑚𝑎𝑡𝑒𝑙𝑦

2^{n-1}(d - 1)C_F + 2^{n-1}dC_G.

Для

d = 3$ , ці оптимізації знижують вартість в 5/3 разів.

• Алгебраїчна оптимізація інтерполяції

Для чесного Провера поліном

𝐶(𝑥0,…,𝑥𝑛−1)

є нулем на

𝐻𝑛

і може бути виражений як

𝐶(𝑥0,…,𝑥𝑛−1)=∑𝑖=0𝑛−1𝑥𝑖(𝑥𝑖−1)𝑄𝑖(𝑥0,…,𝑥𝑛−1)

. Де

𝑄𝑖

обчислюється за допомогою впорядкованого поліноміального ділення, починаючи з

𝑅𝑛=𝐶

. Послідовне ділення на

𝑥𝑖(𝑥𝑖−1)

обчислює

𝑄𝑖

і

𝑅𝑖

, з

𝑅0

представлення мультілінійного розширення

𝐶

на

𝐻𝑛

, вважається рівним нулю.

Аналізуючи рівні

QI

. Для

𝑗>𝑖

,

𝑄𝑗

зберігає той самий ступінь в

𝑥𝑖

як

𝐶

. Для

𝑗=𝑖

, ступінь зменшується на 2, а для

𝑗<𝑖

, ступінь не перевищує 1. Задано вектор

𝑟=(𝑟0,…,𝑟𝑖)

,

𝑄𝑗(𝑟,𝑋)

є багатолінійним для всіх

𝑗≤𝑖

Крім того,

𝑄𝑖(𝑟,𝑋)=∑𝑗=0𝑖𝑟𝑗(𝑟𝑗−1)𝑄𝑗(𝑟,𝑋)

є унікальним мультилінійним поліномом, який відповідає

𝐶(𝑟,𝑋)

на

𝐻𝑛−𝑖

. Для будь-якої

𝑋

та

𝑥∈𝐻𝑛−𝑖−1

, це може бути представлено як

𝐶(𝑟,𝑋,𝑥)−𝑄𝑖(𝑟,𝑋,𝑥)=𝑋(𝑋−1)𝑄𝑖+1(𝑟,𝑋,𝑥).

Отже, під час кожного раунду протоколу новий

𝑄

вводиться, і його оцінка може бути виведена з

𝐶

і попередній

𝑄

, дозволяючи оптимізацію інтерполяції.

3.3 Оптимізація PIOP Sumcheck: Протокол перевірки суми малих полів

У протоколі STARKs, реалізованому Binius, основним обмеженням для доведеннячасто є протокол перевірки суми, а не схема зобов'язання полінома (PCS), через низькі витрати на зобов'язання.

Рисунок 2. Взаємозв'язок між раундом перемикання та покращенням фактору

У 2024 році Ingonyama запропонував покращення для протоколів Sumcheck на основі малих полів, зосереджуючись на алгоритмах 3 та 4. Ці поліпшення були впроваджені та зроблені загальнодоступними тут. Алгоритм 4 включає алгоритм Карацуби в Алгоритм 3, зменшуючи кількість множень полів розширень на користь більшої кількості множень основних полів. Цей підхід є більш ефективним, коли множення полів розширень є дорожчими, ніж множення основних полів.

1. Вплив раундів перемикання та фактори покращення Оптимізація протоколу Sumcheck з малим полем залежить від вибору оптимального раунду перемикання

𝑡

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

Для певних застосувань, таких як Cubic Sumcheck (

𝑑=3

) , протокол малих полів Sumcheck забезпечує покращення порядку величини порівняно з наївним підходом. Наприклад, у базовому полі

𝐺𝐹[2]2. Вплив розміру базового поля на продуктивність Менші базові поля (наприклад,

, Алгоритм 4 перевершує наївний алгоритм майже в 30 разів.

𝐺𝐹[2]

) значно підвищують ефективність оптимізованого алгоритму через більшу розбіжність між вартістю множення у полі розширення та базового поля. Це призводить до більш суттєвого коефіцієнта покращення для оптимізованого алгоритму.

1. Оптимізаційні вигоди від алгоритму Карацуби Алгоритм Карацуби відіграє вирішальну роль у підвищенні продуктивності протоколу Sumcheck з малим полем поля. Для базового поля

𝐺𝐹[2]

, Алгоритм 4 досягає пікових коефіцієнтів покращення 6 для Алгоритму 3 і 30 для Алгоритму 4, що вказує на те, що Алгоритм 4 у п'ять разів ефективніший за Алгоритм 3. Алгоритм Карацуби підвищує ефективність виконання та оптимізує точку перемикання для обох алгоритмів, з оптимальними точками на

𝑡=5

для Алгоритму 3 та

𝑡=8

для Алгоритму 4.

1. Підвищення ефективності пам'яті Протокол Sumcheck з малим полем також підвищує ефективність пам'яті. Алгоритм 4 вимагає

O(d⋅t)

пам'ять, тоді як Алгоритм 3 потребує

𝑂(2𝑑⋅𝑡)

пам'ять. Для

𝑡=8

, Алгоритм 4 використовує лише 0,26 МБ пам'яті, у порівнянні з 67 МБ, необхідними для Алгоритму 3. Це робить Алгоритм 4 особливо підходящим для обмежених пам'яттю середовищ, таких як докази на боці клієнта з обмеженими ресурсами.

3.4 Оптимізація PCS: FRI-Binius Зменшення розміру доказу Binius

Одна з основних проблем протоколу Binius - його відносно великий розмір доказу, який масштабується з квадратним коренем від розміру свідка при

𝑂(𝑁)

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

Ця статтяПолілогарифмічні докази для багатолінійних функцій над двійковими вежами, відомий як FRI-Binius, вводить новий механізм згортання FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity) на основі бінарного поля з чотирма ключовими інноваціями:

• Згладжені поліноми: перетворює початковий багатолінійний поліном у поліноміальну базу з низькою висотою коду (LCH) для оптимізованого обчислення.
• Зникаючі многочлени підпростору: використовує ці многочлени в поєднанні з адитивним NTT (теоретичним перетворенням чисел), щоб увімкнути FFT-подібне розкладання, оптимізуючи операції над полем коефіцієнтів.
• Алгебраічне упаковування бази: забезпечує ефективне упаковування даних, мінімізуючи накладні витрати протоколу, пов'язані з вбудовуванням.
• Ring-Switching SumCheck: Нова оптимізація SumCheck, яка використовує техніки переключення кілець для подальшого покращення продуктивності.

Основний процес схеми зобов'язаності мультилінійного полінома FRI-Binius (PCS)

Протокол FRI-Binius оптимізує схеми зобов'язань багатовимірних бінарних поліномів (PCS), перетворюючи початковий багатовимірний поліном, визначений над бінарним полем

𝐹2

, у мультилинійний поліном над більшим полем

𝐾

.

1. Фаза зобов'язання. Фаза зобов'язання перетворює
2. ℓ
3. -поліном змінної кількох ліній (над $\mathbb{F}2
4. )𝑖𝑛𝑡𝑜𝑎𝑐𝑜𝑚𝑚𝑖𝑡𝑚𝑒𝑛𝑡𝑓𝑜𝑟𝑎𝑝𝑎𝑐𝑘𝑒𝑑
5. \ell’
6. −𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒𝑚𝑢𝑙𝑡𝑖𝑙𝑖𝑛𝑒𝑎𝑟𝑝𝑜𝑙𝑦𝑛𝑜𝑚𝑖𝑎𝑙(𝑜𝑣𝑒𝑟
7. \mathbb{F}{2^{128}}$ ). Цей процес зменшує кількість коефіцієнтів у 128 разів, що дозволяє більш ефективне створення доказів.
8. Фаза оцінки У цій фазі доводчик і перевіряючий виконують
9. ℓ′
10. раунди протоколу переключення у формі хреста SumCheck, поєднані з FRI інтерактивними оракуліними доказами близькості (IOPP). Основні деталі включають:
    • Докази відкриття FRI: Вони складають більшість розміру доказу і обробляються подібно до стандартних доказів FRI над великими полями.
    • Вартість SumCheck від Prover: Порівнянна з вартістю виконання SumCheck у великому полі.
    • Вартість FRI від Prover: Відповідає стандартним витратам FRI, які бачили в реалізаціях для великого поля.
    • Операції перевіряючого: перевіряючий отримує 128 елементів від
    • Ф2128
    • і виконує 128 додаткових множень, що дозволяє ефективну перевірку.

Переваги FRI-Binius

Застосовуючи цей метод, Binius може зменшити розмір свого доказу на порядок, наближаючись до продуктивності сучасних криптографічних систем, залишаючись сумісним з бінарними полями. Метод складання FRI, оптимізований для бінарних полів, спільно з алгебраїчним упакуванням та оптимізацією SumCheck, допомагає Binius генерувати менші докази, не компрометуючи ефективність перевірки.

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

Таблиця 2: Порівняння розмірів доказів Binius і FRI-Binius

Таблиця 3: Порівняння Plonky3 FRI та FRI-Binius

4. Висновок

Вся ціннісна пропозиція Binius полягає в його здатності використовувати найменший розмір поля степеня двох для свідків, вибираючи розмір поля за потреби. Binius — це схема спільного проектування «апаратного, програмного забезпечення та протоколів Sumcheck, прискорених FPGA», що забезпечує швидкі докази з дуже низьким використанням пам'яті.

Системи доведення, такі як Halo2 та Plonky3, включають чотири ключові обчислювально складні кроки: генерація даних свідка, зобов'язання з даними свідка, виконання аргументу зникнення та генерація відкритого доказу.

Наприклад, з функцією хешування Keccak в Plonky3 та функцією хешування Grøstl в Binius, обчислювальний розподіл для цих чотирьох ключових кроків показаний на рисунку 3.

Рисунок 3. Витрати на менший комітет

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

Схема FRI-Binius, варіант FRI, пропонує дуже привабливий варіант, виключаючи накладні вбудовування з рівня доказу полів без значного збільшення вартості в агрегованому рівні доказу.

Наразі команда Irreducible розробляє свій рекурсивний шар таоголосив про партнерство з командою Polygon для створення zkVM на основі Binius; the Jolt zkVM переходить від Lasso до Binius, щоб підвищити свою рекурсивну продуктивність; і Команда Ingonyama реалізує FPGA-версію Binius.

Посилання

1. 2024.04 Стислі аргументи Бініуса щодо веж подвійних полів
2. 2024.07 Полілогарифмічні докази Фрі-Бініуса для багатолінійних веж над двійковими вежами
3. 2024.08 Множення цілих чисел у Binius: підхід на основі GKR
4. 2024.06 zkStudyClub - FRI-Binius: Полілогарифмічні докази для багатолінійних функцій над двійковими вежами
5. 2024.04 ZK11: Binius: апаратно-оптимізований SNARK - Джим Позен
6. 2023.12 Епізод 303: Занурення у Binius з Ulvetanna
7. 2024.09 Розробка високопродуктивних zkVM
8. 2024.07 Sumcheck та Open-Binius
9. 2024.04 Binius: високоефективні докази над бінарними полями
10. 2023.12 SNARKs on binary fields: Binius - Частина 1
11. 2024.06 SNARKs на бінарних полях: Binius - Частина 2
12. @espressosys/hyperplonk-a-zk-proof-system-for-zkevms-d45fd077bfba">2022.10 HyperPlonk, zk-proof-система для ZKEVM

Disclaimer:

1. Ця стаття передрукована з [Бітовий шар]. Усі авторські права належать оригінальному автору [ lynndell]. Якщо є заперечення щодо цього перепринту, будь ласка, зв'яжіться з Ukrainian Learn команди, і вони оперативно впораються з цим.
2. Відмова відповідальності: Погляди та думки, висловлені в цій статті, є виключно авторськими та не становлять жодної інвестиційної поради.
3. Переклад статті на інші мови здійснюється командою gate Learn. Якщо не зазначено, копіювання, розповсюдження або плагіат перекладених статей заборонено.