Объединение вероятностных доказательств и хеш-функций

Это пятый и последний пост в нашей серии STARK Math.

В нашем первом посте мы представили понятие инклюзивной подотчетности и ее важность для публичных блокчейнов. Мы также объяснили, почему свойства масштабируемости STARK позволяют реализовать это понятие. Мы рекомендуем читателю прочитать этот первый пост, прежде чем продолжить.

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

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

Наша цель: масштабируемые прозрачные аргументы

Мы хотим построить STARK, который является криптографическим доказательством (также известным как «аргумент»), который является масштабируемым и прозрачным . Наш первый пост подробно описывает эту цель, которую мы сейчас подытожим.

Мы рассматриваем криптографические доказательства для утверждений о вычислительной целостности (CI). Это означает, что для заданной программы 𝐀 , ввода x , вывода y и ограничения по времени T мы хотим создать строку доказательства 𝛑, подтверждающую утверждение

«𝐀 ( x ) выводит y за T шагов вычисления».

Никакая (эффективная) процедура не должна быть в состоянии производить достоверные доказательства для ложных утверждений (например, утверждение 𝐀 ( x )=1, когда вместо этого 𝐀 ( x )=0). Возможны более общие операторы CI, где 𝐀 дополнительно принимает частный вспомогательный вход, но мы игнорируем это в этом посте.

STARK — это криптографические доказательства, которые удовлетворяют следующим желательным свойствам.

• Масштабируемость: время, необходимое для создания 𝛑, равно T ·polylog( T ), тогда как время, необходимое для проверки 𝛑, равно только polylog( T ); в частности, длина 𝛑 равна polylog( T ). Другими словами, создание доказательств ненамного дороже, чем просто выполнение исходного вычисления, а проверка доказательств экспоненциально быстрее , чем выполнение исходного вычисления. Доказательства экспоненциально короче , чем размер исходного вычисления.
• Прозрачность: глобальные параметры системы криптографических доказательств, используемые для создания и проверки доказательств, не имеют лазеек . Это отличается от систем проверки, которые полагаются на доверенную сторону для выборки общедоступных параметров на основе секретной информации, которую можно использовать в качестве «лазейки» для нарушения безопасности системы проверки.

К концу этого поста у вас будет неформальное понимание того, откуда берутся свойства масштабируемости и прозрачности.

Мы кратко отметим здесь, что STARK используют только облегченную симметричную криптографию (криптографические хэш-функции), что делает их быстрыми и (вероятно) постквантово безопасными . Это контрастирует со многими другими криптографическими доказательствами, безопасность которых зависит от криптографии с открытым ключом, которая является одновременно дорогой и небезопасной для квантовых противников.

Дорожная карта для этого поста

Известные конструкции STARK сочетают в себе два ингредиента:

1. длинные доказательства, которые можно проверить с помощью случайных и недорогих локальных проверок; а также
2. криптографическая хэш-функция , такая как SHA-256 или Keccak.

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

• Во-первых, мы опишем конструкцию Микали , метод построения криптографических доказательств, который следует приведенному выше плану. Системы доказательств, лежащие в основе этой конструкции, известны как вероятностно-проверяемые доказательства (PCP). Мы описываем эту конструкцию из педагогических соображений: это изящный частный случай конструкции, которую мы используем.
• Во-вторых, мы объясняем, почему конструкция Micali обеспечивает прозрачность и масштабируемость.
• В-третьих, мы описываем понятие Interactive Oracle Proofs (IOPs), которое обобщает PCP и позволяет разрабатывать гораздо более эффективные протоколы. Мы также объясняем, почему протоколы арифметизации и низкоуровневого тестирования в предыдущих сообщениях являются IOP.
• Наконец, упомянем конструкцию BCS , расширение конструкции Микали, использующее более общее понятие IOP вместо PCP. Эффективные СТАРКи, в том числе используемые нами, получаются за счет построения БКС .

