30:T23a0,# Abstract Inter Planetary Linked Data (IPLD) is a fundamental building block of the IPFS. IPLD Links (a.k.a CIDs) are quintessential, yet arguably suffer from a major design flaw (on par with null pointers ?) # Introduction [Content identifiers (CIDs)][CID] claim that identify data not by _where it is stored_, but rather by the _content itself_. In our observation however, it moves addressing from "where content is stored" to "how content is stored" more specifically to how data is formatted / encoded. It is a significant improvement, but not quite as addressing by "what content is". Same data may be encoded differently depending on where it is stored, different yet when it is moved over the wire. It is also likely that encoding choices may evolve over time. Encoding choice affecting a content identifier is a major drawback and counter to goal of addressing content by "what content is". Identifying data by how it is encoded has various problems and we will call out major ones to illustrate motivation for this proposal. Then we will define goals for the proposed data identifiers and then proceed with the proposal. ## Locality Problem In most programming languages we build data structures out of primitive data types (scalars) and more complex structures by nesting them into one another through [reference]s. In languages with managed memory we do not have to worry about whether sub-structure can be accessed, reference in itself implies access. Languages where we do need to worry about dereferencing tend to suffer from infamous [null pointer] problems. Data structures in IPLD suffer from similar problem to languages with [null pointer]s. We will refer to it as data "locality problem". Nested sub-structure can either be **local**, inlined in a parent structure, or be **external** referenced through an [IPLD Link]. Local sub-structure can always be dereferenced, external one however may not be in memory space and might require reading from disk, or another machine. In worse cases it may require calling other untrusted machines asking them if they can tell you which machine has it or if they know machine that may know. Possibility for errors is vast, and performance guarantees are intractable it can take a fraction of a microsecond or days to get hold of the data. ## Sizing Problem **External** sub-structures might be coming from untrusted machines over the network, so there is the risk that time and resources spend may be wasted on getting a data that does not match identifier requested. To mitigate this risk **block size limit** of around 2MiB is imposed, that way time and resources wasted is within reason, and you wont waste hours fetching data to discover after that it does not match data identified in the request. Implication is that produced data must fit the established size limit so producer needs to device some strategy to **external**ize parts as necessary. This tends to affect the data model, a lot of time and effort goes into how to partition data to make desired read patterns efficient. Problem in disguise is that data producer must foresee how data will be consumed, which is not only difficult, but practically impossible because future is ofter full of surprises and shifting constraints. ### Encoding Problem Typically programs operate on data structures without consideration of what processor architecture program is going to run or how those data structures will be represented in memory, all of that is abstracted away. We worry about data encoding when storing data structures on disk or when we have to send them over the wire. In fact we have been able to negotiate content encoding over HTTP for decades. #### Encoding affects identifiers In IPLD data encoding format affects data identifier, same data in [DAG-JSON] and in [DAG-CBOR] will have different identifiers so data structure like the one show below ```json ${JSON.stringify(inline, null, 2)} ``` Will be identified as ${await cid(json.link(inline))} if use [DAG-JSON] encoding, however in [DAG-CBOR] encoding it will be identified as ${await cid(CBOR.link(inline))}. So we do not really identify data by what data is, but rather how it is stored in memory or disk. #### Locality affects identifiers Identifiers are also affected by how its pieces had been **external**ized. If in above structure we have chosen to make `message` sub-structure external in [DAG-JSON] it would have a different, ${await cid(json.link({ message: await json.link(message) }))} identifier and be represented like shown below: ```json { message: { "/": "${await json.link(message)}" } } ``` #### Dimensions affecting identifiers As we have established encoding affects data identifier, but also does sub-structure locality. In other words there are multiple dimensions of variability affecting data identifiers. Our last example could also have ${await cid(json.link({ message: await json.link(message) }))} identifier if outer structure was in [DAG-CBOR] and `message` was in [DAG-JSON]. This introduces another level of complexity if store data in [DAG-CBOR] and you are asking me for the same data in [DAG-JSON] I may not even realize I have it. But even if I knew I had requested data and I encoded it in [DAG-JSON] external parts would have to still link to the [DAG-CBOR] identifiers or I would have to traverse whole DAG and re-encode it just to hand requested piece in requested format. # Goals Now that we have outlined problems, we can enumerate what is desired to improve upon and why: 1. Data structure SHOULD be identified by the same content identifier regardless of how parts its comprised of are stored. It SHOLUD NOT matter if some parts are local and other parts external. This will get us flexibility to choose make choices about which parts to inline vs externalize without affecting data identifier. It will give us flexibility to make different choices based on storage constraints. It will give us flexibility to make different choices during data transfer. 1. Data structure SHOULD be identified by the same content identifier regardless of the data encoding. This will give us flexibility to choose encoding based on storage constraint. It will give us ability to negotiate content encoding during data transfer. # Approach At the high level merkle structures identify data structures by the root of the [reference tree], which is a binary merkle tree deterministically derived from the data structure itself. ### Data Types [IPLD data model] offers same data types as pretty much every mainstream programming language. We use same set of data types except for the [`Link`], which introduces outlined issues and a [`Null`], [which is generally a bad idea][billion dollar mistake], they are semantically anemic and alternative modelings are nearly always available, in distributed systems in particular [tombstoning] is more appropriate. ## Reference Tree Reference tree is a binary [merkle tree] tree deterministically derived from the data structure. It is derived from the data structure according to the following algorithm: 1. [Abstract data format], list of two or more nodes, is derived from the data structure. 1. First node, an **operator**, denotes relation the rest of nodes, **operands** form. It is kept for the next final step. 1. Operands are [merkle fold]ed into an **operand** (sub)tree. 1. **Operator** node and **operand** (sub)tree are [merkle fold]ed into a tree that represents **reference tree** of the data. ## Merkle Fold Merkle fold is a process of deriving [BAO] inspired binary [merkle tree] from the list of leaf nodes. Parent nodes in derived tree have exactly two children and the content of each parent node is the hash of its left child concatenated with the hash of its right child. When there's an odd number of nodes in a given level of the tree, the rightmost node is raised to the level above. ${mermaid` graph TB parent(root) --> A(leaf) parent --> B(leaf) parent3(root) --> parent2(node) parent2 --> a(leaf) parent2 --> b(leaf) parent3 --> c(leaf) parent4(root) --> parent5(node) parent4 --> parent6(node) parent5 --> ch51(leaf) parent5 --> ch52(leaf) parent6 --> ch61(leaf) parent6 --> ch62(leaf) `} Merkle fold of a single leaf is a leaf itself ${mermaid` graph TB only(leaf) `} Merkle fold of zero leaves is an empty hash (hash of zero bytes) ${mermaid` graph TB _{ } `} ## Abstract data format Abstract data format is a lists of two or more nodes defined for each data type individually. Each node of the abstract data format is either: - leaf node represented by a byte array - [reference tree] ### Scalars | Type | Format | |---------|--------------------------------------------| | Null | 0 bytes | | Boolean | Single byte `0` for `false`, `1 for `true` | | Integer | [LEB128] | | Float | [Double-precision floating-point format] | | String | [UTF-8] | | Bytes | Raw bytes | ${LINKS}31:T4f1,mermaid` graph TD _((" ")) -- "bh3…6r5q" --> object object["{message}"] object -- "bct…r5la" --> obj_tag(merkle-structureːmap/k+v/ref-tree) object -- "brt…pk3a" --> message("message → {from, payload, to}") message -- "bfg…bjtq" --> key("'message'") message -- "bql…6qta" --> val("{from, payload, to}") val -- "bct…r5la" --> val_tag("merkle-structureːmap/k+v/ref-tree") val -- "bnw…ae2q" --> val_fold("(from, payload, to)") val_fold -- "b73…wb5a" --> left("(from, payload)") left -- "bsc…jolq" --> from("from → 'gozala'") left -- "b2w…aqza" --> payload("payload → 'hi'") from -- "b4f…pmpa" --> from_k("'from'") from -- "b2p…afmq" --> from_v("'gozala'") payload -- "byi…mf6q" --> payload_k("'payload'") payload -- "bkv…treq" --> payload_v("'hi'") val_fold -- "b5r…t5cq" --> to("to → 'mikeal'") to -- "b3l…bfrq" --> to_k("'to'") to -- "bdv…7eda" --> to_v("'mikea'") payload_v:::subject payload:::derive left:::derive val_fold:::derive val:::derive message:::derive object:::subject payload_k:::proof from:::proof to:::proof val_tag:::proof key:::proof obj_tag:::proof classDef proof fill:#4dabf7,stroke-width:2px,stroke:white classDef derive fill:#e599f7,stroke-width:2px,stroke:white classDef subject fill:#099268 `32:T4c5,mermaid` graph TD _((" ")) -- "bh3…6r5q" --> object object["{message}"] object -- "bct…r5la" --> obj_tag(merkle-structureːmap/k+v/ref-tree) object -- "brt…pk3a" --> message("message → {from, payload, to}") message -- "bfg…bjtq" --> key("'message'") message -- "bql…6qta" --> val("{from, payload, to}") val -- "bct…r5la" --> val_tag("merkle-structureːmap/k+v/ref-tree") val -- "bnw…ae2q" --> val_fold("(from, payload, to)") val_fold -- "b73…wb5a" --> left("(from, payload)") left -- "bsc…jolq" --> from("from → 'gozala'") left -- "b2w…aqza" --> payload("payload → 'hi'") from -- "b4f…pmpa" --> from_k("'from'") from -- "b2p…afmq" --> from_v("'gozala'") payload -- "byi…mf6q" --> payload_k("'payload'") payload -- "bkv…treq" --> payload_v("'hi'") val_fold -- "b5r…t5cq" --> to("to → 'mikeal'") to -- "b3l…bfrq" --> to_k("'to'") to -- "bdv…7eda" --> to_v("'mikea'") object:::first message:::first obj_tag:::first key:::first val:::first val_tag:::second val_fold:::second left:::second to:::second to_k:::second to_v:::second classDef third fill:#4dabf7,stroke-width:2px,stroke:white classDef second fill:#e599f7,stroke-width:2px,stroke:white classDef first fill:#099268 `33:Tda2,loremIpsum = `Lorem ipsum dolor sit amet, consectetur adipiscing elit. Integer eros tellus, eleifend in condimentum id, porttitor a nibh. Ut posuere turpis ipsum, et semper felis fermentum a. Aenean blandit ultricies pharetra. Nam aliquet pharetra efficitur. Interdum et malesuada fames ac ante ipsum primis in faucibus. Aliquam gravida nisi vel tincidunt imperdiet. Morbi ut vulputate turpis. Mauris sodales felis vitae augue faucibus ornare. Quisque non ante justo. Pellentesque habitant morbi tristique senectus et netus et malesuada fames ac turpis egestas. Integer quis neque et turpis tincidunt maximus in ac risus. Sed efficitur ultricies diam vitae rutrum. Aliquam tincidunt ornare justo. Suspendisse mattis, nunc a consequat dignissim, sem tellus convallis ante, et pharetra eros erat quis ligula. Praesent pretium fringilla turpis, sit amet consectetur felis interdum sit amet. Pellentesque lacinia risus sit amet magna efficitur consectetur. Etiam luctus magna nisl, ac condimentum nibh tempus at. Duis auctor velit at ullamcorper tincidunt. Sed et tortor vitae odio dapibus tincidunt. Proin nec semper leo. Mauris cursus erat a congue sollicitudin. Nullam quis sem ligula. Nullam pulvinar finibus metus, eu suscipit tortor aliquam sagittis. Mauris ac ligula et diam posuere luctus vel eu ante. Pellentesque facilisis, turpis non eleifend pharetra, lectus eros eleifend augue, sed bibendum nisl tellus sit amet risus. Phasellus enim dolor, semper in eros ac, dapibus vestibulum purus. Aliquam posuere, odio ac sagittis consectetur, turpis arcu consectetur turpis, nec tempor turpis tortor id elit. Sed ut sagittis eros. Curabitur maximus erat a enim ultrices, luctus volutpat lorem cursus. Maecenas molestie tellus sapien, non faucibus urna convallis in. Etiam posuere dignissim mauris, sed ornare nunc ornare quis. Fusce nec rhoncus urna. Ut vestibulum mauris turpis, sed commodo lacus mattis a. Sed arcu massa, eleifend quis dolor eget, posuere luctus sem. In consequat, leo vel condimentum pulvinar, sem orci posuere metus, vitae aliquet leo est nec nulla. Suspendisse maximus, lorem quis convallis sodales, lorem ante consectetur augue, quis porta sem odio quis turpis. Nulla convallis turpis ligula, a imperdiet ligula eleifend quis. Interdum et malesuada fames ac ante ipsum primis in faucibus. Vivamus eget ante velit. Aliquam tempor fermentum orci et euismod. Donec sed scelerisque ante. Ut aliquam est eget fringilla mollis. Aenean sagittis ultricies nisi ut tincidunt. Integer finibus eleifend ullamcorper. Integer laoreet, metus vel consequat eleifend, lorem dolor rutrum mi, vel finibus nisi erat ut neque. Integer blandit sem vel enim malesuada, eget interdum justo fringilla. Aenean non rhoncus ante, sed rhoncus dolor. Praesent pretium felis a imperdiet lacinia. Duis ligula nunc, ultricies scelerisque suscipit id, maximus ut nulla. Pellentesque id mauris ex. Donec bibendum dolor eros, a ultrices arcu commodo ut. Cras sagittis urna id dolor rutrum lacinia. Mauris et venenatis velit. Suspendisse in quam viverra, feugiat justo nec, varius dui. Sed facilisis enim eu magna lobortis, vitae semper augue hendrerit. Suspendisse dictum, lectus vitae auctor fermentum, est quam consectetur sem, quis laoreet ex tortor ut orci. Suspendisse potenti. Cras imperdiet urna at sem lacinia facilisis. Donec sed dui eu erat faucibus gravida. Nunc cursus eros in quam semper sodales. Integer est magna, commodo sed scelerisque nec, blandit et elit. Aliquam erat volutpat.`34:T5c4,class Scalar extends Data { static toTree(value) { return new this({ value }); } constructor({ tag, format, value }) { super(); this.tag = tag; this.format = format; this.value = value; } get content() { return new Leaf(this.toBytes()); } toBytes() { return this.format.toBytes(this.value); } get hash() { return fold(this.toTree()); } get id() { return base32.encode(this.hash); } toReference() { return new Reference(this.hash); } toTree() { return [this.tag.hash, this.toBytes()]; } toDiagramLabel({ compact = false } = {}) { const { value } = this; switch (typeof value) { case "boolean": case "number": case "string": return compact ? String(value) : JSON.stringify(value); case "bigint": return `${Number(value)}`; default: { if (value === null) { return "null"; } else if (value instanceof Uint8Array) { return drawBytes(value); } else { throw new TypeError("Unexpected value"); } } } } toCompactDiagram() { return [drawNode(this)]; } toVerboseDiagram() { return [ drawNode(this), ...this.tag.toDiagram(), ...this.content.toDiagram(), drawLink(this.tag, this), drawLink(this.content, this) ]; } toDiagram({ compact = true } = {}) { return compact ? this.toCompactDiagram() : this.toVerboseDiagram(); } }35:T4fc,class Pair extends Data { static of(left, right) { return new Pair({ data: [left, right] }); } constructor({ data }) { super(); this.data = data; } get left() { return this.data[0]; } get right() { return this.data[1]; } toBytes() { return this.format.toBytes(this.data); } get hash() { return fold([this.left.hash, this.right.hash]); } get id() { return base32.encode(this.hash); } toTree() { return this.data; } toDiagram() { const [left, right] = this.data; return [ // drawLink(this, parent), // `${this.id}: ${this.toDiagramLabel({ // parent: this // })}`, drawNode(this), ...left.toDiagram(), ...right.toDiagram(), drawLink(left, this), drawLink(right, this) ]; } toDiagramLabel({ compact = false } = {}) { const members = [...this] .map(($) => $.toDiagramLabel()) .filter(Boolean) .join(", "); return compact ? members : `(${members})`; } *[Symbol.iterator]() { const [left, right] = this.data; if (left instanceof Pair) { yield* left; } else { yield left; } if (right instanceof Pair) { yield* right; } else { yield right; } } }36:T52b,class Record extends Structure { static brackets = "{}"; static tag = tag("merkle-structure:map/k+v/ref-tree"); static *entries(data) { if (data instanceof Map) { yield* data.entries(); } else if (data instanceof Set) { for (const value of data.values()) { yield [value, true]; } } else { yield* Object.entries(data); } } static *attributes(data, toTree) { const attributes = []; for (const [name, value] of this.entries(data)) { const key = toTree(name); const order = typeof name === "string" ? utf8(name) : toTree(key); attributes.push(Attribute.new(key, toTree(value), order)); } // yield* attributes.sort((left, right) => compare(left.hash, right.hash)); yield* attributes.sort((left, right) => compare(left.order, right.order)); } toTree() { return [this.tag.hash, this.toOperand().hash]; } toOperand() { return toOperand([...Record.attributes(this.data, this.toSubTree)]); } entries() { return Record.entries(this.data); } toAttributes() { return [...Record.attributes(this.data, this.toSubTree)]; } constructor({ data, toTree }) { super({ format: Record, brackets: Record.brackets, tag: Record.tag, data }); this.toSubTree = toTree; } }37:T64a,LINKS = ` [abstract data format]:#abstract-data-format [reference tree]:#reference-tree [merkle fold]:#merkle-fold [data locality]:#data-locality [Data Addressing]:#data-addressing [reference]:https://en.wikipedia.org/wiki/Reference_(computer_science) [null pointer]:https://en.wikipedia.org/wiki/Null_pointer [Single-precision floating-point format]:https://en.wikipedia.org/wiki/Single-precision_floating-point_format#IEEE_754_single-precision_binary_floating-point_format:_binary32 [Double-precision floating-point format]:https://en.wikipedia.org/wiki/Double-precision_floating-point_format [Variable Integer]:# [multiformats]:https://multiformats.io/ [Unsigned Variable Integer]:https://github.com/multiformats/unsigned-varint [LEB 128]:https://en.wikipedia.org/wiki/LEB128 [UTF-8]:https://en.wikipedia.org/wiki/UTF-8 [DAG-JSON]:https://ipld.io/specs/codecs/dag-json/spec [DAG-CBOR]:https://ipld.io/specs/codecs/dag-cbor/spec/ [IPLD Data Model]:https://ipld.io/docs/data-model/kinds/ [LEB128]:https://en.wikipedia.org/wiki/LEB128 [BAO]:https://github.com/oconnor663/bao/blob/master/docs/spec.md [billion dollar mistake]:https://www.infoq.com/presentations/Null-References-The-Billion-Dollar-Mistake-Tony-Hoare/ [\`Link\`]:https://ipld.io/docs/data-model/kinds/#link-kind [\`Null\`]:https://ipld.io/docs/data-model/kinds/#null-kind [tombstoning]:https://en.wikipedia.org/wiki/Tombstone_(data_store) [type identifier]:#type-identifier [Merkle tree]:https://en.wikipedia.org/wiki/Merkle_tree [CID]:https://docs.ipfs.tech/concepts/content-addressing/ [IPLD Link]:https://ipld.io/docs/schemas/features/links/ `38:[] 2e:{"title":"Merkle References","cells":[{"id":0,"value":"# Merkle References","pinned":false,"hidden":false,"mode":"md"},{"id":524,"value":"$30","pinned":false,"hidden":false,"mode":"md"},{"id":2455,"value":"### Null\n\nNull is represented as a [merkle fold] of two leaf nodes. Left node is the cryptographic hash of the UTF-8 encoded string `${Null.tag.name}` and describes binary encoding format of the right node. Right node is a byte array containing zero bytes.\n\n${LINKS}","pinned":false,"hidden":false,"mode":"md"},{"id":2457,"value":"show(() => from(null), \"VerboseReferenceTree\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":2447,"value":"### Boolean\n\nBooleans is represented as a [merkle fold] two leaf nodes. Left node is the cryptographic hash of the UTF-8 encoded string `${Bool.tag.name}` and describes binary encoding format of the right node. Right node is a byte array containing a single byte either `1` for `true` or `0` for false.\n\n${LINKS}","pinned":false,"hidden":false,"mode":"md"},{"id":2044,"value":"show(() => from(true), \"VerboseReferenceTree\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":2060,"value":"show(() => from(false), \"VerboseReferenceTree\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":2114,"value":"### Integer\n\nInteger is represented as a [merkle fold] of pair of leaf nodes. Left node is the cryptographic hash of the UTF-8 encoded string `${Integer.tag.name}` and describes binary encoding format of the right node. Right node is [LEB128] encoded integer.\n\n${LINKS}","pinned":false,"hidden":false,"mode":"md"},{"id":2131,"value":"show(() => from(1985), 'VerboseReferenceTree')","pinned":false,"hidden":false,"mode":"ojs"},{"id":2118,"value":"### Float\n\nFloat is represented as a [merkle fold] of pair of leaf nodes. Left node is the cryptographic hash of the UTF-8 encoded string `${Float.tag.name}` and describes binary encoding format of the right node. Right node is a float encoded in [double-precision floating-point format].\n\n${LINKS}","pinned":false,"hidden":false,"mode":"md"},{"id":2137,"value":"show(() => from(18.033), \"VerboseReferenceTree\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":2109,"value":"### String\n\nString is represented as a [merkle fold] of pair of leaf nodes. Left node is the cryptographic hash of the UTF-8 encoded string `${Text.tag.name}` and describes binary encoding format of the right node. Right node is string content encoded in UTF-8 encoding.\n\n${LINKS}","pinned":false,"hidden":false,"mode":"md"},{"id":2129,"value":"show(() => from(\"hello world\"), \"VerboseReferenceTree\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":2121,"value":"### Bytes\n\nBytes is represented as a [merkle fold] of pair of leaf nodes. Left node is the cryptographic hash of the UTF-8 encoded string `${Bytes.tag.name}` and describes binary encoding format of the right node. Right node is a byte array of the bytes.\n\n${LINKS}","pinned":false,"hidden":false,"mode":"md"},{"id":2140,"value":"show(() => from(new Uint8Array([1, 2, 3, 4])), \"VerboseReferenceTree\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":2032,"value":"### List\n\nLists are identified by a root of the binary merkle tree where left node is a hash of the list encoding format identifier and right node is a binary merkle tree built out of the list element identifiers.\n\n\nList is represented as a [merkle fold] of pair of nodes. Left node is the cryptographic hash of the UTF-8 encoded string `${List.tag.name}` and describes format of the right node. Right node is a [merkle fold] of [reference tree]s derived from the list elements.\n\n${LINKS}","pinned":false,"hidden":false,"mode":"md"},{"id":2157,"value":"show(() => from([1, 2, 3]))","pinned":false,"hidden":false,"mode":"ojs"},{"id":2162,"value":"Right node of the empty list is [merkle-fold] of zero elements\n\n${LINKS}","pinned":false,"hidden":false,"mode":"md"},{"id":2163,"value":"show(() => from([]))","pinned":false,"hidden":false,"mode":"ojs"},{"id":2172,"value":"show(() => from([\"hi\"]))","pinned":false,"hidden":false,"mode":"ojs"},{"id":2534,"value":"show(() => from([\"hi\", \"world\"]))","pinned":false,"hidden":false,"mode":"ojs"},{"id":2175,"value":"show(() => from([\"Point\", [\"x\", 1], [\"y\", 2]]))","pinned":false,"hidden":false,"mode":"ojs"},{"id":2147,"value":"### Map\n\nMap is represented as a [merkle fold] of pair of nodes. Left node is the cryptographic hash of the UTF-8 encoded string `${Record.tag.name}` and describes format of the right node. Right node is a [merkle fold] of attributes sorted by natural sort, where attribute is a [merkle fold] of the key [reference tree] and value [reference tree].\n\n${LINKS}","pinned":false,"hidden":false,"mode":"md"},{"id":3890,"value":"show(() => from({}))","pinned":false,"hidden":false,"mode":"ojs"},{"id":2223,"value":"show(() =>\n from({\n message: { from: \"gozala\", to: \"mikeal\", payload: \"hi\" }\n })\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":2234,"value":"Note that maps keys can also be arbitrary data structures","pinned":false,"hidden":false,"mode":"md"},{"id":2401,"value":"show(() => from(new Map([[{ x: 2 }, { y: 3 }]])))","pinned":true,"hidden":false,"mode":"ojs"},{"id":3930,"value":"show(() => from(new Set([{ x: 2 }])))","pinned":true,"hidden":false,"mode":"ojs"},{"id":4138,"value":"show(() => from(new Set([{ x: 2 }, { y: 3 }])))","pinned":true,"hidden":false,"mode":"ojs"},{"id":4132,"value":"show(() => from(\"\"))","pinned":true,"hidden":false,"mode":"ojs"},{"id":2246,"value":"### Inclusion Proofs\n\nIn the example above if we want to proove that our structure `bec..bv4a` contains string `\"Hi\"` we share the addresses of the siblings leading to the root. In the illustration below hashes for blue nodes constitute the proof, if we combine green node and sibling from the proof we can derive pink node and so on reaching the root.","pinned":false,"hidden":false,"mode":"md"},{"id":2281,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":2276,"value":"### Transport Flexibility\n\nIt is worth calling out that above merkle trees are just visualization of how address of the root is derived. Yet all other addresss are valid and data could be indexed by it if so desired. Put it differently granularity of the index is no longer baked it at the creation, instead it is a choice that varous actors can make when coming across the data.\n\nWe also gained flexibility in terms exchange packet sizes. Peer could ask to send around X `bytes` for `bec..bv4a`, sender can traverse the tree and pack substructures until desired packet size is met and send it over. Recepient is still able to verify that received data indeed corresponds to `bec..bv4a`. ","pinned":false,"hidden":false,"mode":"md"},{"id":2330,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":2323,"value":"### Codec Flexibility\n\nWe have descried how addresses for data are computed not how data sholud be encoded for storage. One could choose to store data in CBOR format, in plain JSON or whatever else. In fact when peers connect they could negotiate encoding they wish to use for the session and encode data accordingly.\n\nNote that most addresses are never stored, or send across the wire. They are simply derived from data. Only case where you want to send addresses is when you're doing a partial sync and want to reference subtree without having to transmit it.\n","pinned":false,"hidden":false,"mode":"md"},{"id":2475,"value":"---","pinned":false,"hidden":false,"mode":"md"},{"id":2484,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":2489,"value":"payload = new TextEncoder().encode(loremIpsum).slice(0, 1024 * 2)","pinned":true,"hidden":false,"mode":"ojs"},{"id":2494,"value":"function* split(payload) {\n let offset = 0;\n while (offset < payload.length) {\n yield payload.subarray(offset, offset + 1024);\n offset += 1024;\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2515,"value":"left = Blake2s(new Uint8Array([0]))","pinned":true,"hidden":false,"mode":"ojs"},{"id":1790,"value":"message = ({\n from: \"@gozala\",\n to: \"@mikeal\",\n payload: \"Hi\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1797,"value":"inline = ({\n message\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":3,"value":"import { CBOR, json, varint, base32, base64 } from \"@gozala/ipld\"","pinned":true,"hidden":false,"mode":"ojs"},{"id":131,"value":"SHA = import(\"https://esm.sh/@noble/hashes/sha256\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":194,"value":"sha256 = SHA.sha256","pinned":false,"hidden":false,"mode":"ojs"},{"id":2471,"value":"Blake3 = (await import(\"https://esm.sh/@noble/hashes/blake3\")).blake3","pinned":true,"hidden":false,"mode":"ojs"},{"id":2513,"value":"Blake2s = (await import(\"https://esm.sh/@noble/hashes/blake2s\")).blake2s","pinned":true,"hidden":false,"mode":"ojs"},{"id":439,"value":"leb128 = (source) => {\n let value = BigInt(source);\n let bytes = [];\n let more = true;\n while (more) {\n let byte = value & 0x7fn;\n value >>= 7n;\n if (\n (value === 0n && (byte & 0x40n) === 0n) ||\n (value === -1n && (byte & 0x40n) !== 0n)\n ) {\n more = false;\n } else {\n byte |= 0x80n;\n }\n bytes.push(Number(byte));\n }\n\n return new Uint8Array(bytes);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1095,"value":"doublePrecisionFloat = (value) => {\n DoublePrecisionFloat[0] = value;\n return new Uint8Array(DoublePrecisionFloat.buffer.slice());\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":487,"value":"DoublePrecisionFloat = new Float64Array(1)","pinned":false,"hidden":false,"mode":"ojs"},{"id":120,"value":"boolean = (value) => new Bool({ value })","pinned":false,"hidden":false,"mode":"ojs"},{"id":1722,"value":"unit = () => tag(\"\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":1744,"value":"pair = (left, right) => Pair.of(left, right)","pinned":false,"hidden":false,"mode":"ojs"},{"id":53,"value":"integer = (value) => new Integer({ value })","pinned":false,"hidden":false,"mode":"ojs"},{"id":78,"value":"float = (value) => new Float({ value })","pinned":false,"hidden":false,"mode":"ojs"},{"id":2415,"value":"nil = () => new Null()","pinned":false,"hidden":false,"mode":"ojs"},{"id":101,"value":"string = (value) => new Text({ value })","pinned":false,"hidden":false,"mode":"ojs"},{"id":123,"value":"bytes = (value) => new Bytes({ value })","pinned":false,"hidden":false,"mode":"ojs"},{"id":126,"value":"scalar = (value) => {\n switch (typeof value) {\n case \"number\":\n return Number.isInteger(value) ? integer(value) : float(value);\n case \"bigint\":\n return integer(value);\n case \"boolean\":\n return boolean(value);\n case \"string\":\n return string(value);\n default: {\n if (value === null) {\n return nil(value);\n } else if (value instanceof Uint8Array) {\n return bytes(value);\n } else {\n throw new Error(`Unsupported data type ${JSON.stringify(value)}`);\n }\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3557,"value":"tag = (name) => new Tag(name)","pinned":true,"hidden":false,"mode":"ojs"},{"id":129,"value":"attribute = (name, value) => new Attribute(from(name), from(value))","pinned":false,"hidden":false,"mode":"ojs"},{"id":137,"value":"concat = (operand, modifier) => {\n const bytes = new Uint8Array(operand.length + modifier.length);\n bytes.set(operand, 0);\n bytes.set(modifier, operand.length);\n return bytes;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":153,"value":"hash = (value) => from(value).hash","pinned":false,"hidden":false,"mode":"ojs"},{"id":144,"value":"list = (...elements) => from(elements)","pinned":false,"hidden":false,"mode":"ojs"},{"id":176,"value":"map = (source) => from(source)","pinned":false,"hidden":false,"mode":"ojs"},{"id":179,"value":"compare = (self, other) => {\n if (self == null) {\n return other == null ? 0 : -1;\n } else if (other == null) {\n return 1;\n } else {\n const count = Math.min(self.length, other.length);\n let offset = 0;\n while (offset < count) {\n const delta = self[offset] - other[offset];\n if (delta < 0) {\n return -1;\n } else if (delta > 0) {\n return 1;\n } else {\n offset++;\n }\n }\n\n const delta = self.length - other.length;\n return delta < 0 ? -1 : delta > 0 ? 1 : 0;\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3641,"value":"from = toTree","pinned":true,"hidden":false,"mode":"ojs"},{"id":1258,"value":"merklefold = (leaves) => {\n if (leaves.length === 0) {\n return unit();\n } else if (leaves.length === 1) {\n return leaves[0];\n }\n\n const layer = [...leaves];\n while (layer.length > 1) {\n const nodes = layer.splice(0);\n const width = nodes.length;\n let offset = 0;\n while (offset < width) {\n const left = nodes[offset++];\n const right = nodes[offset++];\n\n if (right) {\n layer.push(Pair.of(left, right));\n } else {\n layer.push(left);\n }\n }\n }\n\n return layer[0];\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2988,"value":"function toTree(data) {\n const type = infer(data);\n return type.toTree === toTree ? data : type.toTree(data, toTree);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":4166,"value":"refer = (data) => toTree(data).hash","pinned":true,"hidden":false,"mode":"ojs"},{"id":2991,"value":"infer = (data) => {\n switch (typeof data) {\n case \"symbol\":\n return Tag;\n case \"number\":\n return Number.isInteger(data) ? Integer : Float;\n case \"bigint\":\n return Integer;\n case \"boolean\":\n return Bool;\n case \"string\":\n return Text;\n case \"object\": {\n if (data === null) {\n return Null;\n } else if (data instanceof Uint8Array) {\n return Bytes;\n } else if (Array.isArray(data)) {\n return List;\n } else if (data instanceof Data) {\n return Data;\n } else {\n return Record;\n }\n }\n default: {\n throw new TypeError(`Unknown type ${data}`);\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":208,"value":"id = (data) => toTree(data).id","pinned":false,"hidden":false,"mode":"ojs"},{"id":715,"value":"utf8 = (text) => new TextEncoder().encode(text)","pinned":false,"hidden":false,"mode":"ojs"},{"id":793,"value":"drawLink = (to, from) =>\n `${from ? from.id : \"[*]\"} --> ${to.id}: ${drawEdge(to.id)}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1008,"value":"drawEdge = (id) =>\n id.length < 3 ? \"\" : id.length < 7 ? id : `${id.slice(0, 3)}…${id.slice(-4)}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2049,"value":"drawBytes = (bytes) =>\n bytes.length === 0\n ? \" \"\n : bytes.length > 7\n ? `${hexdump(bytes.subarray(0, 3))}…${hexdump(bytes.subarray(-3))}`\n : `${hexdump(bytes)}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":803,"value":"drawNode = (node) => `${node.id}: ${node.toDiagramLabel()}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2675,"value":"class Data {\n static toTree(data) {\n return data;\n }\n toStateDiagram(options) {\n return [\n \"stateDiagram-v2\",\n ...new Set(this.toDiagram(options)),\n drawLink(this, null),\n \"\"\n ];\n }\n toMermaid(options) {\n return mermaid`${this.toStateDiagram(options).join(\"\\n\")}`;\n }\n [show] = {\n ReferenceTree: (view) => view.toMermaid(),\n VerboseReferenceTree: (view) => view.toMermaid({ compact: false }),\n StateDiagram: (view) => html`

