原文: В целости и сохранности — глубокое погружение в безопасность STARK
Перевод и корректура: "Китайское сообщество 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. Итак, давайте посмотрим, почему наш СТАРК все-таки безопасен. Короче говоря, мы покажем, что злоумышленник проходит не более t шагов, а вероятность успеха атаки не превышает (t) t 2⁹⁶.
IOP и надежность при каждом раунде
Безопасность STARK зависит от лежащего в его основе IOP. Но что означает, что IOP имеет 96-битную защиту? По стандартному определению ошибка надежности IOP равна 2⁹⁶: это означает, что вероятность того, что любой злоумышленник (независимо от времени работы) сможет обмануть валидатор, не превышает 2-96. Однако, как мы уже говорили, надежность IOP — это лишь один из трех компонентов, которого недостаточно для получения 96 бит безопасности из STARK, скомпилированного из всех трех шагов. Напротив, безопасность скомпилированного STARK доказывается при условии, что STARK имеет циклическую ошибку надежности 96 бит (иногда используется аналогичное определение, называемое надежностью восстановления состояния).
Интуитивно, «пораундовая надежность» означает, что каждый раунд имеет 96 бит безопасности, а не только весь протокол. Если быть более конкретным, пораундовая надежность относится к существованию предиката, который может получить часть записи протокола и сообщить нам, является ли эта запись «обманчивой»: «пустая запись» не является «обманчивой» и когда И полная запись является «обманчивой», только если она принята валидатором. Наконец, для любой частичной записи, которая не «подменяет» валидатор, вероятность того, что запись станет «поддельной» в следующем раунде, составляет не более 2⁹⁶. Если существует предикат с этими свойствами, мы говорим, что протокол имеет 96 бит циклической надежности (этот предикат не требует эффективных вычислений).
Во многих случаях люди анализируют только надежность IOP, а не его межраундовую надежность. По общему признанию, трудно придумать пример (за исключением промышленных образцов) 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, для получения конкретных границ безопасности.
Посмотреть Оригинал
На этой странице может содержаться сторонний контент, который предоставляется исключительно в информационных целях (не в качестве заявлений/гарантий) и не должен рассматриваться как поддержка взглядов компании Gate или как финансовый или профессиональный совет. Подробности смотрите в разделе «Отказ от ответственности» .
Углубленный анализ полной безопасности STARK
原文: В целости и сохранности — глубокое погружение в безопасность STARK
Перевод и корректура: "Китайское сообщество Starknet"
Избранные краткие факты
Подробное объяснение безопасности 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 бит безопасности» немного по-разному:
В этой статье мы рассмотрим второй вариант.
От 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. Итак, давайте посмотрим, почему наш СТАРК все-таки безопасен. Короче говоря, мы покажем, что злоумышленник проходит не более t шагов, а вероятность успеха атаки не превышает (t) t 2⁹⁶.
IOP и надежность при каждом раунде
Безопасность STARK зависит от лежащего в его основе IOP. Но что означает, что IOP имеет 96-битную защиту? По стандартному определению ошибка надежности IOP равна 2⁹⁶: это означает, что вероятность того, что любой злоумышленник (независимо от времени работы) сможет обмануть валидатор, не превышает 2-96. Однако, как мы уже говорили, надежность IOP — это лишь один из трех компонентов, которого недостаточно для получения 96 бит безопасности из STARK, скомпилированного из всех трех шагов. Напротив, безопасность скомпилированного STARK доказывается при условии, что STARK имеет циклическую ошибку надежности 96 бит (иногда используется аналогичное определение, называемое надежностью восстановления состояния).
Интуитивно, «пораундовая надежность» означает, что каждый раунд имеет 96 бит безопасности, а не только весь протокол. Если быть более конкретным, пораундовая надежность относится к существованию предиката, который может получить часть записи протокола и сообщить нам, является ли эта запись «обманчивой»: «пустая запись» не является «обманчивой» и когда И полная запись является «обманчивой», только если она принята валидатором. Наконец, для любой частичной записи, которая не «подменяет» валидатор, вероятность того, что запись станет «поддельной» в следующем раунде, составляет не более 2⁹⁶. Если существует предикат с этими свойствами, мы говорим, что протокол имеет 96 бит циклической надежности (этот предикат не требует эффективных вычислений).
Во многих случаях люди анализируют только надежность IOP, а не его межраундовую надежность. По общему признанию, трудно придумать пример (за исключением промышленных образцов) 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, для получения конкретных границ безопасности.