ExploreTrendingAnalytics
Nostr Archives
ExploreTrendingAnalytics
SatsAndSports2h ago
This @23d12ef8…b6b12e8a network has N=six nodes and therefore five (N-1) spanning-tree-edges So we have two blooms filters for each spanning-tree-edge, i.e. 10 (possibly distinct) Bloom filters Do we also have two more Bloom filters for each of the *non-spanning-tree* peer connections? For example, if B and C peered with each other here, would we therefore have 12 Bloom filters? @Johnathan Corgan I'm pretty sure I know the answer (Yes), but I'm not 100% sure This diagram is from the intro: https://github.com/jmcorgan/fips/blob/master/docs/design/…
💬 4 replies

Replies (4)

Johnathan Corgan2h ago
One bloom filter advertised by and received from each peer is kept locally. Whenever an update comes from a peer, if it is different from what is already stored, the node will update its local copy, then: For each remaining peer that is either a spanning tree parent or child, calculate a new bloom filter consisting of the union (XOR) of all the other peers and send it. This is called "split horizon" routing and essentially means that after convergence each node has a bloom filter for each of its peers containing all nodes reachable through that peer. Later, at the routing stage, the node can examine all its peers' bloom filters to identify candidate next hops for routing.
000
0 sats
SatsAndSports17m ago
Thanks Johnathan! I think I understand much of that already thanks, including the split-horizon stuff, thanks the your excellent docs that you already have. I'm just trying to identify some simple invariants which might also help when I'm trying to share my understanding with others If there are N nodes in total in a (connected) network, then there will be at least 2N-2 (possibly distinct) Bloom Filters, right? I.e. two for each spanning-tree-edge I ask because some people say N, instead of 2N-2, in that statement
0000 sats
Johnathan Corgan13m ago
Well, to be clear, with k peers the node only stores one bloom filter from each one. During the gossip protocol updates the ones sent up and down the spanning tree are calculated on-the-fly as needed, not stored. So they are 'possible' bloom filters but not stored bloom filters.
0000 sats
Johnathan Corgan13m ago
We are perhaps describing two different things.
0000 sats