На відміну від SNARKs на основі еліптичних кривих, STARKs можна розглядати як SNARKs на основі хешування. Основною причиною низької ефективності STARKs є те, що в реальних програмах більшість чисел є відносно малими, такими як індекси циклів, булеві значення, лічильники тощо. Однак, щоб забезпечити безпеку доказів на основі дерева Меркла, при використанні кодування Ріда-Соломона для розширення даних, багато надлишкових значень заповнюють весь простір, навіть якщо початкове значення дуже мале. Щоб вирішити цю проблему, зменшення розміру поля стає ключовою стратегією.
Перший покоління STARKs має ширину кодування 252 біти, другий - 64 біти, третій - 32 біти, але 32-бітне кодування все ще має велику кількість вільного місця. У порівнянні з цим, двійкове поле дозволяє безпосередньо виконувати операції над бітами, кодування є компактним, ефективним і без втрат, що можна вважати четвертим поколінням STARKs.
Дослідження бінарних полів, на відміну від обмежених полів, таких як Goldilocks, BabyBear, Mersenne31, які були виявлені в останні роки, восходить до 80-х років XX століття. Наразі бінарні поля широко застосовуються в криптографії, таких як AES(F28 поле), GMAC(F2128 поле), кодування Ріда-Соломона для QR-кодів(F28 тощо. Оригінальні протоколи FRI та zk-STARK, а також хеш-функція Grøstl, що потрапила до фіналу SHA-3, також базуються на полі F28.
Використання менших полів робить операції розширення все важливішими для забезпечення безпеки. Бінус, що використовується, повністю залежить від розширення поля для гарантії безпеки та доступності. Більшість обчислень Prover, що стосуються багаточленів, потребують лише операцій у базовому полі, що забезпечує високу ефективність у малих полях. Проте випадкові перевірки точок і обчислення FRI все ще потрібно здійснювати у більшому розширеному полі, щоб забезпечити необхідний рівень безпеки.
Існує дві практичні проблеми під час побудови системи доказів на основі бінарної області:
При обчисленні сліду в STARKs, використане поле повинно бути більшим за ступінь полінома.
При зобов'язанні Merkle-дерева в STARKs потрібно виконати кодування Ріда-Соломона, використане поле має бути більшим за розмір після розширення коду.
Binius запропонував інноваційне рішення, яке окремо вирішує ці дві проблеми:
Використовуйте багатовимірний ) багатолінійний ( многочлен замість одновимірного многочлена, представляючи всю обчислювальну траєкторію через його значення на "гіперкубі".
Оскільки довжина кожного виміру гіперкуба дорівнює 2, неможливо виконати стандартне розширення Ріда-Соломона, як у випадку з STARKs, але гіперкуб можна розглядати як квадрат, і на основі цього квадрата виконати розширення Ріда-Соломона.
Цей метод значно підвищує ефективність кодування та обчислювальні характеристики, забезпечуючи при цьому безпеку.
![Bitlayer Research: Аналіз принципів Binius STARKs та їх оптимізаційні міркування])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
2 Аналіз принципу
Поточна більшість систем SNARK зазвичай складається з двох частин:
Доказ множинних інтерактивних предсказувачів інформаційної теорії ) PIOP (:
Як основа системи доказів, входять обчислювальні відносини в перевіряємий поліноміальний рівняння. Через взаємодію з перевіряючим, доказувач поступово надсилає поліноми, що дозволяє перевіряючому перевірити правильність обчислень, запитуючи невелику кількість поліномів для оцінки результатів. Існуючі протоколи PIOP включають PLONK PIOP, Spartan PIOP та HyperPlonk PIOP.
Поліноміальні зобов'язання ) PCS (:
Використовується для підтвердження того, чи є полігональне рівняння, згенероване PIOP, істинним. PCS є криптографічним інструментом, що дозволяє доказнику зобов'язатися до певного полінома і пізніше перевірити його оцінку, приховуючи при цьому іншу інформацію про поліном. Загальновживані PCS включають KZG, Bulletproofs, FRI та Brakedown.
Вибір різних PIOP та PCS відповідно до вимог, а також поєднання з відповідними скінченними полями або еліптичними кривими дозволяє створити системи доказів з різними властивостями. Наприклад:
Арфметизація на основі баштової двійкової області: становить основу обчислень, реалізація спрощених операцій у двійковій області
Адаптація перевірки добутку та перестановки HyperPlonk: забезпечення ефективної узгодженості перевірки між змінними та перестановками
Нова мульти-лінійна теорія зсуву: оптимізація ефективності верифікації мульти-лінійних відносин на малих полях
Поліпшення доведення пошуку Lasso: забезпечення гнучкості та безпеки механізму пошуку
Схема зобов'язань малих поліномів: реалізація ефективної системи доказів у двійковому полі, зменшення витрат, пов'язаних з великим полем.
![Bitlayer Research：Binius STARKs принципи аналізу та його оптимізаційні міркування])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp(
) 2.1 Обмежене поле: арифметика на основі веж бінарних полів
Турбінна двійкова область є ключем до реалізації швидких перевіряємих обчислень, головним чином завдяки ефективним обчисленням та ефективній арифметиці. Двійкова область по суті підтримує надзвичайно ефективні арифметичні операції, що робить її ідеальним вибором для продуктивних криптографічних застосувань. Структура двійкової області підтримує спрощений арифметичний процес, а операції, що виконуються в двійковій області, можуть бути представлені у компактній та легко перевіряємій алгебраїчній формі. Ці характеристики разом із можливістю повною мірою використовувати її ієрархічні властивості через турбінну структуру роблять двійкову область особливо підходящою для масштабованих систем доказів, таких як Binius.
"канонічний" вказує на унікальний і прямий спосіб представлення елементів у бінарному полі. Наприклад, у базовому бінарному полі F2 будь-який k-бітний рядок може бути безпосередньо відображений на k-бітний елемент бінарного поля. Це відрізняється від простих полів, які не можуть надати таке нормативне представлення в заданій кількості бітів. Хоча 32-бітне просте поле може міститися в 32 бітах, не кожен 32-бітний рядок може унікально відповідати одному елементу поля, тоді як бінарне поле має зручність такого відповідного відображення один до одного.
У полях простих чисел Fp поширеними методами редукції є редукція Барретта, редукція Монтгомері, а також спеціальні методи редукції для певних скінченних полів, таких як Mersenne-31 або Goldilocks-64. У двійкових полях F2k звичайними методами редукції є спеціальна редукція ###, яку використовує AES (, редукція Монтгомері ), яку використовує POLYVAL (, і рекурсивна редукція ), така як Tower (.
У статті «Дослідження простору дизайну реалізацій ECC-апаратури у простих полях проти бінарних полів» зазначено, що в бінарному полі не потрібно вводити переноси ні в операціях додавання, ні в операціях множення, а також обчислення квадратів у бінарному полі дуже ефективні, оскільки вони дотримуються спрощеного правила )X + Y(2 = X2 + Y2.
128-бітний рядок може бути інтерпретований різними способами в контексті бінарного поля. Його можна розглядати як унікальний елемент у 128-бітному бінарному полі або розкладати на два 64-бітних елементи поля, чотири 32-бітних елементи поля, 16 восьмибітних елементів поля або 128 елементів F2. Ця гнучкість представлення не вимагає жодних обчислювальних витрат, а є просто перетворенням типу рядка, що є дуже цікавим і корисним атрибутом. Водночас, менші елементи поля можуть бути упаковані в більші елементи поля без додаткових обчислювальних витрат. Протокол 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 покращив механізм PIOP SumCheck, що існує, підвищивши гнучкість і ефективність протоколу, особливо при обробці більш складних перевірок багатовимірних поліномів, надаючи більш потужну підтримку функцій. Ці покращення не лише вирішують обмеження HyperPlonk, але й закладають основи для майбутніх систем доказів на основі бінарних полів.
( 2.3 PIOP: новий мультихвильовий зсув аргумент------підходить для булевого гіперквадрату
У протоколі Binius конструкція та обробка віртуальних многочленів є однією з ключових технологій, що дозволяє ефективно генерувати та обробляти многочлени, що походять з вхідних дескрипторів або інших віртуальних многочленів. Нижче наведено два ключових методи:
Packing: Цей метод оптимізує операції, упаковуючи сусідні менші елементи у словниковому порядку в більші елементи. Оператор Pack націлений на блочні операції розміром 2κ і об'єднує їх в єдиний елемент у високорозмірному просторі. Завдяки мультилінійному розширенню )Multilinear Extension, MLE###, цей віртуальний поліном може бути ефективно оцінений і оброблений, перетворюючи функцію t в інший поліном, що підвищує обчислювальну продуктивність.
Оператори зсуву: оператор зсуву перерозташовує елементи блоку, виконуючи циклічний зсув на основі заданого зсуву o. Цей метод підходить для блоків розміром 2b, кожен блок виконує зсув відповідно до зсуву. Оператор зсуву визначається за допомогою підтримки функції, що забезпечує узгодженість і ефективність при обробці віртуальних поліномів. Оцінка складності цієї конструкції зростає лінійно зі збільшенням розміру блоку, що робить його особливо підходящим для обробки великих наборів даних або високорозмірних сцен у булевому гіперкубі.
( 2.4 PIOP: адаптована версія аргументу Lasso lookup------підходить для бінарної області
Протокол Lasso дозволяє стороні, що доводить, зобов'язати вектор a ∈ Fm і підтвердити, що всі його елементи існують у заздалегідь визначеній таблиці t ∈ Fn. Lasso відкриває концепцію "знаходження сингулярностей" )lookup singularities### та може бути застосований до схем комітменту багатолінійних поліномів. Його ефективність проявляється в наступних двох аспектах:
Ефективність доказів: для m пошуків у таблиці розміру n, доказник повинен зобов'язатися m+n елементами поля. Ці елементи поля дуже малі, всі знаходяться в множині {0,...,m}. У схемах зобов'язання, заснованих на багаторазових експонентних обчисленнях, обчислювальні витрати доказника становлять O(m + n) разів групових операцій( таких як
Переглянути оригінал
Ця сторінка може містити контент третіх осіб, який надається виключно в інформаційних цілях (не в якості запевнень/гарантій) і не повинен розглядатися як схвалення його поглядів компанією Gate, а також як фінансова або професійна консультація. Див. Застереження для отримання детальної інформації.
Binius: Оптимізація та інновації STARKs на основі двійкової області
Аналіз принципів Binius STARKs та їх оптимізація
1 Вступ
На відміну від SNARKs на основі еліптичних кривих, STARKs можна розглядати як SNARKs на основі хешування. Основною причиною низької ефективності STARKs є те, що в реальних програмах більшість чисел є відносно малими, такими як індекси циклів, булеві значення, лічильники тощо. Однак, щоб забезпечити безпеку доказів на основі дерева Меркла, при використанні кодування Ріда-Соломона для розширення даних, багато надлишкових значень заповнюють весь простір, навіть якщо початкове значення дуже мале. Щоб вирішити цю проблему, зменшення розміру поля стає ключовою стратегією.
Перший покоління STARKs має ширину кодування 252 біти, другий - 64 біти, третій - 32 біти, але 32-бітне кодування все ще має велику кількість вільного місця. У порівнянні з цим, двійкове поле дозволяє безпосередньо виконувати операції над бітами, кодування є компактним, ефективним і без втрат, що можна вважати четвертим поколінням STARKs.
Дослідження бінарних полів, на відміну від обмежених полів, таких як Goldilocks, BabyBear, Mersenne31, які були виявлені в останні роки, восходить до 80-х років XX століття. Наразі бінарні поля широко застосовуються в криптографії, таких як AES(F28 поле), GMAC(F2128 поле), кодування Ріда-Соломона для QR-кодів(F28 тощо. Оригінальні протоколи FRI та zk-STARK, а також хеш-функція Grøstl, що потрапила до фіналу SHA-3, також базуються на полі F28.
Використання менших полів робить операції розширення все важливішими для забезпечення безпеки. Бінус, що використовується, повністю залежить від розширення поля для гарантії безпеки та доступності. Більшість обчислень Prover, що стосуються багаточленів, потребують лише операцій у базовому полі, що забезпечує високу ефективність у малих полях. Проте випадкові перевірки точок і обчислення FRI все ще потрібно здійснювати у більшому розширеному полі, щоб забезпечити необхідний рівень безпеки.
Існує дві практичні проблеми під час побудови системи доказів на основі бінарної області:
Binius запропонував інноваційне рішення, яке окремо вирішує ці дві проблеми:
Цей метод значно підвищує ефективність кодування та обчислювальні характеристики, забезпечуючи при цьому безпеку.
![Bitlayer Research: Аналіз принципів Binius STARKs та їх оптимізаційні міркування])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
2 Аналіз принципу
Поточна більшість систем SNARK зазвичай складається з двох частин:
Доказ множинних інтерактивних предсказувачів інформаційної теорії ) PIOP (: Як основа системи доказів, входять обчислювальні відносини в перевіряємий поліноміальний рівняння. Через взаємодію з перевіряючим, доказувач поступово надсилає поліноми, що дозволяє перевіряючому перевірити правильність обчислень, запитуючи невелику кількість поліномів для оцінки результатів. Існуючі протоколи PIOP включають PLONK PIOP, Spartan PIOP та HyperPlonk PIOP.
Поліноміальні зобов'язання ) PCS (: Використовується для підтвердження того, чи є полігональне рівняння, згенероване PIOP, істинним. PCS є криптографічним інструментом, що дозволяє доказнику зобов'язатися до певного полінома і пізніше перевірити його оцінку, приховуючи при цьому іншу інформацію про поліном. Загальновживані PCS включають KZG, Bulletproofs, FRI та Brakedown.
Вибір різних PIOP та PCS відповідно до вимог, а також поєднання з відповідними скінченними полями або еліптичними кривими дозволяє створити системи доказів з різними властивостями. Наприклад:
Binius включає п'ять ключових технологій:
Арфметизація на основі баштової двійкової області: становить основу обчислень, реалізація спрощених операцій у двійковій області
Адаптація перевірки добутку та перестановки HyperPlonk: забезпечення ефективної узгодженості перевірки між змінними та перестановками
Нова мульти-лінійна теорія зсуву: оптимізація ефективності верифікації мульти-лінійних відносин на малих полях
Поліпшення доведення пошуку Lasso: забезпечення гнучкості та безпеки механізму пошуку
Схема зобов'язань малих поліномів: реалізація ефективної системи доказів у двійковому полі, зменшення витрат, пов'язаних з великим полем.
![Bitlayer Research：Binius STARKs принципи аналізу та його оптимізаційні міркування])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp(
) 2.1 Обмежене поле: арифметика на основі веж бінарних полів
Турбінна двійкова область є ключем до реалізації швидких перевіряємих обчислень, головним чином завдяки ефективним обчисленням та ефективній арифметиці. Двійкова область по суті підтримує надзвичайно ефективні арифметичні операції, що робить її ідеальним вибором для продуктивних криптографічних застосувань. Структура двійкової області підтримує спрощений арифметичний процес, а операції, що виконуються в двійковій області, можуть бути представлені у компактній та легко перевіряємій алгебраїчній формі. Ці характеристики разом із можливістю повною мірою використовувати її ієрархічні властивості через турбінну структуру роблять двійкову область особливо підходящою для масштабованих систем доказів, таких як Binius.
"канонічний" вказує на унікальний і прямий спосіб представлення елементів у бінарному полі. Наприклад, у базовому бінарному полі F2 будь-який k-бітний рядок може бути безпосередньо відображений на k-бітний елемент бінарного поля. Це відрізняється від простих полів, які не можуть надати таке нормативне представлення в заданій кількості бітів. Хоча 32-бітне просте поле може міститися в 32 бітах, не кожен 32-бітний рядок може унікально відповідати одному елементу поля, тоді як бінарне поле має зручність такого відповідного відображення один до одного.
У полях простих чисел Fp поширеними методами редукції є редукція Барретта, редукція Монтгомері, а також спеціальні методи редукції для певних скінченних полів, таких як Mersenne-31 або Goldilocks-64. У двійкових полях F2k звичайними методами редукції є спеціальна редукція ###, яку використовує AES (, редукція Монтгомері ), яку використовує POLYVAL (, і рекурсивна редукція ), така як Tower (.
У статті «Дослідження простору дизайну реалізацій ECC-апаратури у простих полях проти бінарних полів» зазначено, що в бінарному полі не потрібно вводити переноси ні в операціях додавання, ні в операціях множення, а також обчислення квадратів у бінарному полі дуже ефективні, оскільки вони дотримуються спрощеного правила )X + Y(2 = X2 + Y2.
128-бітний рядок може бути інтерпретований різними способами в контексті бінарного поля. Його можна розглядати як унікальний елемент у 128-бітному бінарному полі або розкладати на два 64-бітних елементи поля, чотири 32-бітних елементи поля, 16 восьмибітних елементів поля або 128 елементів F2. Ця гнучкість представлення не вимагає жодних обчислювальних витрат, а є просто перетворенням типу рядка, що є дуже цікавим і корисним атрибутом. Водночас, менші елементи поля можуть бути упаковані в більші елементи поля без додаткових обчислювальних витрат. Протокол 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 покращив механізм PIOP SumCheck, що існує, підвищивши гнучкість і ефективність протоколу, особливо при обробці більш складних перевірок багатовимірних поліномів, надаючи більш потужну підтримку функцій. Ці покращення не лише вирішують обмеження HyperPlonk, але й закладають основи для майбутніх систем доказів на основі бінарних полів.
! Дослідження Bitlayer: Аналіз принципів Бініуса Старка та оптимізаційне мислення
( 2.3 PIOP: новий мультихвильовий зсув аргумент------підходить для булевого гіперквадрату
У протоколі Binius конструкція та обробка віртуальних многочленів є однією з ключових технологій, що дозволяє ефективно генерувати та обробляти многочлени, що походять з вхідних дескрипторів або інших віртуальних многочленів. Нижче наведено два ключових методи:
Packing: Цей метод оптимізує операції, упаковуючи сусідні менші елементи у словниковому порядку в більші елементи. Оператор Pack націлений на блочні операції розміром 2κ і об'єднує їх в єдиний елемент у високорозмірному просторі. Завдяки мультилінійному розширенню )Multilinear Extension, MLE###, цей віртуальний поліном може бути ефективно оцінений і оброблений, перетворюючи функцію t в інший поліном, що підвищує обчислювальну продуктивність.
Оператори зсуву: оператор зсуву перерозташовує елементи блоку, виконуючи циклічний зсув на основі заданого зсуву o. Цей метод підходить для блоків розміром 2b, кожен блок виконує зсув відповідно до зсуву. Оператор зсуву визначається за допомогою підтримки функції, що забезпечує узгодженість і ефективність при обробці віртуальних поліномів. Оцінка складності цієї конструкції зростає лінійно зі збільшенням розміру блоку, що робить його особливо підходящим для обробки великих наборів даних або високорозмірних сцен у булевому гіперкубі.
( 2.4 PIOP: адаптована версія аргументу Lasso lookup------підходить для бінарної області
Протокол Lasso дозволяє стороні, що доводить, зобов'язати вектор a ∈ Fm і підтвердити, що всі його елементи існують у заздалегідь визначеній таблиці t ∈ Fn. Lasso відкриває концепцію "знаходження сингулярностей" )lookup singularities### та може бути застосований до схем комітменту багатолінійних поліномів. Його ефективність проявляється в наступних двох аспектах: