Основною причиною низької ефективності 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 розмір поля, що використовується, повинен бути більшим за ступінь полінома; під час зобов'язання Merkle tree в STARKs необхідно виконати кодування Ріда-Соломона, розмір поля, що використовується, повинен бути більшим за розмір після розширення коду.
Binius запропонував інноваційне рішення для окремого вирішення цих двох проблем, реалізуючи це через два різні способи представлення тих самих даних: по-перше, використовуючи багатозначні (конкретно багатовимірні) многочлени замість одновимірних многочленів, представляючи всю обчислювальну траєкторію через їх значення на "гіперкубах" (hypercubes); по-друге, оскільки довжина кожного виміру гіперкуба дорівнює 2, то не можна здійснити стандартне розширення Ріда-Соломона, як це робиться в STARKs, але можна розглядати гіперкуб як квадрат (square) і на основі цього квадрата проводити розширення Ріда-Соломона. Цей метод значно підвищує ефективність кодування та продуктивність обчислень, забезпечуючи при цьому безпеку.
2 Принципи аналізу
Поточна більшість систем SNARKs зазвичай складається з двох частин:
Інформаційно-теоретичний полінономіальний інтерактивний oracle доказ (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP як основа системи доказів перетворює вхідні обчислювальні відносини в полінономіальні рівності, які можна перевірити. Різні протоколи PIOP, завдяки взаємодії з перевіряючим, дозволяють доказувачу поетапно надсилати полінономи, так що перевіряючий може перевірити правильність обчислень, запитуючи результати оцінки невеликої кількості полінономів. Існуючі протоколи PIOP включають: PLONK PIOP, Spartan PIOP та HyperPlonk PIOP, які по-різному обробляють полінономіальні вирази, що впливає на загальну продуктивність і ефективність системи SNARK.
Поліноміальна схема зобов'язання (Polynomial Commitment Scheme, PCS): Поліноміальна схема зобов'язання використовується для доведення того, чи є рівність поліномів, створених PIOP, істинною. PCS є криптографічним інструментом, за допомогою якого доказувач може зобов'язатися до певного полінома і пізніше перевірити результати оцінки цього полінома, при цьому приховуючи іншу інформацію про поліном. Загальновідомими поліноміальними схемами зобов'язання є KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP) та Brakedown тощо. Різні PCS мають різні характеристики, безпеку та сфери застосування.
Залежно від конкретних вимог, виберіть різні PIOP та PCS, а також поєднайте їх з відповідними скінченними полями або еліптичними кривими, можна створити системи доказів з різними властивостями. Наприклад:
• Halo2: поєднує PLONK PIOP і Bulletproofs PCS та базується на кривій Pasta. При розробці Halo2 акцент був зроблений на масштабованості та усуненні trusted setup у протоколі 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 восьмибітних елементів або 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 вдосконалився в трьох основних аспектах:
Оптимізація ProductCheck: у HyperPlonk ProductCheck вимагає, щоб знаменник U був ненульовим на всіх точках гіперквадрату, а добуток повинен дорівнювати певному значенню; Binius спростив цей процес перевірки, спеціалізуючи це значення на 1, що зменшує обчислювальну складність.
Обробка проблеми ділення на нуль: HyperPlonk не зміг належним чином обробити випадки ділення на нуль, що призвело до неможливості стверджувати, що U є ненульовим у гіперкубі; Binius правильно вирішив цю проблему, навіть у випадках, коли знаменник дорівнює нулю, ProductCheck Binius також може продовжувати обробку, дозволяючи розширити до будь-якого значення добутку.
Перемішування стовпців PermutationCheck: HyperPlonk не має цієї функції; Binius підтримує PermutationCheck між кількома стовпцями, що дозволяє Binius обробляти більш складні випадки перестановки многочленів.
Таким чином, Binius покращив існуючий механізм PIOPSumCheck, підвищивши гнучкість та ефективність протоколу, особливо при обробці більш складних перевірок багатовимірних поліномів, забезпечуючи більш потужну функціональну підтримку. Ці покращення не лише вирішують обмеження HyperPlonk, але й закладають основу для майбутніх систем доказів на основі бінарних полів.
2.3 PIOP: новий многолінійний зсув аргумент------підходить для булевого гіперкутника
У протоколі Binius конструювання та обробка віртуальних多项式 є однією з ключових технологій, яка дозволяє ефективно генерувати та маніпулювати多项式, що походять з вхідних дескрипторів або інших віртуальних多项式. Нижче наведено два ключові методи:
Упаковка：
Переглянути оригінал
Ця сторінка може містити контент третіх осіб, який надається виключно в інформаційних цілях (не в якості запевнень/гарантій) і не повинен розглядатися як схвалення його поглядів компанією Gate, а також як фінансова або професійна консультація. Див. Застереження для отримання детальної інформації.
9 лайків
Нагородити
9
3
Поділіться
Прокоментувати
0/400
BlindBoxVictim
· 08-01 15:40
32bit? Приятель, краще використовуй папір і ручку для підрахунків.
Переглянути оригіналвідповісти на0
AirdropworkerZhang
· 08-01 15:40
Все ще в ролі, ширина місця. Я тільки хочу заробити гроші.
Binius: нова ефективна схема STARKs на основі двійкової області
Аналіз принципів 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 розмір поля, що використовується, повинен бути більшим за ступінь полінома; під час зобов'язання Merkle tree в STARKs необхідно виконати кодування Ріда-Соломона, розмір поля, що використовується, повинен бути більшим за розмір після розширення коду.
Binius запропонував інноваційне рішення для окремого вирішення цих двох проблем, реалізуючи це через два різні способи представлення тих самих даних: по-перше, використовуючи багатозначні (конкретно багатовимірні) многочлени замість одновимірних многочленів, представляючи всю обчислювальну траєкторію через їх значення на "гіперкубах" (hypercubes); по-друге, оскільки довжина кожного виміру гіперкуба дорівнює 2, то не можна здійснити стандартне розширення Ріда-Соломона, як це робиться в STARKs, але можна розглядати гіперкуб як квадрат (square) і на основі цього квадрата проводити розширення Ріда-Соломона. Цей метод значно підвищує ефективність кодування та продуктивність обчислень, забезпечуючи при цьому безпеку.
2 Принципи аналізу
Поточна більшість систем SNARKs зазвичай складається з двох частин:
Інформаційно-теоретичний полінономіальний інтерактивний oracle доказ (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP як основа системи доказів перетворює вхідні обчислювальні відносини в полінономіальні рівності, які можна перевірити. Різні протоколи PIOP, завдяки взаємодії з перевіряючим, дозволяють доказувачу поетапно надсилати полінономи, так що перевіряючий може перевірити правильність обчислень, запитуючи результати оцінки невеликої кількості полінономів. Існуючі протоколи PIOP включають: PLONK PIOP, Spartan PIOP та HyperPlonk PIOP, які по-різному обробляють полінономіальні вирази, що впливає на загальну продуктивність і ефективність системи SNARK.
Поліноміальна схема зобов'язання (Polynomial Commitment Scheme, PCS): Поліноміальна схема зобов'язання використовується для доведення того, чи є рівність поліномів, створених PIOP, істинною. PCS є криптографічним інструментом, за допомогою якого доказувач може зобов'язатися до певного полінома і пізніше перевірити результати оцінки цього полінома, при цьому приховуючи іншу інформацію про поліном. Загальновідомими поліноміальними схемами зобов'язання є KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP) та Brakedown тощо. Різні PCS мають різні характеристики, безпеку та сфери застосування.
Залежно від конкретних вимог, виберіть різні PIOP та PCS, а також поєднайте їх з відповідними скінченними полями або еліптичними кривими, можна створити системи доказів з різними властивостями. Наприклад:
• Halo2: поєднує PLONK PIOP і Bulletproofs PCS та базується на кривій Pasta. При розробці Halo2 акцент був зроблений на масштабованості та усуненні trusted setup у протоколі 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 восьмибітних елементів або 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 вдосконалився в трьох основних аспектах:
Оптимізація ProductCheck: у HyperPlonk ProductCheck вимагає, щоб знаменник U був ненульовим на всіх точках гіперквадрату, а добуток повинен дорівнювати певному значенню; Binius спростив цей процес перевірки, спеціалізуючи це значення на 1, що зменшує обчислювальну складність.
Обробка проблеми ділення на нуль: HyperPlonk не зміг належним чином обробити випадки ділення на нуль, що призвело до неможливості стверджувати, що U є ненульовим у гіперкубі; Binius правильно вирішив цю проблему, навіть у випадках, коли знаменник дорівнює нулю, ProductCheck Binius також може продовжувати обробку, дозволяючи розширити до будь-якого значення добутку.
Перемішування стовпців PermutationCheck: HyperPlonk не має цієї функції; Binius підтримує PermutationCheck між кількома стовпцями, що дозволяє Binius обробляти більш складні випадки перестановки многочленів.
Таким чином, Binius покращив існуючий механізм PIOPSumCheck, підвищивши гнучкість та ефективність протоколу, особливо при обробці більш складних перевірок багатовимірних поліномів, забезпечуючи більш потужну функціональну підтримку. Ці покращення не лише вирішують обмеження HyperPlonk, але й закладають основу для майбутніх систем доказів на основі бінарних полів.
! Дослідження Bitlayer: Аналіз принципів Бініуса Старка та оптимізаційне мислення
2.3 PIOP: новий многолінійний зсув аргумент------підходить для булевого гіперкутника
У протоколі Binius конструювання та обробка віртуальних多项式 є однією з ключових технологій, яка дозволяє ефективно генерувати та маніпулювати多项式, що походять з вхідних дескрипторів або інших віртуальних多项式. Нижче наведено два ключові методи: