Изучите полный анализ безопасности STARK
TL;DR
- Неинтерактивные STARK начинаются как интерактивные доказательства Oracle (IOP), скомпилированные в неинтерактивные доказательства в случайной модели Oracle.
- В этом посте объясняется недавнее обновление документации ethSTARK , в котором дается полный и конкретный анализ безопасности протокола ethSTARK в случайной модели оракула.
Объяснение безопасности STARK
Система доказательств STARK (Масштабируемый прозрачный аргумент знаний) является мощным инструментом обеспечения вычислительной целостности: она позволяет проверять правильность вычислений, выполняемых с общедоступными данными, без доверия. В этом сообщении блога мы углубимся в безопасность, обеспечиваемую доказательствами STARK, дадим ее определение и исследуем методы доказательства безопасности схемы.
(Прочитайте раздел 6 документации ethSTARK (версия 1.2) для получения полной информации и важной и всесторонней независимой работы Блока и др. по этой теме.)
Чего мы пытаемся достичь с помощью нашего анализа безопасности? Мы хотели бы предотвратить «успешную атаку» на систему STARK, которая обеспечивается ложным утверждением и доказательством STARK, принятым верификатором STARK для этого (ложного) утверждения. Поскольку ложные утверждения опасны и могут быть самых разных размеров и форм, мы хотим быть застрахованы от всех ложных заявлений. Любое ложное утверждение, даже такое тривиальное, как 1+1=3, в сочетании с доказательством STARK, принятым верификатором STARK для этого утверждения, считается успешной атакой на систему. (Тем, у кого есть криптографический опыт, возможно, будет интересно узнать, что STARK также удовлетворяют более строгим понятиям безопасности, таким как надежность знаний , но для простоты в этом посте основное внимание уделяется более простому случаю надежности. )
Как мы формально определяем безопасность системы STARK? Мы делаем это путем анализа «ошибки достоверности», которая примерно измеряет ожидаемую «стоимость», которую злоумышленнику придется потратить для построения успешной атаки (т. е. найти STARK-доказательство ложного утверждения, которое, тем не менее, будет принято верификатором STARK). . С математической точки зрения, ошибка обоснованности — это функция e ( t ), которая получает на вход временной параметр « t» , представляющий количество вычислительного времени, которое злоумышленник готов потратить на организацию атаки, и выводит вероятность успеха злоумышленника в достижении успеха. с нападением (нахождение убедительного доказательства ложного утверждения). По мере роста «цены» t , которую готов потратить злоумышленник, вероятность его успеха увеличивается.
До сих пор мы определяли безопасность STARK как функцию e(t), а это не тот способ, которым вы обычно обсуждаете безопасность, скажем, в крипто-Твиттере. Там вы наверняка слышали утверждения вида «Схема имеет 96 бит безопасности». Как такое заявление соотносится с нашим определением безопасности? На этот вопрос нет однозначного ответа, поскольку люди немного по-разному интерпретируют « x бит безопасности»:
- Очень строгий перевод будет означать, что для любого t от 1 до 2⁹⁶ ошибка достоверности равна e ( t ) ≤ 2⁹⁶ . Это означает, что любое время работы злоумышленника не более 2⁹⁶ имеет крошечную вероятность успеха, меньше 1/2⁹⁶ , что меньше одного из миллиарда раз в миллиард раз в миллиард.
- Более простой и, возможно, более распространенный перевод заключается в том, что 96 бит безопасности означают, что для любого t выполняется условие t / e ( t ) ≥ 2⁹⁶ . Это означает, что вероятность успеха (обратно) линейна времени выполнения. Например, если время работы злоумышленника равно 2⁸⁶, вероятность успеха не превышает 1/2¹⁰.
В этом сообщении блога мы рассмотрим второй вариант.
От IOP до STARK с 96-битной безопасностью
Так как же нам доказать, что схема имеет 96 бит безопасности? Чтобы ответить на этот вопрос, нам нужно понять высокоуровневую структуру построения STARK. STARK состоит из трех основных компонентов: IOP (интерактивное доказательство оракула), дерева Меркла и хеша Фиата-Шамира; Основным компонентом, на котором мы сосредоточимся, является ВГД. Как только эти компоненты указаны, их можно скомпилировать, чтобы получить STARK. Мы подробно расскажем о них, что они из себя представляют и как их собрать вместе.
Первый компонент, который мы рассмотрим, — это IOP: IOP похож на стандартное интерактивное доказательство, в котором проверяющий и проверяющий взаимодействуют в течение нескольких раундов (мы ограничиваемся протоколами публичных монет, где проверяющий отправляет проверяющему только случайные запросы). ). В IOP верификатор не читает сообщения проверяющего целиком, а вместо этого выбирает небольшое количество битов из каждого сообщения проверяющего. Именно это обеспечивает краткость позднее составленного STARK.
Итак, у нас есть IOP, как на его основе построить STARK? Сообщения доказывающего устройства могут быть длинными (на самом деле они длиннее, чем само вычисление). Для сжатия сообщений мы используем деревья Меркла. Дерево Меркла — это двоичное хэш-дерево, где каждый листовой узел представляет запрос или ответ в IOP. Корень дерева — это приверженность всему посланию. Когда проверяющий хочет прочитать определенное место в сообщении, проверяющий предоставляет значение в этом месте и путь аутентификации. Затем проверяющий может использовать путь для проверки правильности значения. Средство проверки IOP считывает лишь небольшое количество местоположений из сообщений средства проверки. Таким образом, использование дерева Меркла приводит к созданию краткого протокола (с небольшими связями).
Сжатие раундов
Можно выбрать интерактивные STARK, то есть, но часто удобно сделать их неинтерактивными, чтобы упростить процесс их генерации, чтобы проверяющему не нужно было ждать внешних сообщений при их построении. Действительно, именно так в настоящее время развертываются все системы STARK, и именно так построен протокол ethSTARK. Неинтерактивные STARK также являются особым случаем прозрачных SNARK (прозрачность означает, что для их создания не требуется доверенная настройка; это также известно как «протокол Артура Мерлина» или «IOP публичной монеты»). С этой целью последний шаг — применить Фиат-Шамир для сжатия раундов в одно сообщение, которое мы назовем доказательством STARK. Преобразование Фиата-Шамира преобразует интерактивный протокол в неинтерактивный. Доказывающая программа имитирует интерактивный протокол, «разговаривая с хеш-функцией». Чтобы получить случайную задачу для раунда i , доказывающая программа хеширует частичную расшифровку до раунда i и интерпретирует выходные данные как следующую задачу.
Это гарантирует, что проверяющий не сможет изменить свои ответы после того, как вызов был сгенерирован. Однако у средства доказательства мошенничества есть некоторые новые стратегические возможности, которых не было в интерактивном IOP. Доказывающий может повторно сгенерировать запрос проверяющего, изменив последнее сообщение доказывающего, что даст новую расшифровку и, следовательно, новый вызов. Как оказывается, стандартного представления о надежности IOPs недостаточно, чтобы доказать безопасность трансформации Фиата-Шамира.
Например, рассмотрим IOP с 96 раундами со следующим «хаком» для проверяющего: если первый бит случайности проверяющего равен 0 в каждом из 96 раундов, то проверяющий принимает (не обращая внимания на доказательства). Видно, что добавление этого хака в верификатор добавляет лишь 1/2⁹⁶ к ошибке достоверности IOP. Однако после преобразования Фиата-Шамира злоумышленник может легко изменить сообщения проверяющего устройства, чтобы гарантировать, что каждый хэш начинается с нуля, что по существу приводит к поломке системы за очень короткое время. Будьте уверены, этот пугающий сценарий — всего лишь теоретический пример, а не тот, который применим к развернутым STARK. Итак, давайте разберемся, почему наши STARK все-таки безопасны? В двух словах, мы покажем, что злоумышленник, выполнивший не более t шагов, преуспеет в атаке с вероятностью не более e(t) ≤ t / 2⁹⁶ . Подробности следуют.
IOP и надежность каждого раунда
STARK может быть настолько безопасным, насколько безопасен его базовый IOP. Но что значит для IOP иметь 96-битную защиту? Стандартное определение гласит, что IOP имеет ошибку надежности 1/2⁹⁶ : это означает, что вероятность того, что любой злоумышленник (независимо от времени выполнения) обманет верификатор, составляет не более 1/2⁹⁶ . Однако, как мы уже говорили, надежность IOP — это только один компонент из трех, которого недостаточно для получения 96 бит безопасности для STARK, скомпилированного из всех трех шагов. Вместо этого безопасность скомпилированного STARK доказывается при условии, что STARK имеет 96 битов ошибки циклической достоверности (иногда используется аналогичное определение, называемое надежностью восстановления состояния ).
Интуитивно понятно, что надежность каждого раунда означает, что каждый раунд имеет 96-битную защиту, а не только общий протокол. Более подробно, round-by-round говорит, что существует предикат, который получает частичную расшифровку протокола и сообщает нам, является ли эта расшифровка «обманной»: Пустая расшифровка не «обманывает», полная расшифровка «обманывает». тогда и только тогда, когда верификатор принимает его. Наконец, для любого частичного транскрипта, который не «обманывает» проверяющего, вероятность того, что в следующем раунде транскрипт станет «обманывающим», составляет не более 1/2⁹⁶ . Если такой предикат с этими свойствами существует, мы говорим, что протокол имеет 96 бит циклической корректности (от предиката не требуется, чтобы он был эффективно вычислим).
Во многих случаях анализируется только надежность IOP, а не его надежность по раундам. По общему признанию, трудно придумать примеры, где IOP имел бы стандартную надежность, но не был бы устойчивым по раундам (за исключением надуманных примеров). Однако различия между ними могут возникнуть при определении конкретных границ безопасности, где важен каждый бит. Таким образом, чтобы получить точные и конкретные границы, необходимо провести тщательный анализ надежности ВГД по раундам. Именно это мы делаем с протоколом FRI , а затем с ethSTARK IOP, который лежит в основе IOP наших STARK. Сам анализ далеко не тривиален и выходит за рамки данного поста. Используя новый анализ, мы можем установить точные параметры для наших доказательств.
Стабильность по раундам действительно дает нам желаемую гарантию. Доказывающая может регенерировать задачу много раз, но мы знаем, что для любого раунда вероятность создания «обманной» транскрипта равна 1/2⁹⁶ . Таким образом, если у доказывающего есть время t , которое измеряется как количество вызовов хэша, то он может попытаться получить обманную расшифровку не более t раз, что ограничивает вероятность его успеха до e(t) ≤ min*{t /2⁹⁶. ,1}*.
Добавление всех условий ошибки
Наконец, чтобы все это сохранилось, нам необходимо гарантировать, что доказывающий не сможет изменить дерево Меркла. Можно показать, что до тех пор, пока программа доказывания не обнаружит коллизий в хеш-функции, она не сможет обмануть дерево Меркла. Вероятность того, что злоумышленник обнаружит коллизию с помощью t вызовов (случайной хэш-функции), не превышает min{ t²/ 2ˢ,1} , где s — длина вывода хеш-функции (это связано с «парадоксом дня рождения» ). Вот почему мы устанавливаем длину хеш-функции, которая в два раза превышает желаемую безопасность. Таким образом, если у нас есть хеш-функция с выходной длиной 192 бита и IOP с раундовой корректностью 96 бит, мы получаем скомпилированный STARK с ошибкой корректности e ( t ) = t /2⁹⁶ + min * { t² / 2¹⁹² ,1} . В частности, такая схема имеет 95 бит безопасности, поскольку функция, которую мы используем для определения безопасности, а именно t / e ( t ), удовлетворяет неравенству t / e ( t ) ≥ t/(t /2⁹⁶ + min {t² / 2¹⁹² ,1}),* и правая часть этого неравенства достигает минимального значения при t=2⁹⁶, и для этого значения t имеем t/e(t) ≥ 2⁹⁵.
Краткое содержание
В заключение отметим, что STARK предоставляют мощный метод проверки правильности вычислений, выполняемых с общедоступными данными, без доверия. Безопасность STARK обычно измеряется с точки зрения «ошибки достоверности», которая представляет собой вероятность того, что злоумышленник успешно предоставит ложное заявление и убедит проверяющего доказательства. Чтобы достичь желаемого уровня безопасности, например 96 бит, базовый IOP должен обеспечивать надежность каждого раунда, гарантируя, что каждый раунд поддерживает высокий уровень безопасности. Мы проанализировали надежность IOP, лежащего в основе наших SATRK, что позволило нам вывести конкретные границы