Доказательства с нулевым разглашением: что такое zk-STARK и он работает?

Опубликовано 10 мая 2023 г.Обновлено 21 мая 2024 г.7 мин на чтение121

1. Что это такое?

Система zk-STARK Proof of Reserves (PoR) использует теорию STARK, которая представляет собой сложное математическое решение. zk-STARK означает «Масштабируемый прозрачный аргумент знаний с нулевым разглашением». Это технология криптографического доказательства, основанная на идее Виталика Бутерина для обеспечения целостности и конфиденциальности вычислений в блокчейнах. В этой статье мы расскажем, как это работает, и объясним общую математическую концепцию. Однако, если вы хотите углубиться в эту тему, начните здесь или здесь.

Как это работает?

zero-knowledge-proofs-what-are-zk-starks-and-how-do-they-work image 1

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

Шаг 1: создание ограничений

Для подтверждения обязательств нашей биржи мы выдвигаем три следующих утверждения:

Утверждение 1: мы верно аккумулировали активы каждого пользователя, включая стоимость каждой криптовалюты и чистый баланс каждого пользователя

Утверждение 2: биржа не подделала виртуального пользователя с отрицательной чистой стоимостью, чтобы уменьшить общую сумму обязательств (индивидуальный пользователь с отрицательным балансом допустим только в том случае, если его/ее чистая стоимость выше 0)

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

Чтобы проверить и подтвердить приведенные выше утверждения, нам нужно создать такие ограничения, как:

Утверждение 1: ограничение общего баланса (Ограничение верного общего баланса)

zero-knowledge-proofs-what-are-zk-starks-and-how-do-they-work image 2

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

sum: общий баланс пользователя

N: количество пользователей

Утверждение 2: неотрицательное ограничение (Ограничение положительного чистого капитала)

zero-knowledge-proofs-what-are-zk-starks-and-how-do-they-work image 3

Утверждение 3: ограничение на включение (Ограничение на включение всего баланса аккаунта клиента)

zero-knowledge-proofs-what-are-zk-starks-and-how-do-they-work image 4

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

1)Мы создаем таблицу с 32 строками и 5 столбцами и заполняем пользовательские значения и идентификаторы в ряд

zero-knowledge-proofs-what-are-zk-starks-and-how-do-they-work image 5

, где k % 8 = 6 и

zero-knowledge-proofs-what-are-zk-starks-and-how-do-they-work image 6

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

zero-knowledge-proofs-what-are-zk-starks-and-how-do-they-work image 7

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

zero-knowledge-proofs-what-are-zk-starks-and-how-do-they-work image 8

2. Мы аккумулируем суммы пользовательских активов одну за другой и заносим результат в строки

zero-knowledge-proofs-what-are-zk-starks-and-how-do-they-work image 9

, где k % 8 = 7 и

zero-knowledge-proofs-what-are-zk-starks-and-how-do-they-work image 10

, которые являются последними строками каждого блока

zero-knowledge-proofs-what-are-zk-starks-and-how-do-they-work image 11

3. Мы продолжаем делить общее значение каждого пользователя на 4 построчно от

zero-knowledge-proofs-what-are-zk-starks-and-how-do-they-work image 12

с конца каждого блока. Это делается для того, чтобы чистый баланс пользователя не был отрицательным путем проверки равенства первых строк нулю для каждого блока. Если у кого-то отрицательный чистый баланс, первая строка его блока не будет нулевой, потому что отрицательное значение (-x) окажется (p - x) в конечном поле

zero-knowledge-proofs-what-are-zk-starks-and-how-do-they-work image 13

, что является очень большим положительным значением.

zero-knowledge-proofs-what-are-zk-starks-and-how-do-they-work image 14

4. Мы вводим случайные числа для каждого пользователя и заполняем пустые места в таблице значением 0

zero-knowledge-proofs-what-are-zk-starks-and-how-do-they-work image 15

Шаг 2: увеличение полинома низкой степени Используя приведенные выше полиномиальные ограничения, мы можем получить полином трассировки вычислений длины uts * N. В целях безопасности мы выполняем обязательство по полиному на большей области оценки с коэффициентом усиления домена в качестве extension_factor (коэффициента увеличения).

