[messaging] RFC: Bao, a tree hash and encoding format for incremental verification

[Jack O'Connor]

The need for an incrementally verifiable hash came up at Keybase when we
were adding support for message attachments, though without an
off-the-shelf standard available we decided not to tackle it. Since then
I've had this on the back burner as as personal project. I think it's ready
for review:

Project: https://github.com/oconnor663/bao
Spec: https://github.com/oconnor663/bao/blob/master/docs/spec.md
Rust API docs: https://docs.rs/bao

The implementation is highly parallel, which makes for a nice speed demo at
the top of the README. In-memory benchmarks get to about 8 GB/s on my
laptop, though they go much higher on fancy AWS hardware. Bao might be
several times faster than any existing cryptographic hash implementation,
for large inputs on modern consumer hardware.

I could especially use help reviewing the security section of the spec (
https://github.com/oconnor663/bao/blob/master/docs/spec.md#security) and
pointers to related work that I might've missed.

Thanks!
Jack
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20181101/997ae291/attachment.html>