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

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

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

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

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

Поширені питання щодо використання малих полів

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

Щоб запобігти атакам, нам потрібно вибрати випадкові точки після того, як зловмисник надасть поліном. У 256-бітному полі це досить просто, але в малих полях доступних випадкових значень занадто мало, що робить їх легкою мішенню для перебору зловмисників.

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

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

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

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

Регулярний FRI

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

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

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

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

Коло ПТ

Геніальність Circle STARKs полягає в тому, що для простого числа p можна знайти групу розміру p, яка має схожі властивості двох до одного. Ця група складається з точок, що відповідають певним умовам.

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

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

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

Колові FFT

Група Circle також підтримує FFT, спосіб побудови схожий на FRI. Але об'єктами, які обробляє Circle FFT, не є строго поліно́мії, а простір Рімана-Роша.

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

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

Ділення

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

Ми доводимо, оцінюючи в двох точках, що додавання віртуальної точки.

Зникаючі многочлени

У круговій STARK зникаючий многочлен дорівнює:

Z_1(x,y) = y Z_2(x,y) = x
Z_{n+1}(x,y) = (2 * Z_n(x,y)^2) - 1

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

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

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

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

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

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

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

Висновок

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

У майбутньому оптимізація STARK може зосередитися на:

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

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