3 ms·

So if I understand correctly from the spec, the point is to be able to have slices that include the content and the necessary metadata that confirms this is a p

by rakoo 7y ago

So if I understand correctly from the spec, the point is to be able to have slices that include the content and the necessary metadata that confirms this is a part of the original content. This is something that is already done with merkle tree hashes: specified in bittorrent V2 (http://bittorrent.org/beps/bep_0052.html http://bittorrent.org/beps/bep_0052.html) (although I don't know if any client implements it) and already working in dat (https://datprotocol.github.io/how-dat-works https://datprotocol.github.io/how-dat-works): when receiving a piece, you also receive - its hash - the hash of the brother so you can derive the hash of the parent - the hash of the uncle so you can derive the grand parent - etc... Up until the last brother before the root, so you can verify the root hash In bao it seems to be the opposite: the included hashes are the ones from the direct ancestors ? So how can bao trust the whole chain ? Or maybe there's something in BLAKE3 that explains how "Chaining Values" fix it ?

oconnor663 7y ago
> This is something that is already done with merkle tree hashes Yes, BLAKE3 is a Merkle tree, and what Bao is doing is conceptually similar to BitTorrent. (BEP 30 is even cited in the BLAKE3 spec.) Bao's goal is to be a general-purpose wire format and implementation library, for any application that needs verified streaming. Applications that use BLAKE3 for generic file hashing today can also start doing verified streaming at any point in the future, without needing any other trusted metadata.
- rakoo 7y ago
  Understood. My question was more about what is the exact content of a slice, apart from the chunk: is it the sibling's hash and the uncles hash ? Something else ?
  - oconnor663 7y ago
    It's the set of parent nodes on the path from the root to the chunk(s), plus the chunks themselves. Parent nodes contain the hashes / chaining values of their two children, so you could also think of this as including sibling hashes. For example, consider this tree representing a 4 KiB file: root / \ parent1 parent2 / \ / \ chunk1 chunk2 chunk3 chunk4 Say we build a slice containing only chunk2. The contents of that slice will be: [4096][root][parent1][chunk2] The parent node parent1 is [hash of chunk1][hash of chunk2], and the root node is [hash of parent1][hash of parent2]. The 8-byte total length on the front (4096) is the same as in the full encoding; it defines the structure of the tree, so the decoder knows how many parent nodes to expect. For more details: https://github.com/oconnor663/bao/blob/master/docs/spec.md https://github.com/oconnor663/bao/blob/master/docs/spec.md This is my first time looking at the Dat protocol. Thanks for pointing that out.
    - rakoo 7y ago
      Ok so the intermediary nodes are the concatenation of the children, that's what I missed. Thanks a lot for the details, and even more for the rest of your work !
oconnor663 7y ago
> already working in dat (https://datprotocol.github.io/how-dat-works https://datprotocol.github.io/how-dat-works) I just looked over the doc at https://datprotocol.github.io/how-dat-works https://datprotocol.github.io/how-dat-works, particularly the section on the tree hash. It looks pretty reasonable, and definitely similar to BLAKE3. I think one practical downside of the Dat approach is that root finalization is always done as a separate hashing step. So for example, if I hash the short string "hello world", I have to compute one chunk hash and then one root hash, for a total of two calls to the compression function. Compare that to BLAKE3, which will only do a single compression there, by setting both the chunk flags and the root flag for that one block. This difference is probably totally negligible for Dat's intended use case, where network round trip time is going to completely dwarf hashing time for small inputs. But for a general-purpose hash function you don't want to cut your small input performance in half. A bigger philosophical difference is that Dat doesn't specify a particular chunk size. Again this makes sense for their use case, since you might want to experiment with fancy things like Rabin fingerprinting. Looks like they discuss that here: https://stackoverflow.com/a/51604110/823869 https://stackoverflow.com/a/51604110/823869. But for a cryptographic hash, it's important that every file has exactly one hash, and a fixed chunk size is required. Another upside of a fixed chunk size is that you really cut down on metadata; the 8-byte length at the front of an encoding or a slice determines the structure of the entire tree.
- rakoo 7y ago
  Indeed content-based chunking definitely has appeal, I'm thinking about all the backup softwares that use it as a smart way to cut down on total size in a way that leaves all snapshots independent from each other. On the other hand having a well-defined format and the tools to play with like you provide is definitely better to have it spread, so kudos for it.

by rakoo 7y ago

oconnor663 7y ago

> This is something that is already done with merkle tree hashes Yes, BLAKE3 is a Merkle tree, and what Bao is doing is conceptually similar to BitTorrent. (BEP 30 is even cited in the BLAKE3 spec.) Bao's goal is to be a general-purpose wire format and implementation library, for any application that needs verified streaming. Applications that use BLAKE3 for generic file hashing today can also start doing verified streaming at any point in the future, without needing any other trusted metadata.

rakoo 7y ago
Understood. My question was more about what is the exact content of a slice, apart from the chunk: is it the sibling's hash and the uncles hash ? Something else ?
- oconnor663 7y ago
  It's the set of parent nodes on the path from the root to the chunk(s), plus the chunks themselves. Parent nodes contain the hashes / chaining values of their two children, so you could also think of this as including sibling hashes. For example, consider this tree representing a 4 KiB file: root / \ parent1 parent2 / \ / \ chunk1 chunk2 chunk3 chunk4 Say we build a slice containing only chunk2. The contents of that slice will be: [4096][root][parent1][chunk2] The parent node parent1 is [hash of chunk1][hash of chunk2], and the root node is [hash of parent1][hash of parent2]. The 8-byte total length on the front (4096) is the same as in the full encoding; it defines the structure of the tree, so the decoder knows how many parent nodes to expect. For more details: https://github.com/oconnor663/bao/blob/master/docs/spec.md https://github.com/oconnor663/bao/blob/master/docs/spec.md This is my first time looking at the Dat protocol. Thanks for pointing that out.
  - rakoo 7y ago
    Ok so the intermediary nodes are the concatenation of the children, that's what I missed. Thanks a lot for the details, and even more for the rest of your work !

oconnor663 7y ago

> already working in dat (https://datprotocol.github.io/how-dat-works https://datprotocol.github.io/how-dat-works) I just looked over the doc at https://datprotocol.github.io/how-dat-works https://datprotocol.github.io/how-dat-works, particularly the section on the tree hash. It looks pretty reasonable, and definitely similar to BLAKE3. I think one practical downside of the Dat approach is that root finalization is always done as a separate hashing step. So for example, if I hash the short string "hello world", I have to compute one chunk hash and then one root hash, for a total of two calls to the compression function. Compare that to BLAKE3, which will only do a single compression there, by setting both the chunk flags and the root flag for that one block. This difference is probably totally negligible for Dat's intended use case, where network round trip time is going to completely dwarf hashing time for small inputs. But for a general-purpose hash function you don't want to cut your small input performance in half. A bigger philosophical difference is that Dat doesn't specify a particular chunk size. Again this makes sense for their use case, since you might want to experiment with fancy things like Rabin fingerprinting. Looks like they discuss that here: https://stackoverflow.com/a/51604110/823869 https://stackoverflow.com/a/51604110/823869. But for a cryptographic hash, it's important that every file has exactly one hash, and a fixed chunk size is required. Another upside of a fixed chunk size is that you really cut down on metadata; the 8-byte length at the front of an encoding or a slice determines the structure of the entire tree.

rakoo 7y ago
Indeed content-based chunking definitely has appeal, I'm thinking about all the backup softwares that use it as a smart way to cut down on total size in a way that leaves all snapshots independent from each other. On the other hand having a well-defined format and the tools to play with like you provide is definitely better to have it spread, so kudos for it.