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

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

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

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

Загальні питання щодо використання малих полів

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

Наприклад, припустимо, що потрібно довести, що многочлен 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-бітному полі це досить просто: виберіть випадкове 256-бітне число. Але в малих полях доступних r значень приблизно 2 мільярди, тому хоча обсяг роботи для зловмисника величезний, він все ще може спробувати всі можливі варіанти.

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

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

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

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

Звичайний FRI

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

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 ізоляція парних коефіцієнтів A, C ізоляція непарних коефіцієнтів. Якщо задані B та C, можна відновити A: A(x) = B(x^2) + xC(x^2). Якщо ступінь A < 2^20, ступені B та C відповідно є ступенем A та ступенем A - 1. D як випадкова комбінація, ступінь має бути ступенем A.

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

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

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

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

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

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

Коло ПТ

Геніальність Circle STARKs полягає в тому, що для заданого простого числа 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) є правилом множення точок. Ми перетворюємо x-координати двох протилежних точок на колі в x-координати точок після множення.

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

Кола FFTs

Група Circle також підтримує 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 кола, оскільки немає лінійної функції через одну точку, потрібні різні методи. Можна побудувати дотичну функцію, але вона має кратність 2 в точці. Тому потрібно оцінити в двох точках, щоб це довести.

Якщо P дорівнює y1 у x1, а в x2 дорівнює y2, ми вибираємо інтерполяційну функцію L, в якій ці дві точки рівні. Потім доводимо, що P-L в цих двох точках дорівнює нулю, довівши, що частка Q, отримана шляхом ділення L на L, є多项式.

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

Поліноміальні рівняння, які намагається довести 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

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

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

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

• Перший крок: (x,y) та (x,-y) поєднуються
• Другий крок: x з -x паруються
• Наступні кроки: поєднати p та q, щоб Q^i(p) = -Q^i(q)

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

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

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

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

1. Вбудована арифметика: використовується для бізнес-логіки
2. Рідна арифметика: використовується в криптографії (, як хеш Poseidon )
3. Знайти параметри: загальний ефективний метод обчислень

Ключ до ефективності полягає у повному використанні простору обчислень. Тут розмір поля становить 2^31, тому витрати простору незначні. Хеші, такі як Poseidon, повністю використовують кожен біт кожного числа в будь-якому полі.

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

Висновок

Circle STARKs не є більш складними для розробників, ніж STARKs. Основна різниця в реалізації з традиційним FRI полягає в трьох вищезазначених питаннях. Хоча математика, що стоїть за цим, є складною, ця складність добре прихована.

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

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

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