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

Що таке zk-SNARK?

Уявіть, що у вас є публічний вхід x, приватний вхід w і (відкрита) функція f(x,w) → {True,False}, яка перевіряє вхідні дані. За допомогою zk-SNARK можна довести, що вони знають aw, так що для заданих f і x f(x,w) = True, і все це не розкриваючи, що таке w насправді. Крім того, верифікатори можуть перевірити справжність доказу набагато швидше, ніж вони могли б обчислити f(x,w), навіть якби вони знали w.

Це наділяє zk-SNARK двома атрибутами: конфіденційністю та масштабованістю. Як згадувалося, наші приклади в цій статті в основному зосереджені на аспекті конфіденційності.

Підтвердження членства

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

Особисте введення (w): ваша адреса A, закритий ключ вашої адреси k

Загальнодоступний вхід (x): набір адрес усіх перевірених профілів доказу людськості {H1…Hn}

Функція перевірки f(x,w):

Інтерпретувати w як пару (A, σ) і x як дійсний список профілів {H1…Hn}

Переконайтеся, що A є однією з адрес у {H1…Hn}

Підтвердьте privtoaddr(k) = A

Якщо обидві перевірки пройдено, поверніть True. Якщо будь-який із них не вдається, поверніть False.

Проверник генерує їх адресу A та відповідний ключ k, надаючи w=(A,k) як приватний вхід для f. Вони отримують загальнодоступні дані, які є поточним набором перевірених профілів доказу людськості {H1…Hn}, з ланцюга. Потім вони запускають алгоритм підтвердження zk-SNARK, який (за умови, що вхідні дані правильні) створює підтвердження. Це підтвердження надсилається верифікатору разом із висотою блоку, з якого вони отримали список перевірених профілів.

Верифікатор також зчитує ланцюжок, отримуючи список {H1…Hn} із заданої висоти перевірником, і перевіряє підтвердження. Якщо верифікація пройшла успішно, верифікатор вважає, що прувер володіє перевіреним профілем доказу людськості.

Перш ніж заглиблюватися в більш складні приклади, я наполегливо рекомендую повністю зрозуміти наведений вище приклад.

Робимо докази членства більш ефективними

Одним із недоліків вищезгаданої системи перевірки є те, що верифікатор повинен знати про весь набір профілів {H1…Hn}, що потребує O(n) часу, щоб «ввести» цей набір у механізм zk-SNARK. Цю проблему можна вирішити, використовуючи в ланцюжку корінь Merkle, який охоплює всі профілі, як загальнодоступний вхід (потенційно лише корінь стану). Ми додаємо ще один приватний вхід, доказ Merkle M, який підтверджує, що обліковий запис перевірника A знаходиться у відповідній частині дерева.

Найновішою та більш ефективною альтернативою доказам Merkle для доказів членства в ZK є Caulk. У майбутньому деякі з цих випадків використання можуть перейти до рішень, подібних до Caulk.

ZK-SNARK і монети

Такі проекти, як Zcash і Tornado.cash, дозволяють нам мати валюти, які захищають конфіденційність. Тепер можна подумати, що вони можуть використати згадані «докази людини ZK», але мова не йде про підтвердження доступу до доказів профілю людини; мова йде про підтвердження доступу до монет. Тут виникає проблема: ми повинні одночасно подбати про конфіденційність і подвійні витрати. Тобто ми не повинні витрачати ту саму монету двічі.

Ось як ми це вирішуємо: кожен, хто володіє монетою, має приватний секрет «s». Вони локально обчислюють «листок» L=hash(s,1), який публікується в ланцюжку, стаючи частиною стану N=hash(s,2), який ми називаємо нуліфікатором. Стан зберігається в дереві Меркла.

Щоб витратити монету, відправник повинен надати ZK-SNARK, де:

• Загальнодоступні вхідні дані включають нуліфікатор N, поточний або останній корінь Merkle R і новий аркуш L' (призначений для одержувача, який має секрет s', переданий відправнику як L'=hash(s',1)).

• Приватні вхідні дані містять секрет s, лист L і гілку Merkle M.

Функція перевірки перевіряє:

• M — дійсна гілка Меркла, що доводить, що L — аркуш дерева, що має коріння в R, де R — корінь Меркла поточного стану.

• hash(s,1)=L і hash(s,2)=N.

Транзакція містить нуліфікатор N і новий лист L'. Насправді ми нічого не доводимо про L', але це «підмішано» в доказ, щоб запобігти зміні третіми сторонами під час транзакції. Щоб перевірити транзакцію, ланцюжок перевіряє ZK-SNARK і перевіряє, чи N використовувався в попередніх транзакціях. У разі успіху N додається до набору витрачених нуліфікаторів, що знову робить його непридатним для використання. L' додається до дерева Merkle.

