entropyxyz / synedrion

Implementation of Canetti-Gennaro-Goldfeder-Makriyannis-Peled threshold signing scheme
https://docs.rs/synedrion
GNU Affero General Public License v3.0
63 stars 10 forks source link

Switch to `hashbrown` for maps and sets #95

Closed fjarri closed 1 month ago

fjarri commented 10 months ago

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 3 months ago

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 2 months ago

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 2 months ago

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 1 month ago

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