Переслано оригінальний заголовок 'Віталік детально пояснює Binius: ефективна система доказів на основі бінарних полів'

Цей пост в основному призначений для читачів, які приблизно знайомі з криптографією епохи 2019 року, особливо SNARKs та STARKs. Якщо ви не знайомі з цим, я рекомендую спочатку прочитати ці статті. Особлива подяка Джастіну Дрейку, Джиму Посену, Бенджаміну Даймонду та Раді Коєбасічу за відгуки та рецензію.

Протягом останніх двох років STARKs стали важливою та незамінною технологією для ефективного створення легко перевіряючих криптографічних доказів дуже складних висловлювань (наприклад, доведення того, що блок Ethereum є дійсним). Ключова причина полягає в малих розмірах поля: у той час як SNARKs на основі еліптичних кривих вимагають від вас працювати з 256-бітовими цілими числами, щоб бути достатньо безпечними, STARKs дозволяють використовувати набагато менші розміри полів, які ефективніші: спочатку поле Goldilocks (64-бітові цілі числа), а потім Mersenne31 і BabyBear (обидва по 31 біт). Завдяки цим вигодам ефективності, Plonky2, який використовує Goldilocks, в кілька сотень разів швидше доводить багато видів обчислень, ніж його попередники.

Виникає закономірне питання: чи можемо ми довести цю тенденцію до логічного завершення, побудувавши системи доказів, які працюють ще швидше, працюючи безпосередньо над нулями та одиницями? Це саме те, що намагається зробити Бініус, використовуючи ряд математичних трюків, які сильно відрізняють його від SNARK і STARK трирічної давності. У цій статті ми розглянемо причини, чому малі поля роблять генерацію доказів більш ефективною, чому двійкові поля є унікально потужними, а також трюки, які Бініус використовує, щоб змусити докази над двійковими полями працювати так ефективно.

Binius. До кінця цього посту ви повинні зрозуміти кожну частину цієї діаграми.

Узагальнення: скінченні поля

Одним із ключових завдань криптографічної системи доведення є робота з величезними обсягами даних, зберігаючи числа малими. Якщо ви можете стиснути висловлення про велику програму в математичне рівняння, що включає кілька чисел, але ці числа такі ж великі, як і початкова програма, ви нічого не отримали.