Використовуючи ZK-SNARK, ми пов’язуємо два значення: L (з’являється в ланцюжку під час карбування монети) і N (з’являється після витраченого), не розкриваючи, який L з яким N пов’язаний. Зв’язок між L і N помітний лише тоді, коли ви знати секрети, які їх породжують. Кожну відкарбовану монету можна використати один раз (оскільки для кожного L є лише один дійсний N), але конкретна монета, використана в будь-який час, залишається прихованою.

Це критично важливий примітив для розуміння. Багато механізмів, які ми описуємо нижче, засновані на цьому, хоча і з різними цілями.

Монети з довільним балансом

Вищесказане можна легко поширити на монети з довільним балансом. Ми підтримуємо концепцію «монети», але кожна монета має (приватний) баланс. Простий спосіб досягти цього полягає в тому, щоб кожна монета мала ланцюгове сховище не лише з листком L, але й із зашифрованим балансом. Кожна транзакція споживала б дві монети та створювала дві нові, додаючи дві пари (лист, зашифрований баланс) до стану. ZK-SNARK також перевіряє, що сума вхідних балансів дорівнює сумі вихідних балансів, і обидва вихідні баланси є невід’ємними.

ЗК Антивідмова в обслуговуванні

Інтригуючий інструмент для боротьби з DOS: уявіть, що у вас є ідентифікатор у мережі, який нелегко створити; це може бути безпечний профіль або 32 валідатори ETH, або просто обліковий запис з ненульовим балансом ETH. Ми могли б створити більш стійку до DOS однорангову мережу, приймаючи лише ті повідомлення, які підтверджують наявність у відправника профілю. Кожному профілю буде дозволено до 1000 повідомлень на годину. Якщо відправник обманює, його профіль видаляється зі списку. Але як ми забезпечуємо конфіденційність?

По-перше, налаштування: нехай k буде закритим ключем користувача, а A=privtoaddr(k) відповідна адреса. Список дійсних адрес є загальнодоступним (наприклад, реєстр у мережі). Поки що це віддзеркалює приклад, перевірений людиною: ви повинні довести, що володієте закритим ключем до адреси, не повідомляючи, який саме. Але ми не просто хочемо підтвердити, що ви в списку. Нам потрібен протокол, який дозволить вам довести, що ви в списку, але обмежує ваші докази.

Ми розділимо час на періоди: кожен триває 3,6 секунди (що становить 1000 періодів на годину). Наша мета — дозволити кожному користувачеві надсилати лише одне повідомлення за період; якщо вони надішлють два в той самий період, їх спіймають. Щоб дозволити випадкові спалахи, вони можуть використовувати останні періоди. Отже, якщо користувач має 500 невикористаних періодів, він може надіслати 500 повідомлень одночасно.

Протокол

Почнемо з базової версії з використанням нуліфікаторів. Користувач генерує нуліфікатор із (N = \text{hash}(k, e)), де (k) — його ключ, а (e) — номер епохи, а потім публікує його з повідомленням (m). Потім ZK-SNARK затьмарює (\text{hash}(m)). У цьому процесі нічого про (m) не перевіряється, таким чином прив’язуючи доказ до одного повідомлення. Якщо користувач прив’язує два докази до двох різних повідомлень, використовуючи той самий нуліфікатор, він ризикує бути спійманим.

Тепер переходимо до більш складної версії. У цьому сценарії наступний протокол розкриває їхній закритий ключ, а не просто підтверджує, чи хтось використав ту саму епоху двічі. Наша головна техніка базується на принципі, що «дві точки визначають лінію». Виявлення однієї точки на лінії мало що розкриває, а виявлення двох точок відкриває всю лінію.

Для кожної епохи (e) ми вибираємо лінію (L_e(x) = \text{hash}(k, e) \times x + k). Нахил лінії дорівнює (\text{hash}(k, e)), а точка перетину y — (k), обидва невідомі. Щоб створити сертифікат для повідомлення (m), відправник надає (y = L_e(\text{hash}(m)) = \text{hash}(k, e) \times \text{hash}(m) + k ), разом із доказом ZK-SNARK, що обчислення (y) є точним.

Підсумовуючи, ZK-SNARK виглядає наступним чином:

Публічні дані:

• ({A_1…A_n}): список дійсних облікових записів

• (M): повідомлення перевіряється сертифікатом

• (E): номер епохи для сертифіката

• (Y): Оцінка лінійної функції

Приватний вхід:

• (K): Ваш закритий ключ

Функція перевірки:

• Перевірте, чи існує (\text{privtoaddr}(k)) у ({A_1…A_n})

• Підтвердити (y = \text{hash}(k, e) \times \text{hash}(m) + k)

