Bao Tree Support

[pcfreak30]

I am requesting to have Bao verified streaming/Merkle tree support based on the https://github.com/n0-computer/abao rust fork.

I am also requesting the outboard mode be supported as well.

Thanks.

[lukechampine]

Implemented in https://github.com/lukechampine/blake3/commit/f9980aaa7e4667cdb0556ef85ba2991897109447

Chunk sizes are fixed at 1024. I can make that configurable, but the SIMD stuff all assumes 1024 byte chunks, so there will be a performance hit.

No support for slices at this time, but I can add that if it's an important feature.

[oconnor663]

Awesome! This is probably already clear, but just in case: We can't change the chunk size per se without breaking compatibility with BLAKE3. However, we can use larger "chunk groups" in the encoding, effectively pruning the lower levels of the tree, without breaking back-compat. (The encoding isn't compatible if we change the chunk group sizes, but at least the root hash is unchanged.)

[pcfreak30]

Implemented in f9980aa

Chunk sizes are fixed at 1024. I can make that configurable, but the SIMD stuff all assumes 1024 byte chunks, so there will be a performance hit.

No support for slices at this time, but I can add that if it's an important feature.

IIRC @redsolver S5 uses 256 KB chunks and since verifying the tree data needs to be standardized across clients (and portal nodes), as it would change the tree data, this does need to be configurable. The data generated portal side would be downloadable for the client.

But appreciate the work done so far as this is a starting point to migrate. But I do need 256 kb chunks/chunk groups to interop correctly. I did not state that before as I assumed all chunk sizes could just get ported :sweat_smile:.

Kudos.

[oconnor663]

My fault for taking so long to add chunk group support to the original Bao implementation 😅

[redsolver]

I'm using 256 KiB chunk groups by default, but would like to support other sizes too. For example Iroh is using 64 KiB chunk groups. So right now all of my streaming implementations just download the entire outboard file first and then start streaming (and verify) the file. Long-term it would be nice to switch to a more flexible outboard format that supports efficiently fetching parts of the outboard file down to a specific chunk group size. That would make it possible to generate and host one outboard file that goes down to the 64 KiB level, but a client could only fetch the parts needed down to 256 KiB chunk groups (with range requests) if they don't need to verify smaller chunks (for example when streaming video). But I'm waiting on what the Iroh team comes up with, right now I'll just keep using the default bao outboard format with 256 KiB chunk groups

[pcfreak30]

Also @lukechampine please make baoOutboardSize public and a New constructor for bufferAt as I have to copy this code for my needs as the standard library does not have any WriterAt implementations IIRC.

I am also unsure if baoOutboardSize should be taking an int64?

To give an idea of what I'm currently working with:

func ComputeTree(reader io.Reader, size int64) ([]byte, error) {
    bufSize := baoOutboardSize(int(size))
    buf := bufferAt{buf: make([]byte, bufSize)}

    _, err := blake3.BaoEncode(&buf, bufio.NewReader(reader), size, true)
    if err != nil {
        return nil, err
    }

    return buf.buf, nil
}

[lukechampine]

exported in https://github.com/lukechampine/blake3/commit/6e4325968f64ca24b1bbc8fbf08ea320d17ebfa0

bufferAt is 9 lines of code, just copy it if you need it.

[pcfreak30]

exported in 6e43259

bufferAt is 9 lines of code, just copy it if you need it.

Yes, I have, just wanted to avoid it.

[pcfreak30]

Hello,

To bump this issue, my project currently has the following two requirements I request to be supported.

• Chunk group support, starting with 256 kb, though it may be ideal to design this to be configurable? See https://github.com/n0-computer/abao/blob/9b756ec8097afc782d76f7aec0a5ac9f4b82329a/src/lib.rs#L70
• Verify slice support: https://github.com/s5-dev/web-proxy/blob/a9e5ec14ab6d90a094d50111a7b63c4aeb1f2256/rust/src/lib.rs#L68. I am making use of some of @redsolver work here and need the equivalent to be supported to stream large file data and verify it.

As a secondary nice-to-have, if the existing implementation will not support them, SIMD support on all of this for speed?

Thanks!