Щоб виконати складні арифметичні операції, тримаючи числа маленькими, криптографи використовують, як правило, модулярну арифметику. Ми вибираємо деяке просте "модулюс" p. Оператор% означає "взяти залишок": 15% 7 = 1, 53% 10 = 3, тощо (зазначте, що відповідь завжди невід'ємна, тому, наприклад, -1% 10 = 9).

Можливо, ви вже бачили модулярну арифметику в контексті додавання та віднімання часу (наприклад, який час через чотири години після 9:00?). Але тут ми не просто додаємо та віднімаємо по модулю якогось числа, ми також множимо, ділимо та підносимо до ступеня.

Ми переосмислюємо:

Вищезазначені правила є взаємно узгодженими. Наприклад, якщо p=7, то:

5+3=1 (because 8%7=1)

1-3=5 (because -2%7=5)

2*5=3

3/5=2

Більш загальний термін для такого виду структури - це скінченне поле. Скінченне поле - це математична структура, яка підкоряється звичайним законам арифметики, але де є обмежена кількість можливих значень, і тому кожне значення може бути представлене у фіксованому розмірі.

Модулярна арифметика (або прості поля) є найбільш поширеним типом скінченного поля, але є ще один тип: розширені поля. Ймовірно, ви вже бачили розширене поле: комплексні числа. Ми "уявляємо" новий елемент, який ми позначаємо як 𝑖, і заявляємо, що він задовольняє умову 𝑖2=−1. Потім ви можете брати будь-яку комбінацію звичайних чисел і 𝑖, і проводити з ними математичні операції: (3𝑖+2)∗(2𝑖+4)= 6𝑖2+12𝑖+4𝑖+8=16𝑖+2. Ми так само можемо робити розширення простих полів. Починаючи працювати над полями, які є меншими, розширення простих полів стають все більш важливими для збереження безпеки, і бінарні поля (які використовує Binius) в цілому залежать від розширень, щоб мати практичну корисність.

Узагальнення: аритметизація

Шлях, яким SNARKs та STARKs доводять речі про комп'ютерні програми, полягає в арифметизації: ви перетворюєте висловлення про програму, яку ви хочете довести, у математичне рівняння, що включає поліноми. Дійсне рішення цього рівняння відповідає дійсному виконанню програми.

Для наведення простого прикладу, припустимо, що я обчислив 100-е число Фібоначчі, і я хочу довести вам, що це так. Я створюю поліном 𝐹, який кодує числа Фібоначчі: отже, 𝐹(0)=𝐹(1)=1, 𝐹(2)=2, 𝐹(3)=3, 𝐹(4)=5, і так далі протягом 100 кроків. Умова, яку мені потрібно довести, полягає в тому, що 𝐹(𝑥+2)=𝐹(𝑥)+𝐹(𝑥+1) в межах 𝑥={0,1…98}. Я можу переконати вас у цьому, давши вам частку:

де Z(x) = (x-0) (x-1) …(x-98). Якщо я можу підтвердити, що існує F та H, які задовольняють це рівняння, тоді F повинно задовольняти F(x+2)-F(x+1)-F(x) в цьому діапазоні. Якщо я додатково перевірю, що F задовольняє F(0)=F(1)=1, тоді F(100) фактично повинно бути 100-м числом Фібоначчі.

Якщо ви хочете довести щось складніше, то замінюєте «просте» відношення 𝐹(𝑥+2)=𝐹(𝑥)+𝐹(𝑥+1) більш складним рівнянням, яке в основному говорить про те, що «𝐹(𝑥+1) - це вихід із ініціалізації віртуальної машини зі станом 𝐹(𝑥) та виконанням одного обчислювального кроку». Ви також можете замінити число 100 на більше число, наприклад 100000000, щоб врахувати більше кроків.

Всі SNARKs та STARKs ґрунтуються на цьому ідеї використання простого рівняння над поліномами (іноді векторами та матрицями), щоб представити велику кількість зв'язків між окремими значеннями. Не всі включають перевірку еквівалентності між суміжними обчислювальними кроками так, як у вищезазначеному випадку: PLONK, наприклад, цього не робить, так само як і R1CS. Але багато з найефективніших роблять це, оскільки накладання тієї ж перевірки (або тієї ж кількох перевірок) багато разів полегшує мінімізацію накладних витрат.

Plonky2: від 256-бітних SNARKs та STARKs до 64-бітних... тільки STARKs

П'ять років тому розумний огляд різних типів доказів нульового знання був наступним. Існують два типи доказів: (на основі еліптичних кривих) SNARKs та (на основі хешу) STARKs. Технічно STARKs є типом SNARK, але на практиці звичайно використовувати "SNARK" для посилання лише на довільний тип на основі еліптичних кривих, а "STARK" для посилання на конструкції на основі хешу. SNARKs маленькі, тому їх можна перевірити дуже швидко та легко розмістити на ланцюжку. STARKs великі, але не потребують довірених налаштувань, і вони стійкі до квантових обчислень.

STARKs працюють, розглядаючи дані як поліном, обчислюючи оцінки цього полінома великою кількістю точок, і використовуючи корінь Мерклі з цих розширених даних як "зобов'язання полінома"

Важливою частиною історії тут є те, що SNARKs на основі еліптичних кривих спочатку почали широко використовуватися: приблизно до 2018 року STARKs стали достатньо ефективними для використання, завдяки FRI, а до цього часу Zcash вже працював протягом понад року. SNARKs на основі еліптичних кривих мають ключове обмеження: якщо ви хочете використовувати SNARKs на основі еліптичних кривих, то арифметика в цих рівняннях повинна виконуватися за модулем числа точок на еліптичній кривій. Це велике число, яке зазвичай близько до 2256: наприклад, для кривої bn128 воно складає 21888242871839275222246405745257275088548364400416034343698204186575808495617. Але фактичні обчислення використовують малі числа: якщо ви подумаєте про "реальну" програму у вашій улюбленій мові, то більшість речей, з якими вона працює, це лічильники, індекси в циклах, позиції в програмі, окремі біти, що представляють Істину або Хибність, та інші речі, які майже завжди матимуть лише кілька розрядів.

Навіть якщо ваші «оригінальні» дані складаються з «невеликих» чисел, процес доведення вимагає обчислення часток, розширень, випадкових лінійних комбінацій та інших перетворень даних, що призводить до рівної або більшої кількості об'єктів, які, в середньому, такі великі, як повний розмір вашого поля. Це створює ключову неефективність: для доведення обчислення над n малими значеннями вам потрібно здійснювати ще більше обчислень над n набагато більшими значеннями. Спочатку STARKs успадковували звичку використання поля з 256 бітів від SNARKs, і тому стикалися з такою ж неефективністю.

Розширення Рід-Соломона деяких обчислень поліномів. Навіть якщо початкові значення невеликі, додаткові значення всі розгортаються до повного розміру поля (у цьому випадку 2 в степені 31 -1)

У 2022 році було випущено Plonky2. Основне нововведення Plonky2 полягало в виконанні арифметики за модулем меншого простого числа: 2⁶⁴-2³²+1=18446744069414584321. Тепер кожне додавання або множення завжди можна виконати всього кількома інструкціями на ЦП, а хешування усіх даних разом є в 4 рази швидше, ніж раніше. Але це має свої підводні камені: цей підхід підходить тільки для STARK. Якщо ви спробуєте використати SNARK, з еліптичною кривою такого маленького розміру, еліптична крива стане ненадійною.

Щоб продовжувати залишатися в безпеці, Plonky2 також потребував введення розширених полів. Ключовою технікою перевірки арифметичних рівнянь є "вибір випадкової точки": якщо ви хочете перевірити, чи дійсно дорівнює 𝐻(𝑥)∗𝑍(𝑥) 𝐹(𝑥+2)−𝐹(𝑥+1)−𝐹(𝑥), ви можете вибрати яку-небудь випадкову координату 𝑟, забезпечити докази відкриття поліноміального зобов'язання, що доводять 𝐻(𝑟), 𝑍(𝑟), 𝐹(𝑟), 𝐹(𝑟+1) та 𝐹(𝑟+2), і потім фактично перевірити, чи дорівнює 𝐻(𝑟)∗𝑍(𝑟) 𝐹(𝑟+2)−𝐹(𝑟+1)−𝐹(𝑟). Якщо нападник може передбачити координату заздалегідь, нападник може обманути систему доказів - тому вона повинна бути випадковою. Але це також означає, що координата повинна бути вибрана з набору достатньо великого, щоб нападник не міг вгадати її випадковим чином. Якщо модуль близький до 2²⁵⁶, це, безумовно, так. Але з модулем 2⁶⁴−2³²+1, ми ще не зовсім там, і якщо ми опустимося до 2³¹−1, це абсолютно не так. Спроба підробити доказ два мільярди разів, доки когось не пощастить, абсолютно в межах можливостей атакуючого.

Щоб зупинити це, ми вибираємо 𝑟 з поля розширення. Наприклад, ви можете визначити 𝑦, де 𝑦³=5, і візьміть комбінації 1, 𝑦 та 𝑦². Це збільшує загальну кількість координат ще близько до 2⁹³. Більшість поліномів, обчислених доказуючим, не йдуть у це розширене поле; вони просто використовують цілі числа за модулем 2³¹−1, та ви все ще отримуєте всі ефективності від використання невеликого поля. Але випадкова перевірка точки та обчислення FRI занурюється в це більше поле, щоб забезпечити потрібний рівень безпеки.

Від малих простих чисел до двійкових

Комп'ютери виконують арифметику, представляючи більші числа у вигляді послідовностей нулів і одиниць, та будуючи "схеми" на основі цих бітів для обчислення таких речей, як додавання та множення. Комп'ютери оптимізовані, зокрема, для виконання обчислень з 16-бітними, 32-бітними та 64-бітними цілими числами. Модулі, подібні до 2⁶⁴−2³²+1 and 2³¹−1 обрані не лише тому, що вони вписуються в ці межі, але й тому, що вони гарно узгоджуються з цими межами: ви можете виконувати множення по модулю 2⁶⁴−2³²+1, виконуючи звичайне 32-бітне множення, та зсувати та копіювати виходи бітово на декількох місцях; ця стаття добре пояснює деякі хитрощі.

Що було б ще краще, однак, це виконання обчислень безпосередньо в двійковій системі. Що, якщо додавання може бути "просто" XOR, без необхідності турбуватися про "перенесення" переповнення від додавання 1 + 1 на одному розряді до наступного розряду? Що, якщо множення може бути більш паралельним таким чином? І всі ці переваги прийдуть разом з можливістю представлення значень true/false лише одним бітом.

Захоплення цими перевагами прямого виконання бінарних обчислень - саме те, що намагається зробити Binius. Таблиця з презентації команди Binius на zkSummit показує приріст ефективності:

Незважаючи на приблизно однаковий «розмір», 32-розрядна операція з двійковим полем займає в 5 разів менше обчислювальних ресурсів, ніж операція над 31-бітним полем Мерсенна.

Від одновимірних поліномів до гіперкубів

Припустимо, що ми переконані цим міркуванням і хочемо все зробити за допомогою бітів (нулів і одиниць). Як ми фактично зобов'язуємося до полінома, що представляє мільярд бітів?

Тут ми стикаємося з двома практичними проблемами:

1. Для того щоб поліном представляв багато значень, ці значення повинні бути доступні при обчисленнях полінома: у нашому прикладі чисел Фібоначчі вище, 𝐹(0), 𝐹(1) … 𝐹(100), а в більшому обчисленні індекси будуть доходити до мільйонів. І поле, яке ми використовуємо, повинно містити числа до такого розміру.

2. Доведення будь-чого про значення, до якого ми зобов'язуємося в дереві Меркля (як і всі STARKs), потребує кодування Ріда-Соломона: розширення 𝑛 значень, наприклад, на 8𝑛 значень, використовуючи зайвість, щоб запобігти підвідомому доводу від обману, підробки одного значення в середині обчислення. Це також потребує мати достатньо велике поле: щоб розширити мільйон значень на 8 мільйонів, вам потрібно 8 мільйонів різних точок, в яких ви будете оцінювати поліном.

Ключовою ідеєю в Binius є розв'язання цих двох проблем окремо, причому це робиться шляхом подання одних і тих самих даних двома різними способами. По-перше, сам поліном. SNARK на основі еліптичних кривих, STARK ери 2019 року, Plonky2 та інші системи зазвичай працюють з поліномами над однією змінною: 𝐹(𝑥). З іншого боку, Binius натхненний протоколом Spartan і працює з багатозмінними поліномами: 𝐹(𝑥1,𝑥2…𝑥𝑘). Фактично ми подаємо весь обчислювальний слід на «гіперкубі» оцінок, де кожне 𝑥𝑖 дорівнює 0 або 1. Наприклад, якщо ми хочемо представити послідовність чисел Фібоначчі і все ще використовуємо достатньо велике поле для їх представлення, ми можемо уявити перші шістнадцять з них як щось на зразок цього:

Тобто, F(0,0,0,0) дорівнюватиме 1, F(1,0,0,0) також дорівнюватиме 1, F(0,1,0,0) дорівнюватиме 2 і так далі, поки ми не дійдемо до F(1,1,1,1)=987. Маючи такий гіперкуб оцінок, існує рівно один мультилінійний (ступінь 1 у кожній змінній) многочлен, який продукує ці оцінки. Таким чином, ми можемо думати про цей набір оцінок як про представлення многочлена; Насправді нам ніколи не потрібно морочитися з обчисленням коефіцієнтів.

Цей приклад, звичайно, лише для ілюстрації: на практиці головна мета переходу до гіперкуба полягає в тому, щоб дозволити нам працювати з окремими бітами. "Бініус-рідним" способом підрахунку чисел Фібоначчі було б використовувати вищерозмірний куб, використовуючи кожен набір, наприклад, 16 бітів для зберігання числа. Це вимагає деякої винахідливості для реалізації цілочисельного додавання на основі бітів, але з Бініусом це не занадто складно.

Тепер ми переходимо до кодування стирання. Принцип роботи СТАРКІВ такий: ви берете n значень, Рід-Соломон розширюєте їх до більшої кількості значень (часто 8n, зазвичай від 2n до 32n), а потім випадковим чином вибираєте деякі гілки Меркла з розширення і виконуєте якусь перевірку на них. Гіперкуб має довжину 2 в кожному вимірі. Отже, недоцільно розширювати його безпосередньо: не вистачає «місця» для вибірки гілок Меркла з 16 значень. Що ж робити натомість? Ми прикидаємося, що гіперкуб - це квадрат!

Простий Бініус - приклад

Дивисьтутдля реалізації цього протоколу на Python.

Давайте розглянемо приклад, використовуючи звичайні цілі числа як наше поле для зручності (у реальній реалізації це будуть елементи бінарного поля). Спочатку ми беремо гіперкуб, до якого ми хочемо зобов'язатися, і кодуємо його як квадрат:

Тепер ми розширюємо квадрат Рід-Соломона. Іншими словами, ми розглядаємо кожний ряд як поліном степеня 3, обчислений при x = {0, 1, 2, 3}, і обчислюємо цей же поліном при x = {4, 5, 6, 7}:

Зверніть увагу, що числа швидко вибухають! Ось чому в реальній реалізації ми завжди використовуємо скінченне поле для цього, а не звичайні цілі числа: якщо ми використовували б цілі числа за модулем 11, наприклад, розширення першого рядка було б просто [3, 10, 0, 6].

Якщо ви хочете пограти з розширенням та перевірити ці числа самостійно, ви можете використовувати мій простий розширювальний код Ріда-Соломона тут.

Наступне, ми розглядаємо це розширення як стовпці, і створюємо дерево Меркля зі стовпців. Корінь дерева Меркля - це наше зобов'язання.

Тепер припустимо, що шукач хоче довести оцінку цього многочлена в деякій точці r={r0,r1,r2,r3}. У Бініуса є один нюанс, який робить його дещо слабшим за інші схеми поліноміальних зобов'язань: перфоратор не повинен знати або бути в змозі вгадати s, доки він не звернеться до кореня Меркла (іншими словами, r має бути псевдовипадковою величиною, яка залежить від кореня Меркла). Це робить схему непридатною для «пошуку в базі даних» (напр. "Добре, ви дали мені корінь Меркла, а тепер доведіть мені P(0,0,1,0)!"). Але фактичні протоколи доведення з нульовим розголошенням, які ми використовуємо, як правило, не потребують «пошуку в базі даних»; Їм просто потрібно перевірити многочлен у випадковій точці оцінки. Отже, це обмеження є прийнятним для наших цілей.

Припустимо, ми вибираємо 𝑟={1,2,3,4} (поліном на цьому етапі оцінюється в -137; ви можете підтвердити це з цим кодом). Тепер ми переходимо до процесу фактичного виготовлення доказів. Ми розділили r на дві частини: перша частина {1,2} представляє лінійну комбінацію стовпців у рядку, а друга частина {3,4} представляє лінійну комбінацію рядків. Обчислюємо "тензорний добуток", як для стовпчикової частини:

І для частини рядка:

Що це означає: список усіх можливих продуктів однієї величини з кожного набору. У випадку рядка ми отримуємо:

[(1-r2)(1-r3), (1-r3), (1-r2)r3, r2*r3]

Використовуйте r={1,2,3,4} (таким чином, r2=3 і r3=4):

[(1-3)(1-4), 3(1-4),(1-3)4,34] = [6, -9 -8 -12]

Зараз ми обчислюємо новий «ряд» 𝑡′, взявши цю лінійну комбінацію існуючих рядів. Іншими словами, ми беремо:

Ви можете переглянути те, що тут відбувається, як часткову оцінку. Якби ми помножили повний тензорний добуток ⨂i=03(1−ri,ri) на повний вектор усіх значень, то отримаємо оцінку P(1,2,3,4)=−137. Тут ми множимо частковий тензорний добуток, який використовує лише половину координат оцінки, і зводимо сітку з N значень до рядка N значень. Якщо ви дасте цей рядок комусь іншому, він може використати тензорний добуток іншої половини координат оцінки, щоб завершити решту обчислень.

Доведення надає перевірнику цей новий рядок, 𝑡′, а також докази Меркла деяких випадково вибраних стовпців. Це 𝑂(𝑁) дані. У нашому ілюстративному прикладі доводчик надасть лише останній стовпець; в реальному житті доведеться надати кілька десятків стовпців, щоб досягти відповідного рівня безпеки.

Зараз ми користуємося лінійністю кодів Ріда-Соломона. Ключовою властивістю, яку ми використовуємо, є: взяття лінійної комбінації розширення Ріда-Соломона дає той самий результат, що і розширення Ріда-Соломона лінійної комбінації. Цей вид "незалежності від порядку" часто виникає, коли у вас є дві операції, які є лінійними.

Перевірник робить саме це. Вони обчислюють розширення 𝑡′, і обчислюють ту саму лінійну комбінацію стовпців, яку перевірник обчислював раніше (але тільки для стовпців, наданих перевірником), і перевіряють, що ці два процедури дають однакову відповідь.

У цьому випадку розширення 𝑡′ та обчислення тієї самої лінійної комбінації ([6,−9,−8,12]) стовпця, обидва дають ту саму відповідь: −10746. Це доводить, що корінь Меркла був сконструйований «з доброю вірою» (або принаймні «достатньо близько»), і він відповідає 𝑡′: принаймні значна більшість стовпців сумісні один з одним і з 𝑡′.

Але перевірник все ще повинен перевірити одну річ: фактично перевірити оцінку полінома в {𝑟0..𝑟3}. До цього часу жоден з кроків перевірника фактично не залежав від значення, яке проверник стверджував. Ось як ми робимо цю перевірку. Ми беремо тензорний добуток того, що ми позначили як «частину стовпця» точки оцінки:

У нашому прикладі, де r={1,2,3,4} таким чином, половина обраного стовпця дорівнює {1,2}), це дорівнює:

