Are 512-bit hashes necessary?

[snej]

Bamboo uses 512-bit (64-byte) Blake2b hashes. My gut feeling* is that this is bigger than necessary.

Using 256-bit hashes would reduce an encoded entry by about 75 bytes on average (considering ~⅓ of entries have lipmaa_links.) That's a 25-30% reduction. (Currently an encoded entry can be from 232 to 322 bytes.)

This seems significant, since from what I've seen with Scuttlebutt, there are going to be a lot of entries stored locally, and it's common for the entry to be larger than its payload — for instance, all entries with seq > 1 are longer than any allowed Twitter message.

What do you think?

* I am not a cryptographer! But I've been working with digests & crypto for over a decade...

[snej]

PS: The format could easily accommodate both sizes, by amending the spec of yamf-hash to allow 32 as a valid size. Then it would be up to the sender's software to choose how big a hash it wants. The spec could even allow anything from 32–64 bytes, since Blake2b supports variable lengths.

[AljoschaMeyer]

The choice of the hash function has indeed been pretty arbitrary, with me erring on the side of paranoia rather than efficiency.
I could and probably should have made the bamboo specification more generic, parameterized by any particular choice of cryptographic primitives.

However an explicit design goal of yamf-hash is to support as few functions as possible, only adding new ones as old ones are being broken.

When estimating local storage space, always keep in mind that there is little reason for a database to store entries in the same format as the format used for signing. Hashes could be omitted and recomputed on the fly, signatures can be stored in slower but cheaper storage, compression can be used, etc.

Also, forking specifications is not an evil thing: Just define bamboo256 to be whatever you need and go with it =)

[adzialocha]

Is it possible to add more formats to the yamf-hash spec or does it violate your constraint to only publish new hashes when the old one is broken @AljoschaMeyer?

Otherwise I would suggest adding a new entry to the yamf-hash spec which allows BLAKE3 hashes (we could also introduce BLAKE2s 256 hashes, but why not use the faster algorithm) with numeric id 1 and a digest size of 32 bytes. This seems to be easier than forking the bamboo spec, as I understand it already has this nice, generic YAMF hash 😸