\\`\\`\\`mermaid\n${view.toStateDiagram().join(\"\\n\")}\n\\`\\`\\`

`,\n VerboseStateDiagram: (view) => html`

\\`\\`\\`mermaid\n${view.toStateDiagram({ compact: false }).join(\"\\n\")}\n\\`\\`\\`

`\n };\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2582,"value":"class Reference extends Data {\n /**\n * @param {Uint8Array} bytes\n */\n constructor(bytes) {\n super();\n this[\"merkle/reference\"] = bytes;\n }\n get hash() {\n return this[\"merkle/reference\"];\n }\n get id() {\n return base32.encode(this.hash);\n }\n\n toDiagramLabel() {\n return \"[*]\";\n }\n toDiagram() {\n return [`state ${this.id} <>`];\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3978,"value":"show(() => from({ message: { hello: \"world\" } }))","pinned":true,"hidden":false,"mode":"ojs"},{"id":4092,"value":"from({\n record: { message: {} }\n}).toMermaid()","pinned":true,"hidden":false,"mode":"ojs"},{"id":4097,"value":"from({\n record: { message: {} }\n}).toOperand().model.key","pinned":true,"hidden":false,"mode":"ojs"},{"id":4099,"value":"toTree({ message: {} })","pinned":true,"hidden":false,"mode":"ojs"},{"id":2603,"value":"class Tag extends Data {\n constructor(name) {\n super();\n this.name = name;\n this.hash = sha256(utf8(name));\n this.id = base32.encode(this.hash);\n }\n static toTree(symbol) {\n return new Tag(symbol.description);\n }\n toDiagramLabel() {\n return this.name == \"\" ? \" \" : `${this.name.replace(\":\", \"ː\")}`;\n }\n toDiagram() {\n return [`${this.id}: ${this.toDiagramLabel()}`];\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2785,"value":"class Leaf extends Data {\n constructor(bytes) {\n super();\n this.bytes = bytes;\n }\n get hash() {\n return this.bytes;\n }\n get id() {\n return base32.encode(this.hash);\n }\n toDiagramLabel() {\n const bytes = this.bytes;\n return bytes.length === 0\n ? \" \"\n : bytes.length > 7\n ? `${hexdump(bytes.subarray(0, 3))}…${hexdump(bytes.subarray(-3))}`\n : `${hexdump(bytes)}`;\n }\n toDiagram() {\n return [drawNode(this)];\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2691,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":2825,"value":"class Integer extends Scalar {\n static name = \"Integer\";\n static tag = tag(\"merkle-structure:integer/leb128\");\n static toBytes = leb128;\n constructor({ value }) {\n super({\n value,\n format: Integer,\n tag: Integer.tag\n });\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2830,"value":"class Float extends Scalar {\n static tag = tag(\"merkle-structure:float/double-precision\");\n static toBytes = doublePrecisionFloat;\n constructor({ value }) {\n super({\n value,\n format: Float,\n tag: Float.tag\n });\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2846,"value":"class Null extends Scalar {\n static tag = tag(\"merkle-structure:null\");\n static toBytes = () => new Uint8Array(0);\n constructor() {\n super({ value: null, format: Null, tag: Null.tag });\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2857,"value":"class Bytes extends Scalar {\n static tag = tag(\"merkle-structure:bytes/raw\");\n static toBytes = (value) => value;\n constructor({ value }) {\n super({ value, tag: Bytes.tag, format: Bytes });\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2860,"value":"class Bool extends Scalar {\n static name = \"Boolean\";\n static tag = tag(\"merkle-structure:boolean/byte\");\n static toBytes = (value) => new Uint8Array([value ? 1 : 0]);\n constructor({ value }) {\n super({ value, tag: Bool.tag, format: Bool });\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2866,"value":"class Text extends Scalar {\n static name = \"String\";\n static tag = tag(\"merkle-structure:string/utf-8\");\n static toBytes = utf8;\n constructor({ value }) {\n super({ value, tag: Text.tag, format: Text });\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2696,"value":"/**\n * @param {Uint8Array[]} leaves\n */\nfold = (leaves, hash = sha256) => {\n if (leaves.length === 0) {\n return hash(new Uint8Array(0));\n } else if (leaves.length === 1) {\n return leaves[0];\n }\n\n const layer = [...leaves];\n while (layer.length > 1) {\n const nodes = layer.splice(0);\n const width = nodes.length;\n let offset = 0;\n while (offset < width) {\n const left = nodes[offset++];\n const right = nodes[offset++];\n\n if (right) {\n layer.push(hash(concat(left, right)));\n } else {\n layer.push(left);\n }\n }\n }\n\n return layer[0];\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3047,"value":"toOperand = (operands) => {\n switch (operands.length) {\n case 0:\n return unit();\n case 1: {\n return operands[0];\n }\n default: {\n const layer = [...operands];\n while (layer.length > 1) {\n const nodes = layer.splice(0);\n const width = nodes.length;\n let offset = 0;\n while (offset < width) {\n const left = nodes[offset++];\n const right = nodes[offset++];\n if (right) {\n layer.push(Pair.of(left, right));\n } else {\n layer.push(left);\n }\n }\n }\n return layer[0];\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":366,"value":"class Attribute extends Data {\n static new(key, value, order) {\n return new Attribute({\n model: { key, value, order }\n });\n }\n get order() {\n return this.model.order;\n }\n get hash() {\n const { key, value } = this.model;\n return fold([key.hash, value.hash]);\n }\n get id() {\n return base32.encode(this.hash);\n }\n constructor({ model }) {\n super();\n this.model = model;\n }\n toDiagramLabel({ compact = false } = {}) {\n const { key, value } = this.model;\n return compact\n ? `${key.toDiagramLabel({ compact: true })}`\n : `${key.toDiagramLabel({\n compact: true\n })} → ${value.toDiagramLabel()}`;\n }\n toDiagram() {\n const { key, value } = this.model;\n return [\n drawNode(this),\n ...key.toDiagram(),\n ...value.toDiagram(),\n drawLink(key, this),\n drawLink(value, this)\n ];\n }\n *[Symbol.iterator]() {\n yield this;\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":301,"value":"$35","pinned":false,"hidden":false,"mode":"ojs"},{"id":1242,"value":"class Structure extends Data {\n constructor({ brackets, data, tag, format }) {\n super();\n this.tag = tag;\n this.format = format;\n this.data = data;\n this.brackets = brackets;\n }\n\n static toTree(data, toTree) {\n return new this({ data, toTree });\n }\n\n get hash() {\n return fold(this.toTree());\n }\n get id() {\n return base32.encode(this.hash);\n }\n\n toReference() {\n return new Reference(this.hash);\n }\n\n toOperator() {\n return this.tag;\n }\n\n toDiagram() {\n return [\n drawNode(this),\n ...this.toOperator().toDiagram(),\n ...this.toOperand().toDiagram(),\n drawLink(this.toOperator(), this),\n drawLink(this.toOperand(), this)\n ];\n }\n\n toDiagramLabel() {\n const [open, close] = this.brackets;\n\n return `${open}${this.toOperand().toDiagramLabel({\n compact: true\n })}${close}`;\n }\n\n toString() {\n return this.toDiagramLabel();\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2917,"value":"class List extends Structure {\n static brackets = \"[]\";\n static tag = tag(\"merkle-structure:list/item/ref-tree\");\n\n constructor({ data, toTree }) {\n super({\n format: List,\n brackets: List.brackets,\n tag: List.tag,\n data\n });\n\n this.toSubTree = toTree;\n }\n\n toTree() {\n return [this.tag.hash, this.toOperand().hash];\n }\n\n toOperand() {\n return toOperand(this.data.map(this.toSubTree));\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3286,"value":"$36","pinned":false,"hidden":false,"mode":"ojs"},{"id":1811,"value":"cid = async (promise) =>\n `[${await promise}](https://cid.ipfs.tech/#${await promise})`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1948,"value":"hexdump = (bytes) =>\n `${[...bytes]\n .map((byte) => `0x${byte.toString(16).padStart(2, \"0\").toUpperCase()}`)\n .join(\" \")}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1977,"value":"bits = (uint8Array) => {\n let bits = \"0b\";\n for (let byte of uint8Array) {\n bits += byte.toString(2).padStart(8, \"0\") + \"_\";\n }\n return bits.slice(0, -1);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":4155,"value":"function compile(tree, hash = sha256) {\n // if (tree.length === 1) {\n // const [node] = tree\n // if (node instanceof Uint8Array) {\n // return hash(node)\n // } else {\n // return hash(compile(node, hash))\n // }\n // }\n\n const leaves = [];\n for (const node of tree) {\n if (node instanceof Uint8Array) {\n leaves.push(node);\n } else {\n leaves.push(compile(node, hash));\n }\n }\n\n return fold(leaves, hash);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1987,"value":"import { show, syntax } from \"@gozala/show\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":2037,"value":"$37","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W38","stdlib":"1","titling":"auto"}