Еліптичні криві: де народжуються ключі та commitments Zcash

Оригінальне дослідження від Annkkitaaa

Одностороння вулиця, побудована з точок на кривій

Серія: Zcash from First Principles . Стаття 2 . Еліптичні криві Для кого: новачки. Ми припускаємо лише Статтю 1 (скінченні поля): арифметику, яка «замикається» по модулю простого числа. Жодної іншої підготовки не потрібно. Що ви винесете з цієї статті: інтуїтивне й коректне уявлення про еліптичні криві, «пастку», яка робить їх корисними, і те, як саме Zcash перетворює їх на ключі та commitments.

Стаття 1 дала нам ідеальний майданчик для арифметики: скінченне поле. Але саме по собі поле — це лише числа. Щоб побудувати ключі та «запечатані конверти» зі Статті 0, Zcash потрібен об’єкт з особливим, односпрямованим типом складності: його легко обчислювати вперед, але практично неможливо обернути назад. Цей об’єкт — еліптична крива. У цій статті ми побудуємо її з нуля, починаючи з інтуїції, а вже потім переходячи до алгебри.

1. Чому вам має бути не все одно?

Кожній системі приватності потрібна одностороння вулиця: операція, якою тривіально пройти вперед і фактично неможливо пройти назад.

Ось чому. Ваш секретний ключ — це число, яке ви тримаєте в таємниці. Ваш публічний ключ (і ваша адреса) виводиться з нього й показується світу. Уся безпека системи тримається на одному факті: маючи публічний ключ, ніхто не може повернутися назад до вашого секретного ключа. Якби це було можливо, вони могли б витрачати ваші гроші.

Отже, нам потрібна математична операція, де:

• рух вперед (secret -> public) є швидким і легким, але
• рух назад (public -> secret) настільки складний, що всі комп’ютери на Землі, працюючи весь час існування всесвіту, не впоралися б.

Звичайного множення у скінченному полі недостатньо; ділення миттєво його скасовує (у цьому й був сенс Статті 1). Нам потрібно щось без простої кнопки «скасувати». Еліптичні криві дають саме це, а як бонус їхні точки поєднуються у спосіб, ідеальний для побудови commitments. Подивімося, як саме.

2. Інтуїція: крива, точки якої можна «додавати»

Забудьмо на мить про криптографію. Еліптична крива — це просто множина точок (x, y), що задовольняють рівняння виду:

y^2 = x^3 + ax + b

Над звичайними числами це виглядає як гладка, плавна крива, часто із заокругленою петлею та двома «хвостами»:

По-справжньому дивовижна річ: ви можете «додати» дві точки на цій кривій і отримати третю точку на тій самій кривій. Це не звичайне додавання координат. Це геометричне правило, і його легше побачити, ніж описати словами.

Правило хорди (додавання двох різних точок)

Щоб додати P + Q:

1. Проведіть пряму через P і Q.
2. Ця пряма перетне криву ще рівно в одній точці. Назвімо її R*.
3. Відобразьте R* відносно горизонтальної осі. Це відображення і є відповіддю: P + Q.

Правило дотичної (додавання точки до самої себе)

Щоб обчислити P + P (пишеться як 2P), другої точки для побудови прямої немає, тож замість неї ви берете дотичну до кривої в точці P, а потім застосовуєте той самий рецепт: «третій перетин, потім відображення».

Ось і вся операція. Два геометричні правила. Завдяки їм точки еліптичної кривої утворюють те, що математики називають групою: множину з добре поводящим себе «додаванням». У неї навіть є свій «нуль».

Точка на нескінченності (нуль кривої)

Кожній числовій системі потрібен 0 — річ, яка нічого не змінює при додаванні. На еліптичній кривій цю роль виконує спеціальна додаткова точка, що називається точкою на нескінченності, позначається O. Її можна уявити як точку «нескінченно далеко вгорі», місце, де зустрічаються вертикальні прямі. Додавання O до будь-якої точки залишає її незмінною, так само як додавання 0.

3. Від картинок до скінченного поля

Гладка крива вище — це інтуїція. Але Zcash не використовує дійсні числа (вони округлюються й «витікають» за розміром, як ми бачили у Статті 1). Він використовує еліптичну криву над скінченним полем: те саме рівняння y^2 = x^3 + ax + b, але вся арифметика виконується по модулю простого числа.

