Повний огляд технології zk-SNARKs та перспективи на майбутнє

Резюме

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

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

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

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

Каталог

Вступ

О, 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. Розвиток технологій масштабування ZKP
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 року вчені Goldwasser, Micali та Rackoff у статті "The Knowledge Complexity of Interactive Proof-Systems" вперше запропонували zk-SNARKs (Zero-Knowledge Proof, ZKP ) та Interactive Zero-Knowledge (IZK ). Ця стаття стала основоположною для нульових знань, визначила багато концепцій, що вплинули на подальші академічні дослідження. Наприклад, визначення знань є "вихід невиконуваного обчислення (unfeasible computation )", тобто знання повинні бути виходом, і це невиконуване обчислення, що означає, що це не може бути простою функцією, а має бути складною функцією. Невиконуване обчислення зазвичай можна розуміти як NP-проблему, тобто проблему, для якої можна перевірити правильність її розв'язку за поліноміальний час, де поліноміальний час означає, що час виконання алгоритму може бути представлений як поліноміальна функція розміру вхідних даних. Це важливий стандарт для оцінки ефективності та здійсненності алгоритмів у комп'ютерних науках. Оскільки процес розв'язання NP-проблем є складним, його вважають невиконуваним обчисленням; проте процес перевірки відносно простий, тому дуже підходить для верифікації нульових знань.

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

У своїй статті Гольдвассер та інші ввели концепцію "складності знань" ( knowledge complexity ), щоб кількісно оцінити, яку кількість знань викриває доводчик перевірячу в інтерактивних системах доведення. Вони також запропонували інтерактивні системи доведення ( 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;

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

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

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

)# 1. Фон

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

2. Введення NIZK

1