Ok, so I've done some investigation on this issue, it's very WIP having only been lightly modelled and partially tested, you can find the full thing at:

• rad:z25xEtQambYMzuhcfniEm2Q9n9hsz
• https://app.radicle.xyz/nodes/iris.radicle.xyz/rad%3Az25xEtQambYMzuhcfniEm2Q9n9hsz

Theres a lot of assumptions in the model that may not be reflective of the current network.

The skinny is:

1. I modelled the current system and found theres an upper limit related to the repository churn of the network and INVENTORY_LIMIT (2973). When the churn hits that limit at least in a simplified Alice and Bob setup, Alice will never be able to broadcast her full repository set. In a more complicated network arrangement the particular number of repositories will be higher due to the effect of random sample of repositories and nodes likely connected to multiple Large Nodes (nodes whos repository list is >2973).

2. Theres a simple solution to reduce the number of broadcasts it takes by about ~3-8x, partitioning the set of repositories so we continuously broadcast the full set instead of randomly sampling. It is still subject to the upper churn limit mentioned in 1..

3. Theres a more involved solution whereby we make InventoryAnnouncements additive and allow a node to send their full repository list over multiple announcements but respecting the rate limits. This will increase the per hour gossip of a node relative to number of repositories and churn rate. It isn't subject to the same churn limit, however I suspect there is a limit and backpressure value I haven't quite figured out yet.

4. As for prioritisation it would seem the following is sensible:

• Newly added repositories
• Nodes seeded repositories
• Remaining passively seeded repositories

Other solutions have been considered but not investigated; like 2. but where we enable nodes to query each other for more repositories if they are interested, it would reduce the gossip per hour significantly. Further optimisations like RID compaction may provided some gains in terms of number of RIDs inside the wire limit too - I'm sure theres more!.

I'd like to get some e2e tests running (I got 1 just to prove the INVENTORY_LIMIT was being honoured and had the impace expected) to test out these different routes. Whilst thinking about those e2e tests I noticed it would be great to add an interface on disk storage so we can create nodes and repositories in memory as well as some way of moving hard constant limits to defaulted values with environment variable overrides or dependency injected overrides (e.g. INVENTORY_LIMIT, ANNOUNCEMENT_INTERVAL).

Let me know if you have questions, suggestions or feedback!

I was re-reading the Ink & Switch Keyhive notes and came across a paper they reference specifically for the set reconcilliation problem - of which inventory announcement fits quite nicely, multiple nodes in a network with differing inventory awreness (sets) attempting to reconcile their differences to converge on the total set. New and removed repositories would naturally fall into the set differences between nodes.

Rateless Invertible Bloom Lookup Tables (Rateless IBLT) ¹:

the first set reconciliation protocol that achieves low computation cost and near-optimal communication cost across a wide range of scenarios: set differences of one to millions, bit strings of a few bytes to megabytes, and workloads injected by potential adversaries.

• The reference implementation is in Go ²
• There are 2 Rust crates:
  • https://github.com/samWighton/rateless_iblt
  • https://github.com/Intersubjective/riblt-rust

It’s a far more sophisticated solution than any I’ve proposed, they also reference prior art tackling the same problem (which they improve upon):

• IBLT
• MET-IBLT
• Bloom filters
• Bloom filters + Merkle tries
• Pinsketch

If I get some time it would be worth modelling, I only see them testing up to 100M (10^8) in total set size.

I’ve been thinking about this some more and regardless of the method of set reconsilliation (I just saw a recent paper on CertainSync), we need some way of enabling v1 and v2 Inventory Announcers to co-exist seamlessly.

Digging into the code there seems to be only 2 places we can version our messages afaict:

1. PROTOCOL_VERSION ¹ which is currently rad1 and sits at the start of the protocol frame. Nodes will drop connections to PROTOCOL_VERSION’s they don’t know.
2. Node Features ² which is a u64 of flags, where we currently have 2 sets defined, the NONE set for clients (all empty bits) and SEED (bit 1 set) for seeders.