Коли ви так робите, гарна крива розсипається на розсип незв’язаних точок, по одній точці для кожної пари (x, y), що задовольняє рівняння за модулем p. Вона взагалі перестає бути схожою на криву. Але ось критично важлива річ:

Алгебра правила хорди й дотичної все одно працює бездоганно. Ті самі формули, які геометрично знаходили P + Q, тепер обчислюють його через арифметику скінченного поля. Точки й далі утворюють групу з тим самим 0 (точкою на нескінченності).

Зробімо це реальним на маленькому, повністю перевіреному прикладі.

Повна крива, обчислена точно

Візьмімо y^2 = x^3 + 2x + 2 над скінченним полем F_17. Обчислення всіх допустимих точок дає рівно 18 точок, плюс точка на нескінченності = 19 загалом. Ось деякі з них:

(0,6) (0,11) (3,1) (3,16) (5,1) (5,16) (6,3) (6,14) (7,6) (7,11) ...

Тепер виберімо точку G = (5, 1) і продовжимо додавати її до самої себе. Подивіться, що відбувається (кожен рядок нижче був обчислений, а не вгаданий):

Тут варто помітити дві речі:

• Вона проходить через усі 18 скінченних точок, а потім потрапляє в O на кроці 19, після чого цикл повторювався б вічно. Початкова точка G «генерує» всю групу, тому ми називаємо її генератором.
• Це перевірена група: наприклад, 1G + 2G = (5,1) + (6,3) = (10,6), що рівно дорівнює 3G. Додавання внутрішньо узгоджене, як і вимагає група.

4. Пастка: скалярне множення

Ця таблиця 1G, 2G, 3G, ... — серце всього. Багаторазове додавання точки до самої себе називається скалярним множенням: точка kG означає «G, додану до себе k разів».

А тепер магія. Розгляньмо два напрями:

Ця асиметрія і є тією односторонньою вулицею, яка була нам потрібна в розділі 1. Зворотна задача («яке k породило цю точку?») називається задачею дискретного логарифмування на еліптичній кривій (ECDLP), і на кривих, які використовує Zcash, жоден відомий метод не розв’яже її раніше теплової смерті всесвіту.

На нашій іграшковій кривій F_17 ви могли б просто зчитати k з таблиці, бо в ній лише 19 точок. Справжні криві мають близько 2^(255) точок. У таблиці було б більше рядків, ніж атомів у всесвіті, тож «просто зчитати» — не варіант. Саме малий розмір робить іграшкову криву придатною для навчання і водночас пояснює, чому вона не є безпечною.

5. Як народжуються ключі (головний результат)

Тепер у нас є все необхідне, щоб пояснити справжній криптографічний ключ, і це напрочуд просто:

Виберіть секретне число k. Опублікуйте точку kG. І все. k — це ваш приватний ключ. kG — ваш публічний ключ. Одностороння вулиця (ECDLP) гарантує, що ніхто не зможе повернути kG назад до k.

Ця єдина ідея — публічний ключ є секретним скаляром, помноженим на фіксований генератор — є зерном, з якого виростають spending keys, viewing keys та адреси Zcash. Повне дерево ключів накладає зверху більше структури, але кожна його гілка виростає саме з цього кореня.

Бонус: чому точки кривої ідеально підходять для commitments

Згадайте «запечатаний конверт» (commitment) зі Статті 0, який мав приховувати свій вміст, але водночас бути неможливим до підробки. Еліптичні криві дають нам чистий спосіб його побудувати. Візьмімо дві фіксовані, публічні точки-генератори G і H, секретне значення v та випадкове число маскування r, і утворімо:

Commitment  =  v.G  +  r.H

Це Pedersen commitment, і він має обидві потрібні нам властивості:

• Приховування: випадкове r розмазує результат по всій кривій, тож точка нічого не розкриває про v.
• Зв’язуваність: ECDLP робить практично неможливим знайти іншу пару (v, r), що дає ту саму точку, тож ви не можете «передумати» щодо того, що саме закомітили.

