diff options
Diffstat (limited to 'hyperdrive.md')
| -rw-r--r-- | hyperdrive.md | 220 |
1 files changed, 220 insertions, 0 deletions
diff --git a/hyperdrive.md b/hyperdrive.md new file mode 100644 index 0000000..aab270d --- /dev/null +++ b/hyperdrive.md @@ -0,0 +1,220 @@ +## 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 + +``` +0 + 1 +2 + 3 +4 + 5 +6 +``` + +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. + +``` +5 in binary = 101 (one trailing 1) +3 in binary = 011 (two trailing 1s) +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) +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 + +``` +0 + 1 +2 + 3 +4 + 5 +6 + +8 + 9 +10 +``` + +The roots spanning all the above leafs are 3 an 9. Throughout this document we'll use following tree termonology + +* `parent` - a node that has two children (odd numbered) +* `leaf` - a node with no children (even numbered) +* `sibling` - the other node with whom a node has a mutual parent +* `uncle` - a parent's sibling + +## 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 + +``` +0 = h(a) + 1 = h(0 + 2) +2 = h(b) + 3 = h(1 + 5) +4 = h(c) + 5 = h(4 + 6) +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)` + + +``` +0 = h(a) + 1 = h(0 + 2) +2 = h(b) + 3 = h(1 + 5) +4 = h(c) + 5 = h(4 + 6) +6 = h(d) + +8 = h(e) + 9 = h(8 + 10) +10 = h(f) +``` + +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 + +``` +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 + +``` +0 = h(block received) + 1 = h(0 + 2) +2 = (hash received) + 3 = h(1 + 5) + 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. + +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: + +``` +(a, b, c, d, e) +(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 + +``` +0 + 1 +2 + 3 +4 + 5 +6 + +8 +``` + +We'll notice that the hash stored at 3 will be the same for both trees since the first four blocks are the same. Since we also send uncle hashes when sending a block of data we'll receive the hash for 3 when we request any block. If we maintain a simple index that maps a hash into the range of data it covers we can detect that we already have the data spanning 3 and we won't need to re-download that from another person. + +``` +1 -> (a, b) +3 -> (a, b, c, d) +5 -> (c, d) +``` + +This means that two datasets share a similar sequence of data the merkle tree helps you detect that. + +## 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. + +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)` + +``` +(a) +``` + +We generate a merkle tree for this data set which will have the roots `0` and sign the hash of these roots (see the merkle tree section) with our secret key. + +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 + +``` +(a, b) +``` + +Notice that all new signatures verify the entire dataset since they all sign a merkle tree that spans all data. This serves two purposes. First of all it makes sure that the dataset publisher cannot change old data. It also ensures that the publisher cannot share different versions of the same dataset to different persons without the other people noticing it (at some point they'll get a signature for the same node index that has different hashes if they talk to multiple people). + +This technique has the added benefit that you can always convert a signed merkle tree to a normal unsigned one if you wish (or turn an unsigned tree into a signed tree). + +In general you should send as wide as possible signed tree back when using signed merkle trees as that lowers the amount of signatures the other person needs to verify which has a positive performance impact for some platforms. It will also allow other users to more quickly detect if a tree has duplicated content. + +## 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`. + +``` +// If we trust 3, 2 and 5 are needed to verify 0 + +0 + 1 +2 + 3 +4 + 5 +6 +``` + +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. + +Looking at the above tree that means we want to fetch block `0` we need to communicate wheather of not we already have the uncles `(2, 5)` and the following parent `3`. This information can be compressed into very small bit vector using the following scheme. + +Let the trailing bit donate whether or not the leading bit is a parent and not a uncle. Let the previous trailing bits donate donate wheather or not we have the next uncle. + +For example for block `0` the following bit vector `1011` is decoded the following way + +``` +// for block 0 + +101(1) <-- tell us that the last bit is a parent and not an uncle +10(1)1 <-- we already have the first uncle, 2 so don't send us that +1(0)11 <-- we don't have the next uncle, 5 +(1)000 <-- the final bit so this is parent. we have the next parent, 3 +``` + +So using this digest the person can easily figure out that they only need to send us one hash, `5` for us to verify block `0`. + +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 |