Останніми роками тенденція в проектуванні протоколу STARKs полягає в переході на використання менших полів. Найраніша реалізація виробництва STARKs використовувала 256-розрядне поле, тобто модульні обчислення великих чисел. Але така конструкція має низьку ефективність, обробка великих чисел витрачає багато обчислювальної потужності. Щоб вирішити цю проблему, STARKs почали використовувати менші поля: спочатку Goldilocks, потім Mersenne31 і BabyBear.
Ця зміна значно підвищила швидкість доказів. Наприклад, Starkware тепер може доказувати 620 000 хешів Poseidon2 на секунду на ноутбуці M3. Це означає, що якщо ми довіряємо Poseidon2 як хеш-функції, ми можемо вирішити проблему ефективної розробки ZK-EVM. Як працюють ці технології? Як будується доказ на малих полях? У цій статті ми розглянемо ці деталі, зокрема звернемо увагу на Circle STARKs, який є сумісним з полем Mersenne31.
При створенні доказу на основі хешу важливим прийомом є непряме підтвердження властивостей многочлена шляхом оцінки многочлена в випадкових точках. Це може значно спростити процес доказу.
Наприклад, припустимо, що протокол вимагає від вас згенерувати commitment для многочлена A, який задовольняє рівнянню A^3(x) + x - A(ωx) = x^N. Протокол може вимагати, щоб ви вибрали випадкові координати r і довели, що A(r)^3 + r - A(ωr) = r^N. Потім ви можете вивести A(r) = c, і ви доводите, що Q = (A - c)/(X - r) є многочленом.
Щоб запобігти атакам, нам потрібно вибрати r після того, як зловмисник надасть A. У протоколах на основі еліптичних кривих це досить просто: ми можемо вибрати випадкове 256-бітове число як r. Але в малих полях STARKs доступно лише близько 2 мільярдів варіантів r, і зловмисник може зламати його шляхом перебору.
Цю проблему можна вирішити двома способами:
Проведення кількох випадкових перевірок
Розширене поле
Неоднократні випадкові перевірки є простими та ефективними, але можуть бути проблеми з ефективністю. Розширене поле подібне до множини, але базується на скінченному полі. Ми вводимо нове значення α, стверджуючи, що α^2 = деяке значення. Таким чином, створюється нова математична структура, яка може виконувати більш складні обчислення на скінченному полі.
Завдяки розширенню області, у нас є достатньо значень для вибору, що задовольняє вимоги безпеки. Більшість математичних операцій все ще виконується над основними полями, лише коли потрібно підвищити безпеку, використовується більші поля.
FRI (Швидкий рекурсивний Соломонівський інтерактивний )протокол є важливим кроком у побудові SNARK або STARK. Він спрощує процес перевірки, зводячи задачу доведення поліноміальної ступеня d до задачі доведення поліноміальної ступеня d/2. Цей процес можна повторювати кілька разів, кожного разу спрощуючи задачу вдвічі.
Принцип роботи FRI полягає у повторенні процесу спрощення. Починаючи з доведення, що ступінь многочлена дорівнює d, через ряд етапів врешті-решт доводиться, що ступінь дорівнює d/2. Після кожного спрощення ступінь отриманого многочлена поступово зменшується. Якщо на якому-небудь етапі вихід не відповідає очікуванням, то цей раунд перевірки зазнає невдачі.
Для досягнення поступового зменшення області використано двоєдине відображення. Це відображення дозволяє зменшити розмір набору даних вдвічі, зберігаючи при цьому однакові властивості. Цю операцію можна уявити як процес розтягування відрізка по колу на два оберти.
Щоб зробити технологію відображення ефективною, розмір початкової мультиплікативної підгрупи повинен мати велику ступінь 2 в якості фактора. Модуль BabyBear дозволяє його максимальній мультиплікативній підгрупі містити всі ненульові значення, що дуже підходить для цієї технології. Розмір мультиплікативної підгрупи Mersenne31 має лише один фактор ступеня 2, що обмежує його застосування.
Поле Mersenne31 дуже підходить для виконання арифметичних операцій на 32-бітних ЦПУ/ГПУ, приблизно в 1,3 рази швидше, ніж поле BabyBear. Якщо в поле Mersenne31 буде реалізовано FRI, це значно підвищить обчислювальну ефективність.
Геніальність Circle STARKs полягає в тому, що, given a prime p, можна знайти групу розміром p з подібними властивостями двох до одного. Ця група складається з точок, які задовольняють певним умовам, такими як множина точок, для яких x^2 mod p дорівнює певному значенню.
Circle FRI спочатку зводить всі точки в одну пряму, а потім виконує випадкову лінійну комбінацію, щоб отримати одновимірний поліном P(x). З другого раунду відображення змінюється на: f0(2x^2-1) = (F(x) + F(-x))/2
Ця відображення щоразу зменшує розмір множини вдвічі, перетворюючи x-координати двох протилежних точок на колі в x-координати точок, що збільшуються вдвічі. Це можна було б виконати в двовимірному просторі, але одновимірна операція є більш ефективною.
Circle group також підтримує FFT, спосіб побудови подібний до FRI. Circle FFT обробляє об'єкти простору Рімана-Роша, а не строго поліноми. Коефіцієнти, які виходять з Circle FFT, є специфічними для основи Circle FFT.
Як розробник, ви майже можете повністю ігнорувати це. STARKs просто зберігають поліноми як набір значень для оцінки. Єдине місце, де потрібно FFT, це для виконання низькорівневого розширення: маючи N значень, генерувати k*N значень на одному й тому ж поліномі.
У Circle STARKs, через відсутність лінійних функцій, які можна використовувати через єдину точку, необхідно застосовувати різні техніки замість традиційних бізнес-операцій. Ми змушені доводити, оцінюючи в двох точках, додавши віртуальну точку.
Якщо多项式 P в x1 дорівнює y1, в x2 дорівнює y2, ми вибираємо інтерполяційну функцію L, в яких ці дві точки рівні. Потім доведіть, що P-L в двох точках дорівнює нулю, доводячи, що Q, отримане шляхом ділення P на L, є多项式.
У Circle STARKs багаторазовий поліном зникнення виглядає так:
Z1(x,y) = y
Z2(x,y) = x
Zn+1(x,y) = (2 * Zn(x,y)^2) - 1
Це можна вивести з функції згортання: в Circle STARKs повторно використовується x → 2x^2 - 1. Перший раунд потребує спеціальної обробки.
Зворотний порядок бітів
Circle STARKs використовує модифікований зворотний порядок бітів, перевертаючи всі біти, крім останнього, а останній біт визначає, чи перевертати інші біти. Це відображає унікальну складну структуру Circle STARKs.
Circle STARKs дуже ефективні. Обчислення зазвичай включають:
Первісна арифметика: використовується для бізнес-логіки
Первісна арифметика: використовується в криптографії (, як-от хеш Poseidon )
Пошук параметра: виконання різних обчислень за допомогою таблиці значень
Circle STARKs в повній мірі використовують обчислювальний простір, витрачаючи менше. Вони трохи поступаються Binius, але концепція є більш простою.
Висновок
Circle STARKs не є складнішими для розробників, ніж звичайні STARKs. Розуміння Circle FRI та FFTs може допомогти в розумінні інших спеціальних FFTs. На даний момент ефективність базового рівня STARKs наближається до межі, можливі напрямки оптимізації в майбутньому можуть включати:
Максимізація арифметичної ефективності хеш-функцій та підписів
Рекурсивна конструкція для підвищення паралелізації
Арифметична віртуальна машина для покращення досвіду розробки
Ця сторінка може містити контент третіх осіб, який надається виключно в інформаційних цілях (не в якості запевнень/гарантій) і не повинен розглядатися як схвалення його поглядів компанією Gate, а також як фінансова або професійна консультація. Див. Застереження для отримання детальної інформації.
19 лайків
Нагородити
19
4
Репост
Поділіться
Прокоментувати
0/400
NftBankruptcyClub
· 08-09 22:10
Шрифт став меншим, але ефективність зросла...666
Переглянути оригіналвідповісти на0
GasWhisperer
· 08-09 22:08
хм... менші поля = швидші докази, але чи можемо ми довіряти poseidon2? якщо чесно, я відчуваю конфлікт щодо цього компромісу між ефективністю та безпекою.
Переглянути оригіналвідповісти на0
alpha_leaker
· 08-09 21:58
Stark трохи лякає.
Переглянути оригіналвідповісти на0
ChainDetective
· 08-09 21:54
Тільки зрозумів, в основному це зменшена версія для швидкого обчислення.
Circle STARKs: дослідження та прориви у високоефективних ZK-доказах з малими полями
Дослідження Circle STARKs
Останніми роками тенденція в проектуванні протоколу STARKs полягає в переході на використання менших полів. Найраніша реалізація виробництва STARKs використовувала 256-розрядне поле, тобто модульні обчислення великих чисел. Але така конструкція має низьку ефективність, обробка великих чисел витрачає багато обчислювальної потужності. Щоб вирішити цю проблему, STARKs почали використовувати менші поля: спочатку Goldilocks, потім Mersenne31 і BabyBear.
Ця зміна значно підвищила швидкість доказів. Наприклад, Starkware тепер може доказувати 620 000 хешів Poseidon2 на секунду на ноутбуці M3. Це означає, що якщо ми довіряємо Poseidon2 як хеш-функції, ми можемо вирішити проблему ефективної розробки ZK-EVM. Як працюють ці технології? Як будується доказ на малих полях? У цій статті ми розглянемо ці деталі, зокрема звернемо увагу на Circle STARKs, який є сумісним з полем Mersenne31.
! Нова робота Віталіка: Дослідження кола STARKs
Загальні питання при використанні малих полів
При створенні доказу на основі хешу важливим прийомом є непряме підтвердження властивостей многочлена шляхом оцінки многочлена в випадкових точках. Це може значно спростити процес доказу.
Наприклад, припустимо, що протокол вимагає від вас згенерувати commitment для многочлена A, який задовольняє рівнянню A^3(x) + x - A(ωx) = x^N. Протокол може вимагати, щоб ви вибрали випадкові координати r і довели, що A(r)^3 + r - A(ωr) = r^N. Потім ви можете вивести A(r) = c, і ви доводите, що Q = (A - c)/(X - r) є многочленом.
Щоб запобігти атакам, нам потрібно вибрати r після того, як зловмисник надасть A. У протоколах на основі еліптичних кривих це досить просто: ми можемо вибрати випадкове 256-бітове число як r. Але в малих полях STARKs доступно лише близько 2 мільярдів варіантів r, і зловмисник може зламати його шляхом перебору.
Цю проблему можна вирішити двома способами:
Неоднократні випадкові перевірки є простими та ефективними, але можуть бути проблеми з ефективністю. Розширене поле подібне до множини, але базується на скінченному полі. Ми вводимо нове значення α, стверджуючи, що α^2 = деяке значення. Таким чином, створюється нова математична структура, яка може виконувати більш складні обчислення на скінченному полі.
Завдяки розширенню області, у нас є достатньо значень для вибору, що задовольняє вимоги безпеки. Більшість математичних операцій все ще виконується над основними полями, лише коли потрібно підвищити безпеку, використовується більші поля.
! Нова робота Віталіка: дослідження кола STARKs
Регулярний FRI
FRI (Швидкий рекурсивний Соломонівський інтерактивний )протокол є важливим кроком у побудові SNARK або STARK. Він спрощує процес перевірки, зводячи задачу доведення поліноміальної ступеня d до задачі доведення поліноміальної ступеня d/2. Цей процес можна повторювати кілька разів, кожного разу спрощуючи задачу вдвічі.
Принцип роботи FRI полягає у повторенні процесу спрощення. Починаючи з доведення, що ступінь многочлена дорівнює d, через ряд етапів врешті-решт доводиться, що ступінь дорівнює d/2. Після кожного спрощення ступінь отриманого многочлена поступово зменшується. Якщо на якому-небудь етапі вихід не відповідає очікуванням, то цей раунд перевірки зазнає невдачі.
Для досягнення поступового зменшення області використано двоєдине відображення. Це відображення дозволяє зменшити розмір набору даних вдвічі, зберігаючи при цьому однакові властивості. Цю операцію можна уявити як процес розтягування відрізка по колу на два оберти.
Щоб зробити технологію відображення ефективною, розмір початкової мультиплікативної підгрупи повинен мати велику ступінь 2 в якості фактора. Модуль BabyBear дозволяє його максимальній мультиплікативній підгрупі містити всі ненульові значення, що дуже підходить для цієї технології. Розмір мультиплікативної підгрупи Mersenne31 має лише один фактор ступеня 2, що обмежує його застосування.
Поле Mersenne31 дуже підходить для виконання арифметичних операцій на 32-бітних ЦПУ/ГПУ, приблизно в 1,3 рази швидше, ніж поле BabyBear. Якщо в поле Mersenne31 буде реалізовано FRI, це значно підвищить обчислювальну ефективність.
! Нова робота Віталіка: Explore Circle 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-координати точок, що збільшуються вдвічі. Це можна було б виконати в двовимірному просторі, але одновимірна операція є більш ефективною.
! Нова робота Віталіка: дослідження кола STARKs
Кругові FFTs
Circle group також підтримує FFT, спосіб побудови подібний до FRI. Circle FFT обробляє об'єкти простору Рімана-Роша, а не строго поліноми. Коефіцієнти, які виходять з Circle FFT, є специфічними для основи Circle FFT.
Як розробник, ви майже можете повністю ігнорувати це. STARKs просто зберігають поліноми як набір значень для оцінки. Єдине місце, де потрібно FFT, це для виконання низькорівневого розширення: маючи N значень, генерувати k*N значень на одному й тому ж поліномі.
! Нова робота Віталіка: Дослідження кола STARKs
Квотування
У Circle STARKs, через відсутність лінійних функцій, які можна використовувати через єдину точку, необхідно застосовувати різні техніки замість традиційних бізнес-операцій. Ми змушені доводити, оцінюючи в двох точках, додавши віртуальну точку.
Якщо多项式 P в x1 дорівнює y1, в x2 дорівнює y2, ми вибираємо інтерполяційну функцію L, в яких ці дві точки рівні. Потім доведіть, що P-L в двох точках дорівнює нулю, доводячи, що Q, отримане шляхом ділення P на L, є多项式.
! Нова робота Віталіка: Досліджуючи коло STARKs
Зникаючі многочлени
У Circle STARKs багаторазовий поліном зникнення виглядає так: Z1(x,y) = y Z2(x,y) = x Zn+1(x,y) = (2 * Zn(x,y)^2) - 1
Це можна вивести з функції згортання: в Circle STARKs повторно використовується x → 2x^2 - 1. Перший раунд потребує спеціальної обробки.
Зворотний порядок бітів
Circle STARKs використовує модифікований зворотний порядок бітів, перевертаючи всі біти, крім останнього, а останній біт визначає, чи перевертати інші біти. Це відображає унікальну складну структуру Circle STARKs.
! Нова робота Віталіка: Досліджуючи коло STARKs
Ефективність
Circle STARKs дуже ефективні. Обчислення зазвичай включають:
Circle STARKs в повній мірі використовують обчислювальний простір, витрачаючи менше. Вони трохи поступаються Binius, але концепція є більш простою.
Висновок
Circle STARKs не є складнішими для розробників, ніж звичайні STARKs. Розуміння Circle FRI та FFTs може допомогти в розумінні інших спеціальних FFTs. На даний момент ефективність базового рівня STARKs наближається до межі, можливі напрямки оптимізації в майбутньому можуть включати:
! Нове творіння Віталіка: дослідження кола STARKs