Тепер ми беремо цю лінійну комбінацію 𝑡′:

Яка точно дорівнює відповіді, яку ви отримуєте, якщо обчислите поліном напряму.

Вищезазначене досить близько до повного опису «простого» протоколу Binius. Це вже має деякі цікаві переваги: наприклад, оскільки дані розділені на рядки та стовпці, вам потрібне лише поле напіврозміру. Але це далеко не наближається до реалізації повних переваг обчислень у двійковій системі. Для цього нам знадобиться повний протокол Binius. Але спочатку давайте отримаємо глибше розуміння двійкових полів.

Бінарне поле

Найменше можливе поле - арифметика за модулем 2, настільки маленьке, що ми можемо записати його таблиці додавання та множення:

Ми можемо створювати більші бінарні поля, використовуючи розширення: якщо ми починаємо з 𝐹2 (цілі числа за модулем 2) і потім визначаємо 𝑥, де 𝑥2=𝑥+1, ми отримуємо наступну таблицю додавання та множення:

Виявляється, що ми можемо розширити бінарне поле до довільно великих розмірів, повторюючи цю конструкцію. На відміну від комплексних чисел над дійсними, де ви можете додати один новий елемент 𝑖, але ви не можете додати їх більше (кватеріони існують, але вони математично дивні, наприклад 𝑎𝑏≠𝑏𝑎), з кінцевими полями ви можете безкінечно додавати нові розширення. Зокрема, ми визначаємо елементи наступним чином:

