Аналіз принципів 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 розроблено з акцентом на масштабованість та усунення довіреного налаштування в протоколі 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 елементів 8-бітної баштової області або 128 елементів області F2. Ця гнучкість представлення не потребує жодних обчислювальних витрат, це лише перетворення типу рядка бітів (typecast), що є дуже цікавою та корисною властивістю. Одночасно, елементи малих областей можуть бути упаковані в більші елементи області без додаткових обчислювальних витрат. Протокол Binius використовує цю особливість для підвищення обчислювальної ефективності. Крім того, стаття «On Efficient Inversion in Tower Fields of Characteristic Two» досліджує обчислювальну складність множення, зведення до квадрату та обернення у n-бітних баштових бінарних областях, розкладених на m-бітні підобласті (.
![Bitlayer Research: Аналіз принципів Binius STARKs та їх оптимізаційні роздуми])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
) 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, що існує, підвищивши гнучкість і ефективність протоколу, особливо при обробці більш складних перевірок багатозмінних поліномів, надаючи більш потужну функціональну підтримку. Ці поліпшення не лише вирішують обмеження HyperPlonk, але й закладають основу для майбутніх систем доказів на базі бінарних полів.
![Bitlayer Research：Binius STARKs принципиальний аналіз та оптимізаційні роздуми])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp(
) 2.3 PIOP: новий багатолінійний зсув аргумент------придатний для булевого гіперкуба
У протоколі Binius конструкція та обробка віртуальних поліномів є однією з ключових технологій, що дозволяє ефективно генерувати та оперувати поліномами, що походять з вхідних дескрипторів або інших віртуальних поліномів. Ось два ключових методи:
Упаковка: цей метод
Переглянути оригінал
Ця сторінка може містити контент третіх осіб, який надається виключно в інформаційних цілях (не в якості запевнень/гарантій) і не повинен розглядатися як схвалення його поглядів компанією Gate, а також як фінансова або професійна консультація. Див. Застереження для отримання детальної інформації.
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 розроблено з акцентом на масштабованість та усунення довіреного налаштування в протоколі 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 елементів 8-бітної баштової області або 128 елементів області F2. Ця гнучкість представлення не потребує жодних обчислювальних витрат, це лише перетворення типу рядка бітів (typecast), що є дуже цікавою та корисною властивістю. Одночасно, елементи малих областей можуть бути упаковані в більші елементи області без додаткових обчислювальних витрат. Протокол Binius використовує цю особливість для підвищення обчислювальної ефективності. Крім того, стаття «On Efficient Inversion in Tower Fields of Characteristic Two» досліджує обчислювальну складність множення, зведення до квадрату та обернення у n-бітних баштових бінарних областях, розкладених на m-бітні підобласті (.
![Bitlayer Research: Аналіз принципів Binius STARKs та їх оптимізаційні роздуми])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
) 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, що існує, підвищивши гнучкість і ефективність протоколу, особливо при обробці більш складних перевірок багатозмінних поліномів, надаючи більш потужну функціональну підтримку. Ці поліпшення не лише вирішують обмеження HyperPlonk, але й закладають основу для майбутніх систем доказів на базі бінарних полів.
![Bitlayer Research：Binius STARKs принципиальний аналіз та оптимізаційні роздуми])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp(
) 2.3 PIOP: новий багатолінійний зсув аргумент------придатний для булевого гіперкуба
У протоколі Binius конструкція та обробка віртуальних поліномів є однією з ключових технологій, що дозволяє ефективно генерувати та оперувати поліномами, що походять з вхідних дескрипторів або інших віртуальних поліномів. Ось два ключових методи: