Основною причиною низької ефективності STARKs є те, що більшість чисел у фактичних програмах є досить малими, такими як індекси в циклах for, булеві значення, лічильники тощо. Проте, щоб забезпечити безпеку доказів на основі дерева Меркла, під час розширення даних за допомогою кодування Ріда-Соломона багато додаткових надлишкових значень займають весь простір, навіть якщо вихідні значення самі по собі є дуже малими. Для вирішення цієї проблеми зменшення розміру поля стало ключовою стратегією.
Як показано в таблиці 1, ширина кодування STARKs першого покоління становить 252 біт, ширина кодування STARKs другого покоління становить 64 біти, ширина кодування STARKs третього покоління становить 32 біти, але 32-бітна ширина кодування все ще має значну кількість марного простору. У порівнянні з цим, двійкове поле дозволяє безпосередньо виконувати операції з бітами, кодування є компактним і ефективним, без будь-якого марного простору, тобто STARKs четвертого покоління.
Таблиця 1: Шлях еволюції STARKs
| Алгебра | Ширина кодування | Представницька система |
|------|----------|----------|
| 1-ше покоління | 252 біт | StarkWare |
| Друге покоління | 64bit | Plonky2 |
| 3-є покоління | 32bit | Polygon zkEVM |
| 4-те покоління | 1 біт | 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 докази ( 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 + Y2.
Як показано на малюнку 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 вдосконалився в наступних 3 аспектах:
Оптимізація ProductCheck: у HyperPlonk, ProductCheck вимагає, щоб знаменник U був ненульовим в усіх точках гіперкуба, і добуток повинен дорівнювати певному значенню; Binius спростив цей процес перевірки, спеціалізуючи це значення на 1, що зменшує обчислювальну складність.
Обробка проблеми ділення на нуль: HyperPlonk не зміг належним чином обробити випадки ділення на нуль, що призвело до неможливості стверджувати, що U є ненульовим на гіперкубі; Binius правильно вирішив цю проблему, навіть у випадку, коли знаменник дорівнює нулю, ProductCheck Binius також може продовжувати обробку, що дозволяє розширення до будь-якого значення добутку.
Перемішування стовпців PermutationCheck: HyperPlonk не має цієї функції; Binius підтримує перевірку пермітації між кількома стовпцями, що дозволяє Binius обробляти більш складні випадки перестановки многочленів.
Отже, Binius покращив існуючий механізм PIOPSumCheck, підвищивши гнучкість і ефективність протоколу, особливо при обробці більш складних багатозначних поліноміальних перевірок, забезпечуючи більш потужну функціональну підтримку. Ці покращення не лише вирішили обмеження HyperPlonk, а й заклали основу для майбутніх систем доказів на основі бінарних полів.
) 2.3 PIOP: новий аргумент многолінійного зсуву------підходить для булевого гіперкуба
У протоколі Binius віртуальний
Переглянути оригінал
Ця сторінка може містити контент третіх осіб, який надається виключно в інформаційних цілях (не в якості запевнень/гарантій) і не повинен розглядатися як схвалення його поглядів компанією Gate, а також як фінансова або професійна консультація. Див. Застереження для отримання детальної інформації.
15 лайків
Нагородити
15
5
Поділіться
Прокоментувати
0/400
AirdropHunter007
· 07-21 14:04
Скільки можна зібрати вовни?
Переглянути оригіналвідповісти на0
GateUser-3824aa38
· 07-20 17:31
Навіть 32 знаки здаються занадто багатьма, це вже занадто.
Переглянути оригіналвідповісти на0
SchroedingerGas
· 07-20 17:30
газ дійсно занадто абстрактний! Хто зрозуміє?
Переглянути оригіналвідповісти на0
WhaleWatcher
· 07-20 17:23
Зменшення області оптимізації бик, наш круг вже давно слід було змінити.
Переглянути оригіналвідповісти на0
MechanicalMartel
· 07-20 17:08
stark занадто важкий, коли ж він зможе бути швидшим?
Аналіз протоколу Binius: оптимізація та інновації STARKs у двійковій області
Аналіз принципів Binius STARKs та їх оптимізація
1 Вступ
Основною причиною низької ефективності STARKs є те, що більшість чисел у фактичних програмах є досить малими, такими як індекси в циклах for, булеві значення, лічильники тощо. Проте, щоб забезпечити безпеку доказів на основі дерева Меркла, під час розширення даних за допомогою кодування Ріда-Соломона багато додаткових надлишкових значень займають весь простір, навіть якщо вихідні значення самі по собі є дуже малими. Для вирішення цієї проблеми зменшення розміру поля стало ключовою стратегією.
Як показано в таблиці 1, ширина кодування STARKs першого покоління становить 252 біт, ширина кодування STARKs другого покоління становить 64 біти, ширина кодування STARKs третього покоління становить 32 біти, але 32-бітна ширина кодування все ще має значну кількість марного простору. У порівнянні з цим, двійкове поле дозволяє безпосередньо виконувати операції з бітами, кодування є компактним і ефективним, без будь-якого марного простору, тобто STARKs четвертого покоління.
Таблиця 1: Шлях еволюції STARKs
| Алгебра | Ширина кодування | Представницька система | |------|----------|----------| | 1-ше покоління | 252 біт | StarkWare | | Друге покоління | 64bit | Plonky2 | | 3-є покоління | 32bit | Polygon zkEVM | | 4-те покоління | 1 біт | 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 докази ( 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 + Y2.
Як показано на малюнку 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 вдосконалився в наступних 3 аспектах:
Оптимізація ProductCheck: у HyperPlonk, ProductCheck вимагає, щоб знаменник U був ненульовим в усіх точках гіперкуба, і добуток повинен дорівнювати певному значенню; Binius спростив цей процес перевірки, спеціалізуючи це значення на 1, що зменшує обчислювальну складність.
Обробка проблеми ділення на нуль: HyperPlonk не зміг належним чином обробити випадки ділення на нуль, що призвело до неможливості стверджувати, що U є ненульовим на гіперкубі; Binius правильно вирішив цю проблему, навіть у випадку, коли знаменник дорівнює нулю, ProductCheck Binius також може продовжувати обробку, що дозволяє розширення до будь-якого значення добутку.
Перемішування стовпців PermutationCheck: HyperPlonk не має цієї функції; Binius підтримує перевірку пермітації між кількома стовпцями, що дозволяє Binius обробляти більш складні випадки перестановки многочленів.
Отже, Binius покращив існуючий механізм PIOPSumCheck, підвищивши гнучкість і ефективність протоколу, особливо при обробці більш складних багатозначних поліноміальних перевірок, забезпечуючи більш потужну функціональну підтримку. Ці покращення не лише вирішили обмеження HyperPlonk, а й заклали основу для майбутніх систем доказів на основі бінарних полів.
) 2.3 PIOP: новий аргумент многолінійного зсуву------підходить для булевого гіперкуба
У протоколі Binius віртуальний