Концепции zk-SNARK объясняются на разных уровнях сложности

Последние несколько месяцев я изучал материалы zk-SNARK и помню, каково было слышать многие термины, используемые исследователями zk-SNARK, прежде чем я узнал, что они означают.

Ну, видите ли, сначала вам нужно FRI системы PLONK, чтобы она была R1CS…

Я решил написать ELI15 для жаргона zk-SNARK, так как во время учебы еще не встречал ничего подобного. Обратите внимание на 1 (ELI15). В своих объяснениях я предполагаю наличие некоторого базового понимания криптографии (хеширование, деревья Меркла и т. д.), полиномов и компьютерных наук.

Этот пост написан для моей выгоды. Ведь

Если вы не можете объяснить это шестилетнему ребенку, вы сами этого не понимаете. — Альберт Эйнштейн

Я надеюсь заявить о себе так, чтобы другие исправили любое недопонимание, которое может возникнуть у меня по этому вопросу. Тем не менее, я надеюсь, что этот пост также полезен для других. По этим причинам запись будет общедоступной.

Обратите внимание, что целевой аудиторией этого поста является тот, кто не знаком с zk-SNARK, поэтому многие определения будут математически неточными (см. определение Конечного поля ниже для пример).

Интерактивные доказательства

Интерактивные доказательства — это протоколы, в которых доказывающая и проверяющая стороны взаимодействуют друг с другом таким образом, что доказывающая сторона может доказать проверяющей стороне, что они выполнили некоторые вычисления правильно. Их обычно преподают в качестве предшественника SNARK, поскольку одна и та же ментальная модель может быть перенесена между ними, а интерактивное доказательство может быть преобразовано в SNARK с помощью преобразования Фиата-Шамира.

Трансформация Фиат-Шамир

Так что же такое трансформация Fiat-Shamir?

Это способ сделать интерактивную систему проверки неинтерактивной (N в SNARK). Дэн Боне предлагает хорошее объяснение здесь. Как правило, вы заменяете двусторонние сетевые вызовы между доказывающим и проверяющим хеш-функцией, с помощью которой проверяющий может проверить правильность выполнения доказывающего, чтобы обеспечить его случайность.

Случайная модель Oracle

Это связано с преобразованием Fiat-Shamir. Когда кто-то говорит о модели случайного оракула, они говорят: «Мы предполагаем, что существует некоторая идеализированная случайная хеш-функция». Модель случайного оракула можно рассматривать как ментальную модель, которая использовалась для разработки метода преобразования Фиата-Шамира для удаления интерактивности из интерактивных доказательств.

Интерактивное доказательство Oracle

Теперь, когда мы дали определения большинству этих терминов, определение этого будет проще, так как мы можем использовать эти термины в этом определении.

Интерактивное доказательство оракула (называемое IOP) – это интерактивное доказательство, в котором используется оракул для повышения эффективности доказательства и проверки.

Лемма Шварца-Циппеля

Это наблюдение буквально делает SNARK возможными. — Дэн Боне

Лемма Шварца-Циппеля утверждает, что если вы случайным образом оцениваете ненулевой полином, вероятность того, что оценка равна 0, равна не более чем степени полинома (назовем ее d), деленной на число возможных входные данные полинома (назовем его p).

Звучит сложно, но интуитивно это означает, что вероятность того, что вы выберете корень полинома (d) из всех возможных значений для выбора (p), составляет < em>д/стр.

Что интересно в этой лемме, так это то, что она применима и к полиномам от многих переменных.

Протокол проверки суммы

Этот интерактивный протокол использует лемму Шварца-Циппеля для вероятностной проверки равенства двух полиномов без непосредственной оценки обоих полиномов.

У Дэвида Вонга есть пояснительное видео здесь.

Булев гиперкуб

Кстати, об этом видео. Дэвид упоминает логический гиперкуб. Что это?

Вы часто будете видеть, что это написано как {0,1}^n. Математическая нотация выдает это как набор битовых строк длины n. Например: {0,1}² будет равно {00, 01, 10, 11}.

Протокол GKR

GKR означает авторов протокола: Goldwasser, Kalai и Rothblum. Протокол GKR был одним из первых протоколов (опубликован в 2015 г.) для вероятностной проверки оценки арифметической схемы общего назначения с использованием протокола проверки суммы.

Арифметическая схема

Если вы знакомы с традиционными схемами, которые работают с логическими значениями и операторами, то это та же концепция, но примененная (как вы уже догадались) к арифметике. Следует отметить одну интересную особенность вентилей этих схем: в контексте zk-SNARK на момент написания этой статьи они работали только с операторами сложения и умножения.

R1CS

R1CS расшифровывается как "Система ограничений ранга 1". Ранг 1 исходит из линейной алгебры и подразумевает, что система ограничений использует матрицы. Это обычное промежуточное представление для арифметических схем на пути от вычислений к zk-SNARK.

