Parents hash creating process

ABengrine · July 20, 2022, 12:51pm

Hello,

In Merkle DAGS doc : Merkle DAGs | IPFS Docs
I read “A Merkle DAG is a DAG where each node has an identifier, and this is the result of hashing the node’s contents — any opaque payload carried by the node and the list of identifiers of its children …”

I am trying to fully understand how a parent’s hash is created from its children. From other researches I found that the two hashes are concatenated and the result is hashed. Is it correct and if so in which order are they concatenated ?

Thank you for reading

hector · July 20, 2022, 1:01pm

A hash is not created from the children.

You create a new node, which somehow has “links” in it (to children), and you hash that new node. How you do all that is an implementation detail.

i.e. Kubo uses go-merkledag, so the CID will come from serializing protobufs like go-merkledag/merkledag.proto at master · ipfs/go-merkledag · GitHub, which have a field with a list of links. Afaik, order of links matters.

ABengrine · July 20, 2022, 1:33pm

Thank you for your fast response.

Is there any documentations on what are precisely those “links” to the children ?

Is this choice a specific feature of IPFS ? Because when I search for Merkle Dags in general, this is what I found about how hashed are made.

Thanks

ABengrine · July 20, 2022, 1:51pm

This is a schema of IPLD Tutorial | Merkle DAGs: Structuring Data for the Distributed Web (Lesson 4) | ProtoSchool

From what I understand, The hash of a parent node is the hash of all his children’s CID concatenated. Is it correct and if so in which order are this CID concatenated ?

hector · July 20, 2022, 2:17pm

The answer to your question is implementation specific. I just told you that in the go-merkledag implementation of MerkleDags, the hash of the root is the hash of the serialized protobuf that I linked.

It seems that this library chooses to sort links before serializing: go-merkledag/coding.go at c076715ad64cccb1976de3686b0d6304ec3f2839 · ipfs/go-merkledag · GitHub

Jorropo · July 20, 2022, 2:29pm

Here is a 70 lines of code complete implementation of the merkle dag creation process for unixfs (dag-pb).

github.com

Jorropo/zero-to-unixfs/blob/9eeb369c0dc3804132c55734e42807a2c60082dd/main.go#L129-L205


      
          	roots := leaves
          	for len(roots) > 1 {
          		leaves = roots
          		roots = nil
          		for len(leaves) > 1 {
          
          
			// avoid links to nothing if there is less leaves than the fanOutSize
          			linkCount := fanOutSize
          			if len(leaves) < linkCount {
          				linkCount = len(leaves)
          			}
          
          
			blocksizes := make([]uint64, linkCount)
          			links := make([]*pb.PBLink, linkCount)
          			var fileSize uint64
          			var dagSize uint64
          
          
			for i, v := range leaves[:linkCount] {
          				fileSize += v.fileSize
          				dagSize += v.dagSize

This file has been truncated. show original

ABengrine · July 20, 2022, 2:52pm

very well

I will look into that

Thanks @Jorropo @hector

Topic		Replies	Views
How to create a hash linked Merkle tree_ IPLD dag in jsIPFS Coding js-ipfs , ipld	11	1731	February 15, 2021
Dag-pb and UnixFs confusion	1	197	August 30, 2022
Can you verify my understanding of the Merkle DAG Help	0	726	May 23, 2017
Smaller files in a folder + hashing Coding	0	311	January 15, 2021
Understanding hashes	13	3012	July 18, 2018

Parents hash creating process

Related Topics