Merkle-tree: Как проверить целостность данных без полного доступа?

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

const verificationHash = SHA256(...fileContent);

И отправить хэш получателю, чтобы он мог проверить, что получил именно то, что отправлялось:

const receivedFileHash = SHA256(...receivedFileContent);  if (receivedFileHash === verificationHash) {     // Всё хорошо, хэши совпадают } else {     // Внимание! Весь файл или его часть были изменены }

Но иногда нужно проверять только часть данных. Например, в протоколе BitTorrent нужно убедиться, что чанк, который прислал пир, действительно является частью файла, который мы загружаем и хэш которого мы знаем. Или в протоколе Bitcoin, нужно подтвердить, что определённая транзакция включена в блок с указанным хэшем.

Для таких целей используется структура данных под названием Merkle-tree и её важное свойство — Merkle-proof.

Построение Merkle-tree

Чтобы построить Merkle-tree, данные разбиваются на части. В случае с BitTorrent это чанки, а в случае с Bitcoin блок делится на отдельные транзакции. Затем для каждой части вычисляется хэш, и эти хэши распределяются по парам. Если последний хэш остаётся без пары, он дублируется. Далее из хэшей пар снова вычисляются хэши, и процесс повторяется, пока не останется единственный хэш — корень дерева, называемый Merkle Root.

С помощью этой структуры можно проверить, принадлежит ли конкретная часть данных (например, D1, D2, D3) общему набору, для которого известен хэш (Merkle Root). Для проверки, что D1 относится к общей структуре, вовсе не нужно знать D2 и D3 — достаточно применить алгоритм Merkle-proof.

Merkle-proof

В сети Bitcoin часто используются тонкие клиенты — устройства, которые хранят не весь блокчейн, а только заголовки блоков. Это означает, что такие клиенты не видят список всех транзакций в блоке, а запрашивают данные только о нужных транзакциях у полных узлов сети. Однако полный узел, предоставляющий эти данные, может быть скомпрометирован. В таком случае требуется доказательство, что указанные транзакции действительно включены в блок, но без запроса всего списка транзакций (их может быть очень много).

Вместо полного списка транзакций узел предоставляет так называемое Merkle-proof.

Merkle-proof — это путь в Merkle-tree, позволяющий вычислить Merkle Root на основе интересующих нас данных. Например, чтобы проверить, что транзакция D1 включена в блок, полный узел должен отправить хэши H2 и HH2 в качестве доказательства. Этого будет достаточно, чтобы вычислить Merkle Root и сравнить его с тем, что указано в заголовке блока на стороне клиента.

• Зелёным отмечены узлы, которые составляют Merkle-proof и нужны для вычисления Merkle Root.

• Жёлтым отмечены узлы, которые вычисляются на стороне проверяющего.

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

Таким образом, для проверки включения транзакции в блок требуется получить Merkle-proof [H2, HH2], вычислить Merkle Root и сравнить его с заголовком.

Аналогичным образом проверяются чанки файлов в протоколе BitTorrent. Поскольку невозможно проверить содержимое файла по хэшу до его полной загрузки, в начале загрузки торрент-трекер предоставляет Merkle Root, а затем для каждого чанка, загружаемого клиентом с различных пиров, запрашивается Merkle-proof. Что является подтверждением того, что чанк является частью файла.