I’m reluctant to depend on 1. - it feels more hard fork-y or major upgrade. It’s pretty low level. However 2. doesn’t seem ideal either, I get the impression it was intended for higher level features!

Assuming 1. is off the table it's a matter of how we deal with 2.. The immediate and simplest solution is to take bit 2 for both NONE and SEED to indicate support of the new InventoryAnnouncement message format and subsequent method. When nodes connect they share in their NodeAnnouncement the features they support, so we can track who supports which version… Now the trickier bit comes with simultaneous v1 & v2 support AND signed InventoryAnnouncements. V2 nodes will need to send BOTH v1 & v2 InventoryAnnouncements to their peers because Eve a peer of Bob might be v1 unbenownst to Alice v2 who only knows Bob. V1 nodes can continue sending and relaying v1 InventoryAnnouncements because we’ll maintain dual capability in v2 nodes.

Ok so to break that apart I think theres the following:

• The message version problem: which mechanism to use to indicate a new message format for some subset of messages. Assuming 2. :
  • The feature flag problem: how best to utilise the feature bit.
• The v1 & v2 message format problem: how best to minimise the amount of time v1 messages are around whilst the network converges on v2.

I’m definitely interested in hearing if there are any alternatives to the 2 suggested solutions for the message version problem!

As for the feature flag problem I have a more sophisticated suggestion, instead of wasting 1 of our 63 remaining feature bits on a single message format change, we instead utilise bit 2 to communicate a nodes ability to negotiate message formats. Within this feature, nodes can negotiation via gossip a version of message format and method they both support. I went and investigated how QUIC deals with this; they offer 2 solutions:

• Incompatible Version Negotiation:
  1. client sends server version it’d like to use.
  2. server doesn’t support version (likely able to parse up to the version number), server replies with a list of versions it does support.
  3. client picks mutually supported version and re-initiates connection.
• Compatible Version Negotiation: Two version are considered compatible if the first flight of clients packets in one version can be converted to another. Not always symmetric. Newer versions must explicitly define their compatibility with other versions.
  1. if server can parse clients initial packet and the client’s offered version, and they share a compatible version, the server can internally convert client’s messages and continue with no negotiation required.

In the vein of Incompatible Version Negotation we could use a semver like string for each message format / method combo, where the MAJOR is pinned to the PROTOCOL_VERSION, the MINOR is a breaking change withing the MAJOR and the PATCH is non-breaking. Node A and B would gossip their set of message format / method versions they support and would pick the lowest common denominator.

As for Compatible Version Negotation I’d likely leave that to a future feature!

Thats a rough draft of an idea, open to further refinements, suggestions and issues!

Finally the v1 & v2 message format problem:

1. Frequency Throttle v1: essentially reduce the number of v1 messages being shared over time from v2 nodes. Has the benefit of incentivising upgrades.
2. Some sort of Gossip Sensor Network: take the Nodes with v2 / Total known nodes and when >95% stop sending v1 messages. May have issues with isolated parts of the network!
3. Hard Sunset Date: Pick a date in the future to stop sending v1 messages. Also is a kind of incentive.
4. Feature Flag: Use a deprecation feature flag to signal v2 node ready to stop accepting v1 messages.
5. Hybrid of the above!

Again open to suggestions, refinements and issues 😬!

After the maintainers discussion this morning it was suggested that there might be 2 more places a solution to the message version problem can happen:

1. NodeAnnouncement.version ¹ - a u8 currently set to 1
2. NodeAnnouncement.agent ² - a UserAgent(String) currently set at /radicle:1/ that must be less than 64 bytes

Note both of these refer to the same PROTOCOL_VERSION u8 = 1 ³, not to be confused with the PROTOCOL_VERSION from the radicle-protocol crate⁴ that prefixes the protocol frame with rad1!

It appears there are no hard checks for either 1. or 2. so backwards compatibility is ensured.

2. is less preferable to me, fiddling with strings for messaging version seems a bit off… although if we choose 1. then we’re implicitly changing 2.