[limit499karma]

? If I use something like Blake3 (which is super fast and emits gobs of good bits) and encode a node with say 512 bits of the hash, you are claiming that somehow I am vulnerable to tampering because the hash function is fast? What is the probable number of attempts to forge a document D' that hashes to the very same hash? And if the document in structured per a standard format, you have even less degrees of freedom in forging a fake. So yes, a Merkel tree definitely can provide very strong guarantees against tampering.

[oconnor663]

Fwiw, increasing the BLAKE3 output size beyond 256 bits doesn't add security, because the internal "chaining values" are still 256 bits regardless of the final output length. But 256 bits of security should be enough for any practical purpose.

[limit499karma]

Good to know. But does that also mean that e.g. splitting the full output to n 256 chunks would mean there is correlation between the chunks? (I always assumed one could grab any number of bits (from anywhere) in a cryptographic hash.)

[oconnor663]

You can take as many bytes from the output stream as you want, and they should all be indistinguishable from random to someone who can't guess the input. (Similar to how each of the bytes of a SHA-256 hash should appear independently random. I don't think that's a formal design goal in the SHA-2 spec, but in practice we'd be very surprised and worried if that property didn't hold.) But for example in the catastrophic case where someone found a collision in the default 256-bit BLAKE3 output, they would probably be able to construct colliding outputs of unlimited length with little additional effort.