Дослідження Circle STARKs

У останні роки тенденція в проектуванні протоколів STARKs полягає у переході до використання менших полів. Найперші реалізації STARKs використовували 256-бітні поля, тобто виконували модульні обчислення великих чисел, що робило ці протоколи сумісними з підписами на основі еліптичних кривих. Однак ефективність такого проєкту є досить низькою, зазвичай обробка обчислень великих чисел не має практичного використання і витрачає багато обчислювальної потужності. Щоб вирішити цю проблему, STARKs почали переходити на використання менших полів: спочатку Goldilocks, потім Mersenne31 і BabyBear.

Ця зміна підвищила швидкість доказів, наприклад, Starkware може підтверджувати 620 000 хешів Poseidon2 на одному ноутбуці M3 за секунду. Це означає, що, якщо ми готові довіряти Poseidon2 як хеш-функції, ми можемо вирішити проблему розробки ефективного ZK-EVM. Як же працюють ці технології? Як ці докази створюються на менших полях? Як ці протоколи порівнюються з такими рішеннями, як Binius? У цій статті буде розглянуто ці деталі, з особливим акцентом на рішенні під назвою Circle STARKs, яке має унікальні властивості, сумісні з полем Mersenne31.

! Нова робота Віталіка: Дослідження кола STARKs

Загальні проблеми при використанні менших математичних полів

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

Щоб запобігти атакам, нам потрібно вибрати r після того, як зловмисник надає A. Fiat-Shamir — це технологія, що використовується для підвищення безпеки протоколу, яка дозволяє уникнути атак шляхом встановлення певних параметрів як певного хеш-значення. Вибрані параметри повинні походити з досить великої множини, щоб зловмисник не міг передбачити або вгадати ці параметри, тим самим підвищуючи безпеку системи.

У базованих на еліптичних кривих протоколах і STARKs 2019 року це питання дуже просте: всі наші математичні операції виконуються на 256-бітних числах, тому ми можемо вибрати r як випадкове 256-бітне число, і на цьому все. Проте, у STARKs на менших полях у нас виникає проблема: існує лише близько 2 мільярдів можливих значень r, які можна вибрати, тому атакуючий, який хоче підробити доказ, повинен спробувати 2 мільярди разів, хоча обсяг роботи великий, для рішучого атакуючого це цілком здійсненно!

Цю проблему можна вирішити двома способами:

• Проведення кількох випадкових перевірок
• Розширене поле

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

Це призводить до ще одного рішення: розширене поле, розширене поле схоже на множину, але воно базується на скінченному полі. Ми вводимо нове значення, позначене як α, і стверджуємо, що воно задовольняє певні відносини, наприклад α2=яке-небудь значення. Таким чином, ми створюємо нову математичну структуру, здатну виконувати більш складні обчислення на скінченному полі. У цьому розширеному полі обчислення множення стає множенням з використанням нового значення α. Тепер ми можемо оперувати значеннями пар у розширеному полі, а не лише окремими числами. Наприклад, якщо ми працюємо на полях, таких як Mersenne або BabyBear, таке розширення дозволяє нам мати більше вибору значень, що підвищує безпеку. Щоб ще більше збільшити розмір поля, ми можемо повторно застосувати ту ж саму техніку. Оскільки ми вже використовували α, нам потрібно визначити нове значення, що в Mersenne31 проявляється як вибір α так, щоб α2=яке-небудь значення.

! Нова робота Віталіка: дослідження кола STARKs

За допомогою розширеного домену ми тепер маємо достатню кількість значень для вибору, щоб задовольнити наші вимоги до безпеки. Якщо маємо справу з多项式 з градусом менше d, кожен раунд може забезпечити 104 біти безпеки. Це означає, що у нас є достатня гарантія безпеки. Якщо потрібно досягти більшого рівня безпеки, наприклад, 128 біт, ми можемо додати до протоколу деякі додаткові обчислювальні роботи для посилення безпеки.

