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

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

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

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

Поширені проблеми з використанням менших математичних полів

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

Наприклад, припустимо, що потрібно згенерувати commitment полінома A, який повинен задовольняти A^3(x) + x - A(ωx) = x^N. Протокол може вимагати вибору випадкових координат r і доведення, що A(r) + r - A(ωr) = r^N. Потім зворотньо виводимо A(r) = c, доводячи, що Q = (A - c)/(X - r) є поліномом.

Для запобігання атакам необхідно вибрати r лише після того, як зловмисник надасть A. У протоколах на основі еліптичних кривих можна вибрати випадкове 256-бітне число. Але в STARKs з меншими полями доступно лише близько 2 мільярдів можливих значень r, що може дозволити зловмиснику зламати його методом перебору.

Є два рішення:

1. Провести кілька випадкових перевірок
2. Розширене поле

Багаторазові випадкові перевірки прості та ефективні, але існує проблема з ефективністю. Розширене поле подібне до комплексного, але базується на скінченному полі. Вводимо нове значення α, заявляючи, що α^2=яке-небудь значення. Таким чином, можна виконувати більш складні обчислення на скінченному полі. Розширене поле використовується лише в таких сценаріях, як протокол FRI, більшість математичних операцій все ще виконується на базовому полі.

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

Звичайний FRI

Під час побудови SNARK або STARK першим кроком є арифметизація, перетворення обчислювальної задачі на поліноміальне рівняння. Щоб довести, що воно має розв'язок, потрібно довести, що запропоноване значення є обґрунтованим поліномом і має максимальний ступінь. Для цього використовується техніка випадкових лінійних комбінацій, що застосовується поступово:

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

По суті, B ізолює парні коефіцієнти, C ізолює непарні коефіцієнти. За даними B і C можна відновити A. Якщо ступінь A < 2^20, то ступінь B і C відповідно становить ступінь A та ступінь A - 1. D як випадкова лінійна комбінація, ступінь має бути ступенем A.

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

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

Модуль BabyBear робить так, що його найбільша мультиплікативна підгрупа містить всі ненульові значення, розмір підгрупи дорівнює 2k-1. Можна вибрати підгрупу розміру 2^k, а потім застосувати метод FRI для поступового зменшення степеня полінома до 15. Модуль Mersenne31 робить розмір мультиплікативної підгрупи 2^31-1, може бути поділений лише на 2 один раз, після чого не можна використовувати зазначену техніку.

Поле Mersenne31 підходить для обчислень на 32-бітних ЦПУ/ГПУ. Його характеристика модуля дозволяє виконувати багато операцій за допомогою ефективних бітових операцій. У полі Mersenne31 арифметичні операції виконуються приблизно в 1,3 рази швидше, ніж у полі BabyBear. Якщо FRI вдасться реалізувати в полі Mersenne31, це значно підвищить обчислювальну ефективність.

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

Коло ПТ

Геніальність кругових STARKs полягає в тому, що, given a prime p, можна знайти групу розміром p, яка має подібну двоєдину властивість. Ця група складається з точок, які відповідають певним умовам, такими як набір точок, де x^2 mod p дорівнює певному значенню.

Ці точки слідують правилу додавання: (x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1)

Подвійна форма: 2 * (x,y) = (2x^2 - 1, 2xy)

Ми зосереджуємося на точках на непарних позиціях кола. Спочатку зберемо всі точки на одну пряму: f0(x) = (F(x,y) + F(x,- y))/2

Потім проводиться випадкова лінійна комбінація, отримуючи одномірний多项式 P(x).

З другого туру відображення стає: f0(2x^2-1) = (F(x) + F(-x))/2

Це відображення щоразу зменшує розмір множини вдвічі. Кожен x представляє дві точки: (x,y) та (x,-y). (x → 2x^2 - 1) є законом множення точок.

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

Колові FFT

Кругова група також підтримує FFT, спосіб конструкції схожий на FRI. Об'єктом обробки Circle FFT є простір Рімана-Роша: багаторазові залишки кола (x^2 + y^2 - 1 = 0).

Коефіцієнти, що виходять з Circle FFT, є специфічною основою: {1, y, x, xy, 2x^2 - 1, 2x^2y - y, 2x^3 - x, 2x^3y - xy, 8x^4 - 8x^2 + 1...}

Розробники майже можуть ігнорувати цю деталь. STARKs потрібно лише зберігати поліном як набір значень для оцінювання. FFT використовується для низького масштабу: для заданих N значень генеруються k*N значень на одному й тому ж поліномі.

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

Торгові операції

У протоколі STARK часто використовують операції над певними точками. Наприклад, доведення P(x)=y:

1. Обчисліть коефіцієнт Q = (P - y)/(X - x)
2. Доведіть, що Q є多项式, а не дробом

У групі STARK circle, через відсутність однієї лінійної функції, потрібно використовувати різні техніки замість традиційних методів обчислення. Доказуючи через оцінку в двох точках, додається віртуальна точка, на яку не потрібно звертати увагу.

Якщо багаточлен P дорівнює y1 при x1, а y2 при x2, оберіть інтерполяційну функцію L, яка дорівнює y1 при x1 та y2 при x2: L = ((y2 - y1)/(x2 - x1)) * (x - x1) + у1

Потім доведіть, що P - L в цих двох точках дорівнює нулю, поділивши L на L, щоб довести, що частка Q є поліномом.

! Нова робота Віталіка: Досліджуючи коло STARKs

Зниклий поліном

У STARK багаторазові рівняння зазвичай мають вигляд C(P(x), P(next(x))) = Z(x) · H(x), Z(x) дорівнює нулю на всьому оціночному полю.

У круговій STARK відповідна функція є: Z1(x,y) = y Z2(x,y) = x Zn+1(x,y) = (2 * Zn(x,y)^2) - 1

Зниклі поліноми можна вивести з функцій згортки: звичайний STARK повторює x → x^2, круговий STARK повторює x → 2x^2 - 1.

Зворотний порядок

У STARKs оцінка多项式 зазвичай розташована в зворотному порядку. Наприклад, коли n=16: {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}

Такий порядок дозволяє значенням ранніх груп у процесі оцінки FRI бути сусідніми в порядку, що економить місце.

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

Розмір 16 зворотного порядку: {0, 15, 8, 7, 4, 11, 12, 3, 2, 13, 10, 5, 6, 9, 14, 1}

! Нова робота Віталіка: Досліджуючи коло STARKs

Ефективність

Circle STARKs дуже ефективні. Обчислення зазвичай включають:

1. Нативна арифметика: використовується для бізнес-логіки
2. Первинна арифметика: використовується в криптографії
3. Пошук параметрів: Загальні ефективні методи обчислення

Ключ до ефективності полягає у повному використанні простору обчислювального слідкування. Розмір поля Circle STARKs становить 2^31, що дозволяє мінімізувати витрати простору.

Binius кращий за Circle STARKs, дозволяє змішувати поля різного розміру, забезпечуючи більш ефективну упаковку бітів. Але ціною є більш складна концепція, концепція Circle STARKs відносно проста.

Висновок

Circle STARKs не складніші для розробників, ніж STARKs. Розуміння Circle FRI та Circle FFTs може слугувати шляхом до розуміння інших спеціальних FFTs.

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

1. Максимізація арифметичної ефективності хеш-функцій і підписів тощо
2. Рекурсивна конструкція для забезпечення більшої паралельності
3. Арфметизована віртуальна машина для покращення досвіду розробників

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