Криптографические доказательства от PCP с помощью конструкции Micali

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

Вероятностно -проверяемое доказательство (PCP) — это протокол между доказывающим PCP и проверяющим PCP, который позволяет установить правильность утверждений о вычислительной целостности (CI) посредством случайной локальной проверки для длинного доказательства . Учитывая оператор CI ( 𝐀 , x , y , T ), доказывающий PCP создает строку доказательства 𝚿, которая «кодирует» трассировку вычисления оператора CI. Хотя доказательство 𝚿 длиннее, чем трасса вычисления T-шага (длина 𝚿 квазилинейна по T), 𝚿 имеет замечательную особенность, состоящую в том, что его можно проверить с помощью вероятностного теста, который считывает только небольшую часть 𝚿. А именно, учитывая тот же оператор CI ( A , x ,y , T ), верификатор PCP может проверить 𝚿, случайно прочитав небольшое количество местоположений 𝚿, а затем выполнив недорогую «локальную проверку» считанных значений. (Число мест чтения может быть небольшой константой, например, 3, не зависящей от T!) Если утверждение CI верно, то верификатор всегда принимает его. Если вместо этого утверждение CI ложно, то верификатор отклоняет с высокой вероятностью, независимо от того, как была выбрана строка доказательства 𝚿. См. схему на рис. 2.

Напомним, что наша цель — создать доказательства 𝛑, которые будут короткими и быстрыми для проверки. Это сильно отличается от PCP, которые вместо этого включают недорогие локальные проверки для длинных доказательств 𝚿. Так как же нам перейти от 𝚿 к 𝛑?

Естественная идея, которая может прийти на ум, состоит в том, чтобы доказывающий предварительно сэмплировал локальное представление 𝚿 от имени верификатора, а затем отправлял это локальное представление в качестве доказательства 𝛑. Более подробно, прувер моделируетслучайная локальная проверка верификатора PCP на длинном доказательстве 𝚿, а затем включает в доказательство 𝛑 только местоположения 𝚿, прочитанные с помощью этой локальной проверки; доказывающий также включает в 𝛑 случайность 𝛒, используемую для верификатора PCP. (Обратите внимание, что 𝛑 короткое, потому что количество мест чтения 𝚿 невелико.) Интуиция предварительной выборки заключается в том, что для проверки 𝛑 можно запустить верификатор PCP с той же случайностью 𝛒, что вызовет чтение те самые локации 𝚿, которые были включены в 𝛑. Однако эта привлекательная идея ошибочна. Во-первых, мошенник может включить в 𝛑 выбор «случайности» 𝛒, которая на самом деле не случайна. Во-вторых, мошенник может выбирать ответы на запросы верификатора PCP, которые зависятна 𝛒, чтобы пройти местную проверку верификатора PCP. Это возможно, потому что безопасность PCP зависит от неизменности 𝚿 , т. е. фиксированной до того, как будет выбрана случайная локальная проверка верификатора.

Вышеуказанные проблемы могут быть решены с помощью любой криптографической хеш-функции H, такой как SHA-256 (смоделированной как случайный оракул ), для реализации безопасной предварительной выборки . Здесь «безопасный» означает, что доказывающий сможет убедить верификатора в том, что информация, включенная в короткое доказательство 𝛑, является «честной» случайной локальной проверкой, которая была проведена на каком-то длинном доказательстве 𝚿.