В приведенном выше случае мы могли бы вычислить полином p(x) от I(x). При использовании extension_factor 8 мы вычислим еще 32(8-1)* точек на p(x).

Поскольку два разных полинома со степенью D будут разделять не более D общих точек, пример пары полиномов с допустимым полиномом (который удовлетворяет приведенным выше ограничениям) и фальшивым полиномом со степенью D (который не удовлетворяет указанным выше ограничениям) будут разделять не более D общих точек. Это означает, что фальшивый полином может пройти выборочную проверку с вероятностью

zero-knowledge-proofs-what-are-zk-starks-and-how-do-they-work image 16

. Если мы проведем выборочную проверку n раз, вероятность уменьшится до

zero-knowledge-proofs-what-are-zk-starks-and-how-do-they-work image 17

.

Мы по умолчанию добавляем extension_factor со значением 16 и время выборочной проверки 16, поэтому уровень безопасности будет 80 бит.

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

Шаг 4: создание выборки доказательства Используя корень Меркла в качестве случайного источника, мы выбираем данные. Чтобы избежать утечки данных трассировки вычислений, мы избегаем данных с индексом *k ** extension_factor во время выборки и создаем путь доказательства Меркла, соответствующий индексу выборки.

Мы проводим выборочные проверки, чтобы определить, является ли зафиксированный полином действительным полиномом, удовлетворяющим ограничениям, перечисленным в шаге 1. Как указано в шаге 2, время выборочных проверок влияет на вероятность успешного вмешательства или манипуляции.

Шаг 5: создание доказательства низкой степени

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

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

k0 = hash(root + "0") k1 = hash(root + "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: проверка пользователем подтверждения включения Пользователь проверяет свой баланс, идентификатор, вычисляет хеш-значение данных, соответствующих его индексу, и проверяет хеш-значение на конечной ноде дерева Меркла, используя предоставленный путь Меркла.

2. Как выполнить самостоятельную проверку Подтверждения резервов (PoR)?

2.1 Проверка ограничения включения zk-STARK

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

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

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

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

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

Как выполнить проверку:

1)Для проверки включения баланса вашего аккаунта в листок Меркла zk-STARK войдите в свой аккаунт OKX и откройте «Аудиты», чтобы просмотреть последние аудиты. Нажмите «Подробнее» для просмотра данных аудита.

zero-knowledge-proofs-what-are-zk-starks-and-how-do-they-work image 18

2. Получите данные, необходимые для ручной проверки, нажав «Копировать данные».

zero-knowledge-proofs-what-are-zk-starks-and-how-do-they-work image 19

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].(https://github.com/okx/proof-of-reserves/releases/tag/v2.0.0)

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

zero-knowledge-proofs-what-are-zk-starks-and-how-do-they-work image 20

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

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

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

    zero-knowledge-proofs-what-are-zk-starks-and-how-do-they-work image 21
  • Если проверка не пройдена, будет показан результат «Ошибка проверки ограничения включения»:

    zero-knowledge-proofs-what-are-zk-starks-and-how-do-they-work image 22

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

Как выполнить проверку:

Чтобы проверить и подтвердить наличие активов, которые мы, по нашему заявлению, храним, и что ни один пользователь не имеет отрицательного чистого капитала, посетите страницу «Файлы аудита» и загрузите файлы zk-STARK в разделе «Отчет об обязательствах», а затем сохраните их в новой папке.

zero-knowledge-proofs-what-are-zk-starks-and-how-do-they-work image 23

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

zero-knowledge-proofs-what-are-zk-starks-and-how-do-they-work image 24zero-knowledge-proofs-what-are-zk-starks-and-how-do-they-work image 25

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

Сохраните инструмент проверки OKX с открытым исходным кодомzk-STARKValidator и папку «sum proof data» во вновь созданной папке с шага 1. В нашем случае мы помещаем инструмент, а также файл данных в папку «Загрузки» с именем «proof-of-reserves», как показано ниже:

zero-knowledge-proofs-what-are-zk-starks-and-how-do-they-work image 26

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

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

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

zero-knowledge-proofs-what-are-zk-starks-and-how-do-they-work image 27

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

zero-knowledge-proofs-what-are-zk-starks-and-how-do-they-work image 28