Доказательства с нулевым разглашением: введение в основы

Введение

Доказательства с нулевым разглашением — один из самых мощных инструментов, созданных криптографами. К сожалению, большинство людей не понимают, как они работают. Эта статья призвана исправить ситуацию: в ней представлен подробный обзор доказательств с нулевым разглашением, начиная с базовых принципов. Мы рассмотрим лежащие в их основе теорию, математику и криптографию, чтобы каждый мог понять последние разработки в Solana, а именно ZK Compression и будущее интероперабельности.

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

• Основы криптографических инструментов: объясняем хеш-функции и деревья Меркла
• Модель программирования Solana: введение в разработку на Solana

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

Это также первая статья из двухчастной серии о доказательствах с нулевым разглашением. Настоятельно рекомендуем сначала прочитать ее и только потом переходить к статье Доказательства с нулевым разглашением: применение в Solana.

Теория доказательств с нулевым разглашением

В 1989 году исследователи MIT Shafi Goldwasser, Silvio Micali (основатель Algorand) и Charles Rackoff опубликовали работу Сложность знания в интерактивных системах доказательств. Они исследовали системы, в которых одна сторона (доказывающая) обменивается сообщениями со второй стороной (проверяющей), чтобы убедить ее в истинности некоторого математического утверждения. Они первыми задали вопрос: «Что, если доказывающая и проверяющая стороны не доверяют друг другу?» Вопрос в том, сколько информации, помимо факта истинности утверждения, получит проверяющая сторона в ходе обмена сообщениями. Например, доказывающая сторона может захотеть убедить проверяющую в том, что знает решение сложной головоломки, не раскрывая само решение.

Какие задачи мы вообще пытаемся решить?

Трехцветная раскраска графа

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

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

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

Для этого университет должен создать граф, в котором каждая вершина представляет занятие. Две вершины соединяются ребром, если у соответствующих занятий есть хотя бы один общий студент. Университет назначает каждому занятию временной интервал так, чтобы никакие два смежных занятия не проходили одновременно. Затем университет фиксирует обязательство по готовому расписанию с помощью криптографической схемы обязательств. Для этого он создает криптографический хеш назначенного каждому занятию временного интервала и передает хеши проверяющей стороне, не раскрывая сами интервалы. Затем внешняя аудиторская компания случайным образом выбирает пары смежных занятий и запрашивает проверку назначенных им интервалов. Университет раскрывает зафиксированные интервалы для выбранной пары смежных занятий и предоставляет исходные обязательства (то есть хеши), чтобы внешняя аудиторская компания могла проверить раскрытые значения. Последние этапы — запрос, раскрытие и проверка — повторяются, пока внешняя аудиторская компания не убедится, что занятия не пересекаются. Настоятельно рекомендую интерактивную демонстрацию трехцветной раскраски с нулевым разглашением от MIT, где эти этапы можно увидеть в реальном времени.

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

NP-полнота

В теории вычислительной сложности задача является NP-полной, если:

• Для любых входных данных ответом служит «да» или «нет»
• Если ответ — «да», это можно продемонстрировать с помощью короткого решения
• Корректность каждого решения можно быстро проверить, а алгоритм полного перебора может найти решение, перебрав все возможные варианты

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

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

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

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

Свойства доказательства с нулевым разглашением

Учитывая сложность и важность NP-полных задач, критически важно эффективно и безопасно доказывать решения задач этого класса. Доказательства с нулевым разглашением позволяют делать это без ущерба для конфиденциальности задействованной информации. Goldwasser, Micali и Rackoff предложили, чтобы все доказательства с нулевым разглашением обладали следующими свойствами:

• Полнота — если доказывающая сторона честна, она в итоге убедит проверяющую сторону
• Корректность — обманывающая доказывающая сторона никогда не убедит проверяющую сторону в ложном утверждении
• Нулевое разглашение — взаимодействие между доказывающей и проверяющей сторонами раскрывает только истинность утверждения и ничего больше

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

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

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

• Доказывающая сторона получает решение вычисления (то есть свидетельство), а затем отправляет обязательство по ответу на свидетельство
• Проверяющая сторона отвечает случайно сгенерированным проверочным значением
• Доказывающая сторона вычисляет итоговое доказательство на основе обязательства и проверочного значения

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

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

Эвристика Фиата — Шамира — это метод преобразования интерактивного доказательства знания в цифровую подпись на его основе. Так некоторый факт можно доказать публично, не раскрывая исходную информацию. Вместо того чтобы проверяющая сторона отправляла доказывающей случайное проверочное значение, доказывающая сторона может самостоятельно вычислить цифровую подпись с помощью случайной функции, например хорошей криптографической хеш-функции. Поэтому вместо того, чтобы проверяющая сторона изучала вычисление в 500 разных местах и проверяла их корректность, доказывающая сторона вычисляет корень Меркла для этого вычисления, использует его для псевдослучайного выбора 500 индексов и предоставляет 500 соответствующих ветвей данных дерева Меркла. Ключевая идея в том, что доказывающая сторона не знает, какие ветви ей придется раскрыть, пока данные не будут зафиксированы.

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

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

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

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

