Zero-Knowledge Proofs: Що таке zk-STARK і як вони працюють?

1. Що це таке?

Система підтвердження резервів (PoR) zk-STARK використовує теорію STARK, складне математичне рішення. zk-STARK означає: Zero-Knowledge Scalable Transparent Argument of Knowledge — технологія криптографічного підтвердження, заснована на [ідеї] Віталіка (https://vitalik.eth.limo/general/2022/11/19/proof_of_solvency.html) стосовно забезпечення цілісності та конфіденційності обчислень на блокчейні. У цій статті ми розповімо, як це працює, і пояснимо загальну математичну концепцію, але якщо вам цікаво вивчити це питання глибше, почніть звідси або звідси.

Як це працює?

Рис. 1. Таблиця трасування виконання та дерево Меркла, створені для zk-STARK PoR

Крок 1: будівельні обмеження

Щоб довести відповідальність нашої біржі, ми висуваємо три заяви:

Заява 1: Ми правильно накопичили значення кожного користувача, включаючи вартість кожної криптовалюти та чисту вартість кожного користувача

Заява 2: Біржа не фальсифікує віртуальних користувачів, чия чиста вартість є від’ємною, щоб зменшити свої сукупні зобов’язання (окремий користувач із від’ємним балансом є прийнятним, лише якщо його/її чиста вартість перевищує 0)

Заява 3: Загальна вартість, яку заявляє біржа, відноситься до кожного окремого користувача, тому кожен користувач повинен мати можливість перевірити включення своєї чистої вартості до загальної вартості

Щоб перевірити та підтвердити вищенаведені твердження, нам потрібно створити такі обмеження:

Заява 1: Обмеження загального балансу (Обмеження правильного загального балансу)

uts: розмір трасування користувача, який є кількістю рядків трасувань, включених до даних кожного користувача.

сума: загальний баланс користувача

N: кількість користувачів

Заява 2: Невід’ємне обмеження (Обмеження позитивного чистого капіталу)

Заява 3: Обмеження включення (Обмеження включення всього балансу акаунта клієнта)

Відповідно до вищенаведених обмежень ми створюємо таблицю трасування, щоб фіксувати та перевіряти загальні залишки та невід’ємність за допомогою вибіркових перевірок. Ось як будується таблиця трасування (для простого прикладу, 3 користувачів, максимальне значення в USD менше ніж 4^6 = 4096):

1）Ми формуємо таблицю з 32 рядків і 5 стовпців і заповнюємо значення та ID користувача в рядок, де k % 8 = 6, і . Кожні 8 рядків є блоком, інформація про активи користувача тепер доступна  наприкінці кожного блоку. Першому користувачеві надається віртуальний баланс 0, тому ми можемо опублікувати його, щоб довести, що накопичення вартості не починається з від’ємного значення.

2）Ми накопичуємо значення активів користувача одне за одним і заповнюємо результат  у рядки, де k % 8 = 7, і , які є останніми рядками кожного блоку

3）Ми постійно ділимо загальну вартість кожного користувача на 4 рядок за рядком  з кінця кожного блоку. Ми робимо це, щоб чиста вартість користувача була невід’ємною, перевіряючи, чи перші рядки є нульовими для кожного блоку. Якщо хтось має від’ємне чисте значення, перший рядок його блоку не буде нульовим, оскільки від’ємне значення (-x) виявиться (p - x) у кінцевому полі , що є дуже великим додатним значенням.

4）Ми вводимо випадкові числа для кожного користувача та заповнюємо порожні місця в таблиці 0

Крок 2: Розширення полінома низького ступеня Використовуючи наведені вище поліноміальні обмеження, ми можемо отримати обчислювальний поліном довжини uts * N. З міркувань безпеки ми виконуємо прив’язку до полінома на більшій області оцінки, з коефіцієнтом посилення домену як коефіцієнт_розширення.

У вищенаведеному випадку ми могли б обчислити поліном p(x) від I(x). Коли ми використовуємо коефіцієнт_розширення 8, ми обчислимо ще 32(8-1)* точки на p(x).

Оскільки два різних полінома зі степенем D мають не більше D спільних точок, приклад пари поліномів з дійсним поліномом (який задовольняє вищевказані обмеження) та хибним поліномом зі степенем D (який не задовольняє вищевказані обмеження) матиме не більше D спільних точок. Це означає, що хибний поліном має шанс  пройти вибіркову перевірку. Якщо ми зробимо вибіркову перевірку n разів, шанс зменшиться до .

Ми реалізуємо коефіцієнт_розширення за замовчуванням 16 і час перевірки вибірки за замовчуванням як 16, тому рівень безпеки становитиме 80 біт.

Крок 3: зобов’язання полінома Ми обчислюємо хеш-значення трасування обчислень та відповідний баланс користувача, ідентифікатор користувача та значення відповідного полінома обмеження для кожного рядка та генеруємо дерево Меркла. Корінь Меркла — це значення зобов'язання полінома.

Крок 4: генерація підтвердження вибірки Використовуючи корінь Меркла як випадкове джерело, ми робимо вибірку даних. Щоб уникнути витоку даних трасування обчислень, ми уникаємо даних з індексом *k ** коефіцієнт_розширення під час вибірки та генеруємо шлях підтвердження Меркла, що відповідає індексу вибірки.

Ми виконуємо вибіркові перевірки, щоб перевірити, чи введений поліном є дійсним, який задовольняє обмеження, перелічені на кроці 1. Як зазначено на кроці 2, час вибіркової перевірки впливатиме на ймовірність втручання або маніпуляцій.

Крок 5: створення підтвердження низького ступеня

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

Наприклад, якщо ми хочемо довести, що p0(x), p1(x) і p2(x) не перевищують D рівнів, ми можемо створити 2 випадкові коефіцієнти з кореня Меркла, згенерованого на кроці 3, і обчислити лінійний поліном l(x) як:

k0 = хеш (корінь + "0")
k1 = хеш (корінь + "1")
l(x) = k0 * p0(x) + k1 * p1(x) + p2(x)

Якщо можна було б довести, що рівень l(x) не перевищує D, то ймовірність того, що рівень будь-якого з p0(x), p1(x) і p2(x) буде більшим за D і буде близьким до 0

Крок 6: перевірка загального балансу По-перше, ми перевіряємо підтвердження низького ступеня, створений на кроці 5.

Потім виконується подальша відкрита перевірка вибіркових даних, згенерованих на кроці 4. По-перше, щоб перевірити, що дані узгоджуються з поліноміальним зобов’язанням, а по-друге, щоб перевірити, що дані задовольняють обмеженням, створеним на кроці 1. Нарешті, перевіряються коефіцієнти комбінації тестового полінома низького ступеня.

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

Крок 8: перевірка користувачем підтвердження включення Користувач перевіряє свій баланс, ID, обчислює хеш-значення даних, що відповідають його індексу, і перевіряє хеш-значення на листковому вузлі дерева Меркла за допомогою наданого шляху Меркла.

2. Як виконати самоперевірку підтвердження резервів (PoR)?

2.1 Перевірте обмеження включення zk-STARK

Теорія перевірки

Дотримуючись процедури STARK, ми обчислимо таблицю трасування виконання всіх активів користувача, як показано нижче, і хешуємо інформацію кожного користувача як таблицю трасування, яка стає листком дерева Меркла, а потім зафіксуємо листки в корені Меркла, який буде опубліковано під час кожного аудиторського раунду PoR.

Щоб перевірити, чи ваші активи включено в корінь, ми надамо вам шлях Меркла для перевірки. Ви можете спочатку обчислити свій листок, хешуючи інформацію про активи, а потім перевірити, чи є ваш листок дійсним листком у дереві Меркла та корені, які ми публікуємо.

Наприклад, на рисунку 1 користувач з ідентифікатором id_k обчислює hashk = hash(«20» + «15» + «5» + «id_k» + «99821»), а інші дані в рамці червоного квадрата будуть перевіркою шляху Меркла. Для перевірки користувачам надається інструмент із відкритим кодом.

Оскільки листя дерева Меркла є хешами, жодна ваша особиста інформація не буде передана іншим.

Як перевірити:

1）Щоб перевірити, чи баланс активів вашого акаунта було включено як листок zk-STARK Merkle, увійдіть до свого акаунту OKX, відвідайте «Аудити», щоб переглянути останні аудити, натисніть «Деталі», щоб переглянути дані аудиту.

2）Отримайте дані, необхідні для ручної перевірки, натиснувши «Копіювати дані».

3）Натиснувши «Копіювати дані», відкрийте текстовий редактор (наприклад, блокнот), а потім вставте та збережіть рядок JSON як файл. Файл повинен закінчуватися назвою «_inclusion_proof.json». Рядок JSON містить баланс вашого акаунту та знімок шляху Меркла, а потім зберігає файл у новій папці.

Текст JSON показано нижче:

{
"batch_inclusion_proof": {
"batch_mtree_root": "34d4e17e0071f180736bae075f632845ded76262d19970c47cabb8d88046e9c5",
"user_id": "47db1d296a7c146eab653591583a9a4873c626d8de47ae11393edd153e40f1ed",
"total_value": 138312291,
"BTC": 2152907,
"ETH": 909757,
"USDT": 2319557,
"random_number": "e7b7a5a6fdba87a58559aed4fca66fb63d3d9395ce0d51bda40fcd35893391ac",
"merkle_path": [
"5e3dd0ad776b15743076405d53e12af8fdac85c446bcc6c2eb8cab0e0e0c24f9",
"9dd5fcb0f3835b10772a7baabe7a074ed0b6947f7284e2d7ce5a84c3b5b394da",
"973186c5ea69bdc06c0c786cfae76173a89e0989bd759e1b2c37fdd317c70fe2",
"0c7ea3dd9bc0a15019b9ace6cf003befa31133ee84728d21bf67aa984ef1b60a",
"2adf4a58ccec7a44ed3a3f8bd365c61eac7d25c55524e69a31c6665769b7962a",
"4cddf667adbfa51e1b999e39a2009dcc9786385d9f3e240919f763e4db6f3609",
"4e841f9b5c2641759572fdfaf66c518b191e89b7a4745f179c046fef1eb9c374",
"cc12d77e7d13ee3c57064697dfef230064efaaf5b6ccf22a5ef5b7a2602632ab",
"ead6745e91b88021aeecddd8d014ea26ba26f42c4d5286ef8e196085d3757f62",
"1a583279e243ddc0a36bf870b5af70f2e52f059faeb5f3757d0d1903770371e8",
"5c1729384a2f2c8c434f3b34e99d6152aab42093c4f68aab638eaa212e799933",
"e154c1011883b2cea377c6bc820a21ac01d9d792ce3e1f376f35c1b29df04167"
]
},
"trunk_inclusion_proof": {
"trunk_mtree_root": "9b61d44f4f3de6b284d95a844dee9327d5e2091ac7e6b6f67ca10bd866617290",
"batch_id": "34d4e17e0071f180736bae075f632845ded76262d19970c47cabb8d88046e9c5",
"total_value": 2007657936,
"BTC": 18915744,
"ETH": 21522734,
"USDT": 21268768,
"random_number": "c93d3517d691564f3cc8e1eee6634ba7e0f59125aa89cd6984677459ac5f8164",
"merkle_path": [
"1082ec62ad0bd2b2b2c38a08f4b0de2f9aa77b387c611b927d203deb9bc97376",
"a57a391c137877993cd61ca4ad57bb1754bf8776fd207e630c362b8560fbb34b",
"413cba43d7f7236b5ce21fe951583660277507250ecbabca6a1ac6e9ac66bb5b",
"d87e2c64c34700195e322967ebbbb282810671320d083029fb9e46f92474d47b",
"85438a308f8d668779dbdb462437434f8f9d551229e8ebb2235605fe18cf97f6",
"d1cbf91c33b4cb0366877c4c805548401887f2a428c7297d0c4d97fa0f936cec",
"147fccf20ff7010d2ba162333f62200dce116d337230ee73f7c8bc2abcba148e",
"0901034401e6b6fa7de911d658ebc9b10c6a64c16a5450a22e390859ae87e1c4",
"b2e3525d853749ca2edfa718cd4f12ba26a0f645dfb0d5512d42c67fc74d0a1a",
"ad34d5acf98f7e6234d132d578f823e7bd8410d1850db76a55dd794ce388b2c2",
"7e81326a45550eea02398a8459dbd5d73d6d90b58268ce4453231cf3077f4fdf",
"239263d4cf31258c7910fe7abe8cc23d1b71cf73e796a958e60d3fafe095e49d",
"bb44ebaed47333c967f79c48cb3e0106fe64f55411f94181daa4c55f2a563e43"
]
}
}

4）Завантажте інструмент перевірки OKX з відкритим кодом zk-STARKValidator

5）Збережіть інструмент перевірки з відкритим кодом OKX zk-STARKValidatorі файл рядка JSON разом у новій папці з кроку 3. У нашому випадку: ми помістили інструмент, а також файл даних у папку «Завантаження» під назвою «proof-of-reserves», як показано нижче:

6）Відкрийте zk-STARKValidator, він автоматично запустить файл рядка JSON, який ви зберегли в папці.

7）Перевірте результат

• Якщо перевірку пройдено, буде показано результат «Перевірка обмеження включення пройдена»:

  

• Якщо перевірка не вдалася, буде показано результат «Перевірка обмеження включення не пройдена»:

  

2.2 Перевірте загальний баланс і невід’ємне обмеження zk-STARK

Як перевірити:

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

Розпакуйте завантажений файл, і з’явиться папка «sum proof data», яка містить тисячі папок-гілок й одну папку-стовбур. Кожна папка містить два файли JSON із назвою "sum_proof.json" і "sum_value.json".

Завантажте інструмент перевірки OKX з відкритим кодом zk-STARKValidator

Збережіть інструмент перевірки з відкритим кодом OKXzk-STARKValidator і папку «sum proof data» разом у новоствореній папці з кроку 1. У нашому випадку: ми помістили інструмент і файл даних у папку «Downloads» під назвою «proof-of-reserves», як показано нижче:

Відкрийте zk-STARKValidator, він автоматично запустить файл «sum proof data», який ви зберегли в папці.

Перевірте результат.

Якщо перевірку пройдено, буде показано результат «Перевірку загальної суми та невід’ємного обмеження пройдено»:

Якщо перевірка не пройдена, буде показано результат «Total sum and non-negative constraint validation failed»: