Skip to main content
added 232 characters in body
Source Link
J_H
  • 34.9k
  • 3
  • 32
  • 129

This doesn't appear to be a cryptographically strong hash -- I don't see diffusion and confusion happening here, no avalanche. I am hard pressed to believe that an adversary couldn't craft inputs that deliberately collide with one another. Incrementing "hash" makes it look more like "serial number".

Given that you're returning a 64-bit hash, it appears you believe we won't see anywhere near four billion input bit sequences. This suggests that a 64-bit prefix of SHA3 would suffice.

This doesn't appear to be a cryptographically strong hash -- I don't see diffusion and confusion happening here, no avalanche. I am hard pressed to believe that an adversary couldn't craft inputs that deliberately collide with one another. Incrementing "hash" makes it look more like "serial number".

Given that you're returning a 64-bit hash, it appears you believe we won't see anywhere near four billion input bit sequences. This suggests that a 64-bit prefix of SHA3 would suffice.

Source Link
J_H
  • 34.9k
  • 3
  • 32
  • 129

This is language-agnostic advice, nothing rust-specific.

want to assign a unique identifier to a stream of bits.

The standard answer to this is:

  • assign hash = SHA3(input)
  • return prefix of that hash

where we look at number of inputs, and risk tolerance, to decide how long that prefix should be. Often a prefix of 128 bits suffices for a UUID.

You were a bit vague on length of input, number of inputs, risk tolerance, and maximum acceptable hash length. Knowing more details would make it easier to assess whether your use case is a good fit for the standard solution.

It is important in my application that no collision happen.

That adjective doesn't really map to a probability figure. There is certainly the notion of a perfect hash. But you didn't disclose an essential precondition. You didn't tell us that the ("offline") algorithm gets to see all possible inputs before returning its first hash value. As written the OP appears to describe requirements of an "online" algorithm. If offline operation is acceptable, then just set counter = 1 and verify that each SHA3(counter || input) is distinct. If collision is detected, simply increment the counter and keep trying again until you find a perfect hash. This will happen quickly if we emit 128 bits, and more slowly if we're required to emit fewer bits, especially when presented with a large number of inputs. For practical input values it should take zero or a tiny number of retries to obtain a perfect hash function.


testing

        let a1: [u8; 4] = [0, 0, 0, 0];
        ...
        let a2: [u8; 4] = [0, 0, 0, 1];
        ...
        let a3: [u8; 4] = [0, 1, 0, 0];

Consider renaming these to more natural identifiers: a0, a1, a4.

I found the sequence of .iter() calls confusing. I am convinced you deliberately planned them so as to teach me something. I confess I do not know what you wanted to teach; I am as yet unenlightened. Possibly doing non-interleaved hashing of the various arrays would be clearer.

The fault perhaps lies less with the unit test code, which likely should not have a ton of comment lines, and more with TreeHasher's hash() function. Certainly there's a bunch of comments in there. But the overall datastructure eluded me. The comments are low level, and they're not guiding me to certain spots in a high level overview of the tree you're building. In particular, given an existing tree plus next bit to hash, I don't know how to resort to English prose to learn about appropriate tree update. I saw no diagrams of example trees. I understand that you were trying to communicate the details to me, but in this particular instance communication was not successful.