bao

To be really honest, they can take a look at bao. (I used it for an eerily similar project like this one though its great that this is receiving traction! I Do feel like scuttlebutt protocol might be good implementation for most use cases as well) Bao allows us to have a common hash for the first n contents of the term and then they can still have common hash so you can just loop it over each continuous word to see how much commonly (long?) their hash is and the length becomes the amount similar Some issue might come where if the word changes in the start and the rest is similar but I feel like bao could/does support that as well. My information on bao is pretty rusty (get the pun? It's written in rust) but I am sure that this idea is technically possible & I hope someone experienced in the field could tell more about it https://github.c

> similar to what Bao encoding is used for in BLAKE3 In my mind Sakura and Bao are doing very different things. Sakura is a general framework for defining sound hash functions, while Bao is a BLAKE3-specific interleaving of hash function input and output that let's you do partial/streaming verification. There was an interesting issue where it turned out that the Sakura security properties (which I studied while I was working on Bao, very helpful) weren't sufficient for what Bao wanted to do. I didn't realize that until a couple colleagues pointed it out years later. Luckily it didn't turn out to be a break in practice: https://github.com/oconnor663/bao/issues/41

This is a difference between BLAKE3 and most other hash functions. In the usual arrangement ("Merkle–Damgård"), each block depends on the previous one, so the only way to verify some "slice" of the input is to re-hash the whole thing. But when you arrange the input into a tree shape (a "Merkle tree") instead, suddenly the right half of the tree does not depend on the left half until the very last step at the very top. If you give me the input to that last step, I can verify that it matches the root hash that I know, now I have the hashes ("chaining values") I'd need to verify either the left half or the right half without the other. Then I do our favorite trick in computer science, which is to recursively apply that same procedure all the way down, until I have an efficient "path" to whatever part of the tree I actually care about. For mo

If parts are aligned on a 1024-byte boundary and you know each part's start offset, it should be possible to use the internals of a BLAKE3 tree to get the final hash of all the parts together even as they're uploaded separately. https://github.com/C2SP/C2SP/blob/main/BLAKE3.md#13-tree-has... Edit: This is actually already implemented in the Bao project which exploits the structure of the BLAKE3 merkle tree structure to offer cool features like streaming verification and verifying slices of a file as I described above: https://github.com/oconnor663/bao#verifying-slices

Thanks! I've added a note about this here: https://github.com/oconnor663/bao/issues/41#issuecomment-119.... Does that sound like an accurate summary to you?

I mostly agree with you, but there are a couple other bullet points I like to throw in the mix: - Length extension attacks. I think all of the SHA-3 candidates did the right thing here, and we would never accept a new cryptographic hash function that didn't do the right thing here, but SHA-2 gets a pass for legacy reasons. That's understandable, but we need to replace it eventually. - Kind of niche, but BLAKE3 supports incremental verification, i.e. checking the hash of a file while you stream it rather learning whether it was valid at the end of the stream. https://github.com/oconnor663/bao. That's useful if you know the hash of a file but you don't necessarily trust the service that's storing it.

We go over some of our reasoning around that in section 7.5 of https://github.com/BLAKE3-team/BLAKE3-specs/blob/master/blak.... An early BLAKE3 prototype actually didn't include the chunk counter (https://github.com/oconnor663/bao/blob/master/docs/spec_0.9....), so I'm definitely sympathetic to the use cases that wish it wasn't there. However, after publication we found out that something like a chunk counter is necessary for the security of the Bao streaming verification tool: https://github.com/oconnor663/bao/issues/41. It could be that there's a design that's the best of both worlds, but I'm not sure.

In addition to loeg's point about timing, I'll add that BLAKE3 has its own internal tree structure. It would be unfortunate to have two tree structures layered on top of one another, both because it's "ugly" and because it won't do as good a job of parallelizing things. However, unifying the tree structures would be a big commitment. Every detail of the layout would need to be exactly as it is in BLAKE3. There wouldn't be any space for custom metadata on interior tree nodes, for example. I'm not familiar with the protocol details of BitTorrent myself, but I wouldn't be surprised if that unified approach turned out to be too limiting. (But for a file/tree project that does use the exact BLAKE3 structure, see github.com/oconnor663/bao.)

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 mo

If you squint at it, there's also a Python implementation here: https://github.com/oconnor663/bao/blob/master/tests/bao.py. But it's far too slow to use it for anything besides testing.

Verified streaming is implemented by https://github.com/oconnor663/bao.