Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Introduce Resync bloom filter #72

Open
5 tasks
loongy opened this issue Mar 30, 2020 · 0 comments
Open
5 tasks

Introduce Resync bloom filter #72

loongy opened this issue Mar 30, 2020 · 0 comments
Labels
enhancement New feature or request

Comments

@loongy
Copy link
Contributor

loongy commented Mar 30, 2020

See #50 for more information.

We should also introduce bloom filters for Resync messages. If the Resync message appears in the bloom filter, it gets dropped. If not, it is processed and added to the bloom filter. This filter is periodically cleaned (once per minute). This protects against replays of the exact same Resync message within a one minute window without requiring a large amount of space to remember all Resync messages ever seen.

  • Add two in-memory bloom filters to the Replica: frontResyncBF, and backResyncBF.
  • Check the Resync message against both bloom filters and drop the message if it appears in either filter.
  • Add the Resync message to the front bloom filter if it does not appear in the previous check.
  • Add ResyncBloomFilterCycleInterval to the options.
  • When receiving a Resync message, check a lastCycledResyncBF variable. If it is older than the configured interval, set backResyncBF = frontResyncBF and frontResyncBF = empty.

To prevent a malicious node from constructing a Resync message that, when put into a bloom filter, causes the bloom filter to return as many false positives as possible, we need to make the hash generated from the Resync message unknowable. This is easy to do on a node-by-node basis. A boot, a node will generate a random in-memory hash that it combines with all Resync message hashes before adding/checking against the bloom filter. Since this hash doesn’t change, it will not affect the effectiveness of the bloom filter. Since it is only known by the node (and is different for all nodes), a malicious node will not be able to perform this attack.

@loongy loongy added the enhancement New feature or request label Mar 30, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

1 participant