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

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

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