Loading...
Серия: Zcash from First Principles . Статья 1 . Конечные поля Аудитория: новички. Мы предполагаем только обычную школьную арифметику (сложение, умножение, деление). Никакой предварительной подготовки по криптографии или высшей математике. Что вы получите в итоге: интуитивное и корректное понимание конечных полей, того, почему криптографы их используют и где они появляются внутри Zcash.
В Статье 0 мы познакомились с пятью персонажами: note, commitment, деревом commitments для notes, nullifier и доказательством с нулевым разглашением. Мы оставили один незавершённый вопрос: откуда вообще берутся все эти ключи и секретные рецепты? Они берутся из чисел. Но не из обычных чисел, с которыми вы выросли. Они приходят из особой, замкнутой числовой системы, называемой конечным полем, и почти каждая часть криптографии в Zcash построена поверх неё.
Эта статья подводит к этой идее постепенно. Как и обещано, сначала интуиция. Никаких формул, пока они действительно не начнут работать на нас.
У обычных чисел есть проблема для криптографии: их бесконечно много, и они выдают информацию.
Подумайте, что происходит, когда число становится больше. Если я скажу вам, что секретное вычисление дало 8,142,067, вы уже довольно многое знаете: это семизначное число, оно нечётное, оно «довольно большое». Размер — это подсказка. А подсказки — именно то, что система приватности не может себе позволить раскрывать.
Криптографии нужна такая числовая система, где:
У этого списка желаний есть название. Это конечное поле. Давайте сначала построим интуицию для такого поля, прежде чем писать хоть один символ.
Вы уже каждый день пользуетесь конечным полем. Это часы на стене.
На 12-часовых часах числа оборачиваются по кругу. Начните с 10 часов, прибавьте 5 часов, и вы попадёте не в «15 часов», а в 3 часа. У часов всего двенадцать позиций, и счёт после верхней точки просто возвращается к началу.
Здесь только что произошли три вещи, которые и составляют смысл всей этой статьи:
У этой арифметики с оборачиванием есть формальное название: модульная арифметика. Часы работают «по модулю 12», записывается как mod 12. Математики предпочитают считать позиции, начиная с 0, поэтому «часы mod 12» на самом деле имеют позиции 0, 1, 2, ..., 11. Часы mod 7 имели бы позиции от 0 до 6.
Единственное правило: чтобы вычислить что угодно «mod p», выполните обычную арифметику, затем разделите на
pи оставьте только остаток. Пример mod 7:5 + 4 = 9, а9даёт остаток2после деления на7, так что5 + 4 = 2 (mod 7).
Часы позволяют нам складывать. Поле — это следующий уровень: числовая система, где корректно ведут себя все четыре операции, включая самую коварную — деление.
Неформально, поле — это любой набор «чисел», где можно складывать, вычитать, умножать и делить (на всё, кроме нуля), и при этом сохраняются все привычные правила: порядок не важен для сложения и умножения, скобки можно перегруппировывать, существуют 0 и 1, и у каждого числа есть противоположное и (кроме 0) обратное.
Рациональные числа — это поле. Вещественные числа — это поле. Но нам нужно конечное поле.
Вот главный результат, и он прекрасен:
Возьмите целые числа
0, 1, ..., p-1и выполняйте всю арифметику modp. Еслиp— простое число, результатом будет конечное поле. Мы записываем его какF_p(читается «F с индексом p»).
Итак, F_7 = {0, 1, 2, 3, 4, 5, 6} с арифметикой по модулю 7 в стиле часов — это настоящее конечное поле. Давайте посмотрим, как оно «дышит».
Каждая ячейка — это (строка x столбец) mod 7:
| x | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 2 | 0 | 2 | 4 | 6 | 1 | 3 | 5 |
| 3 | 0 | 3 | 6 | 2 | 5 | 1 | 4 |
| 4 | 0 | 4 | 1 | 5 | 2 | 6 | 3 |
| 5 | 0 | 5 | 3 | 1 | 6 |
Посмотрите на строки для 1–6: каждая из них содержит каждое ненулевое значение 1..6 ровно один раз. Этот паттерн «без повторов, ничего не пропущено» — видимый отпечаток поля.
Деление — это просто «умножение на обратный элемент». В F_7 обратный элемент (или inverse) числа a — это значение a^(-1), для которого a x a^(-1) = 1. Считывая их прямо из таблицы:
a | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
a⁻¹ | 1 | 4 | 5 | 2 | 3 | 6 |
Проверим один пример: 2 x 4 = 8 = 1 (mod 7). Значит, «разделить на 2» в F_7 означает «умножить на 4». У каждого ненулевого элемента есть пара. Именно это делает F_7 полем.
Это самая важная идея в статье, поэтому давайте сделаем её конкретной, а не абстрактной.
Посмотрите, что ломается, если мы наивно попытаемся построить «поле» mod 6 (а 6 не является простым):
Существует ли какое-нибудь
x, для которого2 x x = 1 (mod 6)? Проверим все варианты:2x0=0, 2x1=2, 2x2=4, 2x3=0, 2x4=2, 2x5=4. Ответ1никогда не появляется. Значит, у2нет обратного элемента по модулю 6. Хуже того,2 x 3 = 6 = 0 (mod 6): два ненулевых числа перемножились и дали ноль.
Это второе утверждение — катастрофа для арифметики. Когда два ненулевых объекта перемножаются и дают ноль (это называется делителем нуля), деление ломается, а система с неисправным делением не является полем. Это происходит именно потому, что 6 раскладывается как 2 x 3.
У простого числа, по определению, таких множителей нет. Поэтому по модулю простого числа делители нуля не появляются, каждый ненулевой элемент получает корректный обратный, и структура становится настоящим полем.
Повторно используемая фраза для ваших статей: на входе простой модуль, на выходе корректное деление.
Для F_7 мы считали обратные элементы по таблице, но простое число Zcash имеет сотни цифр; никакая таблица тут невозможна. Есть классическое сокращение, и это единственная формула в статье.
Малая теорема Ферма говорит, что для простого p и любого ненулевого a:
a^(p-1) = 1 (mod p)
Переставим это (отделим один множитель a) — и сразу получим обратный элемент:
a^(-1) = a^(p-2) (mod p)
Проверка в F_7 (p = 7, значит p - 2 = 5): обратный элемент к 2 должен быть 2^5 = 32 = 4 (mod 7). И действительно, наша таблица показала, что 2^(-1) = 4. Компьютеры умеют возводить в большие степени очень быстро, поэтому это превращает задачу «найти обратный элемент» в быстрое и точное вычисление даже для гигантских простых чисел.
Запоминать это не обязательно. Важно понимать, что деление в конечном поле — это быстрая и точная операция, и именно поэтому криптографы охотно строят свои системы на таких полях.
Собрав всю интуицию вместе, вот полное объяснение на одной странице.
Свойство F_p | Почему это нужно системе приватности |
|---|---|
| Конечность | Компьютер хранит любой элемент точно; никакого округления, переполнения или погрешностей чисел с плавающей точкой |
| Оборачивание по кругу | Стирает «размер», поэтому значение ничего не выдаёт о том, как оно было получено |
| Работают все четыре операции | Криптографическим рецептам (ключам, commitments, доказательствам) нужна настоящая алгебра, а не просто счёт |
| Выбираемый размер | Можно взять простое число длиной 255 или 381 бит, и тогда в поле будет больше элементов, чем атомов в наблюдаемой Вселенной; угадывание безнадёжно |
| Точность и детерминированность | Две честные стороны, вычисляющие одно и то же, всегда получают идентичные результаты, а доказательства от этого зависят |
Конечное поле — это, в одной фразе, идеально замкнутая, идеально точная, идеально огромная игровая площадка для арифметики. Всё остальное в Zcash строится игрой внутри неё.
Вам не нужно просто верить на слово, что «Zcash использует конечные поля». Вот конкретная карта (более глубокие механизмы будут в следующих статьях; здесь мы лишь показываем, что отпечатки реальны).
Так что ответ на открытый вопрос из Статьи 0, «откуда берутся секретные рецепты?», начинается здесь: всё начинается с арифметики в конечном поле. В следующей статье мы возьмём это поле и построим уже настоящие объекты — точки на эллиптической кривой, — которые становятся ключами и commitments.
Чтобы текст оставался дружелюбным к новичкам, мы упростили несколько истинных вещей. Конечные поля бывают не только вида F_p; можно также строить поля с p^n элементами (так называемые поля расширения), и они важны для «парных отображений» (pairings), на которые опирается система доказательств Sapling. Мы также пропустили полный список аксиом поля и не стали подробно разбирать, как выбираются и проверяются простые числа такого размера. Всё это не меняет интуицию, которой вы теперь владеете; оно лишь делает её точнее. Мы вернём эту точность, с соответствующими пометками, когда она понадобится в одной из следующих статей.
0..p-1 по модулю простого числа p, получается настоящее поле F_p, где можно также делить, потому что у каждого ненулевого элемента есть обратный.2 x 3 = 0 mod 6) и ломает деление.a^(-1) = a^(p-2)).| Термин | Значение простыми словами |
|---|---|
| Modular arithmetic | Арифметика, которая оборачивается по кругу после достижения фиксированного значения, как часы |
| mod p | «Разделить на p и оставить остаток» |
| Field | Числовая система, где работают сложение, вычитание, умножение и деление |
Finite field F_p | Числа 0..p-1, где арифметика выполняется по модулю простого p |
| Inverse (reciprocal) | Элемент a^(-1), для которого a x a^(-1) = 1; «деление на a» означает умножение на него |
| Zero divisor | Два ненулевых значения, произведение которых равно нулю; именно это ломает составные модули |
| Prime | Целое число больше 1, которое не имеет делителей, кроме 1 и самого себя |
Почему бы просто не использовать обычные целые числа или десятичные дроби? Десятичные дроби округляются и накапливают ошибку; целые числа растут без ограничений и выдают размер. Конечные поля точны, ограничены и нечувствительны к размеру, а именно это и требуется криптографии.
Теряется ли информация при «оборачивании по кругу»? Да, намеренно. Стирание размера промежуточных значений — это для приватности не ошибка, а полезное свойство.
Всегда ли большее простое число означает большую безопасность? В грубом приближении большее поле означает больше возможных значений и более трудное угадывание, но безопасность зависит от всей конструкции, а не только от размера поля. В следующих статьях мы сделаем это точнее.
Почему в Zcash используются именно эти простые числа (255-битные, 381-битные)? Они выбраны так, чтобы кривые, построенные на их основе, имели нужную структуру и эффективность для системы доказательств. Эта «нужная структура» — тема следующих двух статей.
В F_7 чему равно 5 - 6? (Помните: оставайтесь внутри {0,...,6}, оборачиваясь по кругу.) (Ответ ниже.)
5 - 6 = -1, а -1, обёрнутое в F_7, — это 6 (потому что 6 + 1 = 7 = 0). Значит, 5 - 6 = 6 (mod 7). Вычитание никогда не покидает поле; оно просто оборачивается в другую сторону.
Статья 2 . Эллиптические кривые: мы возьмём конечное поле, которое только что построили, и используем его, чтобы нарисовать странный вид кривой, точки на которой можно «складывать» друг с другом. Эти точки становятся ключами и commitments в Zcash и скрывают одностороннюю ловушку, которая делает возможной всю систему приватности. Сначала интуиция, как всегда.
Часть серии Zcash from First Principles для ZecHub. Лицензия CC BY-SA 4.0.
| 4 |
| 2 |
| 6 | 0 | 6 | 5 | 4 | 3 | 2 | 1 |