Глибоке дослідження Circle STARKs

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

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

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

Ця стаття детально розгляне принципи та деталі реалізації Circle STARKs, включаючи:

• Основні виклики, з якими стикаються маленькі поля STARKs
• Основний принцип Circle FRI
• Реалізація Circle FFTs
• Комерційні операції в STARKs кола та зниклі многочлени
• Корекція зворотного порядку
• Аналіз ефективності STARKs

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

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

Виклики використання малих полів

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

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

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

2. Розширене поле: впровадження нових математичних структур для розширення діапазону можливих значень. Наприклад, в полі Mersenne31 ми можемо визначити α так, щоб α^2 = певне конкретне значення, тим самим конструюючи більше поле.

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

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

Принцип Circle FRI

Основна інновація Circle STARKs полягає в Circle FRI. Заданим простим числом p, ми можемо побудувати групу розміру p, яка має властивості, подібні до двохвимірного відображення.

Ця група складається з набору точок, які задовольняють умові x^2 mod p дорівнює певному значенню. Ці точки підпорядковуються особливому правилу додавання:

(x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1)

Формула подвоєння балів:

2 * (x,y) = (2x^2 - 1, 2xy)

Circle FRI спочатку збирає всі точки в одну пряму:

f0(x) = (F(x,y) + F(x,- y))/2

Потім виконується випадкова лінійна комбінація для отримання одновимірного многочлена P(x).

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

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

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

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

Коло FFTs

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

Це означає, що вихідні коефіцієнти Circle FFT не є однозначними, як у звичайному FFT, а є специфічними для базисних функцій Circle FFT.

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

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

Комерційні обчислення та зниклі многочлени

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

Відповідні зміни також потрібні для зникаючих多项式. У Circle STARKs форма зникаючих多项式 виглядає так:

Z1(x,y) = y Z2(x,y) = x
Zn+1(x,y) = (2 * Zn(x,y)^2) - 1

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

Корекція зворотного порядку

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

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

Аналіз ефективності

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

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

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

Висновок

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

Майбутніми напрямками оптимізації STARKs можуть бути:

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

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

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