【IPFS】Merkle DAG

Merkle DAG数据结构是IPFS架构的核心，IPFS整个协议都围绕它进行。^[1]

IPFS架构

IPFS is a stack of network protocols that organize agent networks to create, publish, distribute, serve, and download merkledags.
the IPFS merkledag is the datastructure at the heart of IPFS. It is an acyclic directed graph whose edges are hashes.
The ipfs merkledag is a directed acyclic graph whose edges are merkle-links.

IPFS Merkle DAG的数据结构^[2][1]

type IPFSLink struct {
      Name string
      // name or alias of this link
      Hash Multihash
      // cryptographic hash of target
      Size int
      // total size of target
}
type IPFSObject struct {
      links []IPFSLink
      // array of links
      data []byte
      // opaque content data
}

Merkle DAG和Merkle Tree很相似，但Merkle tree只是Merkle DAG的子集。
Merkel Tree将文件数据都存在leaf node，而Merkel DAG每个node都可以存储数据。对于普通存储文件，Merkel tree是完全没有问题的，但是IPFS为了保证更加的通用性，兼容更多的数据结构，比如区块链、Git。区块链的每个block是由区块数据和下一个block的hash构成的，Merkle DAG的这种数据结构可以兼容区块链。^[3]

列出某object下包含的link

使用ipfs ls命令。
查看一个目录下包含的object：

> ipfs ls -v QmVpmbvkEkgMPMJjBMPzQPvuosoiUK2unWHN29rZdxM3Aa
Hash                                           Size      Name
QmbEnHMmvd56puBMqMZuhDUWn4mVnhkKFJ1NPANt3T3wew 13787765  audio_only.m4a
QmeG6mZEZsSFH6DpmozfVPygYMHCtsNemtwnrgbjwQQs3Z 2329900   audio_only_1.m4a
QmaQY7aiXosDYWRZ3oTkkHSwfoYatV4a6KJiNkcenc44mR 372       chat.txt
QmPrUDTJG1fVKu79L4QFkY5v5XeS1ZqR1WKLgrrkbr6t9q 190       playback.m3u
QmNNYPbkpqBoXkQ99nC9zz84R6cG31RdRdTbYnw1sSMz4f 247176439 zoom_0.mp4
QmPzU5vjnteC8wzgUm6wxGvPaWYtH1ioEtNJs1GVNtp9nW 28638423  zoom_1.mp4

查看文件下包含的object：

> ipfs ls QmNNYPbkpqBoXkQ99nC9zz84R6cG31RdRdTbYnw1sSMz4f
QmRH1LKSSzAbS6hWzvuozxmS7itbz4cipKc2qcFC9n3qoG 45623854
QmfJu8tAEZpyeRZNubpu7NpEWPi9cK17zPCiXPZM747LEP 45623854
QmSbkF98HG5GQ9jL8xCRKYMGZYKFRVk8vxYgGed3dv5VvQ 45623854
QmUx1Z3pAQhpSVmuBphq2ZVW9uGvot9BEU9GeR3YPNgjn7 45623854
QmRTBHJ6dSkCTuZ6FmVzTX1pJgbXdcU7KvuU41cijGjYE8 45623854
QmT5Vt6sajkdpTwykdRennTaGxyFaKCeP4WKKT12wr6rLx 19056860

link下的object也包含link列表，递归查找：

> ipfs refs --recursive QmNNYPbkpqBoXkQ99nC9zz84R6cG31RdRdTbYnw1sSMz4f
QmRH1LKSSzAbS6hWzvuozxmS7itbz4cipKc2qcFC9n3qoG
QmPMaewqUqn7A7omAKHvHWTBseZaoxWywUp5EYm87s1snr
QmfG2pbs89ryHFrDLG1ZFDQ7JqQx4BqsuQKLGBFkJ5ECBF
QmScF5RKEKPeNKReM1gfGGfDrK1amGuemggEfvKu6LAr1p
QmZDcwpZrgJuGjx6BemDJ1A1sDBQmno8YG6kMXq7ZiFb79
QmUMf14PFP12qKqUxQVgh6othkuxhveLEauPi4qvyApWFQ
QmZ1FdQ5stYGBXpuog8mCFJzYMr2UjDpPA3F5fbQ3ZMtJE
QmZFXu5AGbU6PHmyF1FUhCeCfijp4nYseu3ooGqQBuvKq9
Qmb693mkZiKKFTVxqvMwzscjjj2qSP4kJraE2NhxbRwRXA
Qmb2W744T2pKgHZDheDRf5H6yWvD8iCMm8ttpy9E8QSLMf
QmVGeCng3hU2RKVUG2XxeHyJbv44wU7ZR5pfC6zXwUmHCG
QmbrbmSEMiYn6KfZUvXS8AqLg9kk6NKTXMv3Svax6wz9EN
Qmaseapw9WZeBkDLfUgp9r1Lq5XhHA7dZKfed2gWbpdau6
QmYCygkSJYRTNNwrkp9m6mpWUsfoV8kYpdTe1HNkJLzeeE

返回的结果非常长，这里展示一部分。

查看object本身的状态

比如下面这张图片：

> ipfs block stat QmSu1tBmnvugUw1Mv1ajA6jpgqtTGJnqko9ghypMrjA8jN
Key: QmSu1tBmnvugUw1Mv1ajA6jpgqtTGJnqko9ghypMrjA8jN
Size: 102
> ipfs ls QmSu1tBmnvugUw1Mv1ajA6jpgqtTGJnqko9ghypMrjA8jN
QmcqPiVqTYkMzbUEvJxHtXYoA77ebJhWt47dD9QMqrXsYa 262158
Qmbvzc3p7vnxVr6v8azL917RstXbTbyZRDA9LTBn7mTu1f 5928

可以看到这张图片被分成了2个link，再查看这两个link的block state，不再包含link。
object的数据大小限制是 2^18+14 bytes (262158 bytes)。
当文件大于262158 bytes时，IPFS将文件分割成小于或等于262158 bytes的片段。

ref

---

1. https://github.com/ipfs/specs/tree/master/merkledag ↩ ↩

2. IPFS whitepaper 3.5节部分 ↩

3. https://github.com/ipfs/go-ipfs/issues/2053 ↩