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

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

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

Поширені проблеми при використанні менших математичних полів

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

Наприклад, припустимо, що система доказів вимагає від вас згенерувати commitment до полінома A, який повинен задовольняти A^3(x) + x - A(ωx) = x^N(, що є дуже поширеним типом доказу в протоколі ZK-SNARK ). Протокол може вимагати від вас вибрати випадкову координату r і довести, що A(r) + r - A(ωr) = r^N. Потім ви виводите A(r) = c, ви доводите, що Q = (A - c)/(X - r) є поліномом.

Щоб запобігти атакам, нам потрібно вибрати r після того, як зловмисник надасть A. Вибрані параметри повинні походити з досить великої множини, щоб забезпечити неможливість передбачення або вгадування цих параметрів зловмисником, тим самим підвищуючи безпеку системи.

У протоколах на основі еліптичних кривих та STARKs 2019 року ця проблема дуже проста: всі наші математичні операції виконуються над 256-бітними числами, тому ми можемо вибрати r як випадкове 256-бітне число, і цього буде достатньо. Проте, у STARKs на менших полях ми стикаємося з проблемою: є лише близько 2 мільярдів можливих значень r, тому зловмиснику, який хоче підробити доказ, потрібно лише спробувати 2 мільярди разів, хоча це і велика кількість роботи, але для рішучого зловмисника це цілком здійсненно!

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

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

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

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

Це веде до ще одного рішення: розширене поле, розширене поле схоже на множини, але воно базується на скінченних полях. Ми вводимо нове значення, позначене як α, і заявляємо, що воно задовольняє певним відношенням, наприклад, α^2=some value. Таким чином, ми створюємо нову математичну структуру, здатну виконувати більш складні обчислення на скінченних полях. У цьому розширеному полі обчислення множення перетворюється на множення з використанням нового значення α. Тепер ми можемо працювати з парами значень в розширеному полі, а не лише з окремими числами. Наприклад, якщо ми працюємо в полях, таких як Mersenne або BabyBear, таке розширення дозволяє нам мати більше вибору значень, що підвищує безпеку. Щоб ще більше збільшити розмір поля, ми можемо повторно застосовувати ту ж саму техніку. Оскільки ми вже використали α, нам потрібно визначити нове значення, що в Mersenne31 проявляється у виборі α так, щоб α^2=some value.

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

Розширена область фактично використовується лише в протоколі FRI(Fast Reed-Solomon Interactive) та інших сценаріях, які потребують випадкових лінійних комбінацій. Більшість математичних операцій все ще проводяться у базових полях, які зазвичай є полями з модулем p або q. Одночасно практично всі хешовані дані здійснюються у базових полях, тому кожне значення потрібно лише хешувати чотирма байтами. Це дозволяє використовувати ефективність малих полів, одночасно надаючи можливість використовувати більші поля, коли необхідно підвищити безпеку.

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

Регулярний FRI

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

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

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

Сутність полягає в тому, що відбувається ізоляція парних коефіцієнтів A з B, а також ізоляція непарних коефіцієнтів C. Знаючи B та C, ви можете відновити початковий多项式 A:A(x) = B(x^2) + xC(x^2). Якщо ступінь A дійсно менше 2^20, тоді ступінь B та C відповідно буде ступенем A та ступенем A зменшеним на 1. Оскільки комбінація парних та непарних членів не збільшує ступінь. Оскільки D є випадковою лінійною комбінацією B та C, ступінь D також має бути ступенем A, що дозволяє вам перевірити, чи відповідає ступінь A вимогам, за ступенем D.

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

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

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

