Where does ipfs store the pathing data that resolves the content?

Question

So, my understanding is that ipfs uses the ipld format to link data. Once a file is uploaded it is divided up and hashed. The whole thing is then bundled up in a Merkle dag. How to resolve the blobs of data? Given a CIDv0 or CIDv1 which we shall call root:

bafybeihbqaitndot2arwcwxq7i66jjbfpgaurkzkizwhyq74xcnamkc7wm

we may find all the CIDs that "make up" that root. the standard ipfs client gives us the command ipfs dag get cid. In this case for choosing cid=root those resolved cids are:

QmNmigQh6aETtpCjMgb7TZy75XaktAvdyAqcPVhqvvQdW8
QmNoymPywjiE29Q4PyghBgh9WWqGQwYphTFLcuE82CqEPG
QmSA5p69qqjnYLvSNP8fLLkwvD9Fqmt5CEHA4DwbKaE9yD
QmREdziekNW4yLkPC4GsxLRoLWVCWCKfMYcykpbRGMdMQV
QmNWkQ4ozM1rwnLouJsawsgCWcwAyZnPHV5uoJbZycDdSR

And in fact, these are already the little content blobs of my react app sitting on ipfs. Now my question is: where is this information stored? Like the information that resolves those cids? In fact there is also a little bit of metadata that comes with it, depending on the format/codec that is used in the ipld format. For instance:

$ ipfs dag get bafybeihbqaitndot2arwcwxq7i66jjbfpgaurkzkizwhyq74xcnamkc7wm 
{
  "Data": {
    "/": {
      "bytes": "CAIY04BIIICAECCAgBAggIAQIICAECDTgAg"
    }
  },
  "Links": [
    {
      "Hash": {
        "/": "QmNmigQh6aETtpCjMgb7TZy75XaktAvdyAqcPVhqvvQdW8"
      },
      "Name": "",
      "Tsize": 262158
    },
    {
      "Hash": {
        "/": "QmNoymPywjiE29Q4PyghBgh9WWqGQwYphTFLcuE82CqEPG"
      },
      "Name": "",
      "Tsize": 262158
    },
    {
      "Hash": {
        "/": "QmSA5p69qqjnYLvSNP8fLLkwvD9Fqmt5CEHA4DwbKaE9yD"
      },
      "Name": "",
      "Tsize": 262158
    },
    {
      "Hash": {
        "/": "QmREdziekNW4yLkPC4GsxLRoLWVCWCKfMYcykpbRGMdMQV"
      },
      "Name": "",
      "Tsize": 262158
    },
    {
      "Hash": {
        "/": "QmNWkQ4ozM1rwnLouJsawsgCWcwAyZnPHV5uoJbZycDdSR"
      },
      "Name": "",
      "Tsize": 131169
    }
  ]
}

where is that information stored? And is the root cid just the (multi-)hash of the consituent cids or is it the (multi-)hash of the above object?

Answer 1

Here is a more or less readable spec of unixfs (the dataformat used to encode merkle trees of directories and files).

https://github.com/ipfs/specs/pull/331

First the thing you seems to have caught on but adding it for future readers, unixfs is a merkle datastructure, that means we use hashes as pointer, CIDs are hashes + metadata pointing to the next block. Unixfs is then a kinda b-tree of blocks, instead of pointers cryptographic hashes are used to link data (this allows anyone to verify the whole tree starting from the root). I said kinda b-tree because it doesn't actually have to be balanced, and there reasons you might want to not do that.

How to decode it ?

Unixfs is made of two kind of blocks:

You can decode this from the CID, here is an example CID:

bafkreifzjut3te2nhyekklss27nh3k72ysco7y32koao5eei66wof36n5e

The first character is the multibase key, this allows the CID to use some different base encoding, you look it up in this table:

https://github.com/multiformats/multibase/blob/master/multibase.csv

A b gives us base32 rfc4648 case-insensitive - no padding. You then decode the rest of CID using this spec and obtain binary data, I'll represent it as hex for convenience but the implementation works in binary from this point. The next step is to read 4 back to back uvarints, they are so called MSB-128 if you want to look them up (this is the sane version most programing languages implements).

Here unpacked we get:

