Аналіз принципів Binius STARKs та їх оптимізаційні роздуми
1 Вступ
Однією з основних причин низької ефективності STARKs є те, що більшість чисел у реальних програмах є досить малими, такими як індекси в циклах for, логічні значення, лічильники тощо. Однак, щоб забезпечити безпеку доказів на основі дерева Меркла, при розширенні даних за допомогою кодування Ріда-Соломона багато додаткових надмірних значень займають всю область, навіть якщо початкове значення само по собі дуже мале. Щоб вирішити цю проблему, зменшення розміру області стало ключовою стратегією.
Як показано в таблиці 1, ширина кодування STARKs першого покоління становить 252 біт, ширина кодування STARKs другого покоління становить 64 біт, ширина кодування STARKs третього покоління становить 32 біти, але 32-бітна ширина кодування все ще має багато витратного простору. У порівнянні з цим, бінарна область дозволяє безпосередньо виконувати операції над бітами, кодування компактне та ефективне без будь-якого витратного простору, тобто STARKs четвертого покоління.
Таблиця 1: Шлях еволюції STARKs
| Алгебра | Ширина кодування | Представницька реалізація |
|------|----------|------------|
| 1-ше покоління | 252bit | StarkWare |
| 2-ге покоління | 64bit | Plonky2 |
| 3 покоління | 32bit | BabyBear |
| 4-те покоління | 1bit | Binius |
В порівнянні з 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 proof ( 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 вдосконалює в трьох наступних аспектах:
Оптимізація ProductCheck: у HyperPlonk ProductCheck вимагає, щоб знаменник U в гіперкубі всюди був ненульовим, і добуток повинен дорівнювати певному значенню; Binius спростив цей процес перевірки, спеціалізуючи це значення на 1, зменшуючи тим самим обчислювальну складність.
Обробка проблеми ділення на нуль: HyperPlonk не зміг належним чином обробити випадки ділення на нуль, що призвело до неможливості стверджувати, що U є ненульовим на гіперкубі; Binius правильно вирішив цю проблему, навіть коли знаменник дорівнює нулю, ProductCheck Binius також може продовжувати обробку, що дозволяє поширити на будь-яке значення добутку.
Перемішування з перевіркою: HyperPlonk не має цієї функції; Binius підтримує перевірку перемішування між кількома стовпцями, що дозволяє Binius обробляти складніші ситуації з перестановкою багатоцільових поліномів.
Отже, Binius покращив механізм PIOPSumCheck, що існує, підвищивши гнучкість і ефективність протоколу.
! [Бітл
Переглянути оригінал
Ця сторінка може містити контент третіх осіб, який надається виключно в інформаційних цілях (не в якості запевнень/гарантій) і не повинен розглядатися як схвалення його поглядів компанією Gate, а також як фінансова або професійна консультація. Див. Застереження для отримання детальної інформації.
Binius: оптимізовані STARKs на бінарній області
Аналіз принципів Binius STARKs та їх оптимізаційні роздуми
1 Вступ
Однією з основних причин низької ефективності STARKs є те, що більшість чисел у реальних програмах є досить малими, такими як індекси в циклах for, логічні значення, лічильники тощо. Однак, щоб забезпечити безпеку доказів на основі дерева Меркла, при розширенні даних за допомогою кодування Ріда-Соломона багато додаткових надмірних значень займають всю область, навіть якщо початкове значення само по собі дуже мале. Щоб вирішити цю проблему, зменшення розміру області стало ключовою стратегією.
Як показано в таблиці 1, ширина кодування STARKs першого покоління становить 252 біт, ширина кодування STARKs другого покоління становить 64 біт, ширина кодування STARKs третього покоління становить 32 біти, але 32-бітна ширина кодування все ще має багато витратного простору. У порівнянні з цим, бінарна область дозволяє безпосередньо виконувати операції над бітами, кодування компактне та ефективне без будь-якого витратного простору, тобто STARKs четвертого покоління.
Таблиця 1: Шлях еволюції STARKs
| Алгебра | Ширина кодування | Представницька реалізація | |------|----------|------------| | 1-ше покоління | 252bit | StarkWare | | 2-ге покоління | 64bit | Plonky2 | | 3 покоління | 32bit | BabyBear |
| 4-те покоління | 1bit | Binius |
В порівнянні з Goldilocks, BabyBear, Mersenne31 та іншими новими дослідженнями обмежених полів, дослідження двійкових полів можна простежити ще з 80-х років минулого століття. На сьогоднішній день двійкові поля широко використовуються в криптографії, типовими прикладами є:
Коли використовуються менші поля, операції розширення поля стають все більш важливими для забезпечення безпеки. А двійкове поле, яке використовує Binius, повністю покладається на розширення поля для забезпечення його безпеки та фактичної придатності. Більшість поліномів, що залучені до обчислень Prover, не потребують виходу в розширене поле і можуть працювати лише в основному полі, що забезпечує високу ефективність у малих полях. Однак випадкові перевірки точок та обчислення FRI все ще потребують заглиблення в більше розширене поле для забезпечення необхідного рівня безпеки.
При побудові системи доказів на основі бінарних полів існує 2 практичні проблеми: при обчисленні трасування в STARKs розмір поля, що використовується, має бути більшим за ступінь багаточлена; під час зобов'язань Merkle tree в STARKs необхідно виконати кодування Ріда-Соломона, розмір поля, що використовується, має бути більшим за розмір після розширення коду.
Binius запропонував інноваційне рішення, яке окремо вирішує ці дві проблеми, і реалізує їх шляхом представлення тих самих даних двома різними способами: по-перше, використовуючи багатозмінний (, а саме багатоелементний ) поліном замість однозмінного полінома, через його значення на "гіперкубах" (hypercubes) для представлення всієї обчислювальної траєкторії; по-друге, оскільки довжина кожного виміру гіперкуба дорівнює 2, його не можна стандартно розширити, як у випадку з STARKs, але можна розглядати гіперкуб як квадрат (square), на основі якого здійснюється розширення Ріда-Соломона. Цей метод, забезпечуючи безпеку, значно підвищує ефективність кодування та обчислювальну продуктивність.
2 Аналіз принципів
Поточна більшість систем SNARKs зазвичай включає в себе дві частини:
Інформаційно-теоретичний поліноміальний інтерактивний oracle proof ( 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 вдосконалює в трьох наступних аспектах:
Оптимізація ProductCheck: у HyperPlonk ProductCheck вимагає, щоб знаменник U в гіперкубі всюди був ненульовим, і добуток повинен дорівнювати певному значенню; Binius спростив цей процес перевірки, спеціалізуючи це значення на 1, зменшуючи тим самим обчислювальну складність.
Обробка проблеми ділення на нуль: HyperPlonk не зміг належним чином обробити випадки ділення на нуль, що призвело до неможливості стверджувати, що U є ненульовим на гіперкубі; Binius правильно вирішив цю проблему, навіть коли знаменник дорівнює нулю, ProductCheck Binius також може продовжувати обробку, що дозволяє поширити на будь-яке значення добутку.
Перемішування з перевіркою: HyperPlonk не має цієї функції; Binius підтримує перевірку перемішування між кількома стовпцями, що дозволяє Binius обробляти складніші ситуації з перестановкою багатоцільових поліномів.
Отже, Binius покращив механізм PIOPSumCheck, що існує, підвищивши гнучкість і ефективність протоколу.
! [Бітл