Merkle DAG

Merkle DAG — это структура данных, представляющая собой направленный ациклический граф (DAG), в котором каждый узел идентифицируется криптографическим хешем своего содержимого (хеш-суммой). Данная структура сочетает в себе свойства дерева Меркла (Merkle tree) и направленного ациклического графа, обеспечивая верифицируемость, неизменяемость и эффективное дедуплицирование данных. Merkle DAG является фундаментальной структурой для ряда децентрализованных систем, включая распределённые файловые системы (например, IPFS), блокчейн-платформы (например, Ethereum) и системы управления версиями (например, Git).

История

Концепция Merkle DAG возникла как развитие идей, заложенных в деревьях Меркла, предложенных Ральфом Мерклом в 1979 году для эффективной верификации целостности данных в распределённых системах. Деревья Меркла, в свою очередь, базируются на более ранних работах по хешированию и криптографии.

В 2010-х годах, с развитием технологии блокчейн и распределённых реестров, возникла потребность в более гибких структурах данных, способных представлять не только линейные цепочки блоков, но и произвольные графы связей между элементами. В 2014 году Хуан Бенет, создатель IPFS (InterPlanetary File System), формализовал и популяризировал термин Merkle DAG, описав его как ключевой компонент для адресации и обмена контентом в децентрализованных сетях. Впоследствии структура была принята и адаптирована в других проектах, таких как Filecoin, Ethereum (для хранения состояния и транзакций) и Git (для представления истории изменений).

Основные принципы и свойства

Идентификация по содержимому (Content Addressing)

В Merkle DAG каждый узел идентифицируется не по его расположению в сети (например, IP-адресу) или имени, а по криптографическому хешу его содержимого. Это означает, что адрес узла (его идентификатор) однозначно определяется данными, которые он хранит. Если содержимое узла изменяется, его хеш и, следовательно, его адрес также изменяются. Это свойство лежит в основе так называемой адресации по содержимому (content addressing).

Направленный ациклический граф

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

Неизменяемость (Immutability)

Поскольку адрес узла зависит от его содержимого, а содержимое включает в себя хеши дочерних узлов, любое изменение данных в любом узле графа приводит к изменению хеша этого узла, а затем и всех узлов, которые на него ссылаются, вплоть до корневого. Таким образом, Merkle DAG является неизменяемой структурой: любое изменение создаёт новый граф с новым корневым хешем, а старый граф остаётся нетронутым. Это свойство критически важно для систем, требующих целостности и верифицируемости истории данных.

Дедупликация (Deduplication)

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

Верифицируемость (Verifiability)

Любой участник сети, имея корневой хеш Merkle DAG, может независимо проверить целостность и происхождение любых данных в графе. Для этого достаточно вычислить хеши узлов по пути от корня к целевому узлу и сравнить их с хешами, хранящимися в родительских узлах. Это позволяет проверять данные без необходимости доверять третьей стороне.

Структура узла

Типичный узел Merkle DAG состоит из двух частей:

• Данные (Data): Произвольный набор байтов, представляющий собой полезную нагрузку узла (например, часть файла, объект состояния, блок транзакций).
• Ссылки (Links): Массив указателей на дочерние узлы. Каждая ссылка обычно содержит:
• Хеш (Hash): Идентификатор дочернего узла (криптографический хеш его содержимого).
• Имя (Name): Необязательная строка, позволяющая различать дочерние узлы (например, имя файла в каталоге).
• Размер (Size): Необязательное поле, указывающее общий размер подграфа, на который ведёт ссылка (в байтах).

Применение

IPFS (InterPlanetary File System)

В IPFS Merkle DAG является основной структурой для представления файлов и каталогов. Файл разбивается на блоки фиксированного размера, каждый из которых становится узлом Merkle DAG. Каталог представляется узлом, ссылки которого указывают на хеши файлов или подкаталогов. Корневой хеш каталога служит его уникальным адресом. Это позволяет эффективно распространять и верифицировать файлы в децентрализованной сети.

Блокчейн (Ethereum)

В Ethereum Merkle DAG используется для хранения состояния аккаунтов и истории транзакций. Структура, известная как Patricia Merkle Trie, является разновидностью Merkle DAG, оптимизированной для поиска по ключу. Каждый блок содержит корневой хеш этой структуры, что позволяет быстро верифицировать состояние всего реестра на момент создания блока.

Git

Система управления версиями Git внутренне использует структуру, очень похожую на Merkle DAG. Коммиты, деревья (каталоги) и блобы (файлы) являются узлами, идентифицируемыми по SHA-1 хешу их содержимого. Коммит ссылается на дерево (слепок состояния файлов) и на родительские коммиты, формируя направленный ациклический граф истории изменений. Это обеспечивает целостность и неизменяемость всей истории проекта.

Filecoin

Filecoin, децентрализованная сеть хранения данных, построенная на основе IPFS, активно использует Merkle DAG для доказательства того, что поставщики услуг хранения действительно хранят данные в течение оговоренного времени. Специальные структуры, такие как Piece CID и Sector CID, основаны на Merkle DAG и используются в криптографических доказательствах (Proof-of-Replication и Proof-of-Spacetime).

Преимущества и недостатки

Преимущества

• Целостность данных: Любое изменение данных немедленно обнаруживается.
• Децентрализация: Данные могут быть проверены без обращения к центральному серверу.
• Эффективность: Дедупликация и возможность параллельной загрузки частей графа.
• Устойчивость к цензуре: Сложно заблокировать доступ к данным, если известен их хеш.

Недостатки

• Неизменяемость: Затрудняет обновление данных; любое изменение требует создания нового графа.
• Сложность сборки мусора: Удаление старых, неиспользуемых версий графа требует механизмов сборки мусора, так как узлы не могут быть просто удалены, если на них есть ссылки.
• Зависимость от хеш-функции: Безопасность структуры полностью зависит от стойкости используемой криптографической хеш-функции (например, SHA-256). Её компрометация может подорвать всю систему.

Сравнение с деревом Меркла

Хотя Merkle DAG и дерево Меркла имеют общие корни, между ними есть ключевые различия:

Merkle DAG является более общей и гибкой структурой, позволяющей представлять сложные связи между данными, в то время как дерево Меркла — это специализированный инструмент для эффективной верификации упорядоченных наборов данных.

Интересные факты

• Термин «Merkle DAG» был впервые введён в технической документации IPFS в 2014 году, хотя сама концепция использовалась в Git (с 2005 года) и других системах задолго до этого.
• В IPFS существует специальный формат сериализации узлов Merkle DAG, называемый Protobuf, который определяет, как данные и ссылки кодируются в байты.
• Некоторые реализации Merkle DAG, например, в Ethereum, используют не просто хеши, а хеши с префиксами, которые кодируют тип узла (пустой, лист, расширение, ветвь), что делает структуру более эффективной для поиска по ключу.

Источники

• Benet, J. (2014). IPFS - Content Addressed, Versioned, P2P File System. (Технический документ, описывающий IPFS и Merkle DAG).
• Merkle, R. C. (1980). Protocols for public key cryptosystems. (Оригинальная работа по деревьям Меркла).
• Документация IPFS: "Merkle DAG" (ipfs.tech).
• Документация Ethereum: "Patricia Tree" (ethereum.org).
• Документация Git: "Git Internals - Git Objects" (git-scm.com).