Розширена область фактично використовується лише у протоколі FRI та інших сценаріях, де потрібні випадкові лінійні комбінації. Більшість математичних операцій все ще проводиться на базових полях, які зазвичай є полями мод p або q. Водночас майже всі дані хешуються на базових полях, тому кожне значення потрібно лише захешувати в чотири байти. Це дозволяє використовувати ефективність малих полів, одночасно надаючи можливість використовувати більші поля, коли потрібно посилити безпеку.

Регулярний FRI

При побудові SNARK або STARK першим кроком зазвичай є аритметизація. Це перетворення будь-якої обчислювальної задачі в рівняння, в якому деякі змінні та коефіцієнти є поліномами. Зокрема, це рівняння зазвичай виглядає як P(X,Y,Z)=0, де P є поліномом, X, Y та Z є заданими параметрами, а розв'язувач має надати значення X та Y. Як тільки таке рівняння буде отримано, його розв'язок відповідатиме розв'язку основної обчислювальної задачі.

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

• Припустимо, що у вас є значення оцінки многочлена A, і ви хочете довести, що його ступінь менший за 2^20
• Розглянемо багатоцільовий B(x^2) = A(x) + A(-x), C(x^2) = (A(x) - A(-x))/x
• D є випадковою лінійною комбінацією B та C, тобто D=B+rC, де r є випадковим коефіцієнтом.

По суті, те, що відбувається, це те, що B ізолює парні коефіцієнти A, а C ізолює непарні коефіцієнти. З даними B і C ви можете відновити початковий поліном A: A(x) = B(x^2) + xC(x^2). Якщо ступінь A дійсно менша за 2^20, то ступені B і C будуть відповідно дорівнювати ступеню A та ступеню A, зменшеному на 1. Тому що комбінація парних і непарних членів не збільшує ступінь. Оскільки D є випадковою лінійною комбінацією B і C, ступінь D також повинен бути ступенем A, що дозволяє вам перевірити, чи відповідає ступінь A вимогам за допомогою ступеня D.

! Нова робота Віталіка: Explore Circle STARKs

По-перше, FRI спростила процес перевірки, зменшуючи задачу доведення ступеня многочлена до d до задачі доведення ступеня многочлена до d/2. Цей процес можна повторювати кілька разів, щоразу зменшуючи задачу вдвічі.

Принцип роботи FRI полягає в повторенні цього спрощеного процесу. Наприклад, якщо ви починаєте з доведення, що ступінь многочлена дорівнює d, то через серію кроків ви в кінцевому підсумку доведете, що ступінь многочлена дорівнює d/2. Після кожного спрощення ступінь згенерованого многочлена поступово зменшується. Якщо на якомусь етапі вихід не є очікуваним ступенем многочлена, то цей раунд перевірки зазнає невдачі. Якщо хтось намагається просунути многочлен, ступінь якого не дорівнює d, то на другому етапі вихід з певною ймовірністю не відповідатиме очікуванням, а на третьому етапі це буде ще більш імовірно, в результаті чого фінальна перевірка зазнає невдачі. Цей дизайн може ефективно виявляти та відхиляти невідповідні входи. Якщо набір даних на більшості позицій дорівнює многочлену ступеня d, цей набір даних може бути перевірений за допомогою FRI. Однак, щоб створити такий набір даних, зловмисник повинен знати фактичний многочлен, тому навіть легкі дефекти в доведенні підтверджують, що доводячий здатний створити "справжнє" доведення.

Давайте детальніше розглянемо, що тут відбувається, а також властивості, необхідні для правильного функціонування всього цього. На кожному кроці ми зменшуємо ступінь полінома вдвічі, а також зменшуємо множину точок (набір точок, що нас цікавлять) вдвічі. Перше є ключем до нормального функціонування протоколу FRI. Друге дозволяє алгоритму працювати дуже швидко: оскільки масштаб кожного раунду зменшується вдвічі порівняно з попереднім, загальні витрати на обчислення становлять O(N), а не O(N*log(N)).

