Zero-knowledge.

Эволюция ZKP от машины Тьюринга до ZK-STARKs.

Disclaimer: contains math Comment

• If you don’t understand something
• Not your fault, this stuff is hard
• Nobody understands it fully
• If you don’t understand anything
• My fault, anything can be explained at some level
• If you do understand everything
• Collect your Turing Award & Fields Medal
• Many open questions

by Remco Bloemen

1. Математическая основа
1.1. Группы и поля
1.1.1. Основные свойства
1.1.2. Конечные поля и их структура
1.1.3. Применение полей в криптографии
1.2. Полиномы и их свойства
1.2.1. Арифметика полиномов
1.2.2. Поля над полиномами
1.3 Эллиптические кривые
1.3.1 Арифметика эллиптических кривых
1.3.2 Арифметика эллиптических кривых в конечных полях
1.4. Криптографические примитивы
1.4.1. Хеш-функции
1.4.2. Схемы обязательств

2. Теоретические основы криптографии
2.1. Машина Тьюринга и теория сложности
2.2. Интерактивные системы доказательств
2.2.1. Определение и классификация
2.2.2. Примеры и применение

3. Основы доказательств с нулевым разглашением (ZKP)
3.1. Протоколы GMW и BMF
3.2. Протокол Фиата-Шамира
3.3. Протокол Шнорра

4. Проверяемые вычисления и интерактивные протоколы
4.1. PCP и IOP
4.1.1. Основы и определения
4.1.2. Примеры использования
4.2. Коды Рида-Соломона
4.3. Деревья Меркла
4.3.1. Принцип работы и применение
4.3.2. Варианты и усовершенствования

5. Развитие и оптимизация протоколов
5.1. Фаст Фурье и Лагранжева интерполяция
5.2. Алгоритмы масштабирования и оптимизации
5.2.1. Пакетная инверсия Монтгомери
5.2.2. Интерактивные системы доказательств высокой производительности

6. Примеры реализации и применения
6.1. Системы ZK-SNARKs
6.1.1. Алгоритмические основы
6.1.2. Практическое применение
6.2. Теория и практика доказательства близости с Fast RS IOP

Введение

Эта статья прямое продолженние статьи Tawer95 с обзором технологии ZK-STARK, но если первая часть была ознакомительной, то в этой статье мы попробуем погрузиться гораздо глубже в эту кроличью нору.

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

Если вы откроете оригинальную работу 2018 года в которой впервые была описана технология ZK-STARK, весьма вероятно, если вы не работаете на острие криптографии это отпугнет вас и вы мало что поймете. Моя цель показать, то что делает ZK-STARK с точки зрения криптографии, при этом заранее подготовив читателя. Мы пройдемся по нескольким ранним протоколам ZKP, что в полной мере позволит нам осознать красоту "старков".

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

База

Группы и поля

Группы:

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

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

1. Замкнутость: Если взять любые два элемента из группы и применить к ним операцию, результат тоже будет принадлежать этой группе. Например складывая целые числа у вас всегда получится целое число.
2. Ассоциативность: Порядок применения операций не влияет на результат (например, (a + b) + c всегда будет равно a + (b + c)).
3. Наличие единичного элемента: В группе всегда есть такой элемент, который в операции с любым другим элементом оставляет его без изменений (например, в сложении таким элементом является 0).
4. Наличие обратного элемента: Для каждого элемента в группе существует такой, который "аннулирует" его в данной операции (для числа a это будет -a, потому что a + (-a) = 0).

Поля: ПОФИКСИТЬ ФОРМУЛЫ

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

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

1. Коммутативность: В полях операции сложения и умножения коммутативны, то есть порядок операндов не влияет на результат (например, a+b=b+a и a×b=b×a).
2. Дистрибутивность: Умножение в поле дистрибутивно относительно сложения. Это означает, что a×(b+c) будет равно a×b+a×c.
3. Единица и Ноль: В поле всегда присутствуют два особенных элемента: ноль (0), который является нейтральным элементом для сложения, и единица (1), нейтральный элемент для умножения.
4. Обратные Элементы: В поле для каждого элемента, кроме нуля, существует обратный относительно умножения (например, для числа a обратным будет 1/a, так что a×(1/a)=1).

Конечные поля:

Конечные поля, также известные как поля Галуа, являются особым классом полей, которые содержат конечное число элементов. Например конечно поле может содержать всего 5 или 12 элементов. Количество элементов называется степенью поля. Нас будут интересовать поля с простым числом(1,2,3,5,7,11...) элементов, так как они обладают не которыми особыми свойствами о которых мы поговорим несколько позже.

