CODEWITHSUNDEEP
ipfsmerkle-tree
Brent Arias
Brent Arias

Reputation: 30165

Fetching first, last, or nth node from IPFS Merkle tree

Assuming:

  1. I've created a Merkle tree on IPFS with hundreds of data nodes.
  2. Only the leaves of the Merkle tree contain the data nodes (whereas edge nodes contain metadata such as hashes and child CIDs)
  3. In my possession I only have the root CID of the Merkle tree
  4. I don't a priori know exactly how many nodes are in the Merkle tree.

...how do I request a particular data node (i.e. leaf node) from the tree, such as the first, the last, or perhaps the nth data node without traversing the entire tree? I want to find any such data node in O(log2n) time.

In principle I know how to achieve this, finding the nth node in O(log2n) time on a complete binary tree starting from the root, using a solution like this or this. However, as stated in assumption #4, I don't start with knowing how many nodes are in the Merkle tree and...I'm simply hoping that IPLD (or similar mechanism) simply has a way to do this for me.

If indeed IPLD can do this, can someone provide pertinent sample code (or pseudo code)? Ultimately I'm hoping that IPFS provides some means to assist with this.

Also, if there is something wrong with any of my assumptions - please clarify. For example, if Merkle trees on IPFS don't always store data nodes in the leaves, that would be good to know.

Upvotes: 0

Views: 32

Answers (0)

Related Questions