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

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

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

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

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

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

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

Однак така випадкова вибірка в малих полях має проблеми з безпекою. Наприклад, у полі Mersenne31 є лише близько 2 мільярдів можливих точок вибірки, що є здійсненним для рішучого зловмисника.

Існує два рішення:

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

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

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

Загальний FRI

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

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

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

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

Коло ПТ

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

З другого раунду починає відбуватися зміна відображення:

f_0(2x^2-1) = (F(x) + F(-x))/2

Це відображення щоразу зменшує розмір множини точок вдвічі.

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

Коло FFT

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

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

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

Торгові обчислення

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

Ми змушені оцінити два моменти, щоб це довести, і таким чином додати віртуальну точку, на яку не потрібно звертати увагу.

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

У Circle STARKs форма зниклого多项式 виглядає так:

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

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

Обернена послідовність

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

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

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

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

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

Висновок

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

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

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

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