Глибоке дослідження 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. Потім зворотньо виводимо A(r) = c, доводячи, що Q = (A - c)/(X - r) є поліномом.

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

Цю проблему можна вирішити двома способами:

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

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

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

Регулярний FRI

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

Щоб довести правильність розв'язку, потрібно довести, що запропоноване значення є раціональним多项式 і має максимальний ступінь. Використовуючи техніку випадкових лінійних комбінацій:

• Припустимо, що є значення оцінки多项式 A, потрібно довести, що його ступінь < 2^20
• Розгляньте B(x^2) = A(x) + A(-x), C(x^2) = (A(x) - A(-x))/x
• D є випадковою лінійною комбінацією B і C: D = B + rC

По суті, B ізолює парні коефіцієнти, C ізолює непарні коефіцієнти. B та C можуть відновити A. Якщо степінь A < 2^20, то степені B та C відповідно становлять степінь A та степінь A - 1. D як випадкова комбінація, його степінь повинна бути рівною степеню A.

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

! Нова робота Віталіка: 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)

Ми зосереджуємося на точках на непарних позиціях кола, зводячи всі точки в одну пряму: f0(x) = (F(x,y) + F(x,- y))/2

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

З другого туру відбувається зміна відображення на: 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 є простір Рімана-Роша, а не строго багато-члени.

Як розробник, це можна в основному ігнорувати. STARKs просто зберігають поліном у вигляді набору значень оцінки. FFT в основному використовується для низького розширення: з N значеннями генерується k*N значень на одному і тому ж поліномі.

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

Котирування

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

Якщо多项式P дорівнює y1 у x1, а y2 у x2, виберіть інтерполяційну функцію L, яка дорівнює цим двом точкам. Потім доведіть, що P-L дорівнює нулю в обох точках, а частка Q, отримана шляхом ділення L, є多项式.

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

Зникаючі поліноми

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

Це можна вивести з функції складання: повторне використання x → 2x^2 - 1.

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

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

16 розмірів складаного зворотного порядку: {0, 15, 8, 7, 4, 11, 12, 3, 2, 13, 10, 5, 6, 9, 14, 1}

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

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

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

1. Нативна арифметика бізнес-логіки
2. Нативна арифметика криптографії
3. Знайти параметри

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

Висновок

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

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

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

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