Название: В целости и сохранности — глубокое погружение в STARK Security

Перевод и корректура: «Китайское сообщество Starknet»

Избранные краткие факты

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

• В этой статье описаны последние обновления документации ethSTARK и представлен всесторонний и подробный анализ безопасности протокола ethSTARK в модели случайного оракула.

Подробное объяснение безопасности STARK

Система доказательств STARK, или масштабируемый аргумент прозрачного знания, является мощным инструментом обеспечения вычислительной целостности: она позволяет без доверия проверять правильность вычислений, выполняемых на общедоступных данных. В этой статье мы углубимся в безопасность, обеспечиваемую доказательствами STARK, определим их и исследуем методы доказательства безопасности схем.

(Подробности читайте в разделе 6 документации ethSTARK (версия 1.2), а также в важной и всесторонней независимой работе Block et al. по этой теме.)

Чего мы пытаемся достичь с помощью аналитики безопасности? Мы хотим предотвратить «успешные атаки» на систему 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⁹⁶, что составляет менее 1 на миллиард, умноженный на 1 на миллиард.

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

В этой статье мы рассмотрим второй вариант.

От IOP до STARK с 96-битной безопасностью

Итак, как нам доказать, что решение имеет 96 бит безопасности? Чтобы ответить на этот вопрос, нам необходимо понять структуру высокого уровня, на которой построен STARK. STARK состоит из трех основных частей: IOP (Интерактивное доказательство Oracle), Дерево Меркла и хэш Фиата-Шамира. Наше основное внимание уделяется IOP. Как только эти составные части указаны, мы можем скомпилировать их для создания STARK. Мы подробно рассмотрим эти компоненты, включая то, что они собой представляют и как они сочетаются друг с другом.

Первый компонент, который мы рассмотрим, — это IOP: IOP аналогичен стандартному интерактивному доказательству, в котором проверяющий и валидатор взаимодействуют в течение нескольких раундов (мы ограничены протоколами общедоступных монет, где валидатор отправляет проверяющему только случайные запросы). В IOP верификатор не считывает сообщение проверяющего полностью, а вместо этого выбирает небольшую часть битов из каждого сообщения проверяющего. Вот почему позже скомпилированный STARK достигает своей простоты.

Учитывая IOP, как мне построить из него STARK? Сообщения доказывающего могут быть очень длинными (на самом деле они длиннее, чем само вычисление). Для сжатия этой информации мы используем деревья Меркла. Дерево Меркла — это двоичное хэш-дерево, в котором каждый листовой узел представляет запрос или ответ в IOP. Корни – это обещание всего послания. Когда валидатор хочет прочитать определенное место в сообщении, проверяющий предоставляет значение этого местоположения и путь проверки. Затем валидатор может использовать этот путь для проверки правильности значения. Валидатор IOP считывает лишь небольшой объем информации о местоположении из информации проверяющего устройства. Следовательно, краткие протоколы (протоколы с небольшим объемом связи) могут быть реализованы с использованием деревьев Меркла.

Сжатые патроны

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

Это гарантирует, что доказывающая не сможет изменить свой ответ после того, как вызов будет сгенерирован. Однако у средств доказательства мошенничества есть некоторые новые возможности политики, недоступные в интерактивных IOP. Доказывающая может повторно сгенерировать запрос валидатора, изменив последнюю информацию доказывающего, так что он получит новую запись и, следовательно, новый вызов. Оказывается, что стандартных концепций надежности IOP недостаточно, чтобы продемонстрировать безопасность преобразования Fiat-Shamir.

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

IOP и надежность на каждом этапе

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

Интуитивно, «пораундовая надежность» означает, что каждый раунд имеет 96 бит безопасности, а не только весь протокол. Если быть более конкретным, пораундовая надежность относится к существованию предиката, который может получить часть записи протокола и сообщить нам, является ли эта запись «обманчивой»: «пустая запись» не является «обманчивой» и когда И полная запись является «обманчивой», только если она принята валидатором. Наконец, для любой частичной записи, которая не «подменяет» валидатор, вероятность того, что запись станет «поддельной» в следующем раунде, составляет не более 2⁹⁶. Если существует предикат с этими свойствами, мы говорим, что протокол имеет 96 бит циклической надежности (этот предикат не требует эффективных вычислений).

Во многих случаях люди анализируют только надежность IOP, а не его межраундовую надежность. По общему признанию, трудно придумать пример (за исключением промышленных образцов) 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 бит безопасности.

Подведем итог

В совокупности STARK предоставляет мощный метод надежной проверки правильности вычислений, выполняемых с общедоступными данными. Безопасность STARK обычно измеряется «ошибкой надежности», которая представляет собой вероятность того, что злоумышленник успешно предоставит ложное утверждение и убедит валидатора доказательством. Чтобы достичь требуемого уровня безопасности, например 96 бит, базовый IOP должен обеспечивать надежность каждого раунда, гарантируя поддержание высокого уровня безопасности в каждом раунде. Мы проанализировали надежность IOP, на которых основан наш STARK, для получения конкретных границ безопасности.