Розвиток та застосування технології zk-SNARKs: огляд у сфері Блокчейн

Резюме

zk-SNARKs(ZKP) як важливий прорив у галузі криптографії відіграє ключову роль у технології Блокчейн. У цій статті проведено систематичний огляд розвитку ZKP за останні сорок років та останніх досліджень.

По-перше, було представлено основні концепції та історичний фон ZKP. Далі було проаналізовано технології ZKP на основі схем, включаючи проєкти zkSNARK, Ben-Sasson, Pinocchio, Bulletproofs та Ligero, їхнє проєктування, застосування та методи оптимізації. Щодо обчислювального середовища, у статті обговорюється, як ZKVM та ZKEVM підвищують пропускну здатність обробки транзакцій, захищають конфіденційність та підвищують ефективність верифікації. Також було представлено механізми роботи та методи оптимізації нульових знань Rollup як рішення для розширення Layer 2, а також останні досягнення в апаратному прискоренні, змішаних рішеннях та спеціалізованих ZK EVM.

Нарешті, було розглянуто нові концепції, такі як ZKCoprocessor, ZKML, ZKThreads, ZK Sharding та ZK StateChannels, та обговорено їх потенціал у питаннях масштабованості Блокчейн, взаємодії та захисту конфіденційності.

Аналізуючи ці тенденції розвитку технологій, ця стаття надає всебічний погляд на розуміння та застосування технології ZKP, демонструючи її величезний потенціал у підвищенні ефективності та безпеки систем Блокчейн, що є важливим орієнтиром для майбутніх інвестиційних рішень.

Зміст

Вступ

Один. Основи zk-SNARKs

1. Огляд
2. Приклад zk-SNARKs

Два, неінтерактивні zk-SNARKs

1. Фон
2. Введення NIZK
3. Перетворення Фіата-Шаміра
4. Йенс Грот та його дослідження
5. Інші дослідження

Три, zk-SNARKs на основі схем

1. Фон
2. Основні поняття та характеристики електричних моделей
3. Дизайн і застосування електричних схем у zk-SNARKs
4. Потенційні недоліки та виклики

Чотири, модель zk-SNARKs

1. Фон
2. Звичайні алгоритмічні моделі
3. Рішення на основі лінійного PCP та дискретної логарифмічної задачі
4. Програма на основі доказів звичайних людей
5. Основи ймовірності, що підлягає перевірці, доведення ( PCP ) zk-SNARKs
6. Класифікація етапу налаштування загального доказу на основі CPC( конструкції )

П'ять. Огляд та розвиток нульових знань віртуальної машини

1. Фон
2. Існуюча класифікація ZKVM
3. Парадигми фронтенду та бекенду
4. Переваги та недоліки парадигми ZKVM

Шосте. Огляд і розвиток zk-SNARKs Ethereum Virtual Machine

1. Фон
2. Принцип роботи ZKEVM
3. Процес реалізації ZKEVM
4. Особливості ZKEVM

Сім, огляд та розвиток рішень другого рівня з нульовими знаннями

1. Фон
2. Механізм роботи zk-Rollup
3. Недоліки та оптимізація ZK Rollup

Вісім. Майбутні напрямки розвитку zk-SNARKs

1. Прискорення розвитку обчислювального середовища
2. Виникнення та розвиток ZKML
3. Розвиток технологій розширення zk-SNARKs
4. Розвиток інтероперабельності zk-SNARKs

Дев’яте, висновок

Передмова

Інтернет входить в епоху Web3, застосування Блокчейн (DApps) розвивається швидко. Останніми роками Блокчейн платформи щодня обслуговують мільйони користувачів, обробляючи десятки мільярдів транзакцій. Ці транзакції генерують величезну кількість даних, які зазвичай містять чутливу особисту інформацію. Враховуючи відкритість і прозорість Блокчейн, ці збережені дані є загальнодоступними, що викликає різноманітні проблеми безпеки та конфіденційності.

Наразі існує кілька криптографічних технологій, які можуть впоратися з цими викликами, включаючи гомоморфне шифрування, кільцеві підписи, безпечні багатосторонні обчислення та zk-SNARKs. zk-SNARKs є більш комплексним рішенням, цей протокол верифікації дозволяє перевіряти правильність певних тверджень без розкриття жодних проміжних даних. Цей протокол не потребує складних систем відкритих ключів, а його багаторазове впровадження не надає зловмисним користувачам можливості отримати додаткову корисну інформацію. Завдяки ZKP, верифікатор може підтвердити, чи має доводчик достатню суму транзакцій без розкриття будь-яких приватних даних транзакції.

Ця характеристика ZKP робить його ключовим у блокчейн-транзакціях та застосуваннях криптовалюти, особливо в питаннях захисту конфіденційності та масштабування мережі, що робить його не лише об'єктом академічних досліджень, а й широко вважається одним з найважливіших технологічних інновацій з моменту успішного впровадження розподілених реєстраційних технологій. Одночасно це також ключова арена для галузевих застосувань та венчурного капіталу.

