原文：Безпека та надійність — глибоке занурення в STARK Security

Переклад і вичитка: "Китайська спільнота Starknet"

Рекомендовані короткі факти

• Неінтерактивний STARK походить від інтерактивних доказів Oracle (IOP), скомпільованих у неінтерактивні докази в моделі стохастичного оракула.

• У цій статті пояснюється останні оновлення документації ethSTARK і надається вичерпний і детальний аналіз безпеки протоколу ethSTARK у моделі випадкового оракула.

Детальне пояснення безпеки STARK

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

(Деталі дивіться в документації ethSTARK (версія 1.2), розділ 6, а також у важливій та всебічній незалежній роботі Блок та інших на цю тему).

Що ми намагаємося досягти через безпековий аналіз? Ми хочемо запобігти «успішним атакам» на систему STARK, які викликані хибними заявами та STARK-доказами, прийнятими STARK-верифікатором на основі цих (хибних) заяв. Оскільки хибні заяви можуть бути небезпечними та з'являтися в різних формах і масштабах, ми прагнемо безпечно захистити систему від усіх хибних заяв. Будь-яка хибна заява, навіть незначна, як 1+1=3, якщо вона поєднана з STARK-доказом, прийнятим STARK-верифікатором, буде вважатися «успішною атакою» на систему. (Ті, хто має криптографічний бекграунд, можуть бути зацікавлені дізнатися, що STARK також відповідає більш сильним концепціям безпеки, таким як надійність знань, але для простоти ця стаття зосереджується на простих випадках надійності).

Як ми формально визначаємо безпеку системи STARK? Ми визначаємо її через аналіз «помилки надійності». «Помилка надійності» приблизно вимірює очікувану «вартість», яку зловмисник повинен витратити для успішної атаки (тобто знайти STARK-доказ для хибної заяви, який буде прийнятий STARK-верифікатором). З математичної точки зору, помилка надійності є функцією (t), вхідними даними якої є параметр часу t, що представляє собою обчислювальний час, який зловмисник готовий витратити для атаки, а вихід - ймовірність успіху зловмисника (знайти переконливий доказ для хибної заяви). Чим більша «вартість» t, яку зловмисник готовий витратити, тим вища його ймовірність успіху.

На даний момент ми визначили безпеку STARK як функцію (t), що відрізняється від того, як люди зазвичай обговорюють безпеку в крипто-твіттері. У твіттері ви можете почути таку фразу: «Цей протокол має 96 біт безпеки». Як це перетворюється на наше визначення безпеки? На це немає єдиної відповіді, оскільки люди трохи по-різному розуміють «x біт безпеки»:

• Строго кажучи, це означає, що для будь-якого t між 1 та 2⁹⁶, помилка надійності становить (t) 2⁹⁶. Ймовірність успіху зловмисника з часом виконання не більше 2⁹⁶ є дуже малою, менше 2⁹⁶, тобто менше одного мільярда мільярдів.

• Більш вільне, а може й більш поширене тлумачення полягає в тому, що 96 біт безпеки означає, що для будь-якого t існує випадок t/(t) 2⁹⁶. Це означає, що ймовірність успіху має (обернено) лінійний зв'язок з часом виконання. Якщо зловмисник витрачає 2⁸⁶ часу, його ймовірність успіху не перевищує 2¹⁰.

У цій статті ми обговоримо другий варіант.

Від IOP до STARK з 96 бітами безпеки

Отже, як ми можемо довести, що схема має 96 біт безпеки? Щоб відповісти на це питання, нам потрібно зрозуміти високу структуру, що складає STARK. STARK складається з трьох основних частин: IOP (інтерактивне свідчення), дерево Меркла та хеш Фіата-Шаміра; основна частина, на якій ми зосереджуємося, - це IOP. Як тільки ці компоненти визначені, ми можемо скомпілювати їх, щоб створити STARK. Ми детально розглянемо ці компоненти, що вони собою представляють і як їх комбінувати.

Першим компонентом, який ми повинні перевірити, є IOP: IOP подібний до стандартного інтерактивного доказу, де доказувач і верифікатор взаємодіють кілька разів (ми обмежені публічними монетами, тобто верифікатор надсилає випадкові виклики лише доказувачу). У IOP верифікатор не читає повністю повідомлення доказувача, натомість він вибирає невелику частину бітів з кожної інформації доказувача. Це причина, чому скомпільований STARK може досягти стислості.

З IOP як побудувати STARK? Інформація доказувача може бути дуже великою (насправді, вона може бути навіть довшою, ніж само обчислення). Щоб стиснути цю інформацію, ми використовуємо дерево Меркла. Дерево Меркла - це бінарне хеш-дерево, де кожен листовий вузол представляє запит або відповідь в IOP. Корінь дерева є зобов'язанням всіх даних. Коли верифікатор хоче прочитати певну позицію в інформації, доказувач надає значення цієї позиції та шлях перевірки. Верифікатор може використовувати цей шлях, щоб перевірити правильність значення. Верифікатор IOP читає лише невелику кількість бітів з інформації доказувача. Тому використання дерева Меркла дозволяє реалізувати стислий протокол (з малим обсягом зв'язку).

Стиснення раундів

Ми можемо вибрати інтерактивний STARK, але щоб спростити процес генерації STARK, ми зазвичай обираємо неінтерактивний STARK, що дозволяє верифікатору не чекати зовнішньої інформації при побудові STARK. Насправді, це спосіб розгортання всіх STARK-систем на даний момент, а також спосіб побудови протоколу ethSTARK. Неінтерактивний STARK також є особливим випадком прозорого SNARK (прозорий означає, що для їх інстанцій необхідні довірені налаштування; «протокол Артура-Мерліна» або «публічне монетне IOP»). Для цього останнім кроком є застосування алгоритму Фіата-Шаміра, щоб стиснути кілька раундів взаємодії до одного повідомлення, яке ми називаємо STARK-доказом. Перетворення Фіата-Шаміра - це метод перетворення інтерактивного протоколу в неінтерактивний. Доказувач, «взаємодіючи з хеш-функцією», симулює інтерактивний протокол. Щоб отримати випадковий виклик для i-го раунду, доказувач хешує частковий запис i-го раунду та інтерпретує вихід як наступний виклик.

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

