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

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

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

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

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

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

Наприклад, система доказів може вимагати генерувати зобов'язання полінома A, яке задовольняє A^3(x) + x - A(ωx) = x^N. Протокол може вимагати вибору випадкових координат r і доказу A(r) + r - A(ωr) = r^N.

Щоб запобігти атаці, потрібно вибрати r лише після того, як зловмисник надасть A. У 256-бітовому полі це дуже просто, але в малих полях є лише близько 2 мільярдів можливих r, які зловмисник може зламати.

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

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

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

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

Регулярний FRI

Першим кроком у FRI-протоколі є перетворення обчислювальної задачі на многочленне рівняння P(X,Y,Z)=0. Потім необхідно довести, що запропоноване значення є розумним многочленом з обмеженою степенем.

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

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

Коло ПТ

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

Ці точки слідують правилу додавання:(x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1)

Подвійна форма: 2*(x,y) = (2x^2 - 1, 2xy)

Мапування Circle FRI починається з другого раунду: f0(2x^2-1) = (F(x) + F(-x))/2

Ця відображення щоразу зменшує розмір колекції вдвічі, x представляє дві точки: (x, y) та (x, -y). (x → 2x^2 - 1) є законом множення точок.

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

Коло FFTs

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

Коэффициенти Circle FFT є специфічною основою: {1, y, x, xy, 2x^2 - 1, 2x^2y - y, 2x^3 - x, ...}

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

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

Квотування

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

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

Зниклий многочлен у Circle STARK: Z1(x,y) = y Z2(x,y) = x
Zn+1(x,y) = (2 * Zn(x,y)^2) - 1

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

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

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

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

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

1. Нативна арифметика бізнес-логіки
2. Нативна арифметика криптографії (, така як хеш Poseidon )
3. Знайти параметри

Зменшення витрат простору на полях розміром 2^31. Binius є кращим у змішаних розмірах полів, але концепція є більш складною.

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

Висновок

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

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

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

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