Відповідно, численні мережеві проекти на основі ZKP з’являються один за одним, такі як ZkSync, StarkNet, Mina, Filecoin та Aleo. З розвитком цих проектів з’являються нові алгоритмічні інновації в галузі ZKP, і повідомляється, що майже щотижня з’являється новий алгоритм. Крім того, розробка апаратного забезпечення, пов’язаного з технологією ZKP, також стрімко прогресує, включаючи чіпи, оптимізовані спеціально для ZKP. Наприклад, такі проекти, як Ingonyama, Irreducible та Cysic, вже завершили масштабний збір коштів, і ці розробки не лише демонструють швидкий прогрес технології ZKP, але й відображають перехід від загального апаратного забезпечення до спеціалізованого, такого як GPU, FPGA та ASIC.

Ці досягнення свідчать про те, що технологія zk-SNARKs є не лише важливим проривом у галузі криптографії, але й ключовим чинником для реалізації більш широкого застосування технології Блокчейн.

Отже, ми вирішили систематично впорядкувати знання про zk-SNARKs (ZKP), щоб краще допомогти нам приймати майбутні інвестиційні рішення. Для цього ми комплексно переглянули основні академічні статті, пов'язані з ZKP; одночасно, ми також детально проаналізували матеріали та білі книги провідних проєктів у цій сфері. Це комплексне збирання та аналіз матеріалів забезпечили міцну основу для написання цієї статті.

Один. Основи zk-SNARKs

1. Огляд

У 1985 році вчені Голдвассер, Мікалі та Раккоф вперше запропонували zk-SNARKs ( Zero-Knowledge Proof, ZKP ) та інтерактивні знання ( Interactive Zero-Knowledge, IZK ). Ця стаття є основоположною для zk-SNARKs, визначаючи багато концепцій, які вплинули на подальші наукові дослідження. Наприклад, визначення знань звучить як "недоступний обчислювальний вихід", тобто знання повинні бути виходом, і це має бути недоступне обчислення, що означає, що це не може бути простою функцією, а має бути складною функцією. Невиконуване обчислення зазвичай можна розуміти як NP-проблему, тобто проблему, рішення якої можна перевірити за поліноміальний час, поліноміальний час означає, що час роботи алгоритму можна виразити як поліноміальну функцію від розміру вхідних даних. Це важливий стандарт в комп'ютерних науках для оцінки ефективності та здійсненності алгоритмів. Оскільки процес розв'язання NP-проблеми складний, його вважають недоступним обчисленням; але процес перевірки є відносно простим, тому дуже підходить для верифікації zk-SNARKs.

Класичним прикладом задачі NP є задача комівояжера, в якій потрібно знайти найкоротший шлях для відвідування ряду міст і повернення до початкової точки. Хоча знайти найкоротший шлях може бути важко, але перевірити, чи є даний шлях найкоротшим, відносно легко. Оскільки перевірка загальної відстані конкретного шляху може бути виконана за поліноміальний час.

У своїй статті Голдвассер та інші ввели поняття "складності знань", щоб кількісно оцінити обсяги знань, які доказчик розкриває перевіряєві в інтерактивних системах доказів. Вони також запропонували інтерактивні системи доказів (Interactive Proof Systems, IPS), в яких доказчик (Prover) і перевіряючий (Verifier) взаємодіють протягом кількох раундів, щоб довести істинність певного твердження.

Отже, визначення zk-SNARKs, підсумоване Голдвассером та ін. — це особливий інтерактивний доказ, у якому перевіряючий під час процесу перевірки не отримує жодної додаткової інформації, окрім істинності висловлення; і було запропоновано три основні характеристики, що включають:

1. Повнота ( completeness ): якщо доказ є істинним, чесний доводчик може переконати чесного перевіряючого в цьому факті;

2. Надійність (soundness ): Якщо доводчик не знає змісту заяви, він може лише з незначною ймовірністю обманути перевіряючого;

3. zk-SNARKs(zero-knowledge): Після завершення процесу доказу, перевіряючий отримує лише інформацію "доказувач має ці знання", але не може отримати жодного додаткового вмісту.

2. приклади zk-SNARKs

Для кращого розуміння zk-SNARKs та їхніх властивостей, нижче наведено приклад перевірки того, чи має довіритель певну конфіденційну інформацію. Цей приклад поділяється на три етапи: налаштування, виклик та відповідь.

Перший крок: налаштуйте (Setup)

На цьому етапі метою доказувача є створення доказу, що він знає певне таємне число s, але не показує s безпосередньо. Нехай таємне число s;

Виберіть два великі прості числа p та q, обчисліть їх добуток n. Нехай прості числа p та q, обчисліть отримане n;

