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

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

Використання малих полів може значно підвищити швидкість доказів. Наприклад, Starkware може доводити 620 000 хешів Poseidon2 на секунду на ноутбуці M3. Але малі поля також створюють нові виклики, як забезпечити безпеку в обмеженому виборі.

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

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

Коло ПТ

Основна ідея Circle FRI полягає в визначенні групи точок розміром p на колі, яка має властивість двійкового відображення. Точки в групі задовольняють рівнянню x^2 + y^2 = 1 (mod p).

Процес відображення Circle FRI такий:

1. По-перше, зведіть всі точки на вісь x.
2. Виконати випадкову лінійну комбінацію, щоб отримати одновимірний多项式 P(x)
3. З другої частини починається використання відображення f_0(2x^2-1) = (F(x) + F(-x))/2

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

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

Круглі FFT

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

Вихідні коефіцієнти Circle FFT є специфічними для бази Circle FFT: {1, y, x, xy, 2x^2 - 1, 2x^2y - y, ...}

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

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

Інші технічні деталі

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

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

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

Circle STARKs дуже ефективні на полі простих чисел з 31 бітами:

• Повністю використовує обчислювальний простір
• Підходить для бізнес-логіки та криптографічних обчислень
• Підтримка ефективних операцій з таблицями пошуку

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

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

Підсумок

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

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

• Оптимізація хеш-функцій та інших основних криптографічних примітивів
• Використання рекурсивного конструктора для підвищення паралельності
• Покращення арифметики віртуальної машини для підвищення досвіду розробки

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

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

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