Эта статья также познакомит вас с правильной математической нотацией. Например, в следующем подразделе о теории множеств мы введем символы ∈, ∉ и ⊆. По сути, все эти символы — лишь обозначения чего-то другого. Доказательства с нулевым разглашением — тема не для начинающих, поэтому подавляющее большинство материалов о них не рассчитано на новичков. Авторы не объясняют значения этих символов и предполагают, что читатель понимает эту нотацию. Важно познакомиться с ней сейчас, чтобы она не пугала тех, кто хочет глубже изучить доказательства с нулевым разглашением. Постарайтесь не потеряться в обозначениях. Продолжайте читать: наступит момент, когда за этими символами вы увидите исходные понятия, а не просто греческие буквы.

Теория множеств

Теория множеств — раздел математики, изучающий совокупности объектов. Множество — это совокупность различных объектов. Эти объекты называются элементами множества. Например, рассмотрим множество фруктов:

В нотации множеств фигурные скобки обозначают совокупность элементов, образующих множество. Так мы понимаем, что яблоко, апельсин, груша и банан входят в множество, а, например, «картофель» — нет. Символ ∈ обозначает принадлежность множеству и читается как «является элементом». Аналогично, ∉ указывает, что элемент не принадлежит заданному множеству. Поэтому можно записать:

Это читается так: «яблоко является элементом множества Fruit, а картофель не является элементом множества Fruit».

Подмножества

Множества также могут состоять из других множеств. Подмножество — это множество, содержащее только элементы другого множества. Например, если у нас есть:

Можно сказать, что множество Citrus является подмножеством более крупного множества AllFruits. Также можно использовать введенное ранее множество Fruit и сказать, что Fruit является подмножеством более крупного множества AllFruit. В нотации множеств это записывается так:

Зачем мне это знать?

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

Здесь K задает диапазон всех возможных ключей. Мы можем построить доказательство с нулевым разглашением так, чтобы к этому множеству применялись определенные ограничения и допустимыми были только некоторые значения. Например, можно потребовать, чтобы ключ был числом от 1 до 5. 

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

Рекомендую выполнить отличные практические задания Khan Academy по базовой нотации множеств.

Теория чисел

Теория чисел — раздел математики, изучающий целые числа и арифметические функции. Целые числа можно определить как множество чисел без дробной части, включающее положительные и отрицательные числа, а также ноль. Более формально множество целых чисел задается так:

Здесь ℤ обозначает множество целых чисел, а многоточия показывают, что оно простирается от минус бесконечности до плюс бесконечности. Например, 12 — целое число, и -1978649832794275 — тоже целое число.

Рациональные числа

Рациональные числа — это числа, которые можно представить обыкновенной дробью с ненулевым знаменателем (то есть числом под чертой дроби, делителем). Например, $(\frac{1}{2}), 74, (\frac{2}{3})$ — рациональные числа. Более формально рациональные числа можно определить как множество чисел, представимых дробью pq, где p — числитель, q — знаменатель и q не равно 0. Для обозначения рациональных чисел используется символ ℚ. В нотации множеств это записывается так:‍

‍На первый взгляд это может показаться сложным, но запись описывает именно то, что сказано в предыдущем предложении. Этот странный математический жаргон читается так: «Q — множество всех дробей p, деленных на q, где p и q — целые числа, а q не равно нулю». 

Действительные числа

Действительные числа включают рациональные и иррациональные числа. Иррациональные числа нельзя представить простой дробью, а их десятичная запись бесконечна и непериодична. Например, число пи (то есть π) и $\sqrt{2}$ (то есть 1.4.1421…) — иррациональные числа. Пока пропустим их запись в нотации множеств, но отметим, что действительные числа обозначаются символом ℝ.

Зачем мне это знать?

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

Здесь также видна связь между теорией чисел и теорией множеств. Например, можно сказать, что множество всех целых чисел ℤ является подмножеством рациональных чисел ℚ. Это видно из приведенного выше определения рациональных чисел в нотации множеств, где числитель и знаменатель являются целыми числами.

Модульная арифметика

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

Часы

Рассмотрим аналоговые часы (ненавижу, что в наше время приходится уточнять: со стрелками, а не цифровые) с числами от 1 до 12. Если сейчас 11 часов и мы хотим узнать время через два часа, то не получим 13 часов. Вместо этого мы перейдем на новый круг и получим 1 час. Это можно выразить как $11 + 2 \equiv 1 \pmod{12}$ . Правильная математическая запись будет выглядеть так: $13 \bmod 12 = 1$. Программистам знакома операция взятия остатка в формате $13 \% 12 = 1$.

Операция взятия остатка

Когда мы пишем n mod k, это означает, что нам нужен остаток от деления n на k. Такая операция называется взятием остатка. Например:

• 25 mod 3 означает деление 25 на 3, которое дает остаток 1, поскольку $25 = 8 \times 3 + 1$
• 15 mod 4 означает деление 15 на 4, которое дает остаток 3, поскольку $15 = 3 \times 4 + 3$

В модульной арифметике остаток всегда неотрицателен.

Зачем мне это знать?

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

Рассмотрим вычисление x + y = z. Допустим, мы работаем с конечным полем, заданным простым числом p = 17 (мы совсем скоро разберем это понятие, а пока считайте его множеством всех целых чисел от 0 до 16 с переходом на новый круг при 17). В этом поле вычисление будет иметь вид (x + y) mod p = z. Если x = 12, а y = 15, вычисление будет следующим:‍

