Аналіз принципів Binius STARKs та роздуми щодо їх оптимізації
1 Вступ
Основною причиною низької ефективності STARKs є те, що більшість чисел у фактичних програмах є досить малими, але для забезпечення безпеки доказів на основі дерева Меркла, під час розширення даних за допомогою кодування Ріда-Соломона, багато додаткових надмірних значень займають цілу область. Щоб вирішити цю проблему, зменшення розміру області стало ключовою стратегією.
Перший покоління STARKs має ширину коду 252 біт, друге покоління - 64 біт, третє покоління - 32 біти, але 32-бітна ширина коду все ще має багато невикористаного простору. У порівнянні з цим, двійкове поле дозволяє безпосередньо виконувати операції над бітом, кодування компактне, ефективне і не має будь-якого невикористаного простору, тобто четверте покоління STARKs.
Коли використовуються менші поля, операція розширення поля стає все більш важливою для забезпечення безпеки. А двійкове поле, що використовується Binius, повністю покладається на розширення поля для забезпечення своєї безпеки та фактичної придатності. Більшість поліномів, що беруть участь у обчисленнях Prover, не потребують переходу в розширене поле, а лише виконуються в базовому полі, що дозволяє досягти високої ефективності в малих полях. Проте випадкові перевірки точок і обчислення FRI все ще потребують заглиблення у більше розширене поле для забезпечення необхідної безпеки.
При побудові системи доказів на основі бінарного поля виникає 2 практичні проблеми: під час обчислення представлення сліду в STARKs розмір поля, що використовується, повинен бути більшим за ступінь полінома; під час зобов'язання Merkle tree в STARKs необхідно виконати кодування Ріда-Соломона, розмір поля, що використовується, повинен бути більшим за розмір після розширення коду.
Binius запропонував інноваційне рішення для окремого вирішення цих двох проблем і реалізації однакових даних двома різними способами: по-перше, використовуючи багатовимірні (конкретно, багатолінійні) поліноми замість одновимірних поліномів, представляючи всю обчислювальну траєкторію через їх значення на "гіперкубах" (hypercubes); по-друге, оскільки довжина кожного виміру гіперкуба дорівнює 2, стандартне розширення Ріда-Соломона не може бути реалізоване, як у випадку STARKs, але гіперкуб можна розглядати як квадрат (square), ґрунтуючись на якому можна здійснити розширення Ріда-Соломона. Цей підхід значно підвищує ефективність кодування та обчислювальну продуктивність при забезпеченні безпеки.
Binius: HyperPlonk PIOP + Brakedown PCS + бінарна область. Конкретно кажучи, Binius включає п'ять ключових технологій для забезпечення своєї ефективності та безпеки:
Армування на основі баштової двійкової області
Адаптована версія перевірки добутку та перестановки HyperPlonk
Нова множинна теорія зсуву
Поліпшена версія аргументації пошуку Lasso
Схема обіцянки малих многочленів
2.1 Кінцеві поля: арифметика на основі веж бінарних полів
Бінарна область з塔式 є ключем до реалізації швидких перевіряємих обчислень, що обумовлено двома аспектами: ефективними обчисленнями та ефективною алгеброю. Бінарна область в своїй суті підтримує надзвичайно ефективні алгебричні операції, що робить її ідеальним вибором для криптографічних застосувань, чутливих до продуктивності. Крім того, структура бінарної області підтримує спрощений алгебраїчний процес, тобто операції, що виконуються в бінарній області, можуть бути представлені у компактній та легкій для перевірки алгебраїчній формі.
У полях простих чисел Fp поширені методи редукції включають редукцію Барретта, редукцію Монтгомері, а також спеціальні методи редукції для певних скінченних полів, таких як Mersenne-31 або Goldilocks-64. У бінарному полі F2k зазвичай використовують методи редукції, зокрема спеціальну редукцію (як у AES), редукцію Монтгомері (як у POLYVAL) та рекурсивну редукцію (як Tower).
Двійкове поле не потребує переносу в операціях додавання та множення, а квадратування в двійковому полі є дуже ефективним, оскільки воно підпорядковується спрощеному правилу (X + Y )2 = X2 + Y 2.
2.2 PIOP: адаптований продукт HyperPlonk і PermutationCheck
Дизайн PIOP в протоколі Binius запозичив HyperPlonk і використовує ряд основних перевірочних механізмів для верифікації правильності поліномів і множин змінних. Ці основні перевірки включають:
Перевірка воріт
Перевірка перестановки
Перевірка пошуку
Функція MultisetCheck
Перевірка товару
Перевірка нуля
Перевірка суми
Пакетна перевірка
Binius зробив такі покращення в порівнянні з HyperPlonk:
Оптимізація ProductCheck
Обробка проблеми поділу на нуль
Перевірка перестановок через стовпці
2.3 PIOP: новий багаторівневий зсув аргумент
У протоколі Binius конструкція та обробка віртуальних багаторазових поліномів є однією з ключових технологій, що дозволяє ефективно генерувати та оперувати поліномами, які походять від вхідних дескрипторів або інших віртуальних поліномів. Нижче наведено два ключові методи:
Упаковка
Оператори зсуву
2.4 PIOP:адаптована версія аргументу пошуку Lasso
Протокол Lasso дозволяє стороні, що доводить, зобов'язатися вектором a ∈ Fm і довести, що всі його елементи існують у заздалегідь визначеній таблиці t ∈ Fn. Протокол Lasso складається з трьох компонентів:
Віртуальна поліноміальна абстракція великої таблиці
Малий пошук
Перевірка множин
Протокол Binius адаптує Lasso для операцій у бінарному полі, вводячи множинну версію протоколу Lasso.
2.5 PCS:адаптована версія Brakedown PCS
Основна ідея побудови BiniusPCS полягає в пакуванні. У статті Binius представлені 2 схеми обіцянки поліномів Brakedown на основі бінарних полів:
Використовувати конкатенований код для інстанціювання
Використовуючи технологію кодування на рівні блоків, підтримує окреме використання кодів Ріда-Соломона
Binius полігональні зобов'язання в основному використовують такі технології:
Малий поліноміальний обіцянки та оцінка розширеного поля
Малий загальний конструкція
Блочне кодування та коди Ріда-Соломона
3 Оптимізація мислення
Щоб подальше підвищити продуктивність протоколу Binius, у цій статті запропоновано чотири ключові оптимізаційні моменти:
PIOP на основі GKR: для бінарних доменних множення
Оптимізація ZeroCheck PIOP: балансування витрат обчислень між Prover та Verifier
Оптимізація Sumcheck PIOP: оптимізація для малих областей Sumcheck
Оптимізація PCS: оптимізація через FRI-Binius
3.1 GKR-based PIOP: Бінарне множення полів на основі GKR
Алгоритм цілочисельного множення на основі GKR, шляхом перетворення "перевірити, чи два 32-бітних цілочисельних числа A і B задовольняють A·B =? C" на "перевірити, чи (gA)B =? gC є істинним", значно зменшує витрати на зобов'язання завдяки протоколу GKR.
3.2 ZeroCheck PIOP оптимізація: баланс витрат на обчислення Prover та Verifier
Стаття «Деякі поліпшення PIOP для ZeroCheck» пропонує кілька оптимізацій для розподілу обсягу роботи між довіреною стороною (P) та перевіряючою стороною (V), щоб зменшити витрати. Основні оптимізації включають:
Зменшити передачу даних з боку доказувача
Зменшити кількість оцінювальних пунктів для сторони, що підтверджує
3.3 Оптимізація PIOP Sumcheck: протокол Sumcheck на основі малих областей
Ingonyama у 2024 році представив вдосконалену версію протоколу Sumcheck на основі малих областей та опублікував код реалізації з відкритим вихідним кодом. Основні оптимізації включають:
Вплив та фактори покращення зміни раундів
Вплив розміру базової області на продуктивність
Оптимізаційні вигоди алгоритму Карацуби
Підвищення ефективності пам'яті
3.4 PCS оптимізація: FRI-Binius зменшення розміру доказу Binius
Стаття «Полілогарифмічні доведення для мультилінійних функцій над бінарними вежами», скорочено FRI-Binius, реалізує механізм складання FRI для бінарного поля, що приносить 4 аспекти інновацій:
Плоский многочлен
Поліном зникнення підпростору
Пакування алгебраїчної бази
Обмін сумою SumCheck
За допомогою FRI-Binius можна зменшити розмір доказу Binius на один порядок.
4 Підсумок
Binius є "спільним проєктом, що використовує апаратне, програмне забезпечення та прискорений протокол Sumcheck на FPGA", який може швидко доводити при дуже низькому використанні пам'яті. У Binius практично повністю усунуто вузьке місце з коміту Prover, новим вузьким місцем є протокол Sumcheck, де багато оцінок многочленів та проблеми доменного множення можуть бути ефективно розв'язані за допомогою спеціалізованого апаратного забезпечення.
FRI-Binius рішення, для варіанту FRI, може запропонувати дуже привабливий вибір — усунути вбудовані витрати з рівня доказів домену, не призводячи до різкого зростання витрат на рівні агрегованих доказів. Наразі команда Irreducible працює над своїм рекурсивним рівнем і оголосила про співпрацю з командою Polygon для створення zkVM на базі Binius; JoltzkVM переходить з Lasso на Binius, щоб покращити свою рекурсивну продуктивність; команда Ingonyama реалізує версію Binius на FPGA.
Ця сторінка може містити контент третіх осіб, який надається виключно в інформаційних цілях (не в якості запевнень/гарантій) і не повинен розглядатися як схвалення його поглядів компанією Gate, а також як фінансова або професійна консультація. Див. Застереження для отримання детальної інформації.
26 лайків
Нагородити
26
8
Репост
Поділіться
Прокоментувати
0/400
AirdropF5Bro
· 08-13 09:02
Ого, ця ситуація з starknet!
Переглянути оригіналвідповісти на0
¯\_(ツ)_/¯
· 08-12 16:41
Ця оптимізація просто вражаюча, від 252 до двійкової системи.
Переглянути оригіналвідповісти на0
SerumSquirter
· 08-10 20:16
Ефективність зростає, область зменшується.
Переглянути оригіналвідповісти на0
GateUser-afe07a92
· 08-10 09:35
Так нудно, наступний.
Переглянути оригіналвідповісти на0
ForkTongue
· 08-10 09:20
Написано дуже добре, але професіонал не зрозумів...
Переглянути оригіналвідповісти на0
NullWhisperer
· 08-10 09:16
гм... оптимізація двійкових полів виглядає теоретично елегантно, але давайте поговоримо про ці крайні випадки в операціях розширення полів...
Переглянути оригіналвідповісти на0
HalfBuddhaMoney
· 08-10 09:15
Скільки часу не перекладали нульову ширину? Цього разу все зрозуміло.
Переглянути оригіналвідповісти на0
NonFungibleDegen
· 08-10 09:08
цей різкий матеріал базується на... бінарних = число зростає, нарешті якийсь реальний альфа, а не цей меркл-дерево коп.
Аналіз принципів Binius STARKs: оптимізація бінарної області та ефективні полікомітети
Аналіз принципів Binius STARKs та роздуми щодо їх оптимізації
1 Вступ
Основною причиною низької ефективності STARKs є те, що більшість чисел у фактичних програмах є досить малими, але для забезпечення безпеки доказів на основі дерева Меркла, під час розширення даних за допомогою кодування Ріда-Соломона, багато додаткових надмірних значень займають цілу область. Щоб вирішити цю проблему, зменшення розміру області стало ключовою стратегією.
Перший покоління STARKs має ширину коду 252 біт, друге покоління - 64 біт, третє покоління - 32 біти, але 32-бітна ширина коду все ще має багато невикористаного простору. У порівнянні з цим, двійкове поле дозволяє безпосередньо виконувати операції над бітом, кодування компактне, ефективне і не має будь-якого невикористаного простору, тобто четверте покоління STARKs.
Коли використовуються менші поля, операція розширення поля стає все більш важливою для забезпечення безпеки. А двійкове поле, що використовується Binius, повністю покладається на розширення поля для забезпечення своєї безпеки та фактичної придатності. Більшість поліномів, що беруть участь у обчисленнях Prover, не потребують переходу в розширене поле, а лише виконуються в базовому полі, що дозволяє досягти високої ефективності в малих полях. Проте випадкові перевірки точок і обчислення FRI все ще потребують заглиблення у більше розширене поле для забезпечення необхідної безпеки.
При побудові системи доказів на основі бінарного поля виникає 2 практичні проблеми: під час обчислення представлення сліду в STARKs розмір поля, що використовується, повинен бути більшим за ступінь полінома; під час зобов'язання Merkle tree в STARKs необхідно виконати кодування Ріда-Соломона, розмір поля, що використовується, повинен бути більшим за розмір після розширення коду.
Binius запропонував інноваційне рішення для окремого вирішення цих двох проблем і реалізації однакових даних двома різними способами: по-перше, використовуючи багатовимірні (конкретно, багатолінійні) поліноми замість одновимірних поліномів, представляючи всю обчислювальну траєкторію через їх значення на "гіперкубах" (hypercubes); по-друге, оскільки довжина кожного виміру гіперкуба дорівнює 2, стандартне розширення Ріда-Соломона не може бути реалізоване, як у випадку STARKs, але гіперкуб можна розглядати як квадрат (square), ґрунтуючись на якому можна здійснити розширення Ріда-Соломона. Цей підхід значно підвищує ефективність кодування та обчислювальну продуктивність при забезпеченні безпеки.
! Дослідження Bitlayer: Аналіз принципів Бініуса Старка та оптимізаційне мислення
2 Принципи аналізу
Поточна більшість систем SNARKs зазвичай складається з двох частин:
Binius: HyperPlonk PIOP + Brakedown PCS + бінарна область. Конкретно кажучи, Binius включає п'ять ключових технологій для забезпечення своєї ефективності та безпеки:
2.1 Кінцеві поля: арифметика на основі веж бінарних полів
Бінарна область з塔式 є ключем до реалізації швидких перевіряємих обчислень, що обумовлено двома аспектами: ефективними обчисленнями та ефективною алгеброю. Бінарна область в своїй суті підтримує надзвичайно ефективні алгебричні операції, що робить її ідеальним вибором для криптографічних застосувань, чутливих до продуктивності. Крім того, структура бінарної області підтримує спрощений алгебраїчний процес, тобто операції, що виконуються в бінарній області, можуть бути представлені у компактній та легкій для перевірки алгебраїчній формі.
У полях простих чисел Fp поширені методи редукції включають редукцію Барретта, редукцію Монтгомері, а також спеціальні методи редукції для певних скінченних полів, таких як Mersenne-31 або Goldilocks-64. У бінарному полі F2k зазвичай використовують методи редукції, зокрема спеціальну редукцію (як у AES), редукцію Монтгомері (як у POLYVAL) та рекурсивну редукцію (як Tower).
Двійкове поле не потребує переносу в операціях додавання та множення, а квадратування в двійковому полі є дуже ефективним, оскільки воно підпорядковується спрощеному правилу (X + Y )2 = X2 + Y 2.
! Дослідження Bitlayer: Аналіз принципів Бініуса Старка та оптимізаційне мислення
2.2 PIOP: адаптований продукт HyperPlonk і PermutationCheck
Дизайн PIOP в протоколі Binius запозичив HyperPlonk і використовує ряд основних перевірочних механізмів для верифікації правильності поліномів і множин змінних. Ці основні перевірки включають:
Binius зробив такі покращення в порівнянні з HyperPlonk:
2.3 PIOP: новий багаторівневий зсув аргумент
У протоколі Binius конструкція та обробка віртуальних багаторазових поліномів є однією з ключових технологій, що дозволяє ефективно генерувати та оперувати поліномами, які походять від вхідних дескрипторів або інших віртуальних поліномів. Нижче наведено два ключові методи:
2.4 PIOP:адаптована версія аргументу пошуку Lasso
Протокол Lasso дозволяє стороні, що доводить, зобов'язатися вектором a ∈ Fm і довести, що всі його елементи існують у заздалегідь визначеній таблиці t ∈ Fn. Протокол Lasso складається з трьох компонентів:
Протокол Binius адаптує Lasso для операцій у бінарному полі, вводячи множинну версію протоколу Lasso.
2.5 PCS:адаптована версія Brakedown PCS
Основна ідея побудови BiniusPCS полягає в пакуванні. У статті Binius представлені 2 схеми обіцянки поліномів Brakedown на основі бінарних полів:
Binius полігональні зобов'язання в основному використовують такі технології:
3 Оптимізація мислення
Щоб подальше підвищити продуктивність протоколу Binius, у цій статті запропоновано чотири ключові оптимізаційні моменти:
3.1 GKR-based PIOP: Бінарне множення полів на основі GKR
Алгоритм цілочисельного множення на основі GKR, шляхом перетворення "перевірити, чи два 32-бітних цілочисельних числа A і B задовольняють A·B =? C" на "перевірити, чи (gA)B =? gC є істинним", значно зменшує витрати на зобов'язання завдяки протоколу GKR.
3.2 ZeroCheck PIOP оптимізація: баланс витрат на обчислення Prover та Verifier
Стаття «Деякі поліпшення PIOP для ZeroCheck» пропонує кілька оптимізацій для розподілу обсягу роботи між довіреною стороною (P) та перевіряючою стороною (V), щоб зменшити витрати. Основні оптимізації включають:
! Дослідження Bitlayer: Аналіз принципів Бініуса Старка та оптимізаційне мислення
3.3 Оптимізація PIOP Sumcheck: протокол Sumcheck на основі малих областей
Ingonyama у 2024 році представив вдосконалену версію протоколу Sumcheck на основі малих областей та опублікував код реалізації з відкритим вихідним кодом. Основні оптимізації включають:
3.4 PCS оптимізація: FRI-Binius зменшення розміру доказу Binius
Стаття «Полілогарифмічні доведення для мультилінійних функцій над бінарними вежами», скорочено FRI-Binius, реалізує механізм складання FRI для бінарного поля, що приносить 4 аспекти інновацій:
За допомогою FRI-Binius можна зменшити розмір доказу Binius на один порядок.
4 Підсумок
Binius є "спільним проєктом, що використовує апаратне, програмне забезпечення та прискорений протокол Sumcheck на FPGA", який може швидко доводити при дуже низькому використанні пам'яті. У Binius практично повністю усунуто вузьке місце з коміту Prover, новим вузьким місцем є протокол Sumcheck, де багато оцінок многочленів та проблеми доменного множення можуть бути ефективно розв'язані за допомогою спеціалізованого апаратного забезпечення.
FRI-Binius рішення, для варіанту FRI, може запропонувати дуже привабливий вибір — усунути вбудовані витрати з рівня доказів домену, не призводячи до різкого зростання витрат на рівні агрегованих доказів. Наразі команда Irreducible працює над своїм рекурсивним рівнем і оголосила про співпрацю з командою Polygon для створення zkVM на базі Binius; JoltzkVM переходить з Lasso на Binius, щоб покращити свою рекурсивну продуктивність; команда Ingonyama реалізує версію Binius на FPGA.
! Дослідження Bitlayer: Аналіз принципів Бініуса Старка та оптимізаційне мислення