Віталік Бутерін через в Блог Віталіка Бутеріна
Це дзеркало поста на https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
Це третя частина серії статей, що пояснюють, як працює технологія zk-SNARK; попередні статті на програми квадратичної арифметики та поєднання еліптичних кривих є обов’язковими для прочитання, і ця стаття передбачає знання обох понять. Також передбачається базове знання того, що таке zk-SNARK і що вони роблять. Дивись також Стаття Крістіана Райтвіснера тут для іншого технічного вступу.
У попередніх статтях ми представили програму квадратичної арифметики, спосіб представлення будь-якої обчислювальної задачі за допомогою поліноміального рівняння, який набагато легше піддається різноманітним формам математичних трюків. Ми також представили пари еліптичних кривих, які дозволяють дуже обмежену форму одностороннього гомоморфного шифрування, яке дозволяє перевіряти рівність. Тепер ми почнемо з того місця, на якому зупинилися, і використаємо поєднання еліптичних кривих разом із кількома іншими математичними трюками, щоб дозволити перевіряльнику довести, що він знає рішення для конкретного QAP, не розкриваючи нічого іншого про фактичне рішення.
Ця стаття буде присвячена Протокол Піноккіо Парно, Джентрі, Хоуелл і Райкова з 2013 р. (часто називається PGHR13); існує кілька варіацій базового механізму, тому схема zk-SNARK, реалізована на практиці, може працювати дещо інакше, але основні принципи загалом залишаться незмінними.
Для початку давайте перейдемо до ключового криптографічного припущення, яке лежить в основі безпеки механізму, який ми збираємося використовувати: *знання експоненти* припущення.
По суті, якщо ви отримуєте пару точок � і �, де �⋅�=�, і ви отримуєте точку �, тоді неможливо придумати �⋅�, якщо � не буде «похідним» від � якимось чином що ви знаєте. Це може здатися інтуїтивно очевидним, але це припущення насправді не можна вивести з будь-якого іншого припущення (наприклад, дискретного логарифму твердості), яке ми зазвичай використовуємо, коли підтверджуємо безпеку протоколів на основі еліптичних кривих, і тому zk-SNARK фактично спираються на дещо більш хитка основа, ніж криптографія еліптичної кривої загалом — хоча вона все ще достатньо міцна, щоб більшість криптографів з нею погоджувалися.
Тепер давайте розглянемо, як це можна використовувати. Припустимо, що пара точок (�,�) падає з неба, де �⋅�=�, але ніхто не знає, яке значення �. Тепер припустімо, що я знайшов пару точок (�,�), де �⋅�=�. Тоді припущення KoE означає, що єдиний спосіб, яким я міг створити цю пару точок, це взяти � і � і помножити обидва на деякий коефіцієнт r що я особисто знаю. Зауважте також, що завдяки магії поєднання еліптичних кривих перевірка того, що �=�⋅� насправді не потрібно знати � – замість цього ви можете просто перевірити, чи �(�,�)=�(�,�).
Давайте займемося чимось цікавішим. Припустимо, що у нас з неба впало десять пар точок: (�1,�1),(�2,�2)…(�10,�10). У всіх випадках ��⋅�=��. Припустімо, що я надаю вам пару точок (�,�), де �⋅�=�. Що ти тепер знаєш? Ви знаєте, що � є деякою лінійною комбінацією �1⋅�1+�2⋅�2+…+�10⋅�10, де я знаю коефіцієнти �1,�2...�10. Тобто єдиний спосіб отримати таку пару точок (�,�) — це взяти кілька кратних �1,�2...�10 і додати їх разом, і зробити той самий обчислення з �1,�2... �10.
Зауважте, що враховуючи будь-який конкретний набір �1...�10 точок, для яких ви можете перевірити лінійні комбінації, ви не можете фактично створити супутні �1...�10 точок, не знаючи, що таке �, і якщо ви знаєте, що � тоді ви можете створити пару (�,�), де �⋅�=� для будь-якого � ви хочете, не турбуючись про створення лінійної комбінації. Отже, для того, щоб це працювало, абсолютно необхідно, щоб той, хто створює ці точки, заслуговував на довіру та фактично видаляв � як тільки вони створили десять точок. Звідси походить концепція «довіреної установки»..
Пам’ятайте, що розв’язком QAP є набір поліномів (�,�,�), таких що �(�)⋅�(�)−�(�)=�(�)⋅�(�), де:
- � є лінійною комбінацією набору поліномів {�1…��}
- � є лінійною комбінацією {�1…��} з однаковими коефіцієнтами
- � є лінійною комбінацією {�1…��} з однаковими коефіцієнтами
Множини {�1…��}, {�1…��} і {�1…��} і поліном � є частиною постановки задачі.
Однак у більшості реальних випадків �,� і � надзвичайно великі; для чогось із багатьма тисячами ланцюгів, наприклад хеш-функції, поліноми (і множники для лінійних комбінацій) можуть мати багато тисяч членів. Отже, замість того, щоб довідник надавав лінійні комбінації напряму, ми збираємося використати трюк, який ми представили вище, щоб довести, що він надає щось, що є лінійною комбінацією, але не розкриваючи нічого іншого.
Ви могли помітити, що наведений вище трюк працює з точками еліптичної кривої, а не з поліномами. Таким чином, ми додаємо наступні значення до довірених налаштувань:
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
- �⋅�1(�),�⋅�1(�)⋅��
- �⋅�2(�),�⋅�2(�)⋅��
- ...
Ви можете думати про t як про «секретну точку», в якій обчислюється поліном. � є «генератором» (деяка випадкова точка еліптичної кривої, яка вказана як частина протоколу), а �,��,�� і �� є “токсичними відходами”, числами, які обов’язково потрібно видалити будь-якою ціною, інакше той, хто їх має, зможе зробити підроблені докази. Тепер, якщо хтось дає вам пару точок �, � так, що �⋅��=� (нагадуємо: нам не потрібен ��, щоб перевірити це, оскільки ми можемо зробити перевірку пари), то ви знаєте, що вони дають вам лінійну комбінацію �� поліномів, оцінених у �.
Отже, поки що довідник повинен надати:
- ��=�⋅�(�),��′=�⋅�(�)⋅��
- ��=�⋅�(�),��′=�⋅�(�)⋅��
- ��=�⋅�(�),��′=�⋅�(�)⋅��
Зауважте, що перевіряльнику насправді не потрібно знати (і не повинен знати!) �,��,�� або ��, щоб обчислити ці значення; скоріше, перевірка повинна мати можливість обчислити ці значення лише з точок, які ми додаємо до довіреної установки.
Наступним кроком є переконатися, що всі три лінійні комбінації мають однакові коефіцієнти. Це можна зробити, додавши ще один набір значень до довіреної установки: �⋅(��(�)+��(�)+��(�))⋅�, де � інше число, яке слід вважати «токсичним». відходи» та викидається, щойно довірене налаштування буде завершено. Потім ми можемо попросити перевірку створити лінійну комбінацію з цими значеннями з тими самими коефіцієнтами та використати той самий трюк поєднання, що й вище, щоб перевірити, що це значення збігається з наданим �+�+�.
Нарешті, нам потрібно довести, що �⋅�−�=�⋅�. Ми робимо це ще раз за допомогою перевірки сполучення:
�(��,��)/�(��,�)?=�(�ℎ,�⋅�(�))
Де �ℎ=�⋅�(�). Якщо зв’язок між цим рівнянням і �⋅�−�=�⋅� для вас не має сенсу, поверніться назад і прочитайте стаття про пари.
Вище ми бачили, як перетворити �,� і � в точки еліптичної кривої; � є просто генератором (тобто точкою еліптичної кривої, еквівалентною номеру один). Ми можемо додати �⋅�(�) до надійного налаштування. � важче; � є просто поліномом, і ми заздалегідь дуже мало прогнозуємо, якими будуть його коефіцієнти для кожного окремого рішення QAP. Отже, нам потрібно додати ще більше даних до надійної установки; зокрема послідовність:
�,�⋅�,�⋅�2,�⋅�3,�⋅�4….
У довіреній системі Zcash послідовність досягає приблизно 2 мільйонів; Це скільки ступенів � вам потрібно, щоб переконатися, що ви завжди зможете обчислити �(�), принаймні для конкретного екземпляра QAP, який їх цікавить. При цьому перевіряльник може надати всю інформацію верифікатору для остаточної перевірки.
Є ще одна деталь, яку потрібно обговорити. У більшості випадків ми не просто хочемо абстрактно довести, що існує певне рішення для певної проблеми; скоріше, ми хочемо довести або правильність якогось конкретного рішення (наприклад, довести, що якщо взяти слово «корова» і SHA3 хешувати його мільйон разів, кінцевий результат починається з 0x73064fe5), або те, що рішення існує, якщо ви обмежите деякі з параметрів. Наприклад, у екземплярі криптовалюти, де суми транзакцій і залишки на рахунку зашифровано, ви хочете довести, що знаєте якийсь ключ дешифрування k, який:
decrypt(old_balance, k) >= decrypt(tx_value, k)
decrypt(old_balance, k) - decrypt(tx_value, k) = decrypt(new_balance, k)
Зашифрований old_balance
, tx_value
та new_balance
має бути зазначено публічно, оскільки це конкретні значення, які ми хочемо перевірити в той конкретний час; тільки ключ дешифрування має бути прихованим. Деякі незначні модифікації протоколу необхідні для створення «спеціального ключа перевірки», який відповідає певним обмеженням на вхідні дані.
Тепер давайте трохи відступимо. Перш за все, ось повний алгоритм перевірки, люб’язно наданий Беном Сассон, Тромер, Вірза і К'єза:
Перший рядок стосується параметризації; по суті, ви можете думати про його функцію як про створення «спеціального ключа перевірки» для конкретного випадку проблеми де вказані деякі з аргументів. Другий рядок — перевірка лінійної комбінації для �,� і �; третій рядок — перевірка того, що лінійні комбінації мають однакові коефіцієнти, а четвертий рядок — перевірка добутку �⋅�−�=�⋅�.
Загалом процес перевірки складається з кількох множень еліптичної кривої (по одному для кожної «публічної» вхідної змінної) і п’яти перевірок пар, одна з яких включає додаткове множення пар. Доказ містить вісім точок еліптичної кривої: пара точок кожна для �(�),�(�) і �(�), точка �� для �⋅(�(�)+�(�)+�(� )) і точку �ℎ для �(�). Сім із цих точок знаходяться на кривій �� (32 байти кожна, оскільки ви можете стиснути координату � до одного біта), а в реалізації Zcash одна точка (��) знаходиться на скрученій кривій у ��2 (64 байт), тому загальний розмір доказу становить ~288 байт.
Дві складні з обчислювальної точки зору частини створення доказу:
- Ділення (�⋅�−�)/� для отримання � (алгоритми на основі Швидке перетворення Фур'є можна зробити це за субквадратичний час, але це все одно досить інтенсивне обчислення)
- Виконання множень і додавання еліптичної кривої для створення значень �(�),�(�),�(�) і �(�) та їхніх відповідних пар
Основною причиною, чому створення доказу є таким важким, є той факт, що те, що було єдиним двійковим логічним вентилем у початкових обчисленнях, перетворюється на операцію, яку потрібно криптографічно обробити за допомогою операцій еліптичної кривої, якщо ми робимо з цього доказ нульового знання. . Цей факт разом із надлінійністю швидких перетворень Фур’є означає, що створення доказів займає приблизно 20–40 секунд для транзакції Zcash.
Ще одне дуже важливе питання: чи можемо ми спробувати зробити довірене налаштування трохи… менш вимогливим до довіри? На жаль, ми не можемо зробити його повністю ненадійним; саме припущення KoE виключає створення незалежних пар (��,��⋅�), не знаючи, що таке �. Однак ми можемо значно підвищити безпеку, використовуючи багатостороннє обчислення �-of-�, тобто побудувавши довірену систему між � сторонами таким чином, якщо принаймні один із учасників видалив свої токсичні відходи, тоді все гаразд. .
Щоб трохи відчути, як це зробити, ось простий алгоритм для взяття існуючого набору (�,�⋅�,�⋅�2,�⋅�3…) і «додавання» власного секрету так що вам знадобиться як ваш секрет, так і попередній секрет (або попередній набір секретів) для обману.
Вихідний набір простий:
�,(�⋅�)⋅�,(�⋅�2)⋅�2,(�⋅�3)⋅�3…
Зауважте, що ви можете створити цей набір, знаючи лише початковий набір і s, а новий набір функціонує так само, як і старий набір, за винятком використання �⋅� як «токсичних відходів» замість �. До тих пір, поки ви та особа (або люди), які створили попередній набір, не видалили ваші токсичні відходи й пізніше домовилися, набір є «безпечним».
Зробити це для повного довіреного налаштування трохи важче, оскільки задіяно кілька значень, і алгоритм має виконуватися між сторонами в кілька раундів. Це сфера активних досліджень, щоб дізнатися, чи можна ще більше спростити алгоритм багатосторонніх обчислень і зробити так, щоб він вимагав менше раундів або зробити його більш розпаралелюваним, оскільки чим більше ви можете це зробити, тим більше сторін стане доцільним включити в процедуру надійного налаштування. . Розумно зрозуміти, чому довірена організація між шістьма учасниками, які знають і працюють один з одним, може викликати у деяких людей незручність, але довірену схему з тисячами учасників майже неможливо відрізнити від повної відсутності довіри – і якщо ви справді параноїк , ви можете зайти та взяти участь у процедурі налаштування самостійно, і бути впевненим, що ви особисто видалили своє значення.
Ще одна сфера активних досліджень — це використання інших підходів, які не використовують пари та ту саму парадигму надійного налаштування для досягнення тієї самої мети; побачити Недавня презентація Елі бен Сассона для однієї альтернативи (хоча майте на увазі, що вона принаймні така ж математично складна, як і SNARK!)
Особлива подяка Аріелю Габізону та Крістіану Райтвіснеру за рецензування.
- Розповсюдження контенту та PR на основі SEO. Отримайте посилення сьогодні.
- PlatoData.Network Vertical Generative Ai. Додайте собі сили. Доступ тут.
- PlatoAiStream. Web3 Intelligence. Розширення знань. Доступ тут.
- ПлатонЕСГ. вуглець, CleanTech, Енергія, Навколишнє середовище, Сонячна, Поводження з відходами. Доступ тут.
- PlatoHealth. Розвідка про біотехнології та клінічні випробування. Доступ тут.
- BlockOffsets. Модернізація екологічної компенсаційної власності. Доступ тут.
- джерело: Інформація про дані Платона.