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

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

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

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

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

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

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

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

Рішення є два:

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

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

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

Регулярний FRI

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

Принцип роботи FRI полягає в повторенні цього спрощеного процесу. Якщо на якомусь етапі вихід не відповідає очікуваному ступеню多项式, то цей раунд перевірки буде невдалим.

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

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

Коло ПТ

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

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

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

Коло FFTs

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

Як розробник, ви можете практично повністю ігнорувати це. STARKs потрібно лише зберігати поліном як значення оцінки. Єдине місце, де потрібен 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

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

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

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

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

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

Ключем досягнення ефективності є повне використання всього обчислювального простору для виконання корисної роботи.

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

Висновок

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

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

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

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