Давайте детальніше розглянемо, що тут відбувається, а також властивості, необхідні для нормальної роботи всього цього. На кожному кроці ми зменшуємо ступінь полінома вдвічі, одночасно зменшуючи набір точок (, на яких ми зосереджені, вдвічі. Перше є ключем до нормальної роботи протоколу FRI) Fast Reed-Solomon Interactive(. Друге забезпечує надшвидку роботу алгоритму: оскільки розмір кожного раунду зменшується вдвічі в порівнянні з попереднім, загальні витрати на обчислення становлять O)N(, а не O)N*log(N().

Для поступового зменшення області використовується двоєдине відображення, тобто кожна точка відображається на одну з двох точок. Це відображення дозволяє нам зменшити розмір набору даних вдвічі. Однією з важливих переваг цього двоєдиного відображення є те, що воно є повторювальним. Іншими словами, коли ми застосовуємо це відображення, отриманий набір результатів все ще зберігає ті ж атрибути. Припустимо, що ми починаємо з множини множення )multiplicative subgroup(. Ця підгрупа є набором S, в якому кожен елемент x має свій кратний 2x, також в наборі. Якщо застосувати операцію піднесення до квадрату до набору S ), тобто відобразити кожен елемент x на x^2(, новий набір S^2 також зберігатиме ті ж атрибути. Ця операція дозволяє нам продовжувати зменшувати розмір набору даних, поки врешті-решт не залишиться лише одне значення. Хоча теоретично ми можемо зменшити набір даних до залишку лише одного значення, на практиці зазвичай зупиняються, перш ніж досягти більшого менших набору.

Ви можете уявити цю операцію як процес, що розтягує лінію на колі ), наприклад, відрізок або дугу (, що обертається навколо кола двічі. Наприклад, якщо точка на колі знаходиться на позиції x градусів, то після виконання цієї операції вона переміститься на позицію 2x градусів. Кожна точка на колі з позицій від 0 до 179 градусів має відповідну точку на позиціях від 180 до 359 градусів, ці дві точки збігаються. Це означає, що коли ви відображаєте точку з x градусів на 2x градусів, вона збігається з точкою, що знаходиться на позиції x+180 градусів. Цей процес можна повторювати. Тобто, ви можете неодноразово застосовувати цю відображаючу операцію, щоразу переміщуючи точки на колі до їх нових позицій.

! [Нова робота Віталіка: Дослідження кола STARKs])https://img-cdn.gateio.im/webp-social/moments-4e2ceec842bcdcc68f5efb0e9ec2d6ab.webp(

Щоб зробити техніку відображення ефективною, розмір початкової мультиплікативної підгрупи повинен мати великий ступінь 2 як множник. BabyBear - це система з певним модулем, модуль якої має певне значення, що робить її найбільшу мультиплікативну підгрупу, що містить всі ненульові значення, отже, розмір підгрупи становить 2k−1), де k - це кількість біт у модулі (. Такий розмір підгрупи дуже підходить для згаданої техніки, оскільки він дозволяє ефективно зменшувати ступінь полінома шляхом повторного застосування операції відображення. У BabyBear ви можете вибрати підгрупу розміром 2^k ) або безпосередньо використовувати весь набір (, а потім застосувати метод FRI, щоб поступово зменшити ступінь полінома до 15 і в кінці перевірити ступінь полінома. Цей метод використовує властивості модуля та розмір мультиплікативної підгрупи, що робить обчислювальний процес дуже ефективним. Mersenne31 - це ще одна система, модуль якої має певне значення, що робить розмір мультиплікативної підгрупи 2^31 - 1. У цьому випадку розмір мультиплікативної підгрупи має лише один ступінь 2 як множник, що робить можливим ділити його лише один раз на 2. Подальша обробка більше не підходить для згаданої техніки, тобто неможливо використовувати FFT для ефективного зменшення ступеня полінома так, як у BabyBear.

Поле Mersenne31 дуже підходить для виконання арифметичних операцій на існуючих 32-бітних ЦП/ГП. Це пов'язано з характеристиками його модуля ), наприклад, 2^31 - 1(, що дозволяє виконувати багато обчислень за допомогою ефективних бітових операцій: якщо сума двох чисел перевищує модуль, результат можна зменшити, виконавши бітове "і" з модулем.