Re: Formal review request for Hash2

From: Peter Dimov (pdimov_at_[hidden])
Date: 2024-12-03 20:09:16

Ivan Matek wrote:
> I wanted to check the library a bit more with regards to this, but got distracted
> doing something else so here is unrelated question:
> 
> Question probably stems from my lack of understanding why are we hashing
> size of ranges(tried googling if other languages do this, was unable to find info
> about that), but maybe example is best:
...

N3980 has a section on that here:

https://open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3980.html#hash_append_vector

In short, if the size isn't hashed, an empty vector would result in an empty message,
with the corresponding drawbacks.

So I followed N3980 on this when I initially implemented it.

I've since "discovered" that this issue is actually present not just for ranges and
containers, but for empty tuples such as std::tuple<> and std::array<T, 0>. (It's
also present for empty described structs.) I avoid it by imposing the rule that
a hash_append call must always result in at least one byte being sent, and make
sure that empty tuples and structs send a byte instead of nothing.

In principle, we could make containers and ranges also do this, instead of sending
the size.

On one hand, will remove the need for having hash_append_size and
hash_append_sized_range.

On the other hand, it makes it trivial to generate collisions

pair<string, string>( "foo", "bar" )
pair<string, string>( "foob", "ar" )
pair<string, string>( "fooba", "r" )

so maybe not.