У складній галузі криптографії докази з нульовим знанням пропонують унікальне рішення, здавалося б, суперечливого завдання: довести знання частини інформації без розкриття самої інформації. У цьому методі шифрування беруть участь дві сторони: підтверджувач і перевіряльник. Мета перевірки полягає в тому, щоб довести, що вони володіють певною інформацією (назвемо її x), не розкриваючи жодних даних про сам x. Про те, що верифікатор дізнається з обміну, це простий факт, що перевіряльник має ці знання. Найголовніше, що верифікатор не має додаткової інформації про x.
Наприклад, коли Сяолін і Сяоші грають у квест, Сяолінг каже Сяолінгу, що зламав пароль певної «скриньки зі скарбами». Але Сяо Лін не бажає прямо ділитися готовою «відповіддю» і не бажає відкривати скриню зі скарбами перед Сяо Теном. Тож як довести Сяо Ши, що він справді розгадав головоломку та знає пароль скрині зі скарбами?
Тож він попросив Сяо Тена написати на аркуші паперу рядок рядків, які знав лише він, одночасно підписати своє ім’я та просунув папір у щілину в скрині зі скарбами.
Потім Сяо Лін відкрив скриньку зі скарбами, вийняв папір, який поклав Сяо Тень, і показав його Сяо Тену. Сяо Тен перевірив, чи правильний рядок і підпис. Це доводить, що Сяо Лін знає пароль скриньки зі скарбами, і цей папірець справді витягли зі скриньки.
Процес дешифрування не був відомий Сяо Тену, і в той же час Сяо Лін довів, що він зламав пароль скриньки зі скарбами.
Доказ нульового знання
У криптографії Доказ нульового знання (Zero Knowledge Proof, також відомий як ZKP) або протокол нульового знання — це метод, який дозволяє перевіряючому перевіряти без розкриття самої інформації чи будь-якої іншої інформації. Верифікатор вірить або доводить, засіб перевірки істинності певного твердження чи твердження.
Доказ із нульовим знанням вперше запропонували професори Массачусетського технологічного інституту Шафі Голдвассер, Сільвіо Мікалі та майстер криптографії Чарльз Рокофф у статті «Складність знань інтерактивних доказів». Ця концепція алгоритму заклала певну основу для сучасної криптографії.
Докази з нульовим знанням мають дві додаткові властивості: короткі та з нульовим знанням. Стислість дозволяє верифікатору прийняти правильність великого обчислення без обчислення самого твердження чи представлення. А нульове знання гарантує відсутність витоку даних про введення.
Докази з нульовим знанням мають вирішальне значення для забезпечення конфіденційності та безпеки багатьох криптографічних протоколів. Вони є запобіжником від можливого витоку інформації, невидимим бронежилетом криптосвіту. Застосування цих знань можна поширити на різні сфери, включаючи технологію блокчейн і безпечні системи автентифікації, де захист конфіденційних даних має першочергове значення.
Широкий спектр застосування
**Блокчейн і технологія шифрування: **Технологія блокчейну, як-от Zcash, використовує докази нульового знання для захисту конфіденційності транзакцій. Людина може довести, що у неї достатньо кіптовалюти для здійснення транзакції, не розкриваючи точну суму своїх коштів. Це забезпечує конфіденційність, одночасно забезпечуючи цілісність транзакцій. **Перевірка особи та автентифікація: **Підтвердження нульової інформації також можна використовувати для підтвердження особи без розкриття непотрібної інформації. Наприклад, особа може підтвердити, що їй вже виповнилося 18 років, не вказуючи точної дати народження, або підтвердити свою особу, не повідомляючи конфіденційних даних, як-от паролів. Це мінімізує ризик викрадення особистих даних або несанкціонованого доступу.
Безпечні багатосторонні обчислення (SMPC): Докази з нульовим знанням можуть сприяти складній взаємодії між декількома сторонами, де кожна сторона може довести, що вона дотримується узгодженого протоколу, не розкриваючи специфіку свого введення. Це дуже ефективно в багатьох аспектах, таких як інтелектуальний аналіз даних із збереженням конфіденційності, безпечні системи голосування тощо. Мережева безпека: Докази з нульовим знанням можуть забезпечувати покращені протоколи безпеки, такі як безпечні політики паролів. Він може перевірити, чи запропонований користувачем пароль відповідає певним стандартам безпеки, не повідомляючи серверу та не записуючи фактичний пароль. Оскільки паролі ніде не зберігаються, потенційні порушення запобігають. **Обмін даними з одночасним захистом конфіденційності: **Доказ нульової інформації можна використовувати, щоб підтвердити, що певні дані відповідають певним вимогам, не розкриваючи самих даних, що особливо важливо в таких сферах, як медичне обслуговування чи фінанси. Положення щодо конфіденційності даних у цих сферах є суворими, але обмін інформацією безпечним способом із збереженням конфіденційності може принести величезні переваги, наприклад, сприяти розвитку медичної кар’єри тощо. Докази з нульовим знанням відкрили нові технічні можливості в блокчейні. Це можна побачити в різних рівнях 2, таких як ZKSync і zkEVM Polygon. Однак це лише підмножина блокчейнів, створених доказами з нульовим знанням.
Як висловити доказ
У цьому розділі та в решті статті ми зосередимося на доказах, створених для систем перевірки на основі PLONK.
PLONK — це система доказів нульового знання, її повна назва:
«Перестановки над базами Лагранжа для всесвітніх неінтерактивних аргументів знання», тобто «Глобальна система доказів неінтерактивного знання на основі баз Лагранжа».
По суті, PLONK — це універсальна, оновлювана система криптографічного підтвердження, інновація, яка дозволяє ефективну перевірку та масштабування в системах блокчейн та інших розподілених мережах. Ідея PLONK полягає в тому, щоб побудувати загальну й оновлювану систему доказів. У контексті систем доказів з нульовим знанням «універсальний» означає, що його можна використовувати для будь-якого типу обчислень; «оновлюваний» означає, що рядок криптографічного посилання (частина даних, яка використовується для створення та перевірки доказів) безпечно оновлюється з часом. .
PLONK виділяється своєю ефективністю та простотою, що робить його популярним вибором для проектів і компаній, яким потрібна безпечна приватна система транзакцій. Порівняно з іншими системами, вона використовує менше обмежень на гейт (основну одиницю обчислення, яку ми разом називаємо «шлюз»), що робить обчислення швидшим і більш масштабованим. Віталік Бутерін опублікував більш повний опис PLONK. [Скопіюйте посилання в браузер, щоб переглянути вихідний текст
довести
Перш ніж доводити твердження, ми спочатку представляємо твердження в термінах схеми. Схема кодує значення в обчисленні разом із двома іншими типами даних:
Операції: такі як обчислення множення та додавання вхідних даних 2. Порядок виконання операцій
Для кодування цих даних схеми PLONKish представлені як набір векторів і обмежень. Обмеження – це зв’язки, яким повинні підкорятися одиниці у векторі. Типи обмежень: обмеження воріт і обмеження копіювання, які відповідно представляють операції та порядок операцій у схемі.
Існує багато способів вираження схеми за допомогою різних архітектур воріт і схем.
Уявіть оператор як схему
Припустимо, що у нас є два вентилі: вентиль множення та вентиль додавання. Вентиль множення представлено у вигляді вектора |a|b|c| довжини 3. Якщо цей гейт вибрано, він обмежуватиме c рівним a*b. Аналогічно, вентиль додавання представляється як вектор довжини 3, і якщо вибрано вентиль додавання, c дорівнює a+b. Використовуючи ці вентилі, представимо скалярний добуток між двома векторами (a,b) і (c,d). Для цього нам потрібно виконати наступні обчислення: 1. Використовуйте вентиль множення, щоб обчислити a*b2. Використовуйте вентиль множення, щоб обчислити c*d3. Використовуйте вентиль додавання, щоб обчислити ab+cd. Це можна представити так: вектор.
Зауважте, що вихід першого та другого вентилів множення є вхідним значенням вентиля додавання. Ці дані кодуються окремо від обмежень вентиля в нашій схемі. Це називається обмеженням копіювання. Отже, чому обмеження схеми важливі? Якби не було обмежень, тоді зловмисний валідатор міг би ввести в схему будь-яке значення, яке йому подобається. Наприклад, верифікатор може замінити ab+cd на aba*b. Подібно до смарт-контрактів, обмеження повинні бути перевірені за допомогою системи доказів, перш ніж їх можна буде використовувати.
Заява про сертифікат
Тепер, коли ми можемо представити твердження в термінах схем, як перевіряльник переконає верифікатор, що доказ дійсний? Для системи PLONK прувер повинен переконати верифікатор у тому, що обмеження воріт і обмеження копіювання виконуються. Для обмежень копіювання це робиться шляхом перевірки перестановки.
Перевірку заміни вперше запропонував Баєр-Грот, а потім розвинув у статті PLONK Габізон, Вільямсон і Чоботару. Щоб довести обмеження воріт, потрібно обчислити певний частковий поліном (поліном частки).
Інтуїтивно зрозуміло, перевірки перестановки показують, що якщо записи обмежень копіювання переставлені, схема залишається незмінною. Перевірка на заміну
Ми говоримо, що вектор a пов’язаний з вектором b перестановкою σ, якщо для всіх i-х позицій b існує позиція σ(i), яка дорівнює a. Ми позначимо це як σ(a)=b. Дано два вектори a=(a,b,...,c), b=(a',b',...,c')$ і перестановку σ, ми хочемо визначити, що σ(a)= b . Це можна зробити наступним чином:
Представте вектори як a'=((a,1),(b,2),...,(c,n)) і b'=((a',σ(1),(b',σ( 2) )),...,(c',σ(n))).Це кодує вектор відносно перестановки σ.
Перепишіть вектор як поліноміальний вектор: a''=((a+1X),(b+2X),...,(c+nX)) і b''=((a'+σ(1)X ), (b'+σ(2)X),..., (c'+σ(n)X))
Перевірити, чи є a'' і b'' еквівалентними як мультимножини, можна здійснити випадковим вибором гами так, що $(a+1X+γ)(b+2X+γ)....(c+nX+γ ) = ( a'+σ(1)X)+γ)(b'+σ(2)X+γ)....(c'+σ(n)X+γ)$.
Вибираючи β навмання, ми можемо перевірити, чи ці поліноми еквівалентні за допомогою леми Шварца-Ціпеля. Множини a'' і b'' еквівалентні як мультимножини, якщо вони еквівалентні як поліноми. Якщо вони не є еквівалентними поліномами, то a'' і b'' не є еквівалентними мультимножинами.
Написано в кінці
Хоча докази з нульовим знанням є складною темою, їх впровадження зростає. У цій статті ми надали інтуїтивно зрозуміле пояснення того, як працюють докази з нульовим знанням. У майбутньому команда CertiK обговорюватиме поглиблене застосування доказів із нульовим знанням і те, як команда може оптимізувати свої схеми для нових випадків використання.
Переглянути оригінал
Контент має виключно довідковий характер і не є запрошенням до участі або пропозицією. Інвестиційні, податкові чи юридичні консультації не надаються. Перегляньте Відмову від відповідальності , щоб дізнатися більше про ризики.
Як бути анонімним, але зберегти транзакцію дійсною Ця стаття допоможе вам зрозуміти докази нульового знання
У складній галузі криптографії докази з нульовим знанням пропонують унікальне рішення, здавалося б, суперечливого завдання: довести знання частини інформації без розкриття самої інформації. У цьому методі шифрування беруть участь дві сторони: підтверджувач і перевіряльник. Мета перевірки полягає в тому, щоб довести, що вони володіють певною інформацією (назвемо її x), не розкриваючи жодних даних про сам x. Про те, що верифікатор дізнається з обміну, це простий факт, що перевіряльник має ці знання. Найголовніше, що верифікатор не має додаткової інформації про x.
Наприклад, коли Сяолін і Сяоші грають у квест, Сяолінг каже Сяолінгу, що зламав пароль певної «скриньки зі скарбами». Але Сяо Лін не бажає прямо ділитися готовою «відповіддю» і не бажає відкривати скриню зі скарбами перед Сяо Теном. Тож як довести Сяо Ши, що він справді розгадав головоломку та знає пароль скрині зі скарбами?
Тож він попросив Сяо Тена написати на аркуші паперу рядок рядків, які знав лише він, одночасно підписати своє ім’я та просунув папір у щілину в скрині зі скарбами.
Потім Сяо Лін відкрив скриньку зі скарбами, вийняв папір, який поклав Сяо Тень, і показав його Сяо Тену. Сяо Тен перевірив, чи правильний рядок і підпис. Це доводить, що Сяо Лін знає пароль скриньки зі скарбами, і цей папірець справді витягли зі скриньки.
Процес дешифрування не був відомий Сяо Тену, і в той же час Сяо Лін довів, що він зламав пароль скриньки зі скарбами.
Доказ нульового знання
У криптографії Доказ нульового знання (Zero Knowledge Proof, також відомий як ZKP) або протокол нульового знання — це метод, який дозволяє перевіряючому перевіряти без розкриття самої інформації чи будь-якої іншої інформації. Верифікатор вірить або доводить, засіб перевірки істинності певного твердження чи твердження.
Доказ із нульовим знанням вперше запропонували професори Массачусетського технологічного інституту Шафі Голдвассер, Сільвіо Мікалі та майстер криптографії Чарльз Рокофф у статті «Складність знань інтерактивних доказів». Ця концепція алгоритму заклала певну основу для сучасної криптографії.
Докази з нульовим знанням мають дві додаткові властивості: короткі та з нульовим знанням. Стислість дозволяє верифікатору прийняти правильність великого обчислення без обчислення самого твердження чи представлення. А нульове знання гарантує відсутність витоку даних про введення.
Докази з нульовим знанням мають вирішальне значення для забезпечення конфіденційності та безпеки багатьох криптографічних протоколів. Вони є запобіжником від можливого витоку інформації, невидимим бронежилетом криптосвіту. Застосування цих знань можна поширити на різні сфери, включаючи технологію блокчейн і безпечні системи автентифікації, де захист конфіденційних даних має першочергове значення.
Широкий спектр застосування
**Блокчейн і технологія шифрування: **Технологія блокчейну, як-от Zcash, використовує докази нульового знання для захисту конфіденційності транзакцій. Людина може довести, що у неї достатньо кіптовалюти для здійснення транзакції, не розкриваючи точну суму своїх коштів. Це забезпечує конфіденційність, одночасно забезпечуючи цілісність транзакцій. **Перевірка особи та автентифікація: **Підтвердження нульової інформації також можна використовувати для підтвердження особи без розкриття непотрібної інформації. Наприклад, особа може підтвердити, що їй вже виповнилося 18 років, не вказуючи точної дати народження, або підтвердити свою особу, не повідомляючи конфіденційних даних, як-от паролів. Це мінімізує ризик викрадення особистих даних або несанкціонованого доступу.
Безпечні багатосторонні обчислення (SMPC): Докази з нульовим знанням можуть сприяти складній взаємодії між декількома сторонами, де кожна сторона може довести, що вона дотримується узгодженого протоколу, не розкриваючи специфіку свого введення. Це дуже ефективно в багатьох аспектах, таких як інтелектуальний аналіз даних із збереженням конфіденційності, безпечні системи голосування тощо. Мережева безпека: Докази з нульовим знанням можуть забезпечувати покращені протоколи безпеки, такі як безпечні політики паролів. Він може перевірити, чи запропонований користувачем пароль відповідає певним стандартам безпеки, не повідомляючи серверу та не записуючи фактичний пароль. Оскільки паролі ніде не зберігаються, потенційні порушення запобігають. **Обмін даними з одночасним захистом конфіденційності: **Доказ нульової інформації можна використовувати, щоб підтвердити, що певні дані відповідають певним вимогам, не розкриваючи самих даних, що особливо важливо в таких сферах, як медичне обслуговування чи фінанси. Положення щодо конфіденційності даних у цих сферах є суворими, але обмін інформацією безпечним способом із збереженням конфіденційності може принести величезні переваги, наприклад, сприяти розвитку медичної кар’єри тощо. Докази з нульовим знанням відкрили нові технічні можливості в блокчейні. Це можна побачити в різних рівнях 2, таких як ZKSync і zkEVM Polygon. Однак це лише підмножина блокчейнів, створених доказами з нульовим знанням.
Як висловити доказ
У цьому розділі та в решті статті ми зосередимося на доказах, створених для систем перевірки на основі PLONK.
PLONK — це система доказів нульового знання, її повна назва:
«Перестановки над базами Лагранжа для всесвітніх неінтерактивних аргументів знання», тобто «Глобальна система доказів неінтерактивного знання на основі баз Лагранжа».
По суті, PLONK — це універсальна, оновлювана система криптографічного підтвердження, інновація, яка дозволяє ефективну перевірку та масштабування в системах блокчейн та інших розподілених мережах. Ідея PLONK полягає в тому, щоб побудувати загальну й оновлювану систему доказів. У контексті систем доказів з нульовим знанням «універсальний» означає, що його можна використовувати для будь-якого типу обчислень; «оновлюваний» означає, що рядок криптографічного посилання (частина даних, яка використовується для створення та перевірки доказів) безпечно оновлюється з часом. .
PLONK виділяється своєю ефективністю та простотою, що робить його популярним вибором для проектів і компаній, яким потрібна безпечна приватна система транзакцій. Порівняно з іншими системами, вона використовує менше обмежень на гейт (основну одиницю обчислення, яку ми разом називаємо «шлюз»), що робить обчислення швидшим і більш масштабованим. Віталік Бутерін опублікував більш повний опис PLONK. [Скопіюйте посилання в браузер, щоб переглянути вихідний текст
довести
Перш ніж доводити твердження, ми спочатку представляємо твердження в термінах схеми. Схема кодує значення в обчисленні разом із двома іншими типами даних:
Для кодування цих даних схеми PLONKish представлені як набір векторів і обмежень. Обмеження – це зв’язки, яким повинні підкорятися одиниці у векторі. Типи обмежень: обмеження воріт і обмеження копіювання, які відповідно представляють операції та порядок операцій у схемі.
Існує багато способів вираження схеми за допомогою різних архітектур воріт і схем.
Уявіть оператор як схему
Припустимо, що у нас є два вентилі: вентиль множення та вентиль додавання. Вентиль множення представлено у вигляді вектора |a|b|c| довжини 3. Якщо цей гейт вибрано, він обмежуватиме c рівним a*b. Аналогічно, вентиль додавання представляється як вектор довжини 3, і якщо вибрано вентиль додавання, c дорівнює a+b. Використовуючи ці вентилі, представимо скалярний добуток між двома векторами (a,b) і (c,d). Для цього нам потрібно виконати наступні обчислення: 1. Використовуйте вентиль множення, щоб обчислити a*b2. Використовуйте вентиль множення, щоб обчислити c*d3. Використовуйте вентиль додавання, щоб обчислити ab+cd. Це можна представити так: вектор.
Зауважте, що вихід першого та другого вентилів множення є вхідним значенням вентиля додавання. Ці дані кодуються окремо від обмежень вентиля в нашій схемі. Це називається обмеженням копіювання. Отже, чому обмеження схеми важливі? Якби не було обмежень, тоді зловмисний валідатор міг би ввести в схему будь-яке значення, яке йому подобається. Наприклад, верифікатор може замінити ab+cd на aba*b. Подібно до смарт-контрактів, обмеження повинні бути перевірені за допомогою системи доказів, перш ніж їх можна буде використовувати.
Заява про сертифікат
Тепер, коли ми можемо представити твердження в термінах схем, як перевіряльник переконає верифікатор, що доказ дійсний? Для системи PLONK прувер повинен переконати верифікатор у тому, що обмеження воріт і обмеження копіювання виконуються. Для обмежень копіювання це робиться шляхом перевірки перестановки.
Перевірку заміни вперше запропонував Баєр-Грот, а потім розвинув у статті PLONK Габізон, Вільямсон і Чоботару. Щоб довести обмеження воріт, потрібно обчислити певний частковий поліном (поліном частки).
Інтуїтивно зрозуміло, перевірки перестановки показують, що якщо записи обмежень копіювання переставлені, схема залишається незмінною. Перевірка на заміну
Ми говоримо, що вектор a пов’язаний з вектором b перестановкою σ, якщо для всіх i-х позицій b існує позиція σ(i), яка дорівнює a. Ми позначимо це як σ(a)=b. Дано два вектори a=(a,b,...,c), b=(a',b',...,c')$ і перестановку σ, ми хочемо визначити, що σ(a)= b . Це можна зробити наступним чином:
Представте вектори як a'=((a,1),(b,2),...,(c,n)) і b'=((a',σ(1),(b',σ( 2) )),...,(c',σ(n))).Це кодує вектор відносно перестановки σ.
Перепишіть вектор як поліноміальний вектор: a''=((a+1X),(b+2X),...,(c+nX)) і b''=((a'+σ(1)X ), (b'+σ(2)X),..., (c'+σ(n)X))
Перевірити, чи є a'' і b'' еквівалентними як мультимножини, можна здійснити випадковим вибором гами так, що $(a+1X+γ)(b+2X+γ)....(c+nX+γ ) = ( a'+σ(1)X)+γ)(b'+σ(2)X+γ)....(c'+σ(n)X+γ)$.
Вибираючи β навмання, ми можемо перевірити, чи ці поліноми еквівалентні за допомогою леми Шварца-Ціпеля. Множини a'' і b'' еквівалентні як мультимножини, якщо вони еквівалентні як поліноми. Якщо вони не є еквівалентними поліномами, то a'' і b'' не є еквівалентними мультимножинами.
Написано в кінці
Хоча докази з нульовим знанням є складною темою, їх впровадження зростає. У цій статті ми надали інтуїтивно зрозуміле пояснення того, як працюють докази з нульовим знанням. У майбутньому команда CertiK обговорюватиме поглиблене застосування доказів із нульовим знанням і те, як команда може оптимізувати свої схеми для нових випадків використання.