merkle-paths

interplanetary-paths

(was data-pointers, merkle-paths, could-be ipld)

WARNING: A lot is happening, spec can change in the next few hours.

Hierarchical path scheme that traverses in and across objects (or datasets). It extends JSON Pointers to support (1) any type of stuctured data, (2) links across data spaces keeping the same origin path.

was: Hierarchical pathing scheme to traverse in and across merkle trees - merkle dags. (eventually IPLD)

Note

After a great talk with some students at MIT, I realized that this scheme is not just valid for Merkle trees, but for any type of structures. It is a way to link across data (like the Linked Data model), and follow the link with the same path. If we edit MerkleLink to HTTPLink, then we can link data via the web, instead.

Goals

Beyond the goals (and including the goals) of IPLD

• Nice pathing schemes (be consistent /friends/0/name whether these are local or remote data)
• Support multiple types of followable origin urn, including urls, merkle links
• Be nice to JSON
• Efficient encoded representation when possible

Pathing examples

Without hash/merkle links

// _hash_
{
  "name": "Nicola",
  "friends": [{
    name: "Adam"
  }]
}


// /_hash_/name
"Nicola"

// /_hash_/friends
[{
  name: "Adam"
}]

// /_hash_/friends/0
{
  name: "Adam"
}

// /_hash_/friends/0/name
"Adam"

With hash links

// _hash1_
{
  "name": "Nicola",
  "surname": MerkleLink({@link: _hash3_})
  "friends": [MerkleLink({
    @link: _hash2_
  })]
}

// _hash2_
{
  name: "Adam"
}

// _hash3_
"Greco"

// /_hash1_/surname
"Greco"

// /_hash1_/friends
[MerkleLink({
  @link: _hash2_
})]

// /_hash1_/friends/0
{
  name: "Adam"
}

// /_hash1_/friends/0/name
"Adam"

With data about the link

// _hash1_
{
  "name": "Nicola",
  "friends": [MerkleLink({
    @link: _hash_2,
    nickname: "yala"
  })]
}

// _hash2_
{
  name: "Adam"
}

// /_hash1_/friends
[MerkleLink({
  @link: _hash_2,
  nickname: "yala"
})]

// /_hash1_/friends/0
{
  name: "Adam"
}

// /_hash1_/friends/0/name
"Adam"

// /_hash1_/friends/0/nickname
undefined

// /_hash1_/friends/0#nickname
"yala"

With merkle links

// _hash1_
{
  name: /_hash3_/name
  friends: [
    MerkleLink({
      @link: /_hash2_/name
    })
  ]
}

// _hash2_
{
  name: {
    first: /_hash3_/name,
    family: "Greco"
  }
}

// _hash3_
{
  name: "Nicola"
}

// /_hash1_/name
"Nicola"

// /_hash1_/friends/0
{
  first: "Nicola",
  family: "Greco"
}

// /_hash1_/friends/0/first
"Nicola"

Relative graphs (cycle)

Cyclic graphs can be created using relative paths

// _hash1_
{
  name: "Nicola",
  surname: MerkleLink(@link: "./passport/officialSurname")
  passport: {
    officialName: MerkleLink(@link: "../name"),
    officialSurname: "Greco"
  }
}

// /_hash1_/name
"Nicola"

// /_hash1_/surname
"Greco"

// /_hash1_/passport
{
  officialName: MerkleLink(@link: "../name"),
  officialSurname: "Greco"
}

// /_hash1_/passport/officialName
"Nicola"

Cycles in merkle graphs

// _hash1_
{
  nicola: {
    name: "Nicola"
    sister: MerkleLink({@link: "../nicola"})
  },
  lucia: {
    name: "Lucia"
    brother: MerkleLink({@link: "../lucia"})
  }
}

// _hash2_
{
  nicola: _hash3_,
  lucia: _hash4_
}

// _hash3_
{
  name: "Lucia"
  brother: MerkleLink({@link: "../lucia"})
}

// _hash4_
{
  name: "Nicola"
  sister: MerkleLink({@link: "../nicola"})
}

// /_hash1_/nicola/sister/name
{
  name: "Lucia"
}

// /_hash1_/nicola/sister/brother/name
{
  name: "Nicola"
}

// /_hash2_/nicola/sister/name
{
  name: "Lucia"
}

// /_hash2_/nicola/sister/brother/name
{
  name: "Nicola"
}

Mutable paths!

Non-merkle example (http)

// _hash3_
{
  name: HTTPLink({@link: "http://example.com/users/92", @path: "/name"})
  // or name: HTTPLink({@origin: "http://example.com/users/92", @link: "./name"})
  // or name: HTTPLink({@link: "http://example.com/users/92#me"})
  surname: "Greco"
}

// http://example.com/users/92
{
  name: "Nicola",
  ..
}

// /_hash3_/name
"Nicola"

In this example, link points to some data, however we want the /name given that origin

Multilinks

Equivalent property of the magnet uris (that tell where to go and find the content)

{
  name: MultiLink({
    @link:[
      HTTPLink({ @link: "http://example.com/users/92") }, // these are ordered by priority
      MerkleLink({ @link: "_hash2_"),
    ]
  })
}

Implementation note

MerkleLink in the example describe the fact that that branch of the object should be treated differently

Example implementations:

• In CBOR, it can just be a tag
• In JavaScript, one could just check if the property is an object and contains @link inside

Efficient encoding

It may be a good idea to store the data in the following way: list the links before the data. In this way navigating through data will be cheap (no need to retrieve the ENTIRE content, one should just do a binary search in the links (if the number of the links is stored at the top of the entry), otherwise linear)

{
  name: hash2,
  surname: "Greco"
  friends: [{
    name: MerkleLink(hash1/name),
    surname: "Yala
  }]
}
+------------------------------+
| Links: 2                     |
+------------------------------+
| ./friends/0/name: hash1/name |
| ./name: hash2                |
+------------------------------+
| surname: "Nicola"            |
| friends/0/surname: "Yala"    |
+------------------------------+

// or, in other words

+------------------------------+
| Links: 2                     |
+------------------------------+
| {                            |
|   friends: [{                |
|     name: hash1/name         |
|   }],                        |
|   name: hash2                |
| }                            |
+------------------------------+
| {                            |
|  surname: "Greco"            |
|  friends: [{                 |
|    surname: "Yala"           |
|  }]                          |
| }                            |
+------------------------------+

Idea: It could be that we dont need the size of the links to have binary search of links, if links are stored with a prefix, e.g. _, so they are always at the top, then if we know the size of the CBOR object, then, we can do binary search.

Extra

Redirect can't happen (is there a way to solve this?)

The reason why these can't happen is because there is no way to access link properties

// _hash1_
Link({
  @link: Link({ @link: "hash2"}),
  property: 1
})

// _hash2_
"hi"

// /_hash1_/
Link({
  @link: Link({ @link: "hash2"}),
  property: 1
})