Виталик опубликовал запись в блоге, объясняющую, как перейти от вычислений к zk -SNARK, который содержит изображение, которое мне показалось полезным, когда я думал об этом пайплайне.

В посте также есть основное пошаговое объяснение как построить R1CS-представление схемы, построенной из очень простых вычислений, чтобы было легко следовать.

Схема полиномиальных обязательств

Схема фиксации полинома (вы можете услышать это от исследователей как PCS) — это способ, с помощью которого доказывающая сторона принимает заданный полином, не раскрывая коэффициенты полинома проверяющей стороне.

Две распространенные схемы полиномиальных обязательств на момент написания этой статьи: KZG и FRI, но есть и другие версии, с которыми люди экспериментируют, например Дори, Лигеро< /a> и Brakedown.

Опять же, Дэн Боне дает отличное объяснение высокого уровня в этом видео.

Полиномиальные схемы обязательств обычно сочетаются с полиномиальными интерактивными доказательствами оракула и преобразованием Фиата-Шамира для создания SNARK. Удивлен, что ты все это понял? 😛

КЗГ

KZG означает Кейт, Заверуча и Голдберг, которые являются авторами этой полиномиальной схемы обязательств.

Он использует «силы Тау» для генерации глобальных параметров, которые затем используются для фиксации полиномов. Это доверенная установка, поэтому требуется, чтобы силы Тау были удалены после того, как они используются для генерации глобальных параметров. Поскольку их необходимо удалять, вы часто будете слышать, как силы Тау называют «токсичными отходами».

Вы также услышите о «церемониях KZG», которые позволяют каждому участнику церемонии внести свой вклад в случайность сил Тау, так что только 1 участник церемонии должен удалить свой вклад в случайность, чтобы токсичные отходы были выброшены. .

Силы Тау

Итак, что это за силы Тау? Тау — это элемент случайного поля, который многократно умножается на себя и на элементы вашей группы во время полиномиальной схемы обязательств KZG.

Конечное поле

Говоря об «элементах поля», вы можете услышать, что исследователи часто упоминают «конечное поле», что это такое?

На момент написания этой статьи SNARK не может работать со всеми целыми числами, поэтому конечное поле — это подмножество целых чисел, для работы с которым определен ваш SNARK. Элементы поля, о которых я упоминал в Powers of Tau — это элементы этого определенного конечного поля.

Конечные поля используют модульную арифметику, чтобы ограничить поле до необходимого размера.

Быстрые интерактивные доказательства близости Oracle Reed-Solomon (FRI)

FRI — это популярная альтернативная полиномиальная схема обязательств по отношению к KZG, которая не требует доверенной настройки (называемой "прозрачной", что, следовательно, означает T в STARK). Он использует кодировку Рида-Соломона и деревья Меркла для вероятностной проверки достоверности полинома степени D с использованием менее чем D запросов (отсюда и «Fast»).

У Виталика есть хороший объяснитель здесь.

Интерполяция Лагранжа

Интерполяция Лагранжа — это способ построения многочлена, проходящего через заданный набор точек. Он используется как полиномиальный аналог кодирования Рида-Соломона, при котором, если два полинома отличаются даже на небольшую их интерполяционные оценки Лагранжа будут сильно различаться.

В субреддите /r/3Blue1Brown есть отличное объяснение того, как построить интерполяцию Лагранжа здесь. Но важной частью в контексте SNARK является свойство увеличения расстояния, упомянутое выше.

Многострочные расширения

Многолинейные расширения (часто сокращенно до MLE) – это полилинейные полиномы (например, x_1*x_2 +4*x_1 +3*x_2), построенные из многомерных полиномов (например, 3x² + 2xy + y³ + 5) с помощью интерполяции Лагранжа. Эти полилинейные полиномы полезны в контексте zk-SNARK, потому что их обычно быстрее проверить.

Свидетель

Свидетель – это входные данные для некоторых вычислений, которые используются для подтверждения правильности утверждения без непосредственного предоставления утверждения.

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

Обратите внимание, что свидетель доказывающего является секретным, а это означает, что он не передается проверяющему напрямую, а вместо этого дается краткое доказательство (отсюда буква S в SNARK).

Перестановки по базисам Лагранжа для экуменических неинтерактивных аргументов знания (PLONK)

PLONK — это популярный тип SNARK, который включает в себя доказательство 4 фактов об арифметической схеме

1. ворота схемы правильные
2. входы схемы правильные
3. проводка между воротами исправна
4. выход схемы правильный

Термин «перестановка» происходит от способа доказательства соединения, поскольку PLONK использует перестановку полинома для доказательства правильности соединения.

Если вы представляете проект ZK и ищете инженера, защитника разработчиков или специалиста по безопасности, пишите мне в Twitter.

Если вы хотите пройти учебный курс по разработке ZK или безопасности, подпишитесь на этот список рассылки.

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

:::информация Также опубликовано здесь.

:::