• 0x01 this the version of the CID, must be 1 for a CIDv1 (what we are parsing right now)
• 0x55 this is the codec, this maybe tells you what the data is made off, or how you parse it, sadly there is more or less consistency between ways this is used. You can lookup codecs in this table, here we want to look for codecs tagged ipld: https://github.com/multiformats/multicodec/blob/master/table.csv
• 0x12 this the multihash code, this tell you which hashing function was used. To find the correspondance between codes and hashing functions you lookup the same multicodec table from above but this time searching for multihash tagged ids.
• 0x20 this is the length in bytes of the hash digest (this is here to support truncated hashes and variable size output hashing functions). And a bunch of trailing data, this is actually the digest: b94d27b9934d3e08a52e52d7da7dabfac484efe37a5380ee9088f7ace2efcde9

So decoded our CID is:

• v1
• Raw
• sha256
• 32 bytes
• b94d27b9934d3e08a52e52d7da7dabfac484efe37a5380ee9088f7ace2efcde9

By some magic process we now need to find out the bytes that multihashTable[0x12](bytes) == 0xb94d27b9934d3e08a52e52d7da7dabfac484efe37a5380ee9088f7ace2efcde9.

This is taken care of by other layers, the key feature here is that the decoding merkle proofs do not depend of any underlying transport, you can exchange your data using whatever protocol you want as long as you are able to find the bytes that hashed produce the required digest this process can continue.

For this example sha256("hello world") is the answer.

So we have our root block it's hello world.

We can now proceed to decoding it, for unixfs we handle two possible codecs:

0x55 Raw codec

The content of the block is the content of the file.

There is literally no encoding here, hello world is the block content, so it's also a file with length 9 and content hello world.

We just decoded a raw block!

0x70 Dag-pb codec

Let's take this new cid as example: bafybeiejivmdhj3y62h5ejgzctp6oky2dct2ierrqzxlhe3znkt7jusuay Going through the same cid decoding process I described above (multibase then read 4 uvaruints we get):

• v1
• dag-pb
• sha256
• 32 bytes
• 0x89455833a778f68fd224d914dfe72b1a18a7a41231866eb393796aa7f4d25406 digest.

This time we need a protobuf decoder and some schemas:

• ipld.proto
• unixfs.proto

Here is me decoding it using the protoc compiler:

$ ipfs block get bafybeiejivmdhj3y62h5ejgzctp6oky2dct2ierrqzxlhe3znkt7jusuay | protoc --decode=PBNode ipld.proto 
Data: "\010\001"
Links {
  Hash: "\001U\022 \271M\'\271\223M>\010\245.R\327\332}\253\372\304\204\357\343zS\200\356\220\210\367\254\342\357\315\351"
  Name: "hi.txt"
  Tsize: 11
}

Now the next thing to do which is a bit weird (history & backward compatiblity) is to take the .Data bytes field and decode it again but this time using unixfs.proto:

$ echo CAE= | base64 -d | protoc --decode=Data unixfs.proto 
Type: Directory

This tells us this a directory, Dag-pb blocks can be many other things (lookup the spec for a complete description), mainly File! The point of using Dag-pb instead of Raw is that this allows us to link and concatenate smaller files into bigger ones. There are lots of reasons in P2P why downloading many smaller blocks is better than huge ones.

With this new knowledge we can look again at the first decoded protobuf and read the links, for a simple directory, links is a list of various children blocks,

• Hash is a binary CID, we would then apply the same steps (read 4 uvarints, download the block, parse it, ...) in this case this is the first Raw hello world CID we looked at earlier.
• Name field tell you the file name.
• TSize is almost unused and not the size of the file (this is not used while decoding anything).

Directories can point to other directories (for nested structures), files, ...

So the structure we have here is:

.
└── hi.txt -> hello world

Qm... CIDv0 CIDs

Thoses are called CIDv0, they can be converted losslessly to CIDv1 easily.

First you decode them with bitcoin base58 then you skip two magic bytes and then read 32 bytes.

The 32 bytes you just red are the hash digest, the varuints are hardcoded to be dag-pb, sha256, 32 bytes.

When you do this conversion, there is not two files, one of them CIDv0 and an other CIDv1. They both encode the same link.