Ще одна бонусна властивість згодом виявляється безцінною: ці commitments складаються. Commitment до v_1 плюс commitment до v_2 є коректним commitment до v_1 + v_2. Саме така «гомоморфна» поведінка пізніше дозволяє Zcash доводити, що гроші, які входять у транзакцію, дорівнюють грошам, які з неї виходять, не розкриваючи жодної суми. До цього ми ще повернемося приблизно в Статті 6.

6. Де це живе в Zcash

Ці відбитки цілком конкретні й піддаються перевірці.

Причини, чому одну криву «вбудовують» у поле іншої, і чому цикл із двох кривих є корисним, реальні та важливі, але вони належать до статей про системи доказів. Поки що головний висновок такий: кожен ключ Zcash — це скаляр, помножений на генератор, а кожен commitment — це сума точок кривої, що живуть на одній із цих іменованих кривих.

7. Чесне застереження

Кілька спрощень зробили цей текст читабельним. Ми використовували коротку форму Вейєрштраса (y^2 = x^3 + ax + b); криві Zcash часто записують в інших еквівалентних формах (Jubjub — це twisted Edwards крива), обраних заради ефективності та безпеки, але ідея групи повністю та сама. Ми не визначали точні формули додавання точок (це алгебраїчна версія «третій перетин, потім відображення») і залишили осторонь тонкощі на кшталт порядку кривої, кофакторів і «pairings», які стають важливими у статтях про системи доказів. Ніщо з цього не змінює інтуїцію; воно лише робить її точнішою.

8. Підсумок

• Системі приватності потрібна одностороння вулиця: легко вперед, нереально назад. Еліптичні криві її забезпечують.
• Еліптична крива — це множина точок, що задовольняють y^2 = x^3 + ax + b, і її точки можна додавати за геометричним правилом хорди й дотичної, де спеціальна точка на нескінченності відіграє роль нуля.
• Над скінченним полем крива перетворюється на розсип точок, але те саме додавання продовжує працювати, і точки утворюють групу. (Перевірений приклад: y^2 = x^3 + 2x + 2 над F_17 має 19 точок, а G = (5,1) генерує їх усі.)
• Скалярне множення kG легко обчислити, але нереально обернути назад: це ECDLP. У цьому й полягає пастка.
• Ключі: приватний ключ k, публічний ключ kG. Commitments: форма Pedersen v.G + r.H, яка приховує, зв’язує та зручно складається.
• У Zcash Sapling використовує BLS12-381 + Jubjub, а Orchard — криві Pallas/Vesta (Pasta); кожен ключ і commitment живе на них.

Глосарій

FAQ

Чому криві, а не просто великі числа по модулю простого? Обидва підходи можуть дати односторонню вулицю, але еліптичні криві забезпечують ту саму безпеку з набагато меншими ключами та швидшими операціями, а їхня арифметика точок ідеально підходить для commitments.

Чи доведено, що ECDLP є складною? Не доведено, що вона неможлива, але десятиліття інтенсивних зусиль не виявили жодної ефективної атаки на правильно обрані криві. Безпека спирається на це добре перевірене припущення.

Чи міг би квантовий комп’ютер це зламати? Достатньо великий квантовий комп’ютер міг би зламати ECDLP. Це відома довгострокова проблема для всієї індустрії й активна сфера досліджень; нинішні криві залишаються безпечними проти класичних комп’ютерів.

Чому Zcash використовує більше ніж одну криву? Для різних задач. Одна крива несе систему доказів з нульовим розголошенням; інша (вбудована в поле першої) робить операції з ключами та commitments всередині доказу ефективними. Наступні статті пояснять, чому це поєднання має значення.

Перевірте свою інтуїцію

Використовуючи перевірену таблицю з розділу 3, чому дорівнює 9G + 10G на нашій іграшковій кривій? І що ця відповідь говорить вам про G? (Відповідь нижче.)

Що далі

Стаття 3 . Хешування і commitments: ми нарешті як слід розкриємо «магічний запечатаний конверт». Ви вже побачили один спосіб побудувати commitment із точок кривої; далі ми запитаємо, що насправді означають hiding і binding, познайомимося з хеш-функціями й пов’яжемо обидві ідеї з note commitments, на яких ґрунтується кожен платіж Zcash.

Частина серії Zcash from First Principles для ZecHub. Ліцензовано за CC BY-SA 4.0.