Але що, якщо хтось використає епоху двічі? Вони відкриють два значення (m_1) і (m_2) разом із значеннями сертифікатів (y_1 = \text{hash}(k, e) \times \text{hash}(m_1) + k) і (y_2 = \text{hash}(k, e) \times \text{hash}(m_2) + k). Потім ми можемо використати ці дві точки, щоб відновити лінію та згодом точку перехоплення у, яка є закритим ключем.

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

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

Негативна репутація ЗК

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

Система репутації може обслуговувати позитивну чи негативну репутацію; однак пристосування до негативної репутації вимагає додаткової інфраструктури. Це вимагає від користувачів включати всі дані про репутацію у свої докази, навіть якщо вони негативні. Ми в першу чергу зосередимося на цьому складному випадку використання, схожому на те, що Unirep Social прагне реалізувати.

Пов’язана публікація: базові знання

Будь-хто може опублікувати, передавши повідомлення в ланцюжку, що містить пост, супроводжуючи ZK-SNARK. Цей ZK-SNARK є доказом того, що (i) ви володієте унікальною зовнішньою ідентифікацією, яка надає вам дозвіл на створення облікового запису, або (ii) ви раніше публікували певні публікації. Зокрема, ZK-SNARK працює наступним чином:

Публічні дані:

• Нуліфікатор, Н

• Останній корінь стану блокчейну, R

• Вміст публікації («змішаний» із доказом, щоб зв’язати його з публікацією, без будь-яких обчислень на ньому)

Приватні дані:

• Ваш закритий ключ, k

• Зовнішній ідентифікатор (адреса A) або нуліфікатор Nprev, використаний у попередній публікації

• Доказ Меркла, M, що ланцюг містить A або Nprev

• i-й допис, який ви опублікували за допомогою цього облікового запису

Функція перевірки:

1. Підтвердьте, що M є дійсною гілкою Merkle, довівши, що (A або Nprev, залежно від того, що надано) є листом дерева з коренем R.

2. Перевірте N = enc(i, k), де enc — функція шифрування (наприклад, AES).

3. Якщо i=0, перевірте A=privtoaddr(k), інакше перевірте Nprev=enc(i−1,k).

Окрім перевірки доказів, ланцюжок також перевіряє (i) чи R насправді є недавнім коренем стану, і (ii) що нуліфікатор N не використовувався раніше. До цього моменту він нагадує раніше описані монети для збереження конфіденційності, але ми додали процес «карбування» нових облікових записів і видалили можливість «надсилати» ваш обліковий запис іншим ключам. Натомість усі нуліфікатори генеруються за допомогою оригінального ключа. Ми використовуємо enc тут, щоб зробити нуліфікатор оборотним. Якщо у вас є ключ k, ви можете розшифрувати будь-який конкретний нуліфікатор у ланцюжку; якщо результат є дійсним індексом, а не випадковою тарабарщиною (наприклад, ми можемо просто перевірити dec(N) < 2^64), ви б знали, що нуліфікатор було згенеровано за допомогою ключа k.

Додавання репутації:

У цій схемі репутація є локальною та явною. У деяких смарт-контрактах є метод під назвою addReputation, який приймає як вхідні дані нуліфікатор, що вивільняється разом із публікацією, і кількість одиниць репутації, які потрібно додати або відняти.

Ми розширили дані, що зберігаються в ланцюжку для кожної публікації. Замість того, щоб зберігати лише обнулювач N, ми зберігаємо {N, h¯, u¯} , де:

• h¯ = hash(h, r), де h представляє висоту блоку кореня стану, на який посилається в доказі.

• u¯ = hash(u, r), де u — рейтинг репутації облікового запису (починаючи з 0 для нових облікових записів).

R тут випадкове значення, додане для запобігання пошуку h і u шляхом грубого пошуку. З точки зору криптографії, додавання R робить хеш прихованим зобов’язанням.

Припустімо, що публікація використовує root R і зберігає {N, h¯, u¯}. У своєму доказі він посилається на попередню публікацію, у якій зберігаються дані {Nprev, h¯prev, u¯prev}. Підтвердження допису також має проходити через усі записи репутації, розміщені між hprev та h. Для кожного нуліфікатора N функція перевірки розшифровує N за допомогою ключа користувача k. Якщо дешифрування видає дійсний індекс, воно застосовує оновлення репутації. Якщо загальна сума всіх оновлень репутації дорівнює δ, то це доводить, що u = uprev + δ.

Якщо ми хочемо застосувати правило «три попередження, і ти вилетів», ZK-SNARK також забезпечить u > -3. Якщо нам потрібно правило, за яким допис із репутацією ≥ 100 отримує спеціальний тег «допис із високою репутацією», це теж можна зробити.

