Implement Efficient Set Reconciliation algorithm

[pmnoxx]

We should implement and test a few different approaches to Set Reconciliation problem.

White paper provided by @abacabadabacaba

https://www.ics.uci.edu/~eppstein/pubs/EppGooUye-SIGCOMM-11.pdf

I found one existing rust library for Set Reconciliation : https://crates.io/crates/minisketch-rs
You can find explanation how it works here https://github.com/sipa/minisketch/blob/de98387a83ccd5dd7399333ddcf52e1d4f344e53/README.md

• Benchmark minisketch-rs
• Implement IBF in Rust
• Benchmark IBF
• Optimize IBF - maybe faster hash function
• Add implementation of algorithm to estimate size of set difference using IBF
• Test estimator
• rename sketch to IBF?
• Benchmark estimator
• make into template to support both u64, u32
• estimate how good estimator is
• choose proper coefficient for IBF (using 1.5x right now)
• Can we make estimator secure? yes
• Choose number of hashes 3 or 4 (using 3)
• What if we don’t use estimator, but so log n round trips, each time sending bigger ibf
• Write a doc describing algorithm which is resistant to malicious attacks 2 ver
• implement algorithm for syncing - example
• add unit test for it
• Can we write an algorithm better than one sending 120 bytes *d metadata in worst case?
• Find more research papers / algorithm names
• Read https://www.ics.uci.edu/~eppstein/pubs/EppGooUye-SIGCOMM-11.pdf
• Add hash seed to IBF/seed check
• read how IBLT works
• implement Mock graph implementation
• implement graphsync structure
• Add tests for it
• Add benchmarks
• Investigate Cuckoo Filter: Practically Better Than Bloom
• write a proposal using https://github.com/near/NEPs/blob/master/0000-template.md

known algorithms

• IBF - implemented
  https://www.ics.uci.edu/~eppstein/pubs/EppGooUye-SIGCOMM-11.pdf
• IBLT - minisketch-rs implementation was too slow O(N) decode time http://homes.sice.indiana.edu/qzhangcs/papers/sigmod14_robust.pdf
• CPISync - O(n^3) decode time - too slow
• PinSketch - O(n^2) decode time - too slow
• ART - slower according to EppGooUye-SIGCOMM-11.pdf

performance
inserting 1m elements (3 hashes) - 60ms
recover 10k elements - 0.9ms
recover 100k elements - 10.5ms
recover 1m elements - 195ms

[pmnoxx]

@bowenwang1996

[pmnoxx]

I tested minisketch it works, but we won't be able to use it.
They use a variant, which produces a sketch which supports an add operation, but it doesn't support remove operation. This would require to completely recompute sketches on edge removal, so this is not usable for us.
https://github.com/eupn/minisketch-rs/blob/master/examples/simple.rs

[abacabadabacaba]

It was me who provided that white paper, not @evgenykuzyakov.

[pmnoxx]

@abacabadabacaba Sorry, fixed.

[pmnoxx]

I did some early benchmarking
creating sketch with 1m(32bits) elements using minisketch-rs - takes around 2s
my unoptimized code - IBF 1m (64bits) elements - 72ms
In the white paper they claim it takes 4s to insert 1m elements

[pmnoxx]

I tested the time it takes to recover the difference, assuming we use 4 hashes.
10k elements - 1.1ms
100k elements - 22ms
1m elements - 284ms

[pmnoxx]

That should be fine, we need to spend 2ms to verify each edge, for 1m edges that would take 30m.

[pmnoxx]

Here is a link to implementation, I also added benches:
@bowenwang1996 https://github.com/pmnoxx/near-set-reconciliation/blob/master/sr-playground/src/sketch.rs

[pmnoxx]

@abacabadabacaba You had some ideas during the meeting on how to improve BLT. Would you mind writing them down here?

[pmnoxx]

I implemented full algorithm for syncing. You can see how it works in a unit test: https://github.com/pmnoxx/near-set-reconciliation/blob/21bcdfee1a1c30e11f8df729fc49ebcc7f0af5cf/sr-playground/src/blt_graph.rs#L99
I'll write a document with explanation.

[stale]

This issue has been automatically marked as stale because it has not had recent activity in the last 2 months.
It will be closed in 7 days if no further activity occurs.
Thank you for your contributions.

[bowenwang1996]

#4112 is merged