Оригинал — https://sjkelleyjr.medium.com/zk-snark-concepts-explained-like-youre-15-54755f87c6d1

Канал — https://t.me/jetix37eth

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

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

Они обычно преподаются как предшественники SNARK'ов, поскольку одна и та же ментальная модель может быть перенесена между ними, а интерактивное доказательство может быть превращено в SNARK с помощью преобразования Фиата-Шамира.

Протокол Фиата-Шамира

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

Случайный оракул

Это связано с преобразованием Фиата-Шамира. Когда кто-то говорит о модели случайного оракула, он говорит: “мы предполагаем, что существует некоторая идеализированная случайная хэш-функция”. Вы могли бы думать о модели случайного оракула как о ментальной модели, которая была использована для разработки техники преобразования Фиата-Шамира, чтобы убрать интерактивность из интерактивных доказательств.

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

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

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

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

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

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

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

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

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

Видео подробнее:

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

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

Протокол ГКР

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

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

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

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

R1CS

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

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

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

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

Схема полиномиальных обязательств — это способ для верифицируемого привязаться к данному многочлену, не раскрывая его коэффициенты верификатору.

На момент написания этой статьи двумя распространенными схемами полиномиальных обязательств являются KZG и FRI, но есть и другие версии, с которыми люди экспериментируют, такие как Dory, Ligero и Brakedown.

Схемы полиномиальных обязательств обычно комбинируются с полиномиальными интерактивными доказательствами оракула и преобразованием Фиата-Шамира для получения SNARK'ов.

KZG

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

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

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

Степени Тау

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

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

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

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

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

Быстрые доказательства близости интерактивного оракула Рида-Соломона (FRI)

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

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

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

Многолинейные расширения

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

Свидетель

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

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

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

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

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

• вентили схемы установлены правильно
• входные сигналы в схему указаны правильно
• соединение между вентилями правильное
• выходной сигнал схемы правильный

Термин “перестановка” происходит от способа доказательства подключения, поскольку PLONK использует перестановку многочлена для доказательства правильности подключения.