search

filecoin-project / bls-signatures

BLS Signatures in Rust
Other
74 stars 44 forks source link

Quadratic duplicate message check #68

Closed Stebalien closed 11 months ago

Stebalien commented 11 months ago

Right now, the "fallback" duplicate check (when blst is disabled) is has a n^2 runtime. The blst version is using a red/black tree and has a log(n) runtime.

I'd consider:

  1. At a minimum, making the fallback have a log(n) runtime (e.g., use BTreeSet).
  2. Even better, use a HashSet for both. The rust HashSet is pretty damn fast and avoids hashing entirely for small sets, IIRC, so we shouldn't have any issues there.
Stebalien commented 11 months ago

Motivation: Anything other than a linear runtime will be annoying to charge for in terms of gas.