search

stellar / stellar-core

Reference implementation for the peer-to-peer agent that manages the Stellar network.
https://www.stellar.org
Other
3.12k stars 970 forks source link

The quorum-intersection checker cannot handle large networks #4106

Open nano-o opened 10 months ago

nano-o commented 10 months ago

Core's quorum-intersection checker (which will be exposed as a command when https://github.com/stellar/stellar-core/pull/4097/ is merged) takes too long to check networks with more than 10 organizations. It already takes around 2 minutes to check a symmetric network of size 10 on my desktop machine.

I attached example networks to reproduce the issue (all those example have quorum intersection). To reproduce, run for example stellar-core check-quorum-intersection symmetric_network_16_orgs_for_stellar_core.json. networks.zip

nano-o commented 5 months ago

I tried a few ideas here: https://github.com/nano-o/python-fbas It's a bit messy but I'm happy to improve code or documentation upon request as needed.

nano-o commented 1 week ago

A few notes after a discussion with @jayz22 :

I prototyped two options in https://github.com/nano-o/python-fbas

1) Fast heuristic. The advantages are that it can handle large networks and is simple to implement. The disadvantages are that it only returns 'true' or 'unknown'. It only returns 'true' if quorum-intersection holds, but sometimes quorum intersection holds and it returns 'unknown'. However those cases involve non-intersecting quorum-sets arranged in a circular way (the simplest example being A->{{B}}, B->{{A}}), which could be considered a red flag anyway in practice.

2) SAT-based checker. The advantages are that it is precise (returns 'true' or 'false', never 'unknown') and can return concrete non-intersecting quorums (if such exist). The disadvantages are that it is slower than the fast heuristic (but still okay e.g. with a 16-organizations top-tier), more complex to implement, and needs to call a SAT solver.

We should discuss which one we want and whether it should be integrated in core or be a standalone tool, and whether to pick Rust or C++.