Щоб досягти поступового зменшення області, використовується бієктивне відображення, тобто кожна точка відображається на одну з двох точок. Це відображення дозволяє зменшити розмір набору даних вдвічі. Однією з важливих переваг цього бієктивного відображення є те, що воно є відтворювальним. Тобто, коли ми застосовуємо це відображення, отриманий результат зберігає ті ж самі властивості. Припустимо, що ми починаємо з мультиплікативної підгрупи. Ця підгрупа є множиною S, в якій кожен елемент x має свій кратний 2x, також у множині. Якщо виконати квадратні операції над множиною S (тобто відображати кожен елемент x у x^2), нова множина S^2 також зберігатиме ті ж самі властивості. Ця операція дозволяє нам продовжувати зменшувати розмір набору даних, поки врешті-решт не залишиться лише одне значення. Хоча теоретично ми можемо зменшити набір даних до одного значення, на практиці зазвичай зупиняються перед досягненням меншої множини.

Ви можете уявити цю операцію як процес розширення лінії (наприклад, відрізка або дуги) по колу, що обертається навколо кола двічі. Наприклад, якщо точка на колі знаходиться на позиції x градусів, то після цієї операції вона переміститься на позицію 2x градусів. Кожна точка на колі з позицій від 0 до 179 градусів має відповідну точку на позиціях від 180 до 359 градусів, які збігаються. Це означає, що коли ви відображаєте точку з x градусів на 2x градусів, вона буде збігатися з точкою, що знаходиться на позиції x+180 градусів. Цей процес можна повторювати. Тобто, ви можете багаторазово застосовувати цю операцію відображення, кожного разу переміщаючи точки на колі на їх нові позиції.

! Нова робота Віталіка: дослідження кола STARKs

Щоб зробити технологію відображення ефективною, розмір початкової мультиплікативної підгрупи повинен мати великий ступінь двійки як фактор. BabyBear - це система з певним модулем, модуль якої дорівнює певному значенню, що дозволяє максимальній мультиплікативній підгрупі містити всі ненульові значення, тому розмір підгрупи дорівнює 2k−1 (де k - кількість біт у модулі). Такий розмір підгрупи дуже підходить для вищезгаданої технології, оскільки він дозволяє ефективно зменшувати ступінь полінома шляхом багаторазового застосування операції відображення. У BabyBear ви можете вибрати підгрупу розміром 2^k (або безпосередньо використовувати весь набір), а потім застосувати метод FRI, щоб поступово зменшити ступінь полінома до 15 і в кінці перевірити ступінь полінома. Цей метод використовує властивості модуля та розмір мультиплікативної підгрупи, що робить обчислювальний процес дуже ефективним. Mersenne31 - це ще одна система, модуль якої дорівнює певному значенню, що робить розмір мультиплікативної підгрупи дорівнює 2^31 - 1. У цьому випадку розмір мультиплікативної підгрупи має лише одну ступінь двійки як фактор, що дозволяє ділити його лише один раз на 2. Подальша обробка більше не підходить для вищезгаданої технології, тобто не можна ефективно зменшувати ступінь полінома, як у BabyBear, за допомогою FFT.

Область Mersenne31 ідеально підходить для виконання арифметичних операцій на існуючих 32-бітних CPU/GPU. Це пов'язано з властивостями її модуля (наприклад, 2^31 - 1), які дозволяють виконувати багато обчислень за допомогою ефективних бітових операцій: якщо результат додавання двох чисел перевищує модуль, можна зменшити його до відповідного діапазону, застосувавши операцію зсуву з модулем. Операція зсуву є дуже ефективною. Для множення можна використовувати спеціальні команди CPU (зазвичай відомі як команди зсуву високого порядку) для обробки результату. Ці команди можуть ефективно обчислювати старші розряди множення, що підвищує ефективність обчислень. В області Mersenne31 завдяки вищезазначеним властивостям арифметичні операції швидші приблизно на 1,3 рази, ніж у області BabyBear. Mersenne31 забезпечує вищу обчислювальну ефективність. Якщо реалізувати FRI в області Mersenne31, це суттєво підвищить обчислювальну ефективність, що зробить застосування FRI.