Применений групп и полей в криптографии В криптографии наиболее распространненым используемыми полями являются поля Галуа над степенью простых чисел с определенными операциями по модулю. Что это значит? Это говорит нам о том что в криптографии используются конечно множество чисел от 0 до p где p-некоторое простое число, со специальными операциями умножения и сложения по модулю:

Операция % означает что ответом будет остаток от деления на P, например:
(2+6)%3=2
(4+12)%16=0

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

1. Сложность Обратных Задач: В конечных полях решение некоторых задач, таких как дискретное логарифмирование, является вычислительно сложным. Это означает, что хотя умножение или возведение в степень в поле можно выполнить относительно легко, обратная операция (например, определение логарифма) без знания некоторых ключевых данных является очень трудоемкой. Это свойство делает конечные поля особенно подходящими для систем с открытым ключом.
2. Применение в Эллиптических Кривых: Конечные поля являются основой для криптографии на эллиптических кривых (ECC). Эллиптические кривые над конечными полями обеспечивают более высокий уровень безопасности при меньшем размере ключа по сравнению с традиционными методами, такими как RSA. Это делает их особенно привлекательными для использования в устройствах с ограниченными ресурсами.
3. Универсальность и Гибкость: Конечные поля обеспечивают гибкую среду для разработки различных криптографических алгоритмов. Они могут быть настроены с разными порядками и свойствами, что позволяет создавать многообразные и настраиваемые криптографические схемы.
4. Поддержка Алгебраических Операций: Математические операции в конечных полях могут быть эффективно реализованы на аппаратном и программном уровнях, что обеспечивает эффективность в вычислительном отношении для криптографических применений.

Полиномы и их свойства ПОФИКСИТЬ ФОРМУЛЫ

Давайте начнем с того, что полином = многочлен, это слово пугает гораздо меньше на мой вкус. Но, чем же может быть полезны полиномы для криптографии? Ответ кроется в том, что для многочленов высоких степеней, то есть для выражений типа (a1×X^n+a2×X^(n-1)+....+an) где n - большое число, нахождение корней, крайне не тривиальная задача занимающая много вычислительных мощностей, что позволяет с помощью полином кодировать информацию таким образом, чтобы ее трудно было расшифровать, особенно если кроме высоких степеней это будут полиномы над конечным полем.
Вот несколько примеров применения полиномов в криптографии:

1. Алгоритмы Факторизации: Факторизация многочленов, особенно над конечными полями, может быть сложной задачей. Это свойство используется в некоторых криптосистемах, где безопасность зависит от сложности разложения многочлена на множители.
2. Полиномиальные Интерполяции и Схемы Разделения Секрета: Интерполяция полиномов, например, метод Лагранжа, используется в схемах разделения секрета, таких как схема Шамира. В этих схемах секрет делится на части, и для восстановления исходного секрета необходимо собрать определенное количество этих частей.
3. Хэширование и Псевдослучайные Генераторы: Полиномы также используются в конструкциях хеш-функций и псевдослучайных генераторов, где нужны однонаправленные функции, то есть легко вычислимые в одном направлении и практически невозможные для обращения без дополнительной информации.
4. Коды, Исправляющие Ошибки: Полиномы лежат в основе многих алгоритмов кодирования, исправляющих ошибки, важных для защиты данных от искажений при передаче. Эти коды часто основаны на полиномиальных вычислениях.
5. Алгоритмы Дискретного Логарифмирования: В криптографии на эллиптических кривых и в других схемах безопасность часто основана на сложности вычисления дискретных логарифмов в группах, порожденных полиномиальными функциями.

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

Арифметика полиномов ДОБАВИТЬ ПРИМЕРЫ

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

1. Сложение и Вычитание: Сложение или вычитание полиномов происходит путем сложения или вычитания их соответствующих коэффициентов. Например, если у нас есть два полинома (БЛЯ Я В ДУШЕ НЕ ЕБУ КАК ВСТАВИТЬ СЮДА НОРМ ФОРМУЛУ):
2. Умножение: При умножении полиномов каждый член одного полинома умножается на каждый член другого полинома. Это более сложная операция, чем сложение или вычитание, и может привести к увеличению степени результата. Результатом умножения полиномов является полином, степень которого равна сумме степеней исходных полиномов.

Поля над полиномами: ДОБАВИТЬ ПРИМЕРЫ

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