Неформально, как показано на рис. 3, ожидается, что доказывающая сторона будет использовать хеш-функцию H для фиксации длинного доказательства 𝚿 через дерево Меркла , а затем получить случайность 𝛒, используя H для хеширования корня дерева Меркла. Это гарантирует, что случайность 𝛒 является «случайной» (поскольку 𝛒 является результатом хеш-функции H), а также гарантирует, что 𝛒 выбирается последоказывающий обязался 𝚿. Теперь прувер может выполнять предварительную выборку, как описано выше, а именно моделировать случайную локальную проверку верификатора PCP на случайность 𝛒, чтобы определить, какие местоположения 𝚿 должны быть включены в 𝛑. Наконец, доказывающий «декоммитирует» выбранные местоположения, включая в 𝛑 путь аутентификации для каждого выбранного местоположения (путь аутентификации для местоположения состоит из братьев и сестер узлов на пути от местоположения до корня). Пути аутентификации демонстрируют, что заявленные значения 𝚿 согласуются с корнем Меркла и, в частности, не были выбраны доказывающим послеслучайность 𝛒 была получена из корня. В целом, краткое доказательство 𝛑 будет включать только заявленный корень дерева Меркла, заявленные значения 𝚿 для выбранных местоположений и пути аутентификации для каждого из этих значений (относительно корня). Затем можно проверить 𝛑, сверив все пути аутентификации для заявленных значений с корнем, повторно получив случайность 𝛒 из корня и проверив, что верификатор PCP принимает заявленные значения при запуске со случайностью 𝛒.¹

Подводя итог, мы использовали хеш-функцию H для реализации «безопасной предварительной выборки», которая позволяет включить в короткое доказательство 𝛑 одну случайную локальную проверку длинного доказательства 𝚿.

[1]: Это «обоснование» того, почему безопасная предварительная выборка работает, является просто интуицией, а получение формального доказательства безопасности требует некоторой работы. Например, злоумышленник может попытаться использовать множество различных доказательств 𝚿 в поисках «благоприятного» выбора случайности 𝛒, а затем включить этот благоприятный выбор в 𝛑. Доказательство безопасности должно установить, что такие доказывающие, да и вообще любые эффективные доказывающие, с высокой вероятностью потерпят неудачу.

Прозрачность исходит от криптографии

Важной особенностью конструкции Микали является то, что единственной криптографией, необходимой для создания или проверки краткого доказательства 𝛑, является криптографическая хэш-функция H (например, SHA-256 или Keccak). Таким образом, выбор H является единственным «глобальным параметром», который должны знать все пользователи системы доказательств, и этот выбор может быть сделан с помощью общедоступной информации. Это означает, что криптографические доказательства, полученные с помощью конструкции Микали, прозрачны .

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

(G, 𝛂·G, 𝛂²·G, 𝛂³·G, …)

где G — элемент группы, а 𝛂 — секретный скаляр. Такие глобальные параметры должны быть отобраны доверенной стороной или посредством многосторонней церемонии , потому что пользователи не должны знать «лазейку» 𝛂. В самом деле, знание 𝛂 позволило бы создавать достоверные доказательства ложных утверждений.

Масштабируемость исходит из вероятностного доказательства

Еще одна важная особенность конструкции Микали заключается в том, что время создания/проверки короткого доказательства 𝛑 близко ко времени создания/проверки длинного доказательства 𝚿. Это просто потому, что необходимые криптографические операции недороги по сравнению с операциями PCP. Таким образом, мы узнаем, что эффективность конструкции Микали по существу определяется эффективностью базовой PCP. В частности, если PCP является масштабируемым (создание 𝚿 занимает время, квазилинейное по T, тогда как проверка 𝚿 происходит экспоненциально быстрее) , то конструкция Микали дает масштабируемое криптографическое доказательство . Конструкции масштабируемых ПКП известны (см. эту статью ).

К сожалению, стоимость ПХФ остается очень высокой, что делает их непригодными для практического использования. Из-за этого реализации STARK не основаны на PCP через конструкцию Micali. Вместо этого они основаны на другом типе вероятностного доказательства, для которого можно добиться масштабируемости с хорошими конкретными затратами и даже с нулевыми знаниями. Мы обсудим это далее.

IOP: новое понятие вероятностного доказательства

