Модульная арифметика для доказательств с нулевым разглашением
Доказательства с нулевым разглашением (ZKP) сильно зависят от математики. Но эти числа могут действительно выйти из-под контроля, когда мы начинаем генерировать ZKP для больших программ — даже компьютеры могут начать испытывать трудности.
Вот где вступает в игру модульная арифметика. Модульная арифметика, также известная как часовая арифметика или арифметика по модулю, отлично подходит для ZKP благодаря своим математическим свойствам и вычислительной эффективности. Используя модульную арифметику, мы открываем мощные возможности, такие как гомоморфное шифрование — которое является ключевым для функций “скрытия” в основе ZKP.
Что ж, давайте начнем изучать эту увлекательную тему с основ модульной арифметики.
Что такое модульная арифметика
Когда мы делим два целых числа, уравнение выглядит примерно так:
A/B = Q * R
где R — остаток, а Q — частное.
Чаще всего нас интересует частное (Q). Однако, если вы ищете остаток (R), модульная арифметика приходит на помощь.
Мы используем оператор “модуль” или “mod” в качестве сокращения, когда хотим получить остаток от деления двух чисел.
Вот как это выглядит на практике:
A mod B = R
Допустим, A равно 10, а B равно 3. В этом случае 10 mod 3 равно 1.
Прежде чем двигаться дальше, стоит понять одно важное свойство модуля. Для любого модуля остаток может быть всеми целыми числами в диапазоне от 0 до n — 1 (где n — это модуль).
Например, для модуля 5 возможные остатки — это 0, 1, 2, 3 и 4. Предположим, у нас есть набор целых чисел [0, 1, 4, 6, 9, 10, 12, 18], и мы применяем к ним mod 5. Благодаря этому свойству мы знаем, что результатом будут значения [0, 1, 4, 1, 4, 0, 2, 3] — каждое значение попадает в диапазон от 0 до 4.”
Конгруэнция
Мы скоро узнаем, как выполнять модульные вычисления, но сначала нам нужно изучить важное обозначение: оператор ≡.
Оператор ≡ называется оператором “конгруэнции”. Это НЕ то же самое, что оператор равенства =, который нам всем знаком. Вместо этого ≡ имеет 3 переменные и означает, что если у нас есть два положительных целых числа, a и b, то a и b “конгруэнтны по модулю n”, если остаток при делении на n одинаков.
Пример 1:
48 ≡ 13 (mod 5)
48 деленное на 5 дает остаток 3. Точно так же 13 деленное на 5 дает остаток 3. Следовательно, 48 и 13 конгруэнтны по модулю 5.
Пример 2:
93 ≡ 6 (mod 3)
93 деленное на 3 дает остаток 0. Точно так же 6 деленное на 3 дает остаток 0. Следовательно, 93 и 6 конгруэнтны по модулю 3.
Вот и все! Теперь мы готовы к математике. Давайте посмотрим, как выполнять сложение, вычитание, умножение и деление с использованием модуля.
Сложение
Сложение в модульной арифметике — это просто. Мы складываем два числа как обычно, а затем берем остаток при делении на модуль.
Например, 2 + 4 = 6 в обычной арифметике. Но если мы хотим 2 + 4 (mod 5), то получим 1 в качестве остатка. Таким образом, мы говорим:
2 + 4 ≡ 1 (mod 5)
Обратите внимание, как мы использовали оператор конгруэнции.
Вычитание
Вычитание в модульной арифметике следует той же логике. Мы просто вычитаем два числа как обычно, а затем берем модуль результата. Например, 4–2 (mod 5) это 2 (mod 5), что равно 2. Таким образом, мы можем записать это как:
4 − 2 ≡ 2 (mod 5)
Однако, если мы вычитаем два числа и получаем отрицательное число, то мы добавляем модуль к результату, пока не получим неотрицательный ответ, который меньше модуля.
Например, что такое:
2 − 4 (mod 5) ?
2–4 равно -2, но у нас не может быть отрицательных чисел. Поэтому мы добавляем к нему 5 и получаем 3. 3 — это неотрицательное число и наш окончательный ответ.
Таким образом, мы говорим:
2 − 4 ≡ 3 (mod 5)
Умножение
Теперь поговорим об умножении в модульной арифметике. Просто умножьте два числа как обычно, а затем возьмите остаток при делении на модуль. Например, 2 × 4 = 8, но в модульной арифметике с модулем 5 остаток от 8 при делении на 5 равен 3, поэтому мы говорим:
2 × 4 ≡ 3 (mod 5)
Деление
Загвоздка — в модульной арифметике нет операции деления. Но у нас есть модульные обратные числа.
[знак “^” означает возведение в степень]
Модульное обратное для A (mod C) — это A^-1
Таким образом, A × A^-1 ≡ 1 (mod C)
Как мы знаем, умножение числа на обратное другому эквивалентно делению на это другое число.
Например:
10/5 = 10 * 1/5
Таким образом, мы можем по сути “делить” некоторое число “X” на другое число “A” в модульной математике, сначала найдя мультипликативное обратное для A, а затем умножив X на это мультипликативное обратное:
X/A * (mod C) = X * A^-1(mod C)
Важно отметить, что не все числа будут иметь модульное обратное. Только числа, взаимно простые с C (числа, не имеющие общих простых делителей с C), имеют модульное обратное (mod C).
Три причины использовать модульную арифметику в ZKP
Итак, теперь, когда вы понимаете основы модульной математики, вы, возможно, задаетесь вопросом, как она полезна для ZKP. Давайте посмотрим!
Модульная арифметика хорошо работает с большими числами
Когда мы выполняем арифметические операции с использованием модульной арифметики, результат операции всегда находится между 0 и n-1 (где n — это модуль). Это дает нам красивый, чистый конечный набор чисел для работы. Это здорово, потому что, когда нам нужно работать с большими числами, нам не нужно беспокоиться о проблемах переполнения.
Это также предотвращает ошибки точности при делении. Подумайте о стандартном методе деления — иногда результаты имеют десятичные точки. Это может вызвать проблемы. Не удивительно, что с модульной арифметикой деление также дает элемент в конечном поле, так что нет ошибок точности, о которых стоит беспокоиться.
Гомоморфные свойства
Модульная арифметика имеет гомоморфные свойства, что означает, что определенные операции можно выполнять над зашифрованными значениями без их расшифровки. Если вы уже проводите связи с последним постом, отлично! Эти гомоморфные свойства позволяют доказывающему в ZKP выполнять операции и генерировать доказательства без раскрытия основных значений — важная часть ZKP.
Кстати, можете поискать в моем блоге статью о полностью гомоморфном шифровании ;) Она была написана не так давно.
Вычислительная эффективность
Вычисления в модульной арифметике обычно быстрее, чем те, которые включают в себя реальные или рациональные числа, так как они требуют только целых чисел в фиксированном диапазоне. Это делает модульную арифметику хорошо подходящей для сред с ограниченными ресурсами, таких как блокчейн-системы или различные устройства.
Заключение
Вот и все! Надеюсь, это было быстрым, понятным и полезным руководством по использованию модульной арифметики в системах доказательства с нулевым разглашением.
Оставайтесь любознательными, продолжайте учиться и углубляйтесь в экосистему Aleo — путешествие только начинается. Присоединяйтесь к сообществу здесь:
