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

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

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

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

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

Поширені питання щодо використання малих полів

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

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

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

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

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

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

Коло ПТ

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

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

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

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

З другого раунду відображення змінюється на: f0(2x^2-1) = (F(x) + F(-x)) / 2

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

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

Колові FFTs

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

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

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

Торгова операція

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

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

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

Зниклі поліноми

У колі STARK відповідною функцією зникнення є:

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

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

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

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

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

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

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

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

Ключ до ефективності полягає в повному використанні простору в обчислювальному трекінгу. Circle STARKs витрачають менше простору в полі розміром 2^31.

Висновок

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

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

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

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