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

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

Фон

Останніми роками дизайн протоколу STARKs спрямовано на використання менших математичних полів, таких як Goldilocks, Mersenne31 та BabyBear. Ця зміна значно підвищила швидкість доказів, наприклад, Starkware може підтверджувати 620 000 хешів Poseidon2 на ноутбуці M3 за секунду.

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

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

Основний принцип Circle STARKs

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

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

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

Використовуючи це відображення, ми можемо побудувати систему доказів, подібну до FRI, але працювати на менших полях.

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

Коло FFTs

Кругла група також підтримує обчислення FFT, але об'єктами обробки не є строго поліноми, а так звані простори Рімана-Роша. Це означає, що ми розглядаємо будь-які кратні x^2 + y^2 - 1 як нуль.

Це призводить до того, що коефіцієнти, що виходять з Circle FFT, відрізняються від звичайного FFT, а базуються на специфічній основі {1, y, x, xy, 2x^2 - 1, ...}. Але як розробники, ми можемо майже повністю ігнорувати це, просто обробляючи поліном як набір значень для оцінки.

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

Особливі техніки Circle STARKs

комерційні операції

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

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

зниклий поліном

Форма зниклих многочленів у Circle STARKs є:

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

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

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

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

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

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

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

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

Висновок

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

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

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

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