Subnostr

#[0] I’ve been looking into the ‘best relays’ problem given a set of pubkeys to follow.

There will never be an exact solution as followers change, events broadcast or sync between relays indeterminately, etc - however I think we can effectively make use of the Minimal Set Cover Problem. A few different algorithms exist each with trade offs.

I’m also prototyping a custom algorithm that can work pretty well, but likely falls short with 75-90% event coverage.. but often that’s with 15 relays (for ~80 pubkeys) which isn’t ideal. Adding another 5 relays likely boosts that by another 10%. Client apps not retrying failed send posts could be impacting it too - with less replication.

Another factor I’ve ignored for now is inbound DMs, which could be on different relays again. And the relay auth NIP could make it harder to understand where DMs are being relayed to.. perhaps it’s a client space problem.

I’m waiting for more event ‘seen by relay’ data after a code update, so perhaps it will improve when my data is more complete.

https://en.wikipedia.org/wiki/Set_cover_problem

Andrew 2y ago

This is super interesting, is there a repo i can follow to watch the progress on this?

Reply to this note

Please Login to reply.

Discussion

Blake 2y ago

I’m still experimenting. There are lots of ok ways to try do this, however few will consistently hit 95% plus - without adding 20+ relays (or more in future).

I’m currently streaming events from 80+ relays, so I can tag which events have been seen by which relays (without actively asking at present).

The current approach is to lookup who a pubkey follows, then get the most recent N events by them, and then process against which relays would be needed to get coverage across the following event set.

It’s got some recursion, so processing speed or pre-processing are considerations vs good enough.

My other approach is to multiplex and perhaps dynamically do this for clients. https://nostrgraph.net/relay

I’ll share updates on Nostr. It’s a little hard to publish a working algorithm since it’s data dependent.

Andrew 2y ago

Awesome, looking forward to seeing how this goes