diff options
| -rw-r--r-- | hyperdrive.md | 65 |
1 files changed, 47 insertions, 18 deletions
diff --git a/hyperdrive.md b/hyperdrive.md index aab270d..1e586ee 100644 --- a/hyperdrive.md +++ b/hyperdrive.md @@ -1,9 +1,20 @@ -## Flat Trees +# Hyperdrive + +Hyperdrive is the peer-to-peer data distribution protocol that powers Dat. It consists of two parts. First there is hypercore which is the core protocol and swarm that handles distributing append-only logs of any binary data. The second part is hyperdrive which adds a filesystem specific protocol on top of hypercore. + +## Hypercore + +The goal of hypercore is to distribute append-only logs across a network of peers. Peers download parts of the logs from other peers and can choose to only download the parts of a log they care about. Logs can contain arbitrary binary data payloads. + +## How Hypercore works + +### Flat Trees A flat tree is a simple way represent a binary tree as a list. It also allows you to identify every node of a binary tree with a numeric index. Both of these properties makes it useful in distributed applications to simplify wire protocols that uses tree structures. -It is described in the PPSP paper and a node version is available through the [flat-tree](https://github.com/mafintosh/flat-tree) module. -A sample flat tree spanning 4 blocks of data looks like this +Flat trees are described in [PPSP RFC 7574 as "Bin numbers"](https://datatracker.ietf.org/doc/rfc7574/?include_text=1) and a node version is available through the [flat-tree](https://github.com/mafintosh/flat-tree) module. + +A sample flat tree spanning 4 blocks of data looks like this: ``` 0 @@ -16,6 +27,7 @@ A sample flat tree spanning 4 blocks of data looks like this ``` The even numbered entries represent data blocks (leaf nodes) and odd numbered entries represent parent nodes that have two children. + The depth of an tree node can be calculated by counting the number of trailing 1s a node has in binary notation. ``` @@ -24,9 +36,11 @@ The depth of an tree node can be calculated by counting the number of trailing 1 4 in binary = 100 (zero trailing 1s) ``` -1 is the parent of (0, 2), 5 is the parent of (4, 6), and 3 is the parent of (1, 5) +1 is the parent of (0, 2), 5 is the parent of (4, 6), and 3 is the parent of (1, 5). + If the number of leaf nodes is a power of 2 the flat tree will only have a single root. -Otherwise it'll have more than one. As an example here is a tree with 6 leafs + +Otherwise it'll have more than one. As an example here is a tree with 6 leafs: ``` 0 @@ -42,7 +56,7 @@ Otherwise it'll have more than one. As an example here is a tree with 6 leafs 10 ``` -The roots spanning all the above leafs are 3 an 9. Throughout this document we'll use following tree termonology +The roots spanning all the above leafs are 3 an 9. Throughout this document we'll use following tree terminology: * `parent` - a node that has two children (odd numbered) * `leaf` - a node with no children (even numbered) @@ -52,10 +66,12 @@ The roots spanning all the above leafs are 3 an 9. Throughout this document we'l ## Merkle Trees A merkle tree is a binary tree where every leaf is a hash of a data block and every parent is the hash of both of its children. + Merkle trees are useful for ensuring the integrity of content. Let's look at an example. Assume we have 4 data blocks, `(a, b, c, d)` and let `h(x)` be a hash function (the hyperdrive stack uses sha256 per default). -Using flat-tree notation the merkle tree spanning these data blocks looks like this + +Using flat-tree notation the merkle tree spanning these data blocks looks like this: ``` 0 = h(a) @@ -67,8 +83,9 @@ Using flat-tree notation the merkle tree spanning these data blocks looks like t 6 = h(d) ``` -An interesting property of merkle trees is that the node 3 hashes the entire data set. Therefore we only need to trust node 3 to verify all data. However as we learned above there will only be a single root if there is a power of two data blocks. Again lets expand our data set to contain 6 items `(a, b, c, d, e, f)` +An interesting property of merkle trees is that the node 3 hashes the entire data set. Therefore we only need to trust node 3 to verify all data. However as we learned above there will only be a single root if there is a power of two data blocks. +Again lets expand our data set to contain 6 items `(a, b, c, d, e, f)`: ``` 0 = h(a) @@ -85,16 +102,19 @@ An interesting property of merkle trees is that the node 3 hashes the entire dat ``` To ensure always have only a single root we'll simply hash all the roots together again. At most there will be `log2(number of data blocks)`. + In addition to hashing the roots we'll also include a bin endian uint64 binary representation of the corresponding node index. -Using the two above examples the final hashes would be +Using the two above examples the final hashes would be: ``` hash1 = h(uint64be(#3) + 3) hash2 = h(uint64be(#9) + 9 + uint64be(#3) + 3) ``` -Each of these hashes can be used to fully verify each of the trees. Let's look at another example. Assume we trust `hash1` and another person wants to send block `0` to us. To verify block `0` the other person would also have to send the sibling hash and uncles until it reaches a root and the other missing root hashes. For the first tree that would mean hashes `(2, 5)`. Using these hashes we can reproduce `hash1` in the following way +Each of these hashes can be used to fully verify each of the trees. Let's look at another example. Assume we trust `hash1` and another person wants to send block `0` to us. To verify block `0` the other person would also have to send the sibling hash and uncles until it reaches a root and the other missing root hashes. For the first tree that would mean hashes `(2, 5)`. + +Using these hashes we can reproduce `hash1` in the following way: ``` 0 = h(block received) @@ -104,14 +124,16 @@ Each of these hashes can be used to fully verify each of the trees. Let's look a 5 = (hash received) ``` -If `h(uint64be(#3) + 3) == hash1` then we know that data we received from the other person is correct. They sent us `a` and the corresponding hashes -. Since we only need uncle hashes to verify the block the amount of hashes we need is at worst `log2(number-of-blocks)` and the roots of the merkle trees which has the same complexity. +If `h(uint64be(#3) + 3) == hash1` then we know that data we received from the other person is correct. They sent us `a` and the corresponding hashes. + +Since we only need uncle hashes to verify the block the amount of hashes we need is at worst `log2(number-of-blocks)` and the roots of the merkle trees which has the same complexity. A merkle tree generator is available on npm through the [merkle-tree-stream](https://github.com/mafintosh/merkle-tree-stream) module. ## Merkle Tree Deduplication Merkle trees have another great property. They make it easy to deduplicate content that is similar. + Assume we have two similar datasets: ``` @@ -119,7 +141,9 @@ Assume we have two similar datasets: (a, b, c, d, f) ``` -These two datasets are the same except their last element is different. When generating merkle trees for the two data sets you'd get two different root hashes out. However if we look a the flat-tree notation for the two trees +These two datasets are the same except their last element is different. When generating merkle trees for the two data sets you'd get two different root hashes out. + +However if we look a the flat-tree notation for the two trees: ``` 0 @@ -146,13 +170,16 @@ This means that two datasets share a similar sequence of data the merkle tree he ## Signed Merkle Trees As described above the top hash of a merkle tree is the hash of all its content. This has both advantages and disadvanteges. -An advantage is that you can always reproduce a merkle tree simply by having the data contents of a merkle tree. An disadvantage is every time you add content to your data set your merkle tree hash changes and you'll need to re-distribute the new hash. -Using a bit of cryptography however we can make our merkle tree appendable. First generate a cryptographic key pair that can be used to sign data. Using Eliptic Curve Cryptography keys are compact in size (32 bytes public key, similar to a sha256 hash). A key pair (public key, secret key) can be used to sign data. Signing data means that if you trust a public key and you receive data and a signature for that data you can verify that a signature was generated with the corresponding secret key. +An advantage is that you can always reproduce a merkle tree simply by having the data contents of a merkle tree. + +A disadvantage is every time you add content to your data set your merkle tree hash changes and you'll need to re-distribute the new hash. + +Using a bit of cryptography however we can make our merkle tree appendable. First generate a cryptographic key pair that can be used to sign data using [ed25519](https://ed25519.cr.yp.to/) keys, as they are compact in size (32 byte public keys). A key pair (public key, secret key) can be used to sign data. Signing data means that if you trust a public key and you receive data and a signature for that data you can verify that a signature was generated with the corresponding secret key. How does this relate to merkle trees? Instead of distributing the hash of a merkle tree we can distribute our public key instead. We then use our secret key to continously sign the merkle trees of our data set every time we append to it. -Assume we have a data set with only a single item in it `(a)` and a key pair `(secret, public)` +Assume we have a data set with only a single item in it `(a)` and a key pair `(secret, public)`: ``` (a) @@ -162,7 +189,7 @@ We generate a merkle tree for this data set which will have the roots `0` and si If we want to send `a` to another person and they trust our public key we simply send `a` and the uncles needed to generate the roots plus our signature. -If we append a new item to our data set we simply do the same thing +If we append a new item to our data set we simply do the same thing: ``` (a, b) @@ -177,6 +204,7 @@ In general you should send as wide as possible signed tree back when using signe ## Block Tree Digest When asking for a block of data we want to reduce the amount of duplicate hashes that are sent back. + In the merkle tree example for from earlier we ended up sending two hashes `(2, 5)` to verify block `0`. ``` @@ -194,6 +222,7 @@ In the merkle tree example for from earlier we ended up sending two hashes `(2, Now if we ask for block `1` afterwards (`2` in flat tree notation) the other person doesn't need to send us any new hashes since we already received the hash for `2` when fetching block `0`. If we only use non-signed merkle trees the other person can easily calculate which hashes we already have if we tell them which blocks we've got. + This however isn't always possible if we use a signed merkle tree since the roots are changing. In general it also useful to be able to communicate that you have some hashes already without disclosing all the blocks you have. To communicate which hashes we have just have to communicate two things. Which uncles we have and weather or not we any parent node that can verify the tree. @@ -217,4 +246,4 @@ So using this digest the person can easily figure out that they only need to sen The bit vector `1` (only contains a single one) means that we already have all the hashes we need so just send us the block. -These digests are very compatch in size, only `(log2(number-of-blocks) + 2) / 8` bytes needed in the worst case. For example if you are sharing one trillion blocks of data the digest would be `(log2(1000000000000) + 2) / 8 ~= 6` bytes long +These digests are very compatch in size, only `(log2(number-of-blocks) + 2) / 8` bytes needed in the worst case. For example if you are sharing one trillion blocks of data the digest would be `(log2(1000000000000) + 2) / 8 ~= 6` bytes long. |