1. Сложение и Вычитание: Эти операции выполняются так же, как и с обычными многочленами — складываем или вычитаем соответствующие коэффициенты полиномов. Но есть одна особенность: если результат сложения или вычитания выходит за пределы конечного поля, мы берем остаток от деления на число, определяющее размер поля.
2. Умножение: Когда мы умножаем полиномы, мы также умножаем их коэффициенты и складываем степени переменных. В конечных полях важно следить, чтобы результаты умножения не выходили за пределы поля. Если это происходит, мы снова используем остаток от деления.
3. Деление: Деление полиномов в конечных полях может быть более сложным, чем в обычной арифметике. Мы используем алгоритм деления многочленов, но также должны учитывать ограничения конечного поля. Иногда это может потребовать дополнительных шагов для нахождения обратного элемента.
4. Возведение в Степень и Модульная Арифметика: Возведение полинома в степень и другие операции выполняются с учетом того, что все коэффициенты и результаты должны оставаться в пределах конечного поля. Это означает, что мы часто используем модульную арифметику для "обрезания" результатов, чтобы они соответствовали размеру поля.

Эллиптические кривые
Эллиптическая кривая — это множество точек, удовлетворяющих определенному уравнению вида:

где a и b — константы, удовлетворяющие условию:

чтобы исключить особые точки, где кривая пересекает сама себя или имеет разрыв.

Выше пример того как может выглядеть эллиптическая кривая. Основные причина распространнености :

1. Из за сложности задачи дискретного логарифмирования в полях эллиптических кривых, это значит что есть вы возведете точку на эллиптической кривой и попросите другого человека узнать в какую степень вы возвели точку, ему понадобится несравнимо больше времени чем вам для возведения.
2. Также алгоритмы на эллиптических кривых более эффективны по сравнению со стандартными методами шифрования например 256 битный ключ эллиптической кривой примерно равен по безопасности 3072 битному ключу RSA.
3. Так же они быстрее классических алгоритмов и эффективнее по памяти.

Криптографические примитивы

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

1. Симметричное Шифрование: В симметричном шифровании используется один и тот же ключ для шифрования и расшифрования данных. Примеры алгоритмов симметричного шифрования включают AES (Advanced Encryption Standard) и DES (Data Encryption Standard).
2. Асимметричное Шифрование (Криптография с Открытым Ключом): Здесь используются два разных ключа — открытый для шифрования и закрытый для расшифрования. Примеры включают RSA, ECC (Эллиптические Кривые).
3. Цифровые Подписи: Это алгоритмы, позволяющие подтвердить подлинность и целостность сообщения или документа. Они используют пару ключей: закрытый ключ для создания подписи и открытый для её проверки. Примеры включают RSA, DSA (Digital Signature Algorithm) и алгоритмы на основе эллиптических кривых.
4. Криптографические Хеш-Функции: Методы позволяющие необратимо превратить обьект (картинку, текст, число, что угодно) в уникальный набор байтов - идентификатор.
5. Протоколы Рукопожатия и Аутентификации: Это механизмы, обеспечивающие безопасное установление соединений и подтверждение идентичности сторон. Примеры включают TLS (Transport Layer Security) и SSL (Secure Sockets Layer).
6. Псевдослучайные Генераторы (PRNGs): Это алгоритмы, генерирующие последовательности чисел, которые выглядят случайными, но на самом деле являются полностью определенными предыдущими значениями.
7. Криптографические Схемы Разделения Секрета: Методы, позволяющие разделить секрет на части, так что для восстановления исходного секрета нужно иметь определенное количество этих частей. Пример — схема Шамира.
8. Схемы обязательств: Методы позволяющие утверждающему, что либо подтвердить начие информации таким образом, чтобы при раскрытии информации, он не мог подменитть ее с момента начала протокола. Это похоже на игру в которой один загадывает слово, после чего записывает его на бумажке, чтобы угадывающий точно знал, что слово существует и оно неизменно.

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

Хеш-функции

Хеш-функции должны обладать несколькими свойставами:

• Необратимость (невозможность вернуть хеш в исходное состояние или получить из него какие либо данные о начальном состоянии)
• Скорость вычисления
• И минимальное количество коллизий, то есть ситуаций в которых разные наборы данных приводят к одному результату.

На данный момент Starknet используют 3 вида хеш-функций:

1. Keccak - стандартный хеш используемый в SHA256
2. Pedersen(https://iden3-docs.readthedocs.io/en/latest/_downloads/4b929e0f96aef77b75bb5cfc0f832151/Pedersen-Hash.pdf) 2019 - хеш дружественный к элиптическим кривым
3. Poseidon(2019) https://eprint.iacr.org/2019/458 - хеш специально разработанный для крипто в 2019 году один из самых новых алгоритмов губчатых хешей (основной алгоритм хеширования во многих ZKP в том числе ZK-STARK)

Первый из них мы будем мы разбирать не будем так как это IT стандарт и его разборы можете найти в свободном доступе достаточно легко. ПРИМЕР1 ПРИМЕР2 ПРИМЕР3 ПРИМЕР4.

Starknet keccak, usually denoted by sn_keccak_, is defined as the first 250 bits of the Keccak256 hash (this is just Keccak256 augmented in order to fit into a field element).

Если говорить о хеше Pedersen, то он хеширует точку на эллиптической кривой над над конечным полем простого порядка.
Эллиптическая кривая имеет формулу:

Соотвественно для того где:

Напоминаю, что для обеспечения надежности используются достаточно большие числа, как например выше, но так как мы работаем в конечном поле, вычисления над ними выполняются гораздо быстрее.
Давайте определим поле используемое в ZK-Stark на данный момент.
Для определения поля нам необходимо знать, порядок поля, на данный момент в Starknet используется:

Это значит что в поле входят все числа от 0 до числа выше, не включая само число.
Далее нам необходимо задать формулу хеша:

Здесь мы видим, что хеш Педерсона, хеширует точку на эллиптической кривой, преобразуя ее в число (X координату результирующей точки на кривой). Стоит отметить что если мы не хотим хешировать 2 обьекта (2 координаты точки), мы можем хешировать только один следующим образом: h(0,a).

Если же нам нужно хешировать массив данных произвольной длины, то можно сделать следующим образом:

Где n - количество эллементов массива.

Теперь давайте подробнее рассмотрим формулу и разберемся, что именно делает эта хеш-функция.
Начнем с определения входных данных, a,b - представляют два целых числа длинной 252-бит, это значит что максимальное число представленное этими числами это 2^252-1.

Соответсвенно:

a low - это первые 248 битов числа а, аналогично для b.

a high - это последние 4 бита числа а, аналогично для b.

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

P0,P1,P2,P3 - Это константные точки на кривой, которые представляют собой десятичные числа выбранные из числа Pi, то есть это случайным образом выбранные последовательности чисел выбранные из числа Pi, как источника энтропии.
Пример:

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

• То есть нулевой элемент это всегда 3 элемент массива чисел.
• Индекс первого элемента всегда 2+LOW_PART_BITS(количество битов взятых для a low и b low, у нас это 248) = 250
• Индекс второго элемента это 2+размер поля в битах у нас это 252, соответсвенно 254 элемент.
• Индекс третьего элемента это 2+размер поля в битах + количество нижних битов, соответсвенно 502 элемент.

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

PCP IOP коды рида соломона деревья меркла ZK Snarks ZK Starks

Completeness: if the statement is true, the honest verifier (that is, one following the protocol properly) can be convinced of this fact by a honest prover.

Soundness: if the statement is false, no cheating/malicious prover can convince the honest verifier that it is true, except with some negligible probability.

Zero-knowledge: if the statement is true, no cheating verifier learns anything other than this fact.
кратце, доказательство низкой степени — это (вероятностное) доказательство того, что по крайней мере некоторый высокий процент (например, 80%) данного набора значений представляет собой оценки некоторого конкретного полинома, степень которого намного ниже, чем количество заданных значений. . Интуитивно, просто думайте об этом как о доказательстве того, что «некоторый корень Меркла, который, как мы утверждаем, представляет собой полином, на самом деле представляет собой полином, возможно, с несколькими ошибками». В качестве входных данных мы имеем:
Конечные Поля

Двочиные поля

Быстрое преобразование фурье
Пакетная инверсия монгомери
Интерполяция лагранжа

Абстрактная математика
Машина тьюринга

Интерактивная машина Тьюринга

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

Фиата-Шамира

протокола Шнорра

ZKP Общего назначения

Краткость доказательства

О том что доказательство это не точная штука, а снижение вероятности ошибки

Fast Reed-Solomon Interactive Oracle Proof of Proximity

FRI
IOPP
Fast RS IOP

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

ZK-STARKS не полагается на пары частного и открытого ключей (такие как ECDSA), но полагается на устойчивое к коллизиям хеширование для интерактивных решений (которое алгоритм Гровера существенно не нарушает) и случайную модель оракула (модель, которая обычно используется вместо этого). общих криптографических хеш-функций, где для вывода оракула требуются строгие предположения о случайности) для неинтерактивных доказательств (zk-nSTARK, n = неинтерактивный), поэтому ZK-STARK в настоящее время устойчивы к атакам квантового компьютера.