entropyxyz/synedrion

Switch to `hashbrown` for maps and sets

fjarri opened this issue · 4 comments

fjarri commented

Instead of using the standard library BTreeMap, we can use the hash maps from https://crates.io/crates/hashbrown. Perhaps we can even get rid of HoleVec, which was a bit of a premature optimization (need to see if it actually simplifies the code though).

This is particularly important for key resharing protocol (see #20) where we only need to send messages to some of the nodes, and can finalize when we only received messages from some of the nodes.

dvdplm commented

I had a stab at this an ran into a few problems because of how HashMap/HashSet requires keys and values to be core::hash::Hash:

  1. When we have a struct that need to be Hash, and that struct has a HashMap/HashSet as one of its members. HashMaps have undefined order of its elements, which means that hashing can yield different results. See e.g. public_shares member of KeyShare. Some discussion/explanation here.
  2. Another (perhaps minor) problem is that we often use types from the RustCrypto crates and that these types surprisingly often do not implement Hash. E.g. DynResidue or SecretBox, BackendScalar and others. Here we can work around the problem by using a newtype and manually implement Hash; or lobbying the maintainers to make the types Hash.

My gut feeling is that we should rewrite this ticket to focus on a particular area where the use of BTree* types is a performance problem. A wholesale replacement of BTree* with Hash* is more work than the it deserves.

I pushed my WIP investigation here.

Thoughts?

fjarri commented

This was more of an investigation issue, so I don't have strong feelings about it. HoleVec is gone now and BTreeMap/Set are used everywhere, and it seems to be working out. The main reason I was wondering if we should switch to hashbrown was performance (compared to BTree structures), but I doubt it will be particularly impactful. Perhaps we can just close it as wontfix.

dvdplm commented

Yeah that's my feeling too. I opened up a PR to add Hash on some RustCrypto crates but they correctly points out that it is potentially dangerous to use secrets in HashMaps without using a cryptographic hash. If we use Blake2 or similar I doubt we'll get good performance (we'll get worse I bet).

Happy to close this.

fjarri commented

Doesn't seem to be worth it, closing for now.