search

oconnor663 / bao

an implementation of BLAKE3 verified streaming
Other
479 stars 23 forks source link

Add support for incremental updates #30

Open oconnor663 opened 4 years ago

oconnor663 commented 4 years ago

That is, I write to part of a file, and I efficiently update the root hash to reflect the write. This doesn't really make sense as a feature on the command line, but it would be nice to support in the library. The Bao format itself (both combined and outboard) is exactly what's needed here.

dvc94ch commented 3 years ago

what's required for this? I guess the basic gist is probably to offload the finalization step to the slice extraction so that efficient appends are still possible?

Since Encoder implements clone, it can be finalized at any time. I guess the thing that is missing for cheap appends is to be able to serialize/deserialize the Encoder.

oconnor663 commented 3 years ago

Note that encoder derives Clone, which means it depends on the type of the underlying writer. In the common case that you're writing to a File or a &mut Vec<u8>, it's actually not Clone. (I guess you could use it to write to a &File, in which case it might actually be clone? But actually cloning it is likely to lead to confusing bugs.)

Note also that by "updates" here I specifically don't mean appends. What I'm thinking about here is in-place edits that don't change the size of the file. The idea would be to update a chunk and then recompute all the parent nodes above it, including the root. There's nothing particularly complicated or expensive about doing this (at least no more complicated than the original seeking code), it just needs to be implemented and exposed somehow. Probably with some new type, different from Encoder.