Щоб підвищити масштабованість цієї системи, ми можемо розділити її на два типи повідомлень: повідомлення та RCA. Публікація буде поза ланцюжком, хоча вона потребує вказівки на RCA, зроблену минулого тижня. RCA будуть у ланцюжку, проходячи всі оновлення репутації з часу попереднього RCA видавця. Таким чином, навантаження на мережу зменшується до однієї транзакції на публікацію на тиждень, плюс одна транзакція на кожне повідомлення про репутацію.

Притягнення до відповідальності централізованих сторін

Іноді виникає необхідність розробити систему з централізованим «оператором». Причини для цього можуть бути різними: іноді це пов’язано з масштабованістю, а іноді – з метою конфіденційності, особливо конфіденційності даних, які зберігаються оператором. Наприклад, стійка до примусу система голосування MACI вимагає від виборців подавати свої голоси в ланцюжку, зашифровані за допомогою ключа, який зберігається централізованим оператором. Цей оператор розшифровує всі голоси в ланцюжку, підраховує їх і відображає остаточний результат. Вони використовують ZK-SNARK, щоб довести, що все, що вони зробили, було правильним. Ця додаткова складність має вирішальне значення для забезпечення надійної конфіденційності (відомої як примусовий опір): користувачі не можуть довести нікому, як вони проголосували, навіть якби хотіли. Завдяки блокчейну та ZK-SNARK рівень нашої довіри до оператора залишається мінімальним. Зловмисники можуть подолати примусовий опір, але оскільки голоси публікуються в блокчейні, вони не можуть обманювати шляхом цензури голосів. А оскільки вони повинні надати ЗК-СНАРК, вони не можуть обманювати, неправильно обчислюючи результати.

Поєднання ZK-SNARK з MPC

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

Що ми не можемо зробити приватним?

ZK-SNARK дуже ефективний у створенні систем, де користувачі мають приватні стани. Однак він не може підтримувати державу як приватну, про яку ніхто не знає. Щоб інформація була доведена, перевіряючий повинен знати її у відкритому вигляді. Uniswap є прикладом, який важко приватизувати. У Uniswap є центральна логічна «сутність» – рахунок постачальника ліквідності, який нікому не належить, і всі транзакції Uniswap відбуваються з цим обліковим записом. Ви не можете приховати стан цього облікового запису, оскільки хтось повинен зберігати цей стан у відкритому вигляді, щоб підтвердити це, і кожна транзакція вимагатиме їх активної участі. Ви можете використовувати спотворені схеми ZK-SNARK, щоб створити централізовану, безпечну, приватну версію Uniswap, але незрозуміло, чи переваги переважать витрати. Це може навіть не принести жодних реальних переваг: контракти повинні інформувати користувачів про ціни на активи, а зміна цін за блок може виявити активність транзакцій. Блокчейни можуть глобалізувати інформацію про стан, а ZK-SNARK можуть її приватизувати, але немає надійного методу глобалізації та приватизації інформації про стан одночасно.

Складання примітивів разом

У наведених вище розділах ми бачили приклади інструментів, які є потужними самі по собі, але також можуть служити будівельними блоками для інших програм. Нуліфікатори, життєво важливі для валют, тепер знову з’являються в інших випадках використання. Техніка «примусового зв’язування», яка використовується в розділі про негативну репутацію, має широке застосування. Це дуже ефективно для багатьох програм, де «профіль» користувача змінюється з часом складним чином, і ви хочете змусити користувачів дотримуватися системних правил, зберігаючи конфіденційність. Користувачам навіть можна доручити представити свій внутрішній «стан» за допомогою повного приватного дерева Merkle. Згаданий інструмент «пул зобов’язань» можна створити за допомогою ZK-SNARK. Якщо певні додатки не можуть повністю функціонувати в ланцюжку і потребують централізованого оператора, ті самі методи можуть зберегти оператора чесним. ZK-SNARK є потужним інструментом, який поєднує переваги підзвітності та конфіденційності. Хоча вони мають свої обмеження, у деяких випадках розумні розробки програм можуть обійти ці обмеження. Я сподіваюся, що найближчими роками більше додатків приймуть ZK-SNARK і, зрештою, створять програми, які поєднуватимуть ZK-SNARK з іншими формами шифрування.

Відмова від відповідальності:

1. Цю статтю передруковано з [Foresightnews]. Усі авторські права належать оригінальному автору [Jacob Ko]. Якщо є заперечення щодо цього передруку, будь ласка, зв’яжіться з командою Gate Learn, і вони негайно розглянуть це.
2. Відмова від відповідальності: погляди та думки, висловлені в цій статті, належать виключно автору та не є жодною інвестиційною порадою.
3. Переклади статті на інші мови виконує команда Gate Learn. Якщо не зазначено вище, копіювання, розповсюдження або плагіат перекладених статей заборонено.