І так далі. Це часто називають будівництвом вежі, тому що кожне послідовне розширення можна розглядати як додавання нового шару до вежі. Це не єдиний спосіб побудови бінарних полів довільного розміру, але він має деякі унікальні переваги, якими користується Бініус.

Ми можемо представити ці числа у вигляді списку бітів, наприклад 1100101010001111. Перший біт представляє кратні 1, другий біт представляє кратні 𝑥0, наступні біти представляють кратні: 𝑥1, 𝑥1∗𝑥0, 𝑥2, 𝑥2∗𝑥0 і так далі. Це кодування гарне тим, що його можна розкласти на складові частини:

Це досить незвичайна нотація, але мені подобається представляти бінарні елементи поля як цілі числа, беручи бітове представлення, де більш значущі біти перебувають праворуч. Тобто, 1=1, 𝑥₀=01=2, 1+𝑥₀=11=3, 1+𝑥₀+𝑥₂=11001000=19, і так далі. 1100101010001111, у цьому представленні, 61779.

Додавання в двійковому полі - це просто XOR (так само, як і віднімання, до речі); слід зазначити, що це означає x+x=0 для будь-якого x. Щоб перемножити два елементи x*y, існує дуже простий рекурсивний алгоритм: розділіть кожне число навпіл:

Потім розбийте множення на доданки:

