merkle-paths
v0.1.0
Published
Path system that follow the links across Merkle trees
Downloads
5
Readme
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
})