Hashing a fixed size binary stream with a tree structure in Rust

Question

For a research project, I want to assign a unique identifier to a stream of bits. I can assume that all the streams will always have the same size.

Because of this nice property, my idea has been to use a binary tree structure to assign to each stream a leaf storing its unique identifier. In the following, I call these identifiers hashes, as I intend to use them in a HashMap later on (or an array, since these identifiers are just increasing integers). It is important in my application that no collision happen.

Thus, upon being given a stream it has never seen, the tree will expand accordingly to the values of the bits until the stream has been consumed. There, a leaf is created and the unique hash of the stream is stored.

At some point I thought that it may be a good idea to pack the bits in u8 values and to use a tree where each Node would have 256 children. However, I think that this creates a lot of unused pointers, but I may be wrong on this. I designed the code so that if I need to deal with streams of octets instead of bits, only one constant needs to be changed.

All in all, the final goal is to have a method that can assign a unique identifier to a stream of bits with a fixed size in the fastest way possible. In the future, this function will be queried by several threads, but I haven't taken this into account for now.

I'm a beginner in Rust and this project has two goals:

• Performance, since this code will be used in a computationally expensive algorithm;
• Improve in Rust.

Thus, if there is a data structure that I'm unaware of that provides the same functionality, by all means tell me! Whether there is or not, I'm looking for feedback on all possible aspects that could make a good code: performance, good practices, etc...

// main.rs
mod hasher;

fn main() {}

// hasher.rs
use crate::hasher::TreeHasher::{Leaf, Node};

/// Each Node in the TreeHasher has the same number of children. This value must be equal to the
/// largest integer the hasher will ever meet in the stream.
///
/// Since we are dealing with binary streams, its value is currently set to 2.
const TREE_BRANCHES: usize = 2;

/// The enum that represents the tree used for hashing. The data is stored in the leaves only, the
/// nodes are only meant to lead to the leaves.
///
/// The rationale is that it is possible to both access and create an entry in $n$ steps, where $n$
/// is the length of the stream. Note that this hasher assumes that every stream to be hashed has
/// the same length $n$. Otherwise, the `hash` function will panic.
enum TreeHasher {
    Leaf(u64),
    Node(Option<[Box<TreeHasher>; TREE_BRANCHES]>),
}

/// The Hasher is the struct the user will be exposed to in order to hash streams.
pub(crate) struct Hasher {
    /// The `tree_hasher` is the structure that contains all previous hashes and is in charge of
    /// creating new ones.
    tree_hasher: TreeHasher,
    /// The `next_hash` simply represents the hash that will be affected to the next stream to which
    /// no hash is associated yet.
    next_hash: u64,
}

impl TreeHasher {
    /// Creates the root of a new TreeHasher.
    fn new() -> Self {
        Node(None)
    }

    fn hash<'a>(&mut self, mut data: impl Iterator<Item = &'a u8>, next_hash: &mut u64) -> u64 {
        // If the iterator hasn't been entirely consumed yet
        if let Some(next_elt) = data.next() {
            // Since the iterator hasn't been consumed, it is normally impossible to reach a Leaf at
            // this point. If this is the case, it means that the iterator was longer than some
            // previous ones.
            if let Node(children_option) = self {
                // If the node has already been expanded, we simply follow the associated pointer
                if let Some(children) = children_option {
                    children[*next_elt as usize].hash(data, next_hash)
                // Otherwise, we have to create the children of this node
                } else {
                    *self = Node(Some(core::array::from_fn::<
                        Box<TreeHasher>,
                        TREE_BRANCHES,
                        _,
                    >(|_| Box::new(Node(None)))));

                    // Is there a better way? It feels kind of artificial to perform an if condition
                    // and to add an else clause that we know won't ever be used
                    if let Node(Some(children)) = self {
                        children[*next_elt as usize].hash(data, next_hash)
                    } else {
                        // This can't happen, since the if statement is only used to get access to
                        // the pointer we're interested in, it always evaluate to True
                        panic!()
                    }
                }
            } else {
                panic!("Reached a Leaf without having reached the end of the iterator.")
            }
        } else if let Leaf(index) = self {
            // In this case, the iterator has been consumed and we've found a Leaf, so it means that
            // its hash has already been computed, and has been stored there
            *index
        } else if let Node(None) = self {
            // In this case, the iterator has been consumed but no Leaf has been created yet. It
            // means that we have to store its hash in a Leaf here
            let res = *next_hash;
            *self = Leaf(*next_hash);
            *next_hash += 1;
            res
        } else {
            // Isn't reachable, all the cases have been dealt with
            panic!("Reached the end of the iterator without a Leaf having been found.")
        }
    }
}

impl Hasher {
    pub(crate) fn new() -> Self {
        Self {
            tree_hasher: TreeHasher::new(),
            next_hash: 0,
        }
    }

    /// Computes the hash of a stream of data.
    ///
    /// The goal of this function is to set a unique hash to every stream of data it is given. It
    /// does so by storing the stream in a tree-like structure, which allows efficient search and
    /// creation. It is guaranteed that the same stream will always be associated to the same hash
    /// and that two different streams will never be associated to the same hash, as long as the
    /// number of different streams don't exceed $2^64$.
    ///
    /// # Arguments
    ///
    /// * `data` - The stream of data to compute a hash for. Note that it must satisfy two strict
    /// conditions:
    /// - Each stream of data must be of the same length.
    /// - Each stream of data mustn't contain integers larger than `TREE_BRANCHES`.
    /// If one of these conditions  isn't satisfied, this function may panic.
    pub(crate) fn hash<'a>(&mut self, data: impl Iterator<Item = &'a u8>) -> u64 {
        self.tree_hasher.hash(data, &mut self.next_hash)
    }
}

#[cfg(test)]
mod tests {
    use crate::hasher::Hasher;

    #[test]
    fn test_hasher() {
        let mut hasher = Hasher::new();
        let a1: [u8; 4] = [0, 0, 0, 0];
        assert_eq!(hasher.hash(a1.iter()), 0);
        assert_eq!(hasher.hash(a1.iter()), 0);
        let a2: [u8; 4] = [0, 0, 0, 1];
        assert_eq!(hasher.hash(a2.iter()), 1);
        assert_eq!(hasher.hash(a1.iter()), 0);
        assert_eq!(hasher.hash(a2.iter()), 1);
        let a3: [u8; 4] = [0, 1, 0, 0];
        assert_eq!(hasher.hash(a3.iter()), 2);
        assert_eq!(hasher.hash(a1.iter()), 0);
        assert_eq!(hasher.hash(a2.iter()), 1);
        assert_eq!(hasher.hash(a3.iter()), 2);
    }
}

In particular, there are several questions that I couldn't answer:

• Is using an array rather than a vec for storing the children really useful? That's the first idea I got since I do know the size of the array at compile time, but I'm unsure whether this produces better code, or whether this has an impact on performance
• Does the fact that I do know the length of the streams at compile time be useful? I thought it wasn't since I'm consuming them in an iterator way, but I may have missed something obvious.
• Is there another way than doing if let to access an enum's value? This leads to if let statements that will always be true and else clauses that can't be reached.
• In the hash function of Hasher, why isn't data forced to be declared with mut? The function definitely consume the iterator.

Answer 1

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.

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.

---

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.