Останній шматок - єдиний трохи складний, оскільки вам потрібно застосувати правило скорочення і замінити 𝑅𝑥∗𝑅𝑦∗𝑥𝑘2 на 𝑅𝑥∗𝑅𝑦∗(𝑥𝑘−1∗𝑥𝑘+1). Є більш ефективні способи множення, аналоги алгоритму Карацуби та швидких перетворень Фур'є, але я залишу це як вправу для зацікавленого читача, щоб розібратися в цьому.

Ділення в двійкових полях виконується шляхом поєднання множення та інверсії. "Простий, але повільний" спосіб виконання інверсії - це застосування загального малого теореми Ферма. Також існує більш складний, але ефективніший алгоритм інверсії, який ви можете знайти тутВи можете використовуватикод тутграти з додаванням, множенням та діленням бінарних полів самостійно.

Left: addition table for four-bit binary field elements (ie. elements made up only of combinations of 1， 𝑥₀，𝑥₁ та 𝑥₀𝑥₁).

Правильно: таблиця множення для елементів поля чотирибітового бінарного коду.

Прекрасна річ у цьому типі бінарного поля полягає в тому, що воно поєднує деякі з найкращих частин «звичайних» цілих чисел та модулярної арифметики. Як і звичайні цілі числа, елементи бінарного поля є необмеженими: ви можете продовжувати розширюватися настільки, наскільки вам зручно. Але, якщо ви виконуєте операції над значеннями певного розміру, всі ваші відповіді також залишаються в межах одного і того ж обмеження. Наприклад, якщо ви берете послідовні степені числа 42, ви отримуєте:

