Loading...
Серія: Zcash from First Principles . Стаття 1 . Скінченні поля Аудиторія: новачки. Ми припускаємо лише звичайну шкільну арифметику (додавання, множення, ділення). Жодної попередньої підготовки з криптографії чи вищої математики. Що ви винесете з цього: інтуїтивне й коректне розуміння скінченних полів, чому криптографи їх використовують і де саме вони з’являються всередині Zcash.
У Статті 0 ми познайомилися з п’ятьма персонажами: note, commitment, деревом note commitment, 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(читається «еф під p»).
Отже, F_7 = {0, 1, 2, 3, 4, 5, 6} з арифметикою в стилі годинника mod 7 — це справжнє скінченне поле. Подивімося, як воно дихає.
Кожна клітинка — це (row x column) 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не має оберненого mod 6. Гірше того,2 x 3 = 6 = 0 (mod 6): два ненульові числа перемножилися і дали нуль.
Це друге речення — катастрофа для арифметики. Коли дві ненульові величини при множенні дають нуль (це називається zero divisor), ділення зламане, а система зі зламаним діленням не є полем. Це відбувається саме тому, що 6 розкладається як 2 x 3.
Просте число, за означенням, не має таких дільників. Тому mod простого числа не може з’явитися zero divisors, кожен ненульовий елемент отримує коректне обернене, і структура є справжнім полем.
Універсальна фраза для ваших статей: простий модуль на вході — коректне ділення на виході.
Для 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 mod простого 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, для яких арифметика виконується mod простого 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 |