Модульная арифметика позволяет выполнять вычисления в управляемом диапазоне значений, заданном простым числом p. Это особенно важно, поскольку объем памяти компьютеров и процессоров ограничен, поэтому обычно мы работаем с целыми числами фиксированного размера, например u32 или u64. Модульная арифметика гарантирует, что значения остаются в этих границах. Кроме того, использование простых чисел добавляет уровень сложности. С точки зрения криптографии это крайне важно, поскольку повышает безопасность и делает некоторые математические свойства более предсказуемыми и надежными.

Например, модульная арифметика используется в zk-SNARKs, чтобы вычисляемые значения оставались в заданных управляемых границах. Она также применяется для создания арифметических схем над заданным множеством чисел. Это позволяет выражать вычисления и эффективно проверять их. В данном случае доказывающая сторона должна доказать, что выполнила вычисление, не раскрывая значения x, y и z.

Для практики решения задач по модульной арифметике настоятельно рекомендую набор задач Art of Problem Solving и практические задания по модульной арифметике от Joseph Zoller. 

Теория групп

Теория групп — раздел математики, изучающий алгебраические структуры, называемые группами. Группа — это множество элементов с операцией, которая удовлетворяет следующим условиям, известным как аксиомы группы:

• Замкнутость — результат любого арифметического вычисления будет другим элементом этого множества
• Ассоциативность — при выполнении одной операции над тремя или более элементами порядок группировки элементов не влияет на результат
• Нейтральный элемент — существует элемент, операция над которым и любым другим элементом не меняет значение другого элемента
• Обратный элемент — для каждого элемента существует элемент, операция с которым дает нейтральный элемент

Формально они определяются так:

• Замкнутость — если a и b входят в группу, то результат операции (обычно обозначаемой как $a \times b$, $ab$, $a \circ b$, или $ab$) также входит в группу. Формально это записывается как $\forall a, b \in G \mid a \circ b \in G$. Это можно прочитать так: «для всех значений элементов a и b множества G результат операции над a и b входит в G»
• Ассоциативность — если a, b и c входят в группу, то (ab)c = a(cb). Формально это записывается как $\forall a, b, c \in G \mid (a \circ b) \circ c = a \circ (b \circ c)$. Это можно прочитать так: «для всех значений элементов a, b и c множества G операция над a и b, а затем над результатом и c, равна операции над a и результатом операции над b и c»
• Нейтральный элемент — существует элемент e группы, такой что для каждого элемента a группы выполняется $e \circ a = a \circ e = a$. Формально это записывается как $\exists e \in G \mid \forall a \in G \mid e \circ a = a \circ e = a$. Это можно прочитать так: «существует элемент e множества G, для которого при каждом элементе a множества G операция над e и a равна операции над a и e, и обе равны a»
• Обратный элемент — для каждого элемента a группы существует элемент b этой группы, такой что $a \circ b = b \circ a = e$, где e — нейтральный элемент. Формально это записывается как $\forall a \in G \mid \exists b \in G \mid a \circ b = b \circ a = e$. Это можно прочитать так: «для всех значений элементов a множества G существует элемент b множества G, такой что операция над a и b равна операции над b и a, а обе равны нейтральному элементу»

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

• Замкнутость — сумма двух целых чисел также является целым числом
• Ассоциативность — $(5 + 4) + 3 = 5 + (4 + 3)$
• Нейтральный элемент — ноль считается нейтральным элементом, поскольку прибавление нуля к любому целому числу не меняет его значения. Например, $7 + 0 = 0 + 7 = 7$
• Обратный элемент — обратным по сложению для любого целого числа является противоположное число, поскольку их сумма равна нейтральному элементу. Например, $5 + (-5) = 0$. Это можно обобщить как $n + (-n) = 0$

Можно рассмотреть и более сложный пример: множество ненулевых рациональных чисел $\mathbb{Q} = \left\{ \frac{a}{b} \mid a, b \in \mathbb{Z}, b \ne 0 \right\}$ с операцией умножения. Оно также образует группу:

• Замкнутость — произведение двух ненулевых рациональных чисел будет ненулевым рациональным числом
• Ассоциативность — $ab \times cd \times ef = ab \times (cd \times ef)$
• Нейтральный элемент — число 1 считается нейтральным элементом, поскольку умножение любого ненулевого рационального числа на единицу не меняет его значения. Например, $\frac{1}{2} \times 1 = 1 \times \frac{1}{2} = \frac{1}{2}$
• Обратный элемент — обратным для любого ненулевого рационального числа является обратная дробь (то есть дробь с переставленными местами числителем и знаменателем), поскольку их произведение равно 1 — нейтральному элементу. Например, $\frac{3}{5} \times \frac{5}{3} = 1$

Подгруппы

Подгруппа — это группа внутри другой группы. Чтобы подгруппа H группы G была подмножеством G, должны выполняться следующие аксиомы группы:

• Замкнутость — если a и b входят в H, то результат операции над ними также должен входить в H
• Ассоциативность — эта аксиома наследуется от более крупной группы G 
• Нейтральный элемент — нейтральный элемент G также должен входить в H 
• Обратный элемент — для каждого элемента a в H должен существовать элемент b, также входящий в H, такой что ab и ba равны нейтральному элементу

Классический пример — множество четных целых чисел с операцией сложения как подгруппа множества целых чисел с операцией сложения:

• Замкнутость — сумма двух четных целых чисел является четным целым числом
• Ассоциативность — эта аксиома наследуется от целых чисел. Например, $2 + (4 + 6) = (2 + 4) + 6$
• Нейтральный элемент — ноль считается нейтральным элементом, поскольку прибавление нуля к любому четному целому числу не меняет его значения. Ноль также входит во множество целых чисел
• Обратный элемент — обратное по сложению к любому четному числу также является четным числом. Например, обратным для 4 является -4, поскольку $4 + (-4) = 0$, а 0 — нейтральный элемент

Применим это к более сложному примеру. Рассмотрим множество всех ненулевых рациональных чисел (то есть ℚ*) с операцией умножения. Можно доказать, что ℚ* является подгруппой множества ненулевых действительных чисел (то есть ℝ*) с операцией умножения:

• Замкнутость — если a и b — ненулевые рациональные числа, то их произведение ab также является ненулевым числом. Например, $\frac{1}{2} \times \frac{3}{4} = \frac{3}{8}$, что является ненулевым рациональным числом
• Ассоциативность — умножение рациональных чисел ассоциативно. Например, $(\frac{1}{2} \times \frac{3}{4}) \times \frac{5}{6} = \frac{1}{2} \times (\frac{3}{4} \times \frac{5}{6})$
• Нейтральный элемент — число 1 считается нейтральным элементом, поскольку умножение любого ненулевого рационального числа на 1 не меняет его. Например, $\frac{1}{2} \times 1 = 1 \times \frac{1}{2} = \frac{1}{2}$
• Обратный элемент — каждое ненулевое рациональное число $a = \frac{p}{q}$ имеет обратный по умножению элемент $a^{-1} = \frac{q}{p}$, который также является ненулевым рациональным числом, а их произведение равно нейтральному элементу. Например, пусть a = $\frac{2}{3}$. Обратным элементом будет $\frac{3}{2}$, поскольку $\frac{2}{3} \times \frac{3}{2} = 1$

Поскольку ℚ* удовлетворяет всем аксиомам группы, оно образует группу. Кроме того, так как ℚ* является подмножеством ℝ* и наследует его свойства, можно утверждать, что ℚ* — подгруппа ℝ*.

Зачем мне это знать?

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

Поля

Поле — это множество элементов, удовлетворяющее аксиомам поля для сложения и умножения и являющееся коммутативной алгеброй с делением (то есть деление всегда возможно, кроме деления на ноль). Аксиомы поля обычно записываются парами для сложения и умножения:

• Сложение
  • Ассоциативность: $(a + b) + c = a + (b + c)$
  • Коммутативность: $a + b = b + a$
  • Дистрибутивность: $a(b + c) = ab + ac$
  • Нейтральный элемент: $a + 0 = 0 + a = a$
  • Обратный элемент: $a + (-a) = 0$
• Умножение
  • Ассоциативность: $(ab)c = a(bc)$
  • Коммутативность: $ab = ba$
  • Дистрибутивность: $(a + b)c = ac + bc$
  • Нейтральный элемент: $(a + b)c = ac + bc$
  • Обратный элемент: $a \times a^{-1} = a^{-1} \times a = 1, \text{ if } a \ne 0$

Конечные поля и генераторы

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

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

Например, возьмем множество целых чисел по модулю p = 7 и поле $\mathbb{Z}_7 = \{0, 1, 2, 3, 4, 5, 6\}$. Чтобы найти генератор g для $\mathbb{Z}_7^*$ (то есть мультипликативной группы ненулевых элементов $\mathbb{Z}_7$), нужно убедиться, что g1, g2, g3 и так далее могут породить все ненулевые элементы поля.

Проверим, является ли 3 генератором:

Степени числа 3 порождают все ненулевые элементы $\mathbb{Z}_7$. Следовательно, 3 — генератор мультипликативной группы $\mathbb{Z}_7^*$.

Зачем мне это знать?

Криптография — наука, работающая с конечными множествами. Их понимание необходимо для изучения таких тем, как задача дискретного логарифмирования, шифрование, обмен ключами Диффи — Хеллмана и эллиптические кривые. Генераторы позволяют выполнять арифметические операции над зашифрованными многочленами без их расшифровки (то есть использовать гомоморфное шифрование). Иными словами, мы можем выполнять вычисления над зашифрованными данными, сохраняя конфиденциальность исходных значений. Понимание этого раздела критически важно для нулевого разглашения в доказательствах с нулевым разглашением.

Рекомендую посетить Bill’s Security Site, где представлен интерактивный пример создания конечных полей с заданными параметрами и изложена соответствующая теория на Python. 

Функции

Функция — это выражение, правило или закон, определяющий связь между двумя переменными: независимой и зависимой. Эти переменные часто описывают соответственно как причину и следствие. Такая связь обычно обозначается как y = f(x) и читается «f от x». Каждому значению x соответствует уникальное значение y, то есть f(x) не может иметь более одного значения для одного и того же x.

Функции могут быть взаимно однозначными или отображать несколько элементов в один, что часто описывается через мощность множеств. Это означает, что значение x может отображаться в уникальное значение y либо несколько значений x могут отображаться в одно значение y

Представим прямую, заданную уравнением $y = 3x + 4$. Это линейная функция: если подставить значение x, она вернет соответствующее значение y. Вместе эти два значения образуют точку на прямой. Например, уравнение можно переписать как $f(x) = 3x + 4$ и вычислить его при x = 1, получив $f(1) = 7$. У функций также может быть несколько переменных. Например, рассмотрим формулу площади треугольника: $A = \frac{bh}{2}$. Здесь A (то есть площадь) определяется как функция одновременно от b (то есть основания) и h (то есть высоты).