Обчисліть v=s^2 mod n, тут v, як частина доказу, надсилається перевіряючому, але його недостатньо, щоб перевіряючий або будь-який спостерігач міг вивести s;

Випадково виберіть ціле число r, обчисліть x=r^2 mod n і надішліть його валідатору. Це значення x використовується для подальшого процесу верифікації, але також не розкриває s. Нехай випадкове ціле число r, обчислене x.

Другий крок: виклик (Challenge)

Валідатор випадковим чином вибирає позицію a(, яка може бути 0 або 1), а потім відправляє її довірителю. Цей "виклик" визначає наступні кроки, які потрібно зробити довірителю.

Третій крок: відповідь (Response)

Згідно з a-значенням, надісланим валідатором, довіритель надає відповідь:

Якщо a=0, то довіритель надсилає g=r(, де r – це число, яке він вибрав випадковим чином раніше ).

Якщо a=1, довіритель обчислює g=rs mod n та надсилає. Нехай перевіряльник надішле випадковий біт a, відповідно до значення a довіритель обчислює g;

Нарешті, валідатор перевіряє, чи дорівнює x g^2 mod n, спираючись на отримане g. Якщо рівність виконується, валідатор приймає це свідчення. Коли a=0, валідатор обчислює x=g^2 mod n, праворуч перевіряє g^2 mod n; коли a=1, валідатор обчислює x=g^2/v mod n, праворуч перевіряє (rs)^2/s^2 mod n.

Тут ми бачимо, що x=g^2 mod n, обчислене валідатором, свідчить про те, що доказувач успішно пройшов процес верифікації, не розкривши свого секретного числа s. Оскільки a може приймати лише значення 0 або 1, існують лише два варіанти, ймовірність того, що доказувач пройде верифікацію за допомогою везіння, дорівнює 1/2(, коли a дорівнює 0, тобто ). Але валідатор потім викликає доказувача k разів, доказувач постійно змінює відповідні числа і надсилає їх валідатору, і завжди успішно проходить процес верифікації, в цьому випадку ймовірність того, що доказувач пройде верифікацію за допомогою везіння, дорівнює (1/2)^k(, що безмежно наближається до 0), отже, висновок про те, що доказувач дійсно знає певне секретне число s, отримує підтвердження. Цей приклад доводить цілісність, надійність та властивість нульового знання системи нульових знань.

Два, неінтерактивні zk-SNARKs

1. Фон

zk-SNARKs(ZKP)в традиційній концепції зазвичай є інтерактивною та онлайн формою протоколу; наприклад, протокол Sigma зазвичай потребує три-п’ять раундів взаємодії для завершення аутентифікації. Однак у таких сценах, як миттєві транзакції або голосування, часто немає можливості для багатократної взаємодії, особливо в застосуванні технології Блокчейн, функція офлайн-підтвердження стає особливо важливою.

2. Запропоновано NIZK

У 1988 році Блум, Фельдман і Мікалі вперше запропонували концепцію неінтерактивних нульових знань (NIZK), довівши, що без необхідності багаторазової взаємодії, доводчик (Prover) і перевіряючий (Verifier) все ж можуть завершити процес аутентифікації. Цей прорив зробив можливим реалізацію миттєвих транзакцій, голосування та застосувань Блокчейн.

Вони запропонували неінтерактивні zk-SNARKs ( NIZK ), які можна поділити на три етапи:

1. Налаштування
2. Обчислення
3. Підтвердження

Налаштування етапу з використанням обчислювальної функції, що перетворює безпечний параметр на загальновідомий (, доступний як для доказувача, так і для перевіряючого ), зазвичай кодується в спільному довідковому рядку (CRS). Це спосіб обчислення доказу та перевірки з використанням правильних параметрів і алгоритмів.

На етапі обчислення використовуються обчислювальні функції, ключі введення та свідчення, виходять результати обчислень та свідчення.

На етапі перевірки дійсність доказу перевіряється за допомогою перевірочного ключа.

Запропонована ними модель загального довідкового рядка (CRS), тобто на основі того, що всі учасники діляться одним рядком для реалізації NP-проблеми неінтерактивних zk-SNARKs. Робота цієї моделі залежить від надійного генерування CRS, всі учасники повинні мати доступ до однакового рядка. Лише коли CRS правильно та безпечно згенеровано, можна забезпечити безпеку схем, реалізованих за цією моделлю. Для великої кількості учасників процес генерування CRS може бути як складним, так і тривалим, тому, незважаючи на те, що такі схеми зазвичай прості у використанні та мають невелику об'ємність доказів, процес їх налаштування є досить складним.

Потім технологія NIZK зазнала швидкого розвитку, з'явилося безліч методів перетворення інтерактивних нульових доказів на неінтерактивні докази. Ці методи у побудові системи