Эффективные STARK основаны на типе системы вероятностных доказательств, известной как интерактивные доказательства оракула (IOP), которая была введена в 2015 году. Неформально доказывающий и проверяющий участвуют в интерактивном протоколе, где в каждом раунде проверяющий отправляет некоторую случайность 𝛔ᵢ в доказывающий, и доказывающий отвечает длинным доказательством 𝚿ᵢ. В конце взаимодействия верификатор выполняет случайную локальную проверку всех длинных доказательств (𝚿₁, 𝚿₂,…), отправленных проверяющим на протяжении всего взаимодействия. См. схему на рис. 4. Обратите внимание, что PCP — это просто «неинтерактивный IOP», и, таким образом, это ограниченный случай.

За последние несколько лет исследователи разработали множество принципов проектирования высокоэффективных IOP: [BCGV16] , [BCGRS16] , [BB+16] , [BBGR16] , [BCFGRS16] , [BBHR17] , [BBHR18] , [ BCRSVW18] , [BKS19] , [BGKS19] . Протокол IOP, который мы используем в наших конструкциях STARK, наиболее тесно связан с [BBHR18] .

Предыдущие посты описывают эффективное IOP

Теперь мы объясним, как наши предыдущие публикации об арифметизации и низкоуровневом тестировании на самом деле описывали эффективное ВГД. На рисунке 5 мы приводим схему этого ВГД. Первой фазой протокола является арифметизация , которая преобразует данный оператор CI ( 𝐀 , x , y , T ) в задачу, которая включает в себя установление границ степени для определенных полиномов. Второй этап — низкоуровневое тестирование , которое решает эту последнюю проблему. Мы суммируем рабочий процесс протокола.

Арифметизация (синяя область на рисунке 5) . Доказательство и верификатор преобразуют программу 𝐀 в набор полиномиальных ограничений, как описано в нашем посте « Арифметизация I» . Кроме того, программа проверки выполняет вычисление, описываемое ( 𝐀 , x , y , T ), получая трассировку вычислений T -шагов.

Затем, как описано в нашем посте « Арифметизация II », доказывающая сторона кодирует эту трассу, чтобы получить закодированную трассу 𝚽, которая отправляется верификатору. (Здесь доказывающему не нужно получать случайность от верификатора перед отправкой 𝚽.) После этого верификатор отправляет случайность 𝛔₀, что позволяет как доказывающему, так и проверяющему «связать» все полиномиальные ограничения в однополиномиальное ограничение, взяв их случайную линейную комбинацию. Доказывающий комбинирует этот последний с закодированной трассой 𝚽, чтобы получить составленный полином 𝚵, который отправляется верификатору. Верификатор гарантирует с помощью локальной проверки согласованности, что 𝚽 и 𝚵 должным образом связаны. На этом этапе, если локальная проверка согласованности проходит с высокой вероятностью, утверждение CI истинно тогда и только тогда, когда 𝚽 и 𝚵 имеют низкую степень.

Тестирование низкой степени (серая область на рис. 5) . Доказывающая использует протокол FRI (описанный в нашем посте о тестировании низкой степени ), чтобы убедить верификатор в том, что 𝚽 и 𝚵 являются оценками полиномов низкой степени. Это включает в себя участие в протоколе, в котором в каждом раунде верификатор отправляет некоторую случайность 𝛔ᵢ, а доказывающий отвечает вспомогательным доказательством 𝚿ᵢ, а в конце протокола верификатор выполняет случайную локальную проверку 𝚽, 𝚵 и 𝚿ᵢ. Если верификатор протокола FRI принимает с высокой вероятностью, то 𝚽 и 𝚵 имеют желаемые степени. Если это так, верификатор заключает, что утверждение CI ( 𝐀 , x , y , T ) является истинным утверждением.

Криптографические доказательства через конструкцию BCS

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

Вывод

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

На этом мы завершаем серию статей о STARK Math. Мы надеемся, что это было ценно для вас!

Алессандро Кьеза и Гидеон Кемпфер