Аналіз принципів STARKs Binius та його оптимізаційні міркування
1 Вступ
Основною причиною низької ефективності STARKs є те, що більшість чисел у фактичних програмах є досить малими, такими як індекси в циклах for, логічні значення, лічильники тощо. Однак, щоб забезпечити безпеку доказів на основі дерева Меркла, під час розширення даних за допомогою кодування Ріда-Соломона багато додаткових надмірних значень займають весь простір, навіть якщо оригінальні значення самі по собі дуже малі. Для вирішення цієї проблеми зменшення розміру простору стало ключовою стратегією.
Як показано в таблиці 1, ширина коду першого покоління STARKs становить 252 біти, ширина коду другого покоління STARKs становить 64 біти, ширина коду третього покоління STARKs становить 32 біти, але 32-бітна ширина коду все ще має значну кількість невикористаного простору. У порівнянні з цим, двійкове поле дозволяє безпосередньо виконувати операції з бітом, кодування компактне та ефективне без будь-яких витрат простору, тобто четверте покоління STARKs.
Таблиця 1: Шлях еволюції STARKs
| Порядок | Ширина | Опис |
|------|------|------|
| 1-е покоління | 252 біти | на основі полів великих простих чисел |
| 2-ге покоління | 64bit | Домен Goldilocks |
| 3-є покоління | 32bit | Babybear-діапазон |
| 4-те покоління | 1 біт | двійкова область |
Порівняно з такими новими дослідженнями обмежених полів, як Goldilocks, BabyBear, Mersenne31, що з'явилися в останні роки, дослідження двійкових полів можна простежити ще з 80-х років минулого століття. Наразі двійкові поля широко застосовуються в криптографії, типовими прикладами є:
Високий стандарт шифрування (AES), оснований на полі F28;
Galois повідомлення аутентифікації ( GMAC ), на основі поля F2128;
QR-код, що використовує кодування Ріда-Соломона на основі F28;
Первісний протокол FRI та zk-STARK, а також хеш-функція Grøstl, яка потрапила до фіналу SHA-3, заснована на полях F28, є дуже підходящою для рекурсивних хеш-алгоритмів.
Коли використовуються менші поля, операції розширення поля стають дедалі важливішими для забезпечення безпеки. А бінарне поле, яке використовує Binius, повністю залежить від розширення поля для забезпечення його безпеки та фактичної придатності. Більшість поліномів, що беруть участь у обчисленнях Prover, не потребують переходу до розширеного поля, а лише виконуються в базовому полі, що забезпечує високу ефективність у малих полях. Проте випадкові перевірки точок та обчислення FRI все ще потребують поглиблення у більші розширені поля, щоб забезпечити необхідну безпеку.
При побудові системи доказів на основі бінарної області існує 2 практичні проблеми: під час обчислення представлення траси в STARKs використовувана величина області повинна бути більшою за ступінь полінома; під час зобов'язання Merkle tree в STARKs необхідно виконати кодування Ріда-Соломона, використовувана величина області повинна бути більшою за розмір, що розширений кодуванням.
Binius запропонував інноваційне рішення, яке вирішує ці дві проблеми окремо та реалізує їх за допомогою двох різних способів представлення однакових даних: по-перше, використовуючи багатозначний (, а саме багатолінійний ) поліном замість однозмінного полінома, представляючи всю обчислювальну траєкторію через його значення в "гіперкубах" (; по-друге, оскільки довжина кожного виміру гіперкуба дорівнює 2, стандартне розширення Ріда-Соломона, як у STARKs, не може бути застосоване, але гіперкуб може бути розглянутий як квадрат ), на основі якого здійснюється розширення Ріда-Соломона. Цей метод значно підвищує ефективність кодування та обчислювальну продуктивність при забезпеченні безпеки.
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.
Термін "canonical" відноситься до унікального та прямого способу представлення елементів у двійковій області. Наприклад, у найосновнішій двійковій області F2 будь-який рядок довжини k може бути безпосередньо відображений на елемент двійкової області довжини k. Це відрізняється від просторової області, яка не може забезпечити таке нормативне представлення в межах заданої довжини. Хоча 32-бітна проста область може містити 32 біти, не кожен 32-бітний рядок може бути унікально відповідний елементу області, тоді як двійкова область має цю зручність однозначного відображення. У просторовій області Fp поширеними методами редукції є редукція Барретта, редукція Монтгомері та спеціальні методи редукції для певних скінченних областей, таких як Mersenne-31 або Goldilocks-64. У двійковій області F2k поширеними методами редукції є спеціальна редукція ), як у використанні AES ###, редукція Монтгомері (, як у використанні POLYVAL ), та рекурсивна редукція (, як у Tower ). У статті "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" зазначається, що у двійковій області не потрібно вводити переноси при виконанні додавання та множення, а квадратна операція в двійковій області є дуже ефективною, оскільки вона слідує спрощеному правилу (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 і використовує ряд основних механізмів перевірки для верифікації правильності поліномів та множин змінних. До цих основних перевірок входять:
GateCheck: перевірка, чи відповідає конфіденційне свідчення ω та відкритий вхід x обчислювальному співвідношенню C)x, ω###=0, щоб забезпечити правильну роботу схеми.
PermutationCheck: перевірка того, чи є результати обчислення двох багатозмінних многочленів f і g на булевому гіперкубі перестановочними відношеннями f(x) = f(π)x((, щоб забезпечити узгодженість перестановок між змінними многочлена.
LookupCheck: перевірка чи значення多项式 знаходиться в заданій таблиці пошуку, тобто f)Bµ) ⊆ T(Bµ), забезпечуючи, щоб певні значення були в зазначеному діапазоні.
MultisetCheck: перевіряє, чи рівні два багатозначні набори, тобто {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, забезпечуючи узгодженість між кількома наборами.
ProductCheck: Перевірка того, чи дорівнює значення раціонального многочлена певному заявленому значенню ∏x∈Hµ f(x) = s, щоб забезпечити правильність добутку многочлена.
ZeroCheck: перевірка того, чи є будь-яка точка багатозмінного многочлена на булевому гіперкубі нульовою ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, щоб забезпечити розподіл нулів многочлена.
SumCheck: Перевірка того, чи є сума значень багатозмінного полінома оголошеним значенням ∑x∈Hµ f(x) = s. Знижує обчислювальну складність для перевіряючої сторони, перетворюючи задачу оцінки багатозмінного полінома в задачу оцінки однозмінного полінома. Крім того, SumCheck також дозволяє обробку пакетів, вводячи випадкові числа для формування лінійних комбінацій, що дозволяє обробляти кілька прикладів перевірки суми.
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, віртуальне багато
Переглянути оригінал
Ця сторінка може містити контент третіх осіб, який надається виключно в інформаційних цілях (не в якості запевнень/гарантій) і не повинен розглядатися як схвалення його поглядів компанією Gate, а також як фінансова або професійна консультація. Див. Застереження для отримання детальної інформації.
Binius STARKs новий прорив: оптимізація двійкової області та ефективна система доказів
Аналіз принципів STARKs Binius та його оптимізаційні міркування
1 Вступ
Основною причиною низької ефективності STARKs є те, що більшість чисел у фактичних програмах є досить малими, такими як індекси в циклах for, логічні значення, лічильники тощо. Однак, щоб забезпечити безпеку доказів на основі дерева Меркла, під час розширення даних за допомогою кодування Ріда-Соломона багато додаткових надмірних значень займають весь простір, навіть якщо оригінальні значення самі по собі дуже малі. Для вирішення цієї проблеми зменшення розміру простору стало ключовою стратегією.
Як показано в таблиці 1, ширина коду першого покоління STARKs становить 252 біти, ширина коду другого покоління STARKs становить 64 біти, ширина коду третього покоління STARKs становить 32 біти, але 32-бітна ширина коду все ще має значну кількість невикористаного простору. У порівнянні з цим, двійкове поле дозволяє безпосередньо виконувати операції з бітом, кодування компактне та ефективне без будь-яких витрат простору, тобто четверте покоління STARKs.
Таблиця 1: Шлях еволюції STARKs
| Порядок | Ширина | Опис | |------|------|------| | 1-е покоління | 252 біти | на основі полів великих простих чисел | | 2-ге покоління | 64bit | Домен Goldilocks | | 3-є покоління | 32bit | Babybear-діапазон | | 4-те покоління | 1 біт | двійкова область |
Порівняно з такими новими дослідженнями обмежених полів, як Goldilocks, BabyBear, Mersenne31, що з'явилися в останні роки, дослідження двійкових полів можна простежити ще з 80-х років минулого століття. Наразі двійкові поля широко застосовуються в криптографії, типовими прикладами є:
Високий стандарт шифрування (AES), оснований на полі F28;
Galois повідомлення аутентифікації ( GMAC ), на основі поля F2128;
QR-код, що використовує кодування Ріда-Соломона на основі F28;
Первісний протокол FRI та zk-STARK, а також хеш-функція Grøstl, яка потрапила до фіналу SHA-3, заснована на полях F28, є дуже підходящою для рекурсивних хеш-алгоритмів.
Коли використовуються менші поля, операції розширення поля стають дедалі важливішими для забезпечення безпеки. А бінарне поле, яке використовує Binius, повністю залежить від розширення поля для забезпечення його безпеки та фактичної придатності. Більшість поліномів, що беруть участь у обчисленнях Prover, не потребують переходу до розширеного поля, а лише виконуються в базовому полі, що забезпечує високу ефективність у малих полях. Проте випадкові перевірки точок та обчислення FRI все ще потребують поглиблення у більші розширені поля, щоб забезпечити необхідну безпеку.
При побудові системи доказів на основі бінарної області існує 2 практичні проблеми: під час обчислення представлення траси в STARKs використовувана величина області повинна бути більшою за ступінь полінома; під час зобов'язання Merkle tree в STARKs необхідно виконати кодування Ріда-Соломона, використовувана величина області повинна бути більшою за розмір, що розширений кодуванням.
Binius запропонував інноваційне рішення, яке вирішує ці дві проблеми окремо та реалізує їх за допомогою двох різних способів представлення однакових даних: по-перше, використовуючи багатозначний (, а саме багатолінійний ) поліном замість однозмінного полінома, представляючи всю обчислювальну траєкторію через його значення в "гіперкубах" (; по-друге, оскільки довжина кожного виміру гіперкуба дорівнює 2, стандартне розширення Ріда-Соломона, як у STARKs, не може бути застосоване, але гіперкуб може бути розглянутий як квадрат ), на основі якого здійснюється розширення Ріда-Соломона. Цей метод значно підвищує ефективність кодування та обчислювальну продуктивність при забезпеченні безпеки.
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.
Термін "canonical" відноситься до унікального та прямого способу представлення елементів у двійковій області. Наприклад, у найосновнішій двійковій області F2 будь-який рядок довжини k може бути безпосередньо відображений на елемент двійкової області довжини k. Це відрізняється від просторової області, яка не може забезпечити таке нормативне представлення в межах заданої довжини. Хоча 32-бітна проста область може містити 32 біти, не кожен 32-бітний рядок може бути унікально відповідний елементу області, тоді як двійкова область має цю зручність однозначного відображення. У просторовій області Fp поширеними методами редукції є редукція Барретта, редукція Монтгомері та спеціальні методи редукції для певних скінченних областей, таких як Mersenne-31 або Goldilocks-64. У двійковій області F2k поширеними методами редукції є спеціальна редукція ), як у використанні AES ###, редукція Монтгомері (, як у використанні POLYVAL ), та рекурсивна редукція (, як у Tower ). У статті "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" зазначається, що у двійковій області не потрібно вводити переноси при виконанні додавання та множення, а квадратна операція в двійковій області є дуже ефективною, оскільки вона слідує спрощеному правилу (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-бітні підполя ).
! Дослідження Bitlayer: Аналіз принципів Бініуса Старка та оптимізаційне мислення
( 2.2 PIOP: адаптована версія HyperPlonk Product та PermutationCheck------придатні для двійкової області
Дизайн PIOP у протоколі Binius запозичив HyperPlonk і використовує ряд основних механізмів перевірки для верифікації правильності поліномів та множин змінних. До цих основних перевірок входять:
GateCheck: перевірка, чи відповідає конфіденційне свідчення ω та відкритий вхід x обчислювальному співвідношенню C)x, ω###=0, щоб забезпечити правильну роботу схеми.
PermutationCheck: перевірка того, чи є результати обчислення двох багатозмінних многочленів f і g на булевому гіперкубі перестановочними відношеннями f(x) = f(π)x((, щоб забезпечити узгодженість перестановок між змінними многочлена.
LookupCheck: перевірка чи значення多项式 знаходиться в заданій таблиці пошуку, тобто f)Bµ) ⊆ T(Bµ), забезпечуючи, щоб певні значення були в зазначеному діапазоні.
MultisetCheck: перевіряє, чи рівні два багатозначні набори, тобто {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, забезпечуючи узгодженість між кількома наборами.
ProductCheck: Перевірка того, чи дорівнює значення раціонального многочлена певному заявленому значенню ∏x∈Hµ f(x) = s, щоб забезпечити правильність добутку многочлена.
ZeroCheck: перевірка того, чи є будь-яка точка багатозмінного многочлена на булевому гіперкубі нульовою ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, щоб забезпечити розподіл нулів многочлена.
SumCheck: Перевірка того, чи є сума значень багатозмінного полінома оголошеним значенням ∑x∈Hµ f(x) = s. Знижує обчислювальну складність для перевіряючої сторони, перетворюючи задачу оцінки багатозмінного полінома в задачу оцінки однозмінного полінома. Крім того, SumCheck також дозволяє обробку пакетів, вводячи випадкові числа для формування лінійних комбінацій, що дозволяє обробляти кілька прикладів перевірки суми.
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, віртуальне багато