Область определения и область значений

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

Для функции $y = 2x + 2$:

• Область определения — все действительные числа, поскольку подойдет любое число от минус бесконечности до плюс бесконечности. Например:
  • Если x = 2.5, то $y = 2(2.5) + 2 = 7$ 
  • Если x = -9234525, то $y = 2(-9234525) + 2 = -18469048$
• Область значений — также все действительные числа, поскольку можно получить любое число от минус бесконечности до плюс бесконечности. Например:
  • Чтобы получить y = -50, решим уравнение -50 = 2x + 2 и получим x = -26. 
  • Чтобы получить y = 0, решим уравнение 0 = 2x + 2 и получим x = 0

Зачем мне это знать?

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

Чтобы лучше понять функции, рекомендую изучить Paul’s Online Notes и выполнить предложенные там практические задания.

Многочлены

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

Здесь $a_n x^n + a_{n-1} x^{n-1} + \ldots + a_1 x + a_0$ — коэффициенты, а x — переменная. Наибольшая степень переменной x с ненулевым коэффициентом называется степенью многочлена.

Многочлены делятся на одномерные, содержащие одну переменную (как в приведенной выше форме), и многомерные, содержащие несколько переменных (например, $P(x, y) = a_nx^ny^n + a_{n-1}x^{n-1}y^{n-1} + \cdots + a_1xy + a_0$. Sum-Check — пример протокола, использующего многомерные многочлены. Однако в большинстве случаев для доказательств с нулевым разглашением достаточно одной переменной.

Распространенные названия многочленов в зависимости от их степени:

• Степень 0 — ненулевая константа (например, $P(x) = 6$)
• Степень 1 — линейный (например, $P(x) = 2x - 7$)
• Степень 2 — квадратичный (например, $P(x) = 8x^2 - 3x + 1$)
• Степень 3 — кубический (например, $P(x) = 3x^3 - 4x$)

Если у нас есть два неравных многочлена степени не выше $d$, они могут пересекаться не более чем в $d$ точках (например, линейная и кубическая функции могут пересекаться до трех раз). Это свойство следует из способа поиска общих точек. Чтобы найти точки пересечения двух многочленов, мы приравниваем их. В следующем подразделе мы потренируемся находить корни многочлена — точки, в которых заданный многочлен пересекает ось x. Основная теорема алгебры гласит, что многочлен степени $d$ может иметь не более $d$ решений и, следовательно, не более $d$ общих точек.

Корни многочленов 

Корни, или нули, многочлена — это значения x, при которых многочлен равен нулю. Иными словами, если $P(x)$ — многочлен, то корень $r$ является решением уравнения $P(r) = 0$. Чтобы находить корни, нужно уметь раскладывать многочлены на множители. Разложение на множители — это определение того, какие величины нужно перемножить, чтобы получить заданную величину. Например, число 12 можно разложить несколькими способами:

Распространенный метод разложения — полностью разложить число на положительные простые множители. При разложении всегда лучше начинать с наибольшего общего делителя (НОД) всех членов. Например:

В примере выше оба члена (то есть 6x и 3) делятся на 3, поэтому их НОД равен 3. Таким образом, множителями являются 3 и $2x + 1$. Мы применяем распределительное свойство в обратном порядке: $3 \times 2x$ и $3 \times 1$. Поиск корней означает решение относительно x при $P(x) = 0$.

Раскладывать на множители многочлены из двух членов несложно. По графику это сделать еще проще: корни находятся в точках пересечения многочлена с осью x. Однако многочлены третьей и более высоких степеней могут быть сложнее. Для более подробного объяснения рекомендуем прочитать статью Как раскладывать многочлены на множители. 

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

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

Лемма Шварца — Циппеля — вероятностный инструмент для проверки того, всегда ли верно полиномиальное равенство. Многочлен вычисляют в случайных точках и проверяют, равен ли результат нулю.

Представьте сложное уравнение с переменными $x_1, x_2, \ldots, x_n$. Если это уравнение является многочленом, а не случайным набором членов, лемма Шварца — Циппеля помогает проверить, выполняется ли оно для всех возможных значений этих переменных.

Вот как это работает:

• Пусть $P(x_1, x_2, \ldots, x_n)$ — многочлен общей степени d (то есть наибольшей суммы показателей степеней в одном члене)
• Выберите конечное множество S из поля (например, некоторый набор чисел)
• Случайным образом выберите из множества S значения каждой переменной $x_1, x_2, \ldots, x_n$

Согласно лемме, вероятность того, что P окажется равным нулю в этих случайно выбранных точках, не превышает $\frac{d}{S}$. Это означает, что если многочлен не равен нулю, то вероятность того, что он случайно покажется нулевым, очень мала. Это особенно полезно для доказательств с нулевым разглашением, где необходимо эффективно проверять полиномиальные тождества.

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

Интерполяция Лагранжа — метод построения многочлена, проходящего через заданный набор точек. Многочлен Лагранжа — это многочлен наименьшей степени, проходящий через каждую заданную точку. Для n точек можно построить проходящий через них многочлен степени n-1. Например, через две точки на плоскости можно провести прямую. Через три точки на плоскости можно провести квадратичный многочлен (то есть $y = ax^2 + bx + c$). И так далее.

Почему это важно?

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

У многочленов также есть несколько свойств, полезных при создании доказательств:

• Если для заданного многочлена известно достаточно точек, можно восстановить весь многочлен
• Небольшое изменение входного значения многочлена может значительно изменить результат, благодаря чему ошибки легче обнаружить
• Многочлены позволяют обнаруживать и исправлять ошибки в вычислениях, подобно тому как коды стирания обеспечивают отказоустойчивость данных (это критически важно для работы Turbine)

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

• Закодируйте данные в многочлен $P(x)$ так, чтобы вычисление $P(x)$ в определенных точках давало исходные данные или результат заданного вычисления
• Чтобы многочлен соответствовал заданным критериям (например, все значения находились в определенном диапазоне), создайте многочлен ограничений $C(x)$. Например, $C(x) = (P(x) - 0)(P(x) - 1)$ гарантирует, что $P(x)$ равен 0 или 1
• Сведите задачу к доказательству того, что $P(x)$ удовлетворяет определенным условиям для вашего набора данных или вычисления
• Создайте известный многочлен $H(x)$, кратный $P(x)$ и кодирующий эти условия
• Доказывающая сторона фиксирует значения $P(x)$ и связанных с ним многочленов, создавая дерево Меркла из результатов вычислений, и отправляет корневой хеш проверяющей стороне
• Проверяющая сторона случайным образом выбирает несколько точек и просит доказывающую сторону предоставить значения $P(x)$ и $C(x)$ в этих точках
• Проверяющая сторона сверяет предоставленные значения с зафиксированным корневым хешем и ожидаемыми соотношениями между многочленами

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

Чтобы углубить понимание темы, рекомендуем решить следующие практические задачи:

• Практические задачи по многочленам
• Практические задачи на поиск нулей многочленов
• Разложение многочленов на множители: очень сложные задачи с решениями

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

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

Криптография в основе доказательств с нулевым разглашением

Рассмотрим симметричное и асимметричное шифрование.

Симметричное шифрование

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

К распространенным алгоритмам симметричного шифрования относятся:

Расширенный стандарт шифрования (AES)

Расширенный стандарт шифрования (AES) — вариант блочного шифра Rijndael, широко используемый по всему миру для защиты данных. Он поддерживает ключи длиной 128, 192 и 256 бит.

ChaCha20

ChaCha20 — современный эффективный потоковый шифр, разработанный Дэниелом Дж. Бернштейном. Это вариант потокового шифра Salsa20, использующий операции сложения, циклического сдвига и XOR (ARX). Он отображает 256-битный ключ, 64-битный nonce и 64-битный счетчик в 512-битный блок ключевого потока, благодаря чему пользователь может за постоянное время эффективно перейти к любой позиции ключевого потока.

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

Асимметричное шифрование

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

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

К распространенным алгоритмам асимметричного шифрования относятся:

• Ривест — Шамир — Адлеман (RSA) — одна из старейших и наиболее распространенных криптосистем с открытым ключом для безопасной передачи данных. Она разработана в 1970-х годах и опирается на практическую сложность разложения произведения двух больших простых чисел на множители
• Криптография на эллиптических кривых (ECC) — подход к криптографии с открытым ключом, основанный на алгебраической структуре эллиптических кривых над конечными полями. Он обеспечивает уровень безопасности, сопоставимый с RSA, но использует ключи меньшего размера, что ускоряет вычисления и снижает требования к хранилищу. Solana использует эллиптическую кривую Ed25519 для генерации пар ключей

Цифровые подписи

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

К распространенным алгоритмам цифровой подписи относятся:

• Алгоритм цифровой подписи (DSA) — подход, основанный на модульном возведении в степень (то есть возведении в степень по модулю) и задаче дискретного логарифмирования
• Алгоритм цифровой подписи на эллиптических кривых (ECDSA) — вариант DSA, использующий криптографию на эллиптических кривых для повышения уровня безопасности при меньшем размере ключей

Задача дискретного логарифмирования

Задача дискретного логарифмирования состоит в нахождении показателя степени k в уравнении $g^k \equiv h \pmod{p}$, где:

• g — известное основание (то есть генератор)
• h — известный результат (то есть элемент группы)
• p — простое число (то есть порядок группы)
• k — неизвестный показатель степени (то есть дискретный логарифм h по основанию g)

Иными словами, если известны значения g, h и p, задача дискретного логарифмирования заключается в нахождении k. Например, для уравнения $2^k \equiv 9 \pmod{23}$ нужно найти k.

Задачу дискретного логарифмирования считают трудноразрешимой эффективными методами, особенно для больших чисел. На этой сложности основана безопасность различных криптографических систем, включая Solana, шифрование ElGamal, алгоритмы цифровой подписи (то есть DSA и ECDSA) и обмен ключами Диффи — Хеллмана.

Обмен ключами Диффи — Хеллмана

Обмен ключами Диффи — Хеллмана — метод безопасного обмена криптографическими ключами через общедоступный канал.  Простейшая исходная реализация (то есть Диффи — Хеллман над конечным полем) выглядит так:

• Алиса и Боб публично согласуют два числа: большое простое число p (то есть модуль) и основание g (то есть генератор), являющееся первообразным корнем по модулю p 
• Алиса выбирает секретное целое число a, а затем отправляет Бобу $A \equiv g^a \pmod{p}$
• Боб выбирает секретное целое число b, а затем отправляет Алисе $B \equiv g^b \pmod{p}$
• Алиса вычисляет $s \equiv B^a \pmod{p}$ 
• Боб вычисляет $s = A^b \pmod{p}$ 

Теперь у Алисы и Боба есть одно и то же секретное значение. Оба вычисления дают одинаковый секрет s, потому что:

Затем общий секрет s можно использовать как ключ симметричного шифрования, позволяя Алисе и Бобу безопасно обмениваться данными. Безопасность обмена ключами Диффи — Хеллмана основана на сложности задачи дискретного логарифмирования. Не зная секретных значений a и b, перехватчик практически не сможет вычислить общий секрет. Это называется односторонней функцией: ее сравнительно легко вычислить, но крайне сложно обратить.

Обмен ключами Диффи — Хеллмана над конечным полем безопасен и широко распространен, однако для обеспечения безопасности ему требуются большие ключи. Например, если бы Алиса и Боб публично выбрали модуль 23, взломать систему было бы намного проще, поскольку существует лишь 23 возможных результата вычисления n по модулю 23. Поэтому этот метод может требовать значительных вычислительных ресурсов и быть менее эффективным. Криптография на эллиптических кривых (ECC) предлагает более эффективную альтернативу: тот же уровень безопасности при значительно меньших ключах и более быстрых вычислениях.

Эллиптические кривые

Эллиптическая кривая задается уравнением $y^2 = x^3 + ax + b$, где a и b — константы. Криптография на эллиптических кривых — это работа с точками заданной эллиптической кривой. У этих кривых есть ряд уникальных свойств, полезных в криптографии. Например:

• Сложение точек — если на заданной эллиптической кривой находятся две точки, P и Q, то их сумма R = P + Q также будет точкой этой кривой. В статье Прити Касиредди Простое руководство по криптографии для доказательств с нулевым разглашением хорошо объясняется, как складывать точки на эллиптической кривой
• Умножение на скаляр — если дана точка P на эллиптической кривой и целое число k, умножение на скаляр означает сложение точки P с самой собой k раз. В результате получается другая точка (то есть kP) на кривой. Этот метод используют для получения открытых ключей из закрытых
• Задача дискретного логарифмирования — решить задачу дискретного логарифмирования на эллиптических кривых намного сложнее, чем ее аналог для целых чисел. Если известны точки P и q = kP, при правильно выбранных параметрах кривой вычислить k практически невозможно. Поэтому эллиптические кривые обеспечивают тот же уровень безопасности, что и традиционные системы, при значительно меньшем размере ключей и большей эффективности

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

• Любые две точки можно сложить и получить третью точку
• Порядок сложения двух точек не имеет значения
• При сложении более двух точек порядок их сложения не имеет значения
• Существует нейтральный элемент (то есть прибавление нуля к любой точке кривой дает ту же точку)

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

Эллиптические кривые обеспечивают тот же уровень безопасности, что и другие традиционные криптосистемы, например RSA, но используют значительно меньшие ключи. Например, 256-битный ключ ECC обеспечивает безопасность, сопоставимую с 3072-битным ключом RSA. Это дает следующие преимущества:

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

Кривые Монтгомери

Кривые Монтгомери — это эллиптические кривые, заданные над конечным полем уравнением $By^2 = x^3 + Ax^2 + x$, где A и B — константы, B не равно нулю, а A не равно -2 или 2. Эти кривые примечательны тем, что умножение на эллиптической кривой можно эффективнее реализовать с помощью лестницы Монтгомери. 

Лестница Монтгомери принимает точку P на кривой Монтгомери и скаляр k, инициализирует две точки от бесконечности до P и обрабатывает каждый бит скаляра k от старшего к младшему. Основная идея заключается в том, чтобы поддерживать две точки и обновлять их постоянной последовательностью операций независимо от битов скаляра k.

Это важно по нескольким причинам:

• Она устойчива к атакам по сторонним каналам — атакам, основанным на дополнительной информации, которую можно получить из-за особенностей реализации или устройства протокола либо алгоритма. Это очень, очень глубокая техническая тема, которую стоит изучить. Такие атаки используют самые разные признаки: от изменений энергопотребления оборудования во время вычислений до утечки электромагнитного излучения
• Координата y не требуется, поскольку умножение на скаляр можно выполнять только с координатами x
• Она работает за постоянное время, то есть продолжительность вычисления не зависит от входного значения

Кривые Монтгомери широко применяются в криптографических протоколах. Например, алгоритм обмена ключами X25519 использует представление Монтгомери для кривой Curve25519. Этот алгоритм лежит в основе современной защищенной связи и используется в популярных протоколах, таких как TLS. 

Кривые Эдвардса

Кривые Эдвардса — вид эллиптических кривых, заданных уравнением $x^2 + y^2 = 1 + d x^2 y^2$, где d — ненулевая константа, не равная 1.  

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

• Эффективные операции с точками — сложение двух точек на кривой Эдвардса эффективнее, чем для других форм эллиптических кривых. Формулы сложения и удвоения точек проще и требуют меньше операций в поле, поэтому вычисляются быстрее
• Единая формула сложения — кривые Эдвардса используют единую формулу сложения, то есть одна и та же формула применяется для сложения и удвоения точек. Это снижает вероятность ошибок реализации и повышает безопасность
• Полнота — при определенных значениях d кривые Эдвардса являются полными. Это означает, что закон сложения без исключений охватывает все возможные входные значения.
• Устойчивость к атакам по сторонним каналам — как и кривые Монтгомери, кривые Эдвардса устойчивы к атакам по сторонним каналам благодаря единообразным и предсказуемым шаблонам операций.

Широко распространена кривая Эдвардса Edwards25519, заданная уравнением $x^2 + y^2 = 1 - \frac{121665}{121666} x^2 y^2$. Эта кривая известна эффективной арифметикой и 256-битным размером ключа. Ее схема подписи реализована в различных протоколах и системах безопасности, включая Solana, OpenSSH и Tor. Monero использует Edwards25519 как основу для генерации пар ключей.

Почему это важно?

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

В конечном счете эллиптические кривые можно представить как замену модульной арифметики. На эллиптических кривых получить конкретную точку значительно сложнее. Допустим, мы используем традиционную модульную арифметику с $g^a \bmod n$, где g — генератор, n — большое простое число, а a — секретный ключ. Как мы выяснили при рассмотрении задачи дискретного логарифмирования, для защиты секретного ключа потребуется очень большое простое число. Эллиптические кривые предлагают более эффективную альтернативу с меньшими ключами: тот же уровень безопасности при значительно более высокой производительности.

Случайность

Без случайности, фундаментального аспекта криптографии, все остальное в этой статье не имело бы значения. Как система может быть безопасной, если ее значения предсказуемы и смещены? Истинной случайности сложно достичь, но она необходима по нескольким причинам:

• Генерация ключей — криптографические ключи необходимо генерировать случайным образом, чтобы они были непредсказуемыми и безопасными
• Nonce и соли — nonce (то есть числа, используемые один раз) и соли (то есть случайные значения, добавляемые к данным перед хешированием) предотвращают соответственно атаки повторного воспроизведения и защищают от атак с предварительными вычислениями
• Безопасные протоколы — случайность обеспечивает справедливость и безопасность, устраняя предсказуемость и закономерности, которыми могут воспользоваться злоумышленники

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

Проверяемые случайные функции

Проверяемая случайная функция (VRF) — криптографический примитив, создающий случайный результат и доказательство того, что этот результат правильно получен из заданных входных данных. VRF должна быть непредсказуемой: для любого, кто не знает секретные входные данные, ее результат должен быть неотличим от случайного значения. Ее безопасность опирается на предположение RSA о сложности вычисления $y = h^d \bmod n$ без знания секретного показателя степени d, а также на безопасность хеш-функции H. 

Основные этапы работы VRF выглядят так:

• Генерация ключей — пользователь создает пару ключей RSA: (e, n) как открытый ключ и (d, n) как закрытый ключ. В открытом ключе e — показатель степени, а n — модуль. В закрытом ключе d — секретный показатель степени
• Вычисление — для входного значения x пользователь вычисляет результат VRF y и доказательство π. Сначала вычисляется хеш h = H(x), где H — криптографическая хеш-функция. Затем вычисляется $y = h^d \bmod n$ — подпись RSA для хеша. Наконец вычисляется доказательство π = (h, y)
• Проверка — имея открытый ключ (e, n), входное значение x, результат y и доказательство π = (h, y), любой пользователь может проверить правильность результата VRF. Для этого нужно убедиться, что хеш h равен $H(x)$, а также проверить уравнение RSA $y^e \equiv h \pmod{n}$‍

VRF часто используют в протоколах консенсуса, где случайность должна быть непредсказуемой, но проверяемой. L1, включая Algorand, Cardano, Internet Computer и Polkadot, используют VRF в механизмах консенсуса для случайного выбора производителей блоков. Chainlink предлагает Chainlink VRF как уровень абстракции между пользователем и блокчейном для генерации доказуемо справедливых и проверяемых значений. Pyth Entropy также предлагает надежный и безопасный источник случайности.

Церемонии и доверенные настройки

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

• Церемонии генерации ключей — предусматривают создание криптографических ключей таким образом, чтобы ни одна сторона не контролировала процесс генерации
• Церемонии генерации параметров — предусматривают создание криптографических параметров, которые будут использовать несколько сторон
• Церемонии многосторонних вычислений (MPC) — предусматривают совместное выполнение криптографических вычислений несколькими сторонами, чтобы ни одна из них не могла скомпрометировать процесс

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

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

Zcash широко известен использованием доверенной церемонии для первоначального запуска функций конфиденциальности сети. В Ethereum также прошла церемония KZG — скоординированный публичный ритуал для создания криптографической основы масштабирования (например, EIP-4844 / прото-данкшардинга). 

Обратите внимание, что некоторым системам доказательств с нулевым разглашением, например zk-STARK, доверенная настройка не требуется. Мы подробнее рассмотрим это во второй статье.

Заключение

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

Мы продолжим этот анализ во второй, заключительной статье нашей серии из двух частей о доказательствах с нулевым разглашением. Она называется Доказательства с нулевым разглашением: их применение в Solana. 

Если вы дочитали до этого места — спасибо, анон! Обязательно укажите свой адрес электронной почты ниже, чтобы не пропустить новости об обновлениях Solana. Готовы погрузиться глубже? Читайте свежие статьи в блоге Helius и продолжайте знакомство с Solana уже сегодня.

Дополнительные материалы

• Существует ли истинная случайность?
• Эллиптические кривые — Computerphile
• Введение в класс NP-полных задач
• Проблемы обмена ключами — Computerphile
• Курс Khan Academy по криптографии
• Криптография с открытым ключом — Computerphile
• Сложность знания в интерактивных системах доказательств