Наприклад, з IOP, що має 96 раундів, і до нього додається наступний хак: якщо перший біт випадковості верифікатора в кожному з 96 раундів є 0, тоді верифікатор прийме (не перевіряючи жодних доказів). Ми можемо побачити, що додавання цього хаку до верифікатора лише додає термін 2⁹⁶ до помилки надійності IOP. Однак після перетворення Фіата-Шаміра зловмисник може легко змінити інформацію доказувача, щоб усі хеш-значення починалися з 0, що дозволяє йому зламати систему за дуже короткий час. Не бійтеся, ця жахлива ситуація є лише теоретичним прикладом і не застосовується до розгорнутого STARK. Отже, давайте розглянемо, чому наш STARK зрештою є безпечним. Коротше кажучи, ми доведемо, що зловмисник може виконати максимум t кроків, ймовірність успіху атаки становитиме не більше (t) t 2⁹⁶.

IOP та поетапна надійність

Безпека STARK залежить від його базового IOP. Але що означає, що IOP має 96 біт безпеки? За стандартним визначенням, помилка надійності IOP становить 2⁹⁶: це означає, що ймовірність того, що будь-який зловмисник (незалежно від часу виконання) зможе обманути верифікатора, становить не більше 2-96. Проте, як ми вже обговорювали, надійність IOP - це лише одна з трьох частин, і цього недостатньо, щоб STARK, скомпільований з усіх трьох кроків, мав 96 біт безпеки. Натомість, якщо припустити, що STARK має 96 біт поетапної надійності (іноді також використовується подібне визначення, яке називається надійністю відновлення стану), то безпека скомпільованого STARK буде доведена.

Інтуїтивно, «поетапна надійність» (round-by-round soundness) означає, що кожен етап має 96 біт безпеки, а не лише вся протокол. Кажучи детальніше, поетапна надійність вказує на існування предиката, який може отримати часткові записи протоколу та сказати нам, чи є цей запис «обманним»: «пустий запис» не є «обманним», тоді як лише якщо верифікатор приймає, повний запис є «обманним». Нарешті, для будь-якого часткового запису, який не є «обманом» для верифікатора, ймовірність того, що запис стане «обманним» на наступному етапі, не перевищує 2⁹⁶. Якщо існує рішення з цими властивостями, ми скажемо, що протокол має 96 біт поетапної надійності (цей предикат не вимагає ефективного обчислення).

В багатьох випадках люди аналізують лише надійність IOP, не аналізуючи його поетапну надійність. Безперечно, важко уявити приклад IOP зі стандартною надійністю без поетапної надійності (якщо не враховувати штучні приклади). Проте, коли йдеться про виведення конкретних меж безпеки, різниця між обома може бути суттєвою, і кожен біт має значення. Тому, щоб вивести суворі та конкретні межі, необхідно ретельно проаналізувати поетапну надійність IOP. Це саме те, що ми зробили для протоколу FRI та IOP ethSTARK, на якому базується STARK. Сам аналіз є далеко не простим і виходить за межі цієї статті. Використовуючи новий аналіз, ми можемо встановити точні параметри для нашого доказу.

Поетапна надійність дійсно забезпечує нам необхідні гарантії. Доказувач може багаторазово перегенерувати виклики, але ми знаємо, що на будь-якому з етапів ймовірність генерування «обманного запису» становить 2⁹⁶. Отже, якщо доказувач має t разів часу (вимірюється кількістю викликів до хеш-функції), тоді він може спробувати максимум t разів отримати обманний запис, що обмежує його ймовірність успіху до (t) t 2⁹⁶.

Додати всі помилкові терміни

Нарешті, щоб все це спрацювало, нам потрібно забезпечити, щоб доказувач не міг підробити дерево Меркла. Ми можемо довести, що поки доказувач не знайде колізію в хеш-функції, він не зможе обманути дерево Меркла. Ймовірність того, що зловмисник знайде колізію, використовуючи t викликів (випадкових хеш-функцій), не перевищує t²/2, що є довжиною виходу хеш-функції (викликаною «парадоксом дня народження»). Ось чому ми повинні налаштувати довжину хеш-функції вдвічі більшу, ніж потрібна безпека. Таким чином, якщо ми маємо хеш-функцію з довжиною виходу 192 та IOP з поетапною надійністю 96 біт, ми отримаємо скомпільований STARK, у якого помилка надійності (t)=t²-⁹⁶ + t² 2¹⁹⁶. Оскільки t/(t) = t/(t²⁹⁶+t² 2¹⁹⁶) 1/(2⁹⁶+1/2⁹⁶) = 2²⁹⁵, отже, ця схема має 95 біт безпеки.

Підсумок

Отже, STARK пропонує потужний спосіб перевірки правильності обчислень, виконаних на публічних даних, без довіри. Безпека STARK зазвичай вимірюється «помилкою надійності», що представляє собою ймовірність успішного надання зловмисником хибної заяви та переконання верифікатора за допомогою доказів. Щоб досягти бажаного рівня безпеки, наприклад, 96 біт, базове IOP повинно відповідати поетапній надійності, щоб забезпечити високий рівень безпеки на кожному етапі. Ми проаналізували поетапну надійність IOP, на основі якого побудований наш STARK, що дало нам конкретні межі безпеки.