原文：Безпека та надійність — глибоке занурення в STARK Security
Переклад і вичитка: "Китайська спільнота Starknet"
Рекомендовані короткі факти
Неінтерактивний STARK є похідним від Interactive Oracle Proof (IOP), скомпільованого в неінтерактивне доказ у моделі випадкового оракула.
У цій статті пояснюється останні оновлення документації ethSTARK і надається вичерпний і детальний аналіз безпеки протоколу ethSTARK у моделі випадкового оракула.
Детальне пояснення безпеки STARK
Система доказів STARK, або масштабований прозорий аргумент знань, є потужним інструментом для обчислювальної цілісності: вона дозволяє надійно перевіряти правильність обчислень, виконаних із загальнодоступними даними. У цій статті ми заглибимося в безпеку, яку забезпечують докази STARK, визначимо їх і дослідимо методи підтвердження безпеки схем.
(Прочитайте розділ 6 документації ethSTARK (версія 1.2), щоб дізнатися більше, а також важливу та всебічну незалежну роботу на цю тему, виконану Блоком та ін.).
Чого ми намагаємося досягти за допомогою аналітики безпеки? Ми хочемо запобігти «успішним атакам» на систему STARK, викликаним хибним твердженням і доказом STARK, прийнятим валідатором STARK у відповідь на це (хибне) твердження. Оскільки введення в оману небезпечні та можуть бути будь-яких розмірів і форм, ми хочемо захиститися від усіх. Будь-яке хибне твердження, навіть таке тривіальне, як 1+1=3, у поєднанні з доказом STARK, прийнятим валідатором STARK, вважатиметься успішною атакою на систему. (Тим, хто має досвід криптографії, може бути цікаво дізнатися, що STARK також може задовольнити більш сильні концепції безпеки, такі як надійність знань, але для простоти ця стаття зосередиться на простих випадках щодо надійності).
Як формально визначити безпеку системи STARK? Ми визначаємо це, аналізуючи «помилку надійності». «Помилка надійності» приблизно вимірює очікувану «вартість», яку обійдеться зловмиснику для запуску успішної атаки (тобто знайти доказ STARK для помилкового твердження, але доказ приймається валідатором STARK). Математично кажучи, помилка надійності є функцією (t), вхідним параметром якої є параметр часу t, що представляє обчислювальний час, який зловмисник готовий витратити, щоб почати атаку, а виходом є ймовірність того, що атака зловмисника вдасться (знайдена для неправдиві твердження переконливий доказ). Чим більше «вартість» t, яку зловмисник готовий витратити, тим вище його ймовірність успіху.
Наразі ми визначили безпеку STARK як функцію (t), яка відрізняється від того, як усі щодня обговорюють безпеку в криптовалютному Twitter. У Twitter ви можете почути щось на кшталт цього: «Це рішення має 96 біт безпеки». Як це перекладається на наше визначення безпеки? На це питання немає однозначної відповіді, оскільки люди розуміють «х бітів безпеки» дещо по-різному:
У строгому тлумаченні це означає, що для будь-якого t від 1 до 2⁹⁶ помилка надійності становить (t) 2⁹⁶. Зловмисник із часом роботи 2⁹⁶ або менше має дуже малу ймовірність успіху, менше ніж 2⁹⁶, що менше ніж 1 на мільярд помножити на 1 на мільярд.
Більш вільна і, можливо, більш поширена інтерпретація полягає в тому, що 96-бітна безпека означає, що для будь-якого t існує ситуація, коли t/(t) 2⁹⁶. Це означає, що ймовірність успіху є (обернено) лінійною залежно від часу виконання. Якщо зловмисник має час роботи 2⁸⁶, то його ймовірність успіху становить щонайбільше 2¹⁰.
У цій статті ми обговоримо другий варіант.
Від IOP до STARK із 96-бітною безпекою
Отже, як ми доведемо, що рішення має 96 біт безпеки? Щоб відповісти на це запитання, нам потрібно зрозуміти структуру високого рівня, на якій побудовано STARK. STARK складається з трьох основних частин: IOP (Interactive Oracle Proof), дерева Меркле та хешу Фіата-Шаміра; наша основна увага — IOP. Після визначення цих складових частин ми можемо скомпілювати їх для створення STARK. Ми детально розглянемо ці компоненти, включно з тим, що вони являють собою та як вони поєднуються.
Перший компонент, який ми розглянемо, — це IOP: IOP подібний до стандартного інтерактивного доказу, де прувер і валідатор взаємодіють протягом кількох раундів (ми обмежені загальнодоступними протоколами монет, де валідатор лише надсилає випадкові виклики пруверу). У IOP верифікатор не повністю читає повідомлення перевірювача, а натомість відбирає невелику частину бітів із кожного повідомлення перевірювача. Ось чому пізніше скомпільований STARK досягає простоти.
Враховуючи IOP, як мені створити STARK з нього? Повідомлення перевірника можуть бути дуже довгими (насправді вони довші за сам обчислення). Щоб стиснути цю інформацію, ми використовуємо дерева Merkle. Дерево Merkle — це бінарне хеш-дерево, у якому кожен листовий вузол представляє запит або відповідь у IOP. Коріння є обіцянкою всього повідомлення. Коли валідатор хоче прочитати певне місце в повідомленні, перевірка надає значення цього розташування та шлях перевірки. Потім валідатор може використати цей шлях для перевірки правильності значення. Валідатор IOP зчитує лише невелику кількість інформації про місцезнаходження з інформації прувера. Таким чином, короткі протоколи (протоколи з низьким обсягом зв’язку) можуть бути реалізовані за допомогою дерев Merkle.
Раунди стиснення
Ми можемо вибрати інтерактивний STARK, але для спрощення процесу генерації STARK ми зазвичай вибираємо неінтерактивний STARK, щоб валідатору не потрібно було чекати зовнішньої інформації під час створення STARK. Насправді, це те, як розгортаються всі поточні системи STARK і як побудований протокол ethSTARK. Неінтерактивні STARK також є особливим випадком прозорих SNARK (прозорі означає, що для їх створення не потрібні довірені налаштування; «Протокол Артура Мерліна» або «Публічний IOP монети»). Для цього останнім кроком є застосування алгоритму Фіата-Шаміра для стиснення кількох раундів взаємодії в одне повідомлення, яке ми називаємо доказом STARK. Перетворення Фіата-Шаміра - це метод перетворення інтерактивного протоколу в неінтерактивний протокол. Прувер симулює інтерактивний протокол під час спілкування з хеш-функцією. Щоб отримати випадкову перевірку для раунду i, перевірка хешує частковий запис для раунду i та інтерпретує вихідні дані як наступну перевірку.
Це гарантує, що довідник не зможе змінити свою відповідь після створення виклику. Однак засіб перевірки шахрайства має деякі нові стратегічні шляхи, недоступні в інтерактивних IOP. Пристрій перевірки може повторно створити виклик валідатора, змінивши останню інформацію перевірника, щоб отримати новий запис і, отже, новий виклик. Виявляється, стандартної концепції надійності IOP недостатньо, щоб довести безпеку конверсії Fiat-Shamir.
Наприклад, мати IOP 96 раундів і додати такий хак до валідатора: якщо перший біт випадковості валідатора дорівнює 0 у кожному з 96 раундів, то валідатор прийме це (не побачивши жодних доказів). Ми бачимо, що додавання цього хаку до валідатора лише додає термін 2⁹⁶ до похибки надійності IOP. Однак після перетворення Fiat-Shamir зловмисник може легко змінити інформацію перевірки, щоб переконатися, що кожне хеш-значення починається з 0, таким чином проникаючи в систему за дуже короткий час. Будьте певні, цей страшний сценарій є лише теоретичним прикладом і не стосується розгорнутих STARK. Отже, давайте подивимося, чому все-таки наш STARK безпечний. Коротше кажучи, ми покажемо, що зловмисник пробігає щонайбільше t кроків, а ймовірність успіху атаки становить не більше (t) t 2⁹⁶.
ВГД і надійність кожного циклу
Безпека STARK залежить від базового IOP. Але що означає для IOP мати 96 біт безпеки? За стандартним визначенням похибка надійності IOP становить 2⁹⁶: це означає, що ймовірність того, що будь-який зловмисник (незалежно від часу роботи) зможе обдурити валідатор, становить не більше 2-96. Однак, як ми обговорювали, надійність IOP є лише одним із трьох компонентів, чого недостатньо для отримання 96 біт безпеки від STARK, скомпільованого з усіх трьох кроків. Навпаки, безпека скомпільованого STARK доведена за умови, що STARK має покрокову помилку надійності 96 біт (іноді використовується подібне визначення, яке називається надійністю відновлення стану).
Інтуїтивно зрозуміло, що «повна надійність» означає, що кожен раунд має 96 біт безпеки, а не лише весь протокол. Точніше кажучи, покрокова надійність відноситься до існування предикату, який може отримати частину запису протоколу та повідомити нам, чи є цей запис «оманливим»: «порожній запис» не є «оманливим», а коли І повний запис є "оманливим", лише якщо його приймає валідатор. Нарешті, для будь-якого часткового запису, який не «підмінює» валідатор, ймовірність того, що запис стане «підробкою» в наступному раунді, становить не більше 2⁹⁶. Якщо є предикат із такими властивостями, ми говоримо, що протокол має 96 біт повної надійності (цей предикат не вимагає ефективних обчислень).
У багатьох випадках люди аналізують лише надійність ВОТ, а не його повну надійність. Слід визнати, що важко придумати приклад (за винятком виготовлених зразків) ВГД, який має стандартну надійність, але не надійність від циклу до раунду. Однак під час визначення певних меж безпеки між ними можуть виникнути відмінності, і кожен біт має значення. Таким чином, щоб отримати точні та конкретні межі, необхідний ретельний аналіз надійності IOP раунд за раундом. Це саме те, що ми робимо з протоколом FRI та ethSTARK IOP, на якому базується STARK IOP. Сам аналіз далеко не тривіальний і виходить за рамки цієї статті. Використовуючи новий аналіз, ми можемо встановити точні параметри для нашого доказу.
Повна надійність дійсно дає нам необхідну впевненість. Пристрій перевірки може повторно генерувати виклик кілька разів, але ми знаємо, що в будь-якому раунді ймовірність створення шахрайського запису становить 2⁹⁶. Тому, якщо перевірка має t разів (вимірюється кількістю викликів хешування), то вона може спробувати більшість t разів, щоб отримати оманливий запис, що обмежує його ймовірність успіху (t) t 2⁹⁶.
Додати всі помилки
Нарешті, щоб усе це було правдою, нам потрібно переконатися, що прувер не може втручатися в дерево Меркла. Ми можемо показати, що поки перевіряльник не знаходить колізій у хеш-функції, він не може шахраювати в дереві Меркла. Імовірність того, що зловмисник знайде колізію за допомогою t викликів (випадкова хеш-функція), не перевищує t2/2, що є довжиною виводу хеш-функції (спричиненої «парадоксом дня народження»). Ось чому нам потрібно встановити хеш-функція. Довжина вдвічі перевищує необхідну безпеку. Отже, якщо у нас є хеш-функція з довжиною виводу 192 і IOP із повною надійністю 96 біт, ми отримаємо скомпільований STARK, який є надійним. Сексуальна помилка (t )=t2-⁹⁶ + t2 2¹⁹⁶. Оскільки t/(t) = t/(t 2⁹⁶+t2 2¹⁹⁶) 1/(2⁹⁶+1/2⁹⁶) = 2²⁹⁵, ця схема має 95 біт безпеки sex.
Підведіть підсумки
У сукупності STARK забезпечує потужний метод надійної перевірки правильності обчислень, виконаних із загальнодоступними даними. Безпека STARK зазвичай вимірюється «помилкою надійності», яка представляє ймовірність того, що зловмисник успішно надає неправдиве твердження та переконує валідатор доказом. Щоб досягти необхідного рівня безпеки, наприклад 96 біт, базовий IOP має відповідати надійності циклу за раундом, щоб забезпечити підтримку високих рівнів безпеки на кожному раунді. Ми проаналізували послідовний аналіз надійності IOP, на якому базується наш STARK, щоб отримати конкретні межі безпеки.
Переглянути оригінал
Ця сторінка може містити контент третіх осіб, який надається виключно в інформаційних цілях (не в якості запевнень/гарантій) і не повинен розглядатися як схвалення його поглядів компанією Gate, а також як фінансова або професійна консультація. Див. Застереження для отримання детальної інформації.
Поглиблений аналіз повної безпеки STARK
原文：Безпека та надійність — глибоке занурення в STARK Security
Переклад і вичитка: "Китайська спільнота Starknet"
Рекомендовані короткі факти
Детальне пояснення безпеки STARK
Система доказів STARK, або масштабований прозорий аргумент знань, є потужним інструментом для обчислювальної цілісності: вона дозволяє надійно перевіряти правильність обчислень, виконаних із загальнодоступними даними. У цій статті ми заглибимося в безпеку, яку забезпечують докази STARK, визначимо їх і дослідимо методи підтвердження безпеки схем.
(Прочитайте розділ 6 документації ethSTARK (версія 1.2), щоб дізнатися більше, а також важливу та всебічну незалежну роботу на цю тему, виконану Блоком та ін.).
Чого ми намагаємося досягти за допомогою аналітики безпеки? Ми хочемо запобігти «успішним атакам» на систему STARK, викликаним хибним твердженням і доказом STARK, прийнятим валідатором STARK у відповідь на це (хибне) твердження. Оскільки введення в оману небезпечні та можуть бути будь-яких розмірів і форм, ми хочемо захиститися від усіх. Будь-яке хибне твердження, навіть таке тривіальне, як 1+1=3, у поєднанні з доказом STARK, прийнятим валідатором STARK, вважатиметься успішною атакою на систему. (Тим, хто має досвід криптографії, може бути цікаво дізнатися, що STARK також може задовольнити більш сильні концепції безпеки, такі як надійність знань, але для простоти ця стаття зосередиться на простих випадках щодо надійності).
Як формально визначити безпеку системи STARK? Ми визначаємо це, аналізуючи «помилку надійності». «Помилка надійності» приблизно вимірює очікувану «вартість», яку обійдеться зловмиснику для запуску успішної атаки (тобто знайти доказ STARK для помилкового твердження, але доказ приймається валідатором STARK). Математично кажучи, помилка надійності є функцією (t), вхідним параметром якої є параметр часу t, що представляє обчислювальний час, який зловмисник готовий витратити, щоб почати атаку, а виходом є ймовірність того, що атака зловмисника вдасться (знайдена для неправдиві твердження переконливий доказ). Чим більше «вартість» t, яку зловмисник готовий витратити, тим вище його ймовірність успіху.
Наразі ми визначили безпеку STARK як функцію (t), яка відрізняється від того, як усі щодня обговорюють безпеку в криптовалютному Twitter. У Twitter ви можете почути щось на кшталт цього: «Це рішення має 96 біт безпеки». Як це перекладається на наше визначення безпеки? На це питання немає однозначної відповіді, оскільки люди розуміють «х бітів безпеки» дещо по-різному:
У цій статті ми обговоримо другий варіант.
Від IOP до STARK із 96-бітною безпекою
Отже, як ми доведемо, що рішення має 96 біт безпеки? Щоб відповісти на це запитання, нам потрібно зрозуміти структуру високого рівня, на якій побудовано STARK. STARK складається з трьох основних частин: IOP (Interactive Oracle Proof), дерева Меркле та хешу Фіата-Шаміра; наша основна увага — IOP. Після визначення цих складових частин ми можемо скомпілювати їх для створення STARK. Ми детально розглянемо ці компоненти, включно з тим, що вони являють собою та як вони поєднуються.
Перший компонент, який ми розглянемо, — це IOP: IOP подібний до стандартного інтерактивного доказу, де прувер і валідатор взаємодіють протягом кількох раундів (ми обмежені загальнодоступними протоколами монет, де валідатор лише надсилає випадкові виклики пруверу). У IOP верифікатор не повністю читає повідомлення перевірювача, а натомість відбирає невелику частину бітів із кожного повідомлення перевірювача. Ось чому пізніше скомпільований STARK досягає простоти.
Враховуючи IOP, як мені створити STARK з нього? Повідомлення перевірника можуть бути дуже довгими (насправді вони довші за сам обчислення). Щоб стиснути цю інформацію, ми використовуємо дерева Merkle. Дерево Merkle — це бінарне хеш-дерево, у якому кожен листовий вузол представляє запит або відповідь у IOP. Коріння є обіцянкою всього повідомлення. Коли валідатор хоче прочитати певне місце в повідомленні, перевірка надає значення цього розташування та шлях перевірки. Потім валідатор може використати цей шлях для перевірки правильності значення. Валідатор IOP зчитує лише невелику кількість інформації про місцезнаходження з інформації прувера. Таким чином, короткі протоколи (протоколи з низьким обсягом зв’язку) можуть бути реалізовані за допомогою дерев Merkle.
Раунди стиснення
Ми можемо вибрати інтерактивний STARK, але для спрощення процесу генерації STARK ми зазвичай вибираємо неінтерактивний STARK, щоб валідатору не потрібно було чекати зовнішньої інформації під час створення STARK. Насправді, це те, як розгортаються всі поточні системи STARK і як побудований протокол ethSTARK. Неінтерактивні STARK також є особливим випадком прозорих SNARK (прозорі означає, що для їх створення не потрібні довірені налаштування; «Протокол Артура Мерліна» або «Публічний IOP монети»). Для цього останнім кроком є застосування алгоритму Фіата-Шаміра для стиснення кількох раундів взаємодії в одне повідомлення, яке ми називаємо доказом STARK. Перетворення Фіата-Шаміра - це метод перетворення інтерактивного протоколу в неінтерактивний протокол. Прувер симулює інтерактивний протокол під час спілкування з хеш-функцією. Щоб отримати випадкову перевірку для раунду i, перевірка хешує частковий запис для раунду i та інтерпретує вихідні дані як наступну перевірку.
Це гарантує, що довідник не зможе змінити свою відповідь після створення виклику. Однак засіб перевірки шахрайства має деякі нові стратегічні шляхи, недоступні в інтерактивних IOP. Пристрій перевірки може повторно створити виклик валідатора, змінивши останню інформацію перевірника, щоб отримати новий запис і, отже, новий виклик. Виявляється, стандартної концепції надійності IOP недостатньо, щоб довести безпеку конверсії Fiat-Shamir.
Наприклад, мати IOP 96 раундів і додати такий хак до валідатора: якщо перший біт випадковості валідатора дорівнює 0 у кожному з 96 раундів, то валідатор прийме це (не побачивши жодних доказів). Ми бачимо, що додавання цього хаку до валідатора лише додає термін 2⁹⁶ до похибки надійності IOP. Однак після перетворення Fiat-Shamir зловмисник може легко змінити інформацію перевірки, щоб переконатися, що кожне хеш-значення починається з 0, таким чином проникаючи в систему за дуже короткий час. Будьте певні, цей страшний сценарій є лише теоретичним прикладом і не стосується розгорнутих STARK. Отже, давайте подивимося, чому все-таки наш STARK безпечний. Коротше кажучи, ми покажемо, що зловмисник пробігає щонайбільше t кроків, а ймовірність успіху атаки становить не більше (t) t 2⁹⁶.
ВГД і надійність кожного циклу
Безпека STARK залежить від базового IOP. Але що означає для IOP мати 96 біт безпеки? За стандартним визначенням похибка надійності IOP становить 2⁹⁶: це означає, що ймовірність того, що будь-який зловмисник (незалежно від часу роботи) зможе обдурити валідатор, становить не більше 2-96. Однак, як ми обговорювали, надійність IOP є лише одним із трьох компонентів, чого недостатньо для отримання 96 біт безпеки від STARK, скомпільованого з усіх трьох кроків. Навпаки, безпека скомпільованого STARK доведена за умови, що STARK має покрокову помилку надійності 96 біт (іноді використовується подібне визначення, яке називається надійністю відновлення стану).
Інтуїтивно зрозуміло, що «повна надійність» означає, що кожен раунд має 96 біт безпеки, а не лише весь протокол. Точніше кажучи, покрокова надійність відноситься до існування предикату, який може отримати частину запису протоколу та повідомити нам, чи є цей запис «оманливим»: «порожній запис» не є «оманливим», а коли І повний запис є "оманливим", лише якщо його приймає валідатор. Нарешті, для будь-якого часткового запису, який не «підмінює» валідатор, ймовірність того, що запис стане «підробкою» в наступному раунді, становить не більше 2⁹⁶. Якщо є предикат із такими властивостями, ми говоримо, що протокол має 96 біт повної надійності (цей предикат не вимагає ефективних обчислень).
У багатьох випадках люди аналізують лише надійність ВОТ, а не його повну надійність. Слід визнати, що важко придумати приклад (за винятком виготовлених зразків) ВГД, який має стандартну надійність, але не надійність від циклу до раунду. Однак під час визначення певних меж безпеки між ними можуть виникнути відмінності, і кожен біт має значення. Таким чином, щоб отримати точні та конкретні межі, необхідний ретельний аналіз надійності IOP раунд за раундом. Це саме те, що ми робимо з протоколом FRI та ethSTARK IOP, на якому базується STARK IOP. Сам аналіз далеко не тривіальний і виходить за рамки цієї статті. Використовуючи новий аналіз, ми можемо встановити точні параметри для нашого доказу.
Повна надійність дійсно дає нам необхідну впевненість. Пристрій перевірки може повторно генерувати виклик кілька разів, але ми знаємо, що в будь-якому раунді ймовірність створення шахрайського запису становить 2⁹⁶. Тому, якщо перевірка має t разів (вимірюється кількістю викликів хешування), то вона може спробувати більшість t разів, щоб отримати оманливий запис, що обмежує його ймовірність успіху (t) t 2⁹⁶.
Додати всі помилки
Нарешті, щоб усе це було правдою, нам потрібно переконатися, що прувер не може втручатися в дерево Меркла. Ми можемо показати, що поки перевіряльник не знаходить колізій у хеш-функції, він не може шахраювати в дереві Меркла. Імовірність того, що зловмисник знайде колізію за допомогою t викликів (випадкова хеш-функція), не перевищує t2/2, що є довжиною виводу хеш-функції (спричиненої «парадоксом дня народження»). Ось чому нам потрібно встановити хеш-функція. Довжина вдвічі перевищує необхідну безпеку. Отже, якщо у нас є хеш-функція з довжиною виводу 192 і IOP із повною надійністю 96 біт, ми отримаємо скомпільований STARK, який є надійним. Сексуальна помилка (t )=t2-⁹⁶ + t2 2¹⁹⁶. Оскільки t/(t) = t/(t 2⁹⁶+t2 2¹⁹⁶) 1/(2⁹⁶+1/2⁹⁶) = 2²⁹⁵, ця схема має 95 біт безпеки sex.
Підведіть підсумки
У сукупності STARK забезпечує потужний метод надійної перевірки правильності обчислень, виконаних із загальнодоступними даними. Безпека STARK зазвичай вимірюється «помилкою надійності», яка представляє ймовірність того, що зловмисник успішно надає неправдиве твердження та переконує валідатор доказом. Щоб досягти необхідного рівня безпеки, наприклад 96 біт, базовий IOP має відповідати надійності циклу за раундом, щоб забезпечити підтримку високих рівнів безпеки на кожному раунді. Ми проаналізували послідовний аналіз надійності IOP, на якому базується наш STARK, щоб отримати конкретні межі безпеки.