Доказательства с нулевым разглашением ZK-STARK: как они работают (zk-Stark V2)

Что такое подтверждение резервов и доказательство с нулевым разглашением

Подтверждение резервов (PoR)

Это процесс, при котором криптовалютные биржи показывают, что у них достаточно активов для покрытия всех балансов клиентов. Так биржи доказывают, что им можно доверять и у них нет скрытых обязательств. Самый простой способ сделать это — опубликовать суммы активов биржи и список балансов пользователей. Вот что гарантирует подтверждение резервов:

• Общая сумма активов пользователей, которая по заявлению OKX есть у биржи, — это сумма общего баланса активов каждого пользователя.

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

• Общий баланс, заявленный биржей, учитывает каждого отдельного пользователя, поэтому каждый пользователь должен иметь возможность проверить включение своего чистого баланса в общую сумму.

Однако раскрытие этих балансов может поставить под угрозу конфиденциальность пользователей. Мы используем метод доказательства с нулевым разглашением (ZKP) для защиты конфиденциальности пользователей.

Доказательство с нулевым разглашением (ZKP)

Это метод безопасности, который позволяет криптовалютной бирже давать гарантии, не раскрывая дополнительной информации.

В этом случае мы доказываем, что у нас достаточно средств, не раскрывая данные конкретных пользователей. Большинство ZKP делятся на две категории:

• zk-SNARK

• zk-STARK

Мы используем ZK-STARK, потому что этот вариант безопаснее и имеет минимальный риск. В этой статье мы расскажем, как используем zk-STARK для защиты конфиденциальности пользователей и доказательства нашей платежеспособности. Прежде чем продолжить, советуем ознакомиться с основными терминами ZKP, такими как схемы, дерево Меркла и обязательства.

Для новичков есть много материалов на эту тему. Продвинутые пользователи могут ознакомиться с курсом MOOC и академической монографией.

Как работает zk-STARK

Мы создаем дерево Меркла, в качестве листьев используя хеш аккаунта каждого пользователя. На каждом аккаунте приведены балансы различных токенов в USD (например, BTC и ETH). Для обработки этих балансов мы разделяем их на неотрицательное количество капитала и долги для каждого токена. Таким образом, мы работаем только с положительными числами, что упрощает обработку расчетов и позволяет избегать ошибок.

Примеры:

• Если у пользователя баланс BTC равен A, то его капитал в BTC равен A, а долг в BTC равен 0.

• Если у пользователя баланс ETH равен -B, то соответствующий капитал равен 0, а долг равен B.

Далее мы создаем дерево Меркла с этими значениями аккаунта в виде листьев. Корень дерева представляет собой единое значение, представляющее все балансы пользователей. Каждый пользователь может доказать, что его аккаунт является частью этого дерева, используя путь Меркла, который показывает, как его аккаунт связан с корнями.

Кроме того, мы публикуем данные общего капитала и долга, суммированные по всем токенам и пользователям. Затем мы создаем доказательство с нулевым разглашением (ZKP), чтобы гарантировать две вещи:

• Доказательств суммы. Стоимость капитала и долга в дереве Меркла суммируются правильно.

• Неотрицательное доказательство. Общий капитал каждого пользователя больше его общего долга.

Когда мы пытаемся проверить дерево Меркла для большого количества аккаунтов, то не можем обработать их за раз. Чтобы решить эту проблему, мы разделяем аккаунты на более мелкие группы. Каждая группа обрабатывается отдельно с помощью групповых схем, которые проверяют нижнюю часть дерева Меркла.

Разделение на группы не только улучшает управление, но и позволяет запускать проверки одновременно (параллельная обработка). После получения результатов из каждой группы мы используем другой уровень схем — рекурсивный, чтобы объединить и проверить все группы вместе, пока не проверим все дерево Меркла.

Что такое групповая схема

Групповая схема включает 1024 аккаунта (acc₀, acc₁,..., acc₁₀₂₃) в качестве входных данных и создает три элемента выходных данных: хеш(h_batch), общий капитал (e_batch) и общий долг (d_batch). Вот что проверяет групповая схема:

• Общий капитал каждого аккаунта в USD больше общего долга.

• e_batch — это сумма значений капиталов всех аккаунтов в USD.

• d_batch — это сумма значений долга всех аккаунтов в USD.

• h_batch — это корень дерева Меркла, созданный с помощью хешей аккаунтов.

• Во время суммирования для не произошло переполнения e_batch и d_batch

Что такое рекурсивная схема

Рекурсивная схема включает 64 различных доказательства (π₀, ..., π₆₃), хеши (h₀, ..., h₆₃), капиталы (e₀, ..., e₆₃₎ и долги (d₀, ..., d₆₃), используя схемы нижнего уровня как входные данные. Она объединяет эти входные данные и создает три элемента выходных данных: новый хеш (h_recursive), общий капитал (e_recursive) и общий долг (d_recursive). Вот что проверяет рекурсивная схема:

• Каждое из 64 подтверждений верное.

• Каждое подтверждение π₀, ..., π₆₃ из схемы нижнего уровня верное.

• e_recursive — это сумма e₀, ..., e₆₃.

• d_recursive — это сумма d₀, ..., d₆₃.

• h_recursive — это хеш цепочки h₀, ..., h₆₃ и так далее.

  • h_recursive = хеш (h₀ || h₁ || ... || h₆₃₎.

• Во время суммирования e_recursive и d_recursive не произошло переполнения.

Какова связь между групповыми и рекурсивными схемами

На изображениях ниже показано, как групповые и рекурсивные схемы связаны и обмениваются данными. Обратите внимание, что на изображении мы дублируем схемы в справочных целях, но в действительности используем только одну схему для каждого уровня.

Наша структура дерева Меркла немного отличается. На нижних 10 уровнях у каждой родительской ноды есть 2 ребенка, а на верхних уровнях — 64 ребенка. Это связано с тем, что групповые схемы обрабатывают нижнюю часть, а рекурсивные — верхнюю. На приведенном ниже изображении используется пример с Алисой, чтобы показать дерево Меркла и ее доказательства Меркла (зеленым цветом).

Чтобы узнать больше технических сведений, например о том, как мы корректируем номера аккаунтов в соответствии с размером группы или выбираем алгоритм хеша, перейдите по ссылке.

Улучшения в zk-PoR версии 2

Вот что улучшено во второй версии zk-PoR по сравнению с предыдущей:

• Повышена эффективность. Текущая версия в 50 раз быстрее предыдущей. Сейчас одной 10-ядерной машине требуется 3 часа, а предыдущая версия справлялась за 36 часов с девятью 64-ядерными машинами. Это происходит из-за использования фреймворка Plonky2, который компилирует схемы с кодом Rust в эффективный машинный язык, а не медленные скрипты Python. Кроме того, мы улучшили Plonky2, чтобы выполнять некоторые вычисления на графических процессорах, сократив время еще на 30%.

• Улучшенный аудит. Во второй версии мы используем высокоуровневую структуру, которая обрабатывает сложные криптографические детали. Это делает наш код более понятным, читаемым и менее подверженным ошибкам.

• Точное доказательство. Размер доказательства второй версии (около 500 КБ) составляет всего 0,05% от того, что было в предыдущей (около 1,2 ГБ). Благодаря рекурсивному методу доказательства можно неоднократно объединять в одно.

Как самостоятельно проверить подтверждение резервов (PoR)

Вот как проверить, включен ли ваш баланс активов в лист Меркла zk-STARK:

1. Войдите в аккаунт OKX и перейдите в раздел Активы. Нажмите Отчеты PoR

2. Выберите Подробнее, чтобы посмотреть данные аудита

   

3. Скопируйте данные, необходимые для самостоятельной проверки, нажав Копировать данные

   

4. После нажатия Копировать данные откройте текстовый редактор (например, «Блокнот»), затем вставьте и сохраните строку JSON в виде файла. Файл должен заканчиваться на _inclusion_proof.json. Строка JSON содержит баланс вашего аккаунта и снимок пути Меркла. Затем сохраните файл в новой папке

5. Откройте текстовый редактор (например, «Блокнот»), затем вставьте и сохраните строку JSON в виде файла. Название файла должно заканчиваться на _inclusion_proof.json. Сохраните файл в новой папке

   • Строка JSON содержит баланс вашего аккаунта и снимок пути Меркла.

   • Текст JSON:

     {"sum_tree_siblings":["9ffb169fecf075e203edca2af65e4c69fa4331d13ac75ccae4cd5b990c91b675","7149661a789763cb61293ebf5d8bdd5570e79ee203738f87a444c79642b89a79","788aac9e392fa62bc3f79c98c7afd7bb41ee7d5bd496876cd0580080f19e002f","e828a44d345e6799e232aabc57cb2b92986ee1c52b65344d83e79d84b4b571b7","6c0675de9cd6b2be1abd6a98260e7ea776492c4aa9aadf31086f23452cb7c48d","2dfe3aadb5ac00ee0b1110ee8c313afdee85d9f9c62904d6ee79c8f02354d80a","5068ae26192587432892a6de8b54ea25a8aafd1c010ab5e67b55b2c30c6257fa","a1bb026ec9f3d8a1fa1b6f498c40ed8b117a57e1af9816d08d9135ab4fe43a60","119dfcd214191405b7f7f7c7091b89196c0cae818bfcd8252a48f20d9cf3c378","4d9403482ca177c669df34a60bb2afab7a18097012d0b70703c8e59258cdfee6"],"recursive_tree_siblings":[{"right_hashes":["e041eaa366259f873e9e1477aac77362f4b1b460c2d5e1c14907fa9288d66cff","b45a8c503e649ff39543a918996b06fc65f4df9b61d071b22f7342f94862c9be","e00ec1225dfe6b7e950f6b9b8e9d1121bf17eb60c444fd7191b861a2ddddad23","c02c12beb73c03f996508cdce7bef927f0aa8b77ebd899f6a75df83de9d4022e","d36b95f14c5fd5bfaf1347e3177340e2fc9475a77b852321b80527132e7d539c","c0b9770178e70a7bba4ac8aeaadab2bcb2ae7f90d0f678bd463f2c42ff4f4a7b","fab5e7c6f7f8bc6d51f515c5db235cc1ebe987adee8c19c9bc7313e9e266d72c","b3884fb88fc95949c78ca8867cfa9e8a3c4c59fa1a48d8371f7fbfbebda0acfd","0c6da9bdbd40065f92ddaa45297670f2f0bffedb74020c5d5752e70d8b507b77","left_hashes":["1101beee3c6a36a168ceee9d43fcf6cb6de7e5c87ed4d22cd0308c9870d17839","d40a8e9eb4c873996ec515600def480eaa9378ca8481a7bcdf5f77725dbec4ae","63b12566ba8473f502386e92d500664cb63683dca6c26593378dcc9715257b77","166440a8ccbfbc1ce6ec5efaf8bc0b25e1bf692fa972e2729e45ce709d1d35a3","724451ad1d937fc47de5ede930d159dce78093d5e6a1f2e698452f8a29b4de3a","081a88f12d4e23173a1bf5038d4a9413cc92dd421c92261065de06492b5010ec","a76dbb1d4c393539b9546f4460d50ebc7582748d7de63c62c463b793c55bac7c","91e6c21de3f4060e1bd864131a570af42de31bbcd84a5afcbbc8fedcbf806002","fad08eca5bfdc5f37d39eabb44c2216afc6498afcb6b913d72586eaaf132a572","d39b06fe28387ba8045e2b2f95e90613916beef4f79df7961514e6e4cbfd07fa","81d07e300a116a0e4fcb56c39715c5fd5921abe8d10329b07c3f33d417b70ca8","7b72a7e62a45c9958a8a55eec2ba47352f2af701bacba098668589f6a3ce0423","8766bc64c38c2bb4188d89de0e732bca103daaed0c779cba9a8b191e24b51c9c","fa57ae4409e46c605f3cbfd01dfd9ccebc86cbd765cdc067206cb9367832442f"]}, ...... "index":9583119,"account":{"id":"50f5f08cc5036e15a541c64ac4ac6d2d9aa8ddab1ec32ed58b10e6ed3edfad59","debt":["0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0"],"equity":["8412384","9386185","45265193","0","0","8751","3824171","2716990","0","313671","28319","0","0","0","41261","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","142353","0","0","0","0","0","4435","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","662","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","993","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","25132","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","305","0","0","0","0","0","0","0","0","6141","0","0","0","0","0","0","0","0","0","0","0","5511","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0"]}}

6. Скачайте инструмент проверки OKX с открытым исходным кодом: zk-STARKValidator

7. Сохраните инструмент проверки OKX с открытым исходным кодом zk-STARKValidator и файл со строкой JSON вместе в новой папке из шага 5. В нашем случае мы помещаем инструмент и файл данных в папку Загрузки с именем proof-of-reserves, как показано ниже

   

8. Откройте zk-STARKValidator. Он автоматически запустит файл JSON, который вы сохранили в папке

9. Проверьте результат.

   • Если проверка пройдена, будет показан результат Проверка ограничения включения пройдена:

     

   • Если проверка не пройдена, будет показан результат Ошибка проверки ограничения включения:

     

Как проверить общий баланс zk-STARK и неотрицательное ограничение

Вот как проверить, что мы действительно храним активы и ни у одного пользователя нет отрицательного чистого капитала:

1. Перейдите на страницу подтверждения резервов и нажмите Отчет об обязательствах

2. Скачайте файл ZK-STARK и сохраните его в новой папке

   

3. Распакуйте файл, чтобы извлечь sum_proof_data.json:

   

4. Скачайте инструмент проверки OKX с открытым исходным кодом: zk-STARKValidator

5. Сохраните инструмент проверки OKX с открытым исходным кодом zk-STARKValidator и файл sum_proof_data.json в новой папке, созданной на шаге 2. В нашем случае мы помещаем инструмент и файл данных в папку Загрузки с именем proof-of-reserves, как показано ниже

   

6. Откройте zk-STARKValidator. Он автоматически запустит файл sum proof data, который вы сохранили в папке

7. Проверьте результат

   • Если проверка пройдена, будет показан результат Проверка общей суммы и неотрицательного ограничения пройдена:

     

   • Если проверка не пройдена, будет показан результат Проверка общей суммы и неотрицательного ограничения не пройдена:

     

Чтобы узнать больше технических деталей, ознакомьтесь с нашей системой подтверждения резервов с открытым исходным кодом. Она доступна просмотра и использования на github.