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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Мы аккумулируем суммы пользовательских активов одну за другой и заносим результат в строки , где k % 8 = 7 и , которые являются последними строками каждого блока

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

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

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

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

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

Мы по умолчанию добавляем 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 и откройте «Аудиты», чтобы просмотреть последние аудиты. Нажмите «Подробнее» для просмотра данных аудита.

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

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

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

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

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

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

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