Після 255 кроків ви знову на 42²⁵⁵ = 1. Так само як і додатні цілі числа та модулярна арифметика, вони підкоряються звичайним математичним законам: аb=ba, a(b+c)=a b+a*c, є навіть деякі дивні нові закони.

Нарешті, бінарні поля дозволяють легко керувати бітами: якщо ви працюєте з числами, які вміщують 2^kбіти, то всі ваші виведення також вмістять 2 кілобіти. Це уникне незручностей. У EIP-4844 Ethereum кожний «блок» блобу повинен бути цифровим модулем 52435875175126190479447740508185965837690552500527637822603658699938581184513, тому кодування бінарних даних потребує викидання певного простору та додаткової перевірки, щоб переконатися, що кожен елемент зберігає значення менше ніж 2²⁴⁸. Це також означає, що бінарні операції над полями виконуються надзвичайно швидко на комп'ютерах - як на ЦП, так і в теоретично оптимальних конструкціях FPGA та ASIC.

Що все це означає, це те, що ми можемо зробити щось на зразок кодування Ріда-Соломона, яке ми робили вище, таким чином, що повністю уникне “вибуху” цілих чисел, як ми бачили у нашому прикладі, і дуже “вибуховим” способом. “Природній” спосіб, такий тип обчислень, які вміють робити комп'ютери. Атрибут “розділення” бінарних полів - як ми це робимо 1100101010001111=11001010+10001111*x₃і потім розділіть його відповідно до наших потреб, що є також важливим для досягнення великої гнучкості.

Повний Binius

See тутдля реалізації цього протоколу на python.

Тепер, ми можемо дійти до "повного Бінію", який налаштовує "простий Бініум" так, щоб (i) працювати над двійковими полями, і (ii) дозволити нам зафіксувати окремі біти. Цей протокол складний для розуміння, тому що він постійно перемикається між різними способами розгляду матриці бітів; Звичайно, мені знадобилося більше часу, щоб зрозуміти криптографічний протокол. Але як тільки ви зрозумієте двійкові поля, хороша новина полягає в тому, що не існує «складнішої математики», від якої залежить Бініус. Це не еліптичні пари кривих, де є все глибші і глибші кролячі нори алгебраїчної геометрії, щоб спуститися вниз; Тут двійкові поля – це все, що вам потрібно.

Давайте знову подивимося на повну схему:

До цього часу ви повинні бути знайомі з більшістю компонентів. Ідея «згладжування» гіперкуба в сітку, ідея обчислення комбінації рядка та комбінації стовпця як тензорних добутків точки оцінки, і ідея перевірки еквівалентності між «розширенням Ріда-Соломона, а потім обчисленням комбінації рядка», і «обчисленням комбінації рядка, а потім розширенням Ріда-Соломона», усе це було у простому Бініусі.

Що нового в "повному Binius"? Основно три речі:

• Індивідуальні значення в гіперкубі та в квадраті повинні бути бітами (0 або 1)
• Процес розширення розширює біти на більше бітів, групуючи біти в стовпці та тимчасово претендуючи, що вони є більшими елементами поля
• Після кроку комбінації рядків є крок розкладання на елементи "на біти", який перетворює розширення назад на біти.

Ми пройдемо обидва по черзі. Спочатку нова процедура розширення. Код Ріда-Соломона має фундаментальне обмеження, що якщо ви розширяєте значення 𝑛 до значень 𝑘*𝑛, вам потрібно працювати в полі, яке має 𝑘*𝑛 різних значень, які ви можете використовувати як координати. З 𝐹₂ (тобто, біти), ви не можете цього зробити. І тому ми робимо так, ми «упаковуємо» сусідні 𝐹₂елементи разом у більші значення. У цьому прикладі ми упаковуємо по два біти в елементи у {0,1,2,3}, оскільки наше розширення має лише чотири точки оцінки, і цього достатньо для нас. У «реальному» доказі ми, ймовірно, зв'язували б по 16 біт разом. Потім ми виконуємо код Ріда-Соломона над цими упакованими значеннями, і знову розпаковуємо їх у біти.

Тепер комбінація рядків. Щоб зробити «оцінку в довільній точці» криптографічно безпечною, нам потрібно, щоб ця точка була вибрана з досить великого простору, значно більшого, ніж самий гіперкуб. Таким чином, тоді як точки всередині гіперкуба є бітами, оцінки поза гіперкубом будуть набагато більшими. У нашому зазначеному прикладі «комбінація рядків» виявляється [11,4,6,1].

Це створює проблему: ми знаємо, як комбінувати пари бітів у більше значення, а потім робити розширення Ріда-Соломона на цьому, але як ви робите те саме для пар значно більших значень?

Секрет полягає в тому, щоб робити це побітово: ми дивимося на окремі біти кожного значення (наприклад, для того, що ми позначили як "11", це [1,1,0,1]), а потім ми розширюємо рядково. Тобто ми виконуємо процедуру розширення на 1 рядку кожного елемента, потім на рядку 𝑥0, а потім на "𝑥"₁«ряд, потім на 𝑥₀∗𝑥₁строка, і так далі (ну, у нашому іграшковому прикладі ми зупиняємося тут, але в реальній реалізації ми б пішли до 128 рядків (останній з яких - 𝑥₆∗ …∗ 𝑥₀)).

Підсумовуючи:

• Ми беремо біти в гіперкубі та перетворюємо їх у сітку
• Потім ми обробляємо сусідні групи бітів на кожному рядку як більші елементи поля, і виконуємо арифметику над ними для розширення рядків за схемою Ріда-Соломона
• Тоді ми беремо комбінацію рядка кожного стовпця бітів і отримуємо (для квадратів розміром більше, ніж 4x4, набагато менше) стовпець бітів для кожного рядка як вихідний
• Потім ми дивимося на вихід у вигляді матриці, і знову обробляємо біти як рядки

Чому це працює? У «звичайній» математиці можливість (часто) виконувати лінійні операції в будь-якому порядку та отримувати той самий результат перестає працювати, якщо ви починаєте розрізати число на цифри. Наприклад, якщо я почну з числа 345, і помножу його на 8, а потім на 3, я отримаю 8280, і якщо я виконаю ці дві операції у зворотньому порядку, я також отримаю 8280. Але якщо вставити операцію «розбивання за цифрами» між цими двома кроками, все руйнується: якщо ви спочатку виконаєте 8x, а потім 3x, ви отримаєте:

Але якщо зробити 3х, а потім 8х, то отримаємо:

Але в бінарному полі, побудованому з вежевою структурою, цей підхід працює. Причина полягає в їх роздільності: якщо ви перемножите велике значення на мале, те, що відбувається на кожному сегменті, залишається на кожному сегменті. Якщо ми перемножимо 1100101010001111 на 11, це те саме, що і перше розкладання 1100101010001111, яке є

І потім окремо множимо кожну компоненту на 11.

Зібравши все разом

Загалом, системи доведення нульового знання працюють за допомогою висловлювань про поліноми, які одночасно представляють висловлювання про вихідні оцінки: так само, як ми бачили в прикладі Фібоначчі, 𝐹(𝑋+2)−𝐹(𝑋+1)−𝐹(𝑋)=𝑍(𝑋)∗𝐻(𝑋) одночасно перевіряє всі кроки обчислення Фібоначчі. Ми перевіряємо висловлювання про поліноми, доводячи оцінки випадкової точки. Ця перевірка випадкової точки стоїть на варті перевірки всього полінома: якщо поліномне рівняння не відповідає, шанс того, що воно відповідає в конкретній випадковій координаті, дуже малий.

На практиці основним джерелом неефективності є той факт, що в реальних програмах більшість чисел, з якими ми працюємо, є невеликими: індекси в циклах, значення True/False, лічильники та подібні речі. Але коли ми “розширюємо” дані, використовуючи кодування Ріда-Соломона, щоб надати їм потрібну зайвість для забезпечення безпеки перевірок на основі доказів Меркла, більшість “додаткових” значень виявляються повними за розміром поля, навіть якщо початкові значення є невеликими.

Для обходу цього ми хочемо зробити поле як можна меншим. Plonky2 знизив нас з 256-розрядних чисел до 64-розрядних чисел, а потім Plonky3 пішов далі до 31 біту. Але навіть це є підоптимальним. З бінарними полями ми можемо працювати над окремими бітами. Це робить кодування «щільним»: якщо ваші фактичні базові дані мають n бітів, то ваше кодування матиме n бітів, а розширення матиме 8 * n бітів, без додаткового накладання.

Тепер давайте подивимося на діаграму втретє:

У Binius ми зобов'язуємося до мультилінійного полінома: гіперкуб 𝑃(x₀,x₁,…x_k) , де окремі оцінки 𝑃(0,0…0), 𝑃(0,0…1) до 𝑃(1,1,…1) містять дані, які нас цікавлять. Щоб довести оцінку в точці, ми «переінтерпретуємо» ті самі дані як квадрат. Потім ми розширюємо кожний ряд, використовуючи кодування Ріда-Соломона над групами бітів, щоб надати даним необхідну надлишковість для того, щоб запити випадкових гілок Меркла були безпечними. Потім ми обчислюємо випадкову лінійну комбінацію рядків з коефіцієнтами, розробленими так, що новий комбінований ряд фактично містить оцінку, яка нас цікавить. Цей новостворений ряд (який переінтерпретується як 128 рядків бітів) та кілька випадково вибраних стовпців з гілками Меркла подаються на перевірку.

Потім верифікатор робить «комбінацію рядка розширення» (або, скоріше, декілька стовпців розширення), та «розширення комбінації рядка», і перевіряє, що вони відповідають один одному. Потім вони обчислюють комбінацію стовпців, і перевіряють, що це повертає значення, яке проверник стверджує. Ось наша система доказів (або, скоріше, схема зобов'язання поліномів, яка є ключовим будівельним блоком системи доказів).

Що ми не охопили?

• Ефективні алгоритми для розширення рядків, які необхідно фактично зробити обчислювальну ефективність перевіряючого. Ми використовуємо швидкі преобразування Фур'є над бінарними полями, описанітут(хоча точна реалізація буде відмінна, оскільки цей пост використовує менш ефективну конструкцію, не ґрунтуючись на рекурсивному розширенні).
• Арифметизація. Одновимірні многочлени зручні тим, що ви можете робити такі речі, як F(X+2)-F(X+1)-F(X) = Z(X)*H(X), щоб пов'язати сусідні кроки в обчисленні . У гіперкубі «наступний крок» набагато гірше інтерпретується, ніж «Х+1». Ви можете зробити X+k, степені k, але така поведінка стрибків пожертвує багатьма ключовими перевагами Binius. Рішення представлено в Binius paper(Див. розділ 4.3), але це є глибока кроляча нора в самому собі.
• Як фактично безпечно виконувати перевірки конкретних значень. На прикладі Фібоначчі потрібно перевірити межові умови ключа: F(0)=F(1)=1 та значення F(100). Але з «сирим» Бінієм небезпечно перевіряти на передвідомі оціночні точки. Є досить прості способи перетворити перевірку відомої оцінки на невідому оцінку, використовуючи так звані протоколи перевірки суми; але ми не будемо вдаватися в це тут.
• Протоколи пошуку, ще одна технологія, яка недавно почала набирати популярність як засіб створення ультраефективних систем підтвердження. Binius може бути поєднаний з протоколами пошуку для багатьох застосувань.
• Виходячи за межі часу перевірки квадратного кореня. Квадратний корінь дорогий: доказ Binius для бітів має приблизно 11 МБ. Це можна виправити, використовуючи іншу систему доведення для створення «доказу доказу Binius», тим самим отримуючи як ефективність Binius у доведенні основного твердження, так і невеликий розмір доказу. Ще один варіант - набагато складніший протокол FRI-Binius, який створює доказ розміром полілогарифмічний (як звичайний FRI).
• Як Binius впливає на те, що вважається «SNARK-friendly». Основний висновок полягає в тому, що, якщо ви використовуєте Binius, вам вже не потрібно дбати про те, щоб обчислення були «арифметично-дружніми»: «звичайні» хеші більше не є ефективнішими, ніж традиційні арифметичні хеші, множення за модулем або модулем вже не є великою головною болючкою порівняно з множенням за модулем та інше. Але це складна тема; багато речей змінюються, коли все виконується у двійковому вигляді.

Я очікую багато інших поліпшень у техніках доведення на основі бінарного поля в наступних місяцях.

Disclaimer:

1. Ця стаття розміщена з [GatePanews]. Переслати оригінальний заголовок ‘Vitalik розповідає про Binius: ефективна система доведення на основі двійкових полів’. Усі авторські права належать оригінальному автору [Віталік Бутерін*]. Якщо є зауваження до цього перепублікування, будь ласка, зв'яжіться з Gate Learnкоманда, і вони оперативно цим займуться.
2. Предуповідь про відповідальність: Погляди та думки, висловлені в цій статті, є виключно тими автора і не складають жодної інвестиційної поради.
3. Переклади статей на інші мови виконуються командою Gate Learn. Якщо не зазначено інше, копіювання, поширення або плагіатування перекладених статей заборонене.