Requesting Ideas for Multi-Hop Group Destinations

[LinuxinaBit]

Seeing as 'group chat' is such a popular feature request, I figured I'd make a place to put down ideas/proposals for how to make the foundational requirement for the functionality, multi-hop group destinations (aka. true multicast), work.

Getting the group messaging working is (relatively) easy, but making truly efficient and reliable multicast that fully supports end-to-end and forward secret encryption and works alongside Reticulum's current routing protocols is very difficult.

Here is a list of all the requirements that I could think of:

1. Efficiency - It must be at least more efficient than flood routing a packet or spraying duplicate single-destination packets everywhere.
2. Reliability - There must be a way to handle recipients being offline or unreachable; this may end up being handled mostly by LXMF.
3. Encryption - It must use end-to-end encryption, ideally with some degree of forward secrecy.
4. Compatibility - It must be as compatible as possible with Reticulum's other components and philosophy.

If anyone has any changes/additions they would like to make to this list, please let me know.

I'm not sure how much Mark has thought about this (my guess is a lot), but other people's ideas might still help provide some inspiration.

[markqvist]

Referencing the comment I made over here, as it is also relevant for this discussion.

[LinuxinaBit]

Ooh, yes, the LXMF side of things is indeed a difficult thing to solve as well. I can see why this has been in the works for so long 😅

I’m very much in favor of taking things one step at a time and just nailing down multicast first, but I do think other projects have something to offer in the way of inspiration for the more messaging-specific problems you brought up.

I definitely want to point out Briar. If you haven’t seen it before, it’s pretty much LXMF but over TOR instead of Reticulum. They have an interesting way of handling the asynchronous messaging problem: https://briarproject.org/how-it-works/

Another example is Matrix and their peer to peer experiments, but I’m sure you’ve already considered that ;)

Maybe also consider writing a dedicated reply here or even a blog post on unsigned.io explaining some of the better (and worse) options you’ve considered. I know it helps me when I write stuff out and other people catch things that I fail to consider; maybe it’ll help you too…

Either way, hope something here can help you get some more ideas.
Best of luck! ❤️

[KenSamson]

Is the intention to use an LXMF destination as the group conversation identifier?

What Briar would call a forum.

That starts to set the stage. Mark has created such elegant solutions to other core problems that I'm sure some of that is clear.

How we share secrets around group messaging is a deep topic. Feldman's VSS implementation could work... every decision has tradeoffs. Meshtastic's URL-type format to give the secret for the channel and QR format is interesting but seems overly simplistic. It seems like admins should be able to rotate a secret that only gets shared with valid members of the group over time. Having the URL text should not be sufficient to gain full content access... IMHO. It may be sufficient to request access. Similarly a forum owner should not be able to add me and send spam without my approval either.

Publish-only groups where only admins can push entries would make "publishing" info easy and create very low-noise forums.

A threaded message view that groups replies under message topics that are replied to will be important as members take days to reply to a topic in an active forum. If someone replies to a message 3 weeks after that thread has more content, it will be so far out of context in the forum that it only has value when associated to the message that is being replied to. Then being able to skip to unread messages within that would help.

In my brain, LXMF propagation nodes are the real force multipliers for forum messages. I'll get the contents of my forums from the closest LXMF propagation nodes with the lowest hops, automating regional distribution. Owners of the propagation nodes can limit resources allocated or acceptance of new forums. Allowing an LXMF node to accept a request for group contents could then automate a request for that LXMF propagation node to being carrying that forum. Similarly, if no requests are made for that forum for some time, that LXMF propagation node could elect to stop replicating that forum. A full catalog of forums available could be replicated among nodes, but only those forums actually requested would get replicated in terms of contents. LXMF nodes already understand the concept of an access allow list... so limiting them to specific clients is pretty easy to form closed LXMF group distribution.

I have not played with static pairing of LXMF nodes.. but that seems like it could be useful here too.

There are other ideas bumbling around... but I'm not sure if this is the kind of thing we want to talk about here.

This a very complex topic.

[LinuxinaBit]

@KenSamson
Group destinations are a different type of destination that, just like any other destination, is not specific to LXMF.
It's looking like it's going to be basically a single address, similar to the more standard Single and Link destinations, except it routes to multiple people at once; it's essentially just a fancy way of saying multicast.
See https://reticulum.network/manual/understanding.html#destinations for details.

The messaging side of things is a little different, and is way more LXMF specific.
As already discussed, that will involve some kind of offline sync, and then various messaging features like replies etc. will come with time.

These won't be forums, but theoretically Group destinations could also be used for some kind of separate distributed forum software, though that's really out of scope for what LXMF specifically is trying to do.

[KenSamson]

Thanks for the reply. I really like how simple building blocks are available to build things based on the goals of a specific effort. I'll read the link and try to get smarter on the direction this is going.

[faragher]

The complexity is in the routing requirements. The Group destination is already defined as having symmetric encryption, so the messages themselves are taken care of, it's getting them to the destinations efficiently.

But before that, here's the fundamental difficulties:

• All messages are end to end encrypted and signed.
• Messages are not stored in a central hub to be accessed, but are directly sent to the recipient.
• Routing tables are dynamic and known only to the transport node in question.
• The system should, ideally, function well over a 2400 baud uplink.

So, in a trivial example, Alice wants to send a message to Bob, Claire, Dave, and Frank. She encrypts the message and shoves it into Reticulum's handlers. From here, multiple concepts have been proposed, if only to say that system isn't feasible.

1. Alice sends an individual message to each person. This is simple and already supported (even with single destinations) but she sends four times the data over the network. This doesn't scale well. A hundred recipients would mean a hundred times the bandwidth, all with repeated data. (and if the data is individually encrypted, this is Eve's best chance to break encryption. Not good, but best)
2. Alice sends one message with all the destinations included in the encrypted payload. This requires every transport node to have the key which means it might as well not be encrypted at all.
3. Alice sends one message with all the destinations in the clear. This allows a transport node to relay the packets to the next hop for each recipient. This will cause duplication and multi-path, but previously seen messages can be dropped by the transport node.
4. As 3, but each transport node re-processes the recipient list. So if Bob is behind one next hop, Claire another, and both Dave and Frank behind a third, the transport node would send three new messages, each only to the next hop for that address. This is efficient, but requires the message either not include the destinations in the signed data, or the data would be re-signed by each transport node. This could allow malicious actors to forward any given group packet to arbitrary destinations, even if they're rather useless since they can't be decrypted.

I'm sure there were other suggestions I've forgotten, but each of these shows the fundamental compromises required, and trying to achieve as many goals as possible with a single system requires considerable thought.

Anyhow, if you're looking for distribution lists or message boards with trusted servers and access control, there are multiple options available. Just trying to really answer the specific intent of the question, rather than what I think you're asking. So I'm hedging my bets by answering both ways. :D

[LinuxinaBit]

One of the ideas I've had for a while is almost identical to the 3rd one @faragher mentioned: #705 (reply in thread) which proposes splitting a list of all recipients at each hop.
Another problem with this is that all recipients are public. I believe Single destinations also have this problem, though that doesn't have a large risk of associating people. This combines with its general fragility and all of the other issues Faragher mentions to make this method feel like too much of a compromise if any other solutions are available.

The first solution I can think of for that problem is to somehow allow multiple nodes to announce what is effectively the same destination over the network.
That undermines the entire premise of Reticulum however, and at best this would allow for a somewhat broken form of anycast (which might still be useful???), but there doesn't seem to be a good solution for multicast here.

Another possibility is to do it almost entirely on the application layer, effectively forming an LXMF propagation net but for a private group chat.
That feels dumb, but it does have the potential to solve a lot of the other application layer issues group messaging causes.

This could also be coordinated on a network level by forming some kind of hybrid Group/Link destination where some routing topology is constructed between group members based on hop count. A ton of bandwidth could be wasted coordinating and arranging these links though?
Something possibly worth looking into just to make sure; there could be an optimal way to do this that I don't see...

In the end the only network layer multicast system I can think of that's actually efficient is the first one I mentioned, though I really can't shake the feeling that something else is out there that I'm just not seeing.

[LinuxinaBit]

This paper may be at least adjacent to this endeavor:
https://www.cise.ufl.edu/~yx1/publications/acom.pdf

I've only really skimmed the introduction and conclusion, but it looks promising?

This paper proposes an any-source overlay multicast service on top of a random overlay network with an augmented ring. It is able to deliver a multicast message from any source with a hop complexity of [LaTeX omitted] and a communication complexity of [LaTeX omitted]. Remarkably, this is achieved without maintaining any explicit multicast trees.

The augmented ring stuff might be a problem, but avoiding explicit multicast trees is exactly what we're looking for (probably, I think?).
Reticulum doesn't necessarily need to invent an entirely new paradigm, but it does at least need to do some pretty inventive stuff to current ones.

Edit: Two others that may be related as well. Note that I haven't read these at all.
https://ieeexplore.ieee.org/abstract/document/4110273
https://www.sciencedirect.com/science/article/abs/pii/S1084804507000343

[faragher]

You are correct that any non-IFAC message lists its recipient openly. It's a minor risk that's effectively unavoidable. Without access to the destination a packet can't be routed, and any access for a transport node is either insecure or basically IFAC.

You are also correct that bundling destinations together presents a risk for network-centric analysis (the human kind of network, not the technological kind).

However, I believe these issues are generally insurmountable. Any technical work-around quickly runs afoul of some other issue, such as the routing failing or seeing the same patterns of different destinations so an onlooker just sees, "Oh, those six people are chatting again, they just have different destinations now." Frankly, on a sliding scale with efficiency on one side and security on the other, an application designed for maximum security would bite the bandwidth bullet and do point to point communications with each station. Any time you link two people, you start an association matrix, so any multicast would, effectively, link people together.

But I think where you sit on that scale is application layer.

I haven't read too much into ACOM, but broadcasts to all stations are very inefficient, and anything that requires a designated topography or trust won't work reliably over Reticulum.

Now, this is all network-level. You can do strange things at the application level, such as having trusted servers with the keys to an encrypted destination list, but then you're on a subnet and you need to establish a number of trusted servers and we have a whole new level of problems. It's worth separating the concept of multicast with specialized high-security applications so as to not chase two rabbits.

[LinuxinaBit]

That makes a lot of sense. Thank you 👍
One question though, what is an IFAC message? All I can find is stuff about an "International Federation of Accountants"

[faragher]

That makes a lot of sense. Thank you 👍 One question though, what is an IFAC message? All I can find is stuff about an "International Federation of Accountants"

Oh, Okay, this might solve a lot of your issues. IFAC is, AFAIK, Interface Access Control. It's a fundamental part of the RNS. If you look at the wire format, you'll see the first bit is always a zero. This is to show that IFAC is disabled and everything is broadcast in the clear (of course the payload is still encrypted). If it's a one, then IFAC is enabled. This is a setting usable on any(?) interface that enables encryption on the entire packet, including the header. It's roughly analogous to a PSK on WiFi, and has the advantage of seeming like any random packet of similar size on the physical layer. There's really no marker it's a Reticulum packet, the stack just checks if the first bit is a one, then tries to decode it.

That's my understanding, anyway, Mark may have corrections.

[KenSamson]

If the propagation nodes held and synched the members of a group destination rather than holding the group members in the message or in the originator, the network could most effectively duplicate the message whenever that makes sense.

…

On Tue, Feb 11, 2025, 9:39 PM faragher ***@***.***> wrote: You are correct that any non-IFAC message lists its recipient openly. It's a minor risk that's effectively unavoidable. Without access to the destination a packet can't be routed, and any access for a transport node is either insecure or basically IFAC. You are also correct that bundling destinations together presents a risk for network-centric analysis (the human kind of network, not the technological kind). However, I believe these issues are generally insurmountable. Any technical work-around quickly runs afoul of some other issue, such as the routing failing or seeing the same patterns of different destinations so an onlooker just sees, "Oh, those six people are chatting again, they just have different destinations now." Frankly, on a sliding scale with efficiency on one side and security on the other, an application designed for maximum security would bite the bandwidth bullet and do point to point communications with each station. Any time you link two people, you start an association matrix, so any multicast would, effectively, link people together. But I think where you sit on that scale is application layer. I haven't read too much into ACOM, but broadcasts to all stations are very inefficient, and anything that requires a designated topography or trust won't work reliably over Reticulum. Now, this is all network-level. You can do strange things at the application level, such as having trusted servers with the keys to an encrypted destination list, but then you're on a subnet and you need to establish a number of trusted servers and we have a whole new level of problems. It's worth separating the concept of multicast with specialized high-security applications so as to not chase two rabbits. — Reply to this email directly, view it on GitHub <#705 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AEKP7JZFZHU6VZRCE3TMVAL2PK65RAVCNFSM6AAAAABWITY7Y6VHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTEMJWGAYTGNA> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[LinuxinaBit]

That brings up an interesting idea.
It's definitely on the application layer more than on the network layer, but using standard LXMF propagation nodes as they are designed and simply allowing multiple people to retrieve the same message is actually a pretty attainable system.
Probably better if they all use the same symmetrically encrypted destination (so a massive plaintext list of destinations doesn't need to be stored anywhere).
There are a ton of asterisks, but it could work.
This definitely isn't actual multicast, but it's an interesting approach to the specific problem of group messaging.

Edit: I read this again, and realized you probably don't know the difference between a Propagation Node and a Transport Node. You might want to read/watch my explainer: https://linuxinabit.codeberg.page/blog/reticulum/

[faragher]

It is interesting, however it contains all the same issues as routing does regarding the destinations/access list. It's a good alternate way of looking at things, however. I mean, the most absurd idea I had was to send a notification via direct message which contained a key, then have a hashed messageID that relies on that key hashed with the destination, and have THAT be an access list, but it still fails network analysis and efficiency goals.

Still, very interesting. The concept of requesting a message through a hash rather than by a destination has some merit. It's just important to make sure we're not confusing "extra steps" with "solving the problem." I know that happens to me too often. Ask me about this custom power distribution block I designed that was literally three light switches.

[LinuxinaBit]

Yeah, I did kind of realize that; it probably takes up more bandwidth than a ton of single destinations (depending on network topology ofc)

[KenSamson]

Allowing an incoming query for a group destination to trigger local storage for that destination could keep the distribution lean. No need to replicate where nobody is asking for that destination. How to identify admins who can edit group members in a problem to solve. An attribute in the list structure maybe.

…

On Tue, Feb 11, 2025, 10:38 PM faragher ***@***.***> wrote: It is interesting, however it contains all the same issues as routing does regarding the destinations/access list. It's a good alternate way of looking at things, however. I mean, the most absurd idea I had was to send a notification via direct message which contained a key, then have a hashed messageID that relies on that key hashed with the destination, and have THAT be an access list, but it still fails network analysis and efficiency goals. Still, very interesting. The concept of requesting a message through a hash rather than by a destination has some merit. It's just important to make sure we're not confusing "extra steps" with "solving the problem." I know that happens to me too often. Ask me about this custom power distribution block I designed that was literally three light switches. — Reply to this email directly, view it on GitHub <#705 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AEKP7J5SZV6VC2USPMZ7UW32PLF43AVCNFSM6AAAAABWITY7Y6VHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTEMJWGA3TMMI> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[LinuxinaBit]

Ok, here’s a better idea, combining some of the previous approaches.

For this idea, Group Destination announces would contain:

1. A group ID referring to the entire group
2. An individual address, different for each node

Packets are addressed to the group ID, and transport nodes automatically send it down multiple paths to get to smaller groups of nodes as announces diverge.

This creates a problem; it could easily end up creating many duplicate transmissions, getting exponentially worse for larger groups.

To remedy this, hash each of the individual addresses to which each packet is headed, and append them somehow to the packet before its first split.
This list of hashes would be split each time packets are sent down multiple paths, slowly shrinking the list down until the packets reach their destination.
These can be small 1-2 byte hashes, duplicates shouldn't incur significant overhead unless the group is exceedingly large.
These hash lists could be combined at nodes where paths converge as well (assuming a delay caused by an interface hitting its bandwidth limit or similar), avoiding unnecessary duplication.

If more individual addresses than fit inside the limit on the hash list's length are needed, multiple packets can be sent, each with different hash lists. These may be able to be combined at different nodes where possible.
The actual content of the packets should be used to differentiate them so hash lists aren't erroneously combined.

Is this a sound idea?
It's simple, but feels reasonably elegant, to the point where I think it shows some promise...

Example (simplified for readability)

Alice, Bob, Charlie, Dan, Erin, and Frank are in a group.

Each announces, Group ID - 72C followed by 7A, B2, C9, D0, E3, and F5 for each participant respectively

---

Alice wants to sent a packet to the group. Announces 7A, B2, and C9 come from Node 1, D0, E3, and F5 come from Node 2.

Alice sends two packets:

1. To=node 1 | Group=72C | Hello | Hashes=ABC
2. To=node 2 | Group=72C | Hello | Hashes=DEF

---

Nodes 1 and 2 determine that the best path towards Charlie, Dan, and Erin is Node 3, the best path towards Alice and Bob is Node 4, and the best path towards Frank is Node 5.

From Node 1:

1. To=node 3 | Group=72C | Hello | Hashes=C
2. To=node 4 | Group=72C | Hello | Hashes=AB

From Node 2:

1. To=node 3 | Group=72C | Hello | Hashes=DE
2. To=node 5 | Group=72C | Hello | Hashes=F

---

Node 3 combines the two packets it received as the best path to all three destinations is Node 6, and the packet contents are identical.
Nodes 4 and 5 send their packets directly to the destinations.

From Node 3:

1. To=node 6 | Group=72C | Hello | Hashes=CDE

From Node 4:

1. To=Broadcast | Group=72C | Hello | Hashes=AB (Alice and Bob receive the message)

From Node 5:

1. To=F5 | Group=72C | Hello | Hashes=F (Frank receives the message)

---

From Node 6:

1. To=C9 | Group=72C | Hello | Hashes=C (Charlie receives the message)
2. To=Broadcast | Group=72C | Hello | Hashes=DE (Dan and Erin receive the message)

---

Hopefully this helps explain things somewhat.
I have not demonstrated some of the edge cases described previously, I'll leave that to your imagination ;)

[LinuxinaBit]

This isn’t a great explanation, I know. It's late and I'm tired.
Hopefully this makes at least some sense, let me know if you have any questions.

[LinuxinaBit]

@liamcottle I’m going to mention you here because I think you might be somewhat interested in this too.
I kinda borrowed an idea from MeshCore here (using it for an entirely different thing) and I think it might actually work well.

[LinuxinaBit]

The reason that the individual addresses are full addresses instead of shorter hashes themselves is to differentiate the announces in the case of duplicates or larger groups, without requiring coordination between group members first.
Having duplicate hashes in the hash list shouldn’t cause issues (so long as there aren’t too many - there might need to be mitigations on the transport node side to prevent this), but having duplicate announces breaks things to a much greater degree.

Edit: Just realized that some mechanism to automatically expand hashes in the hash list when duplicates diverge to differentiate them could avoid all the issues caused by duplicate hashes.

[KenSamson]

Added a few options for multipath if that is a concern....

[KenSamson]

I think having a simplistic topology to talk through might help. Visually it makes sense that some of these nodes are going to possibly get some messages twice, and they need to know what to do with them. For very large groups, having something in the message for all members seems to be like a lot of overhead... It is good to talk through ideas.

[KenSamson]

In a completely different universe each group messaging LXMF type transport node could keep the group messages for a given group address for x amount of time, and if anyone asks them for the messages passed a certain timestamp as long as they are on the list of people in that group, the server could just hand them over.

In this way LXMF does it's job, and people can go to any server any time and ask for messages for a group so far back. Central routing as a push, last hop as a client software pull or even a push based on announce, like LXMF works today. LXMF already knows how to auto=peer, and how to not send the same info multiple times if it happens to have already gotten it from another peered LXMF node.

The idea of identity in presenting yourself to the LXMF node seems to already built in as well.. or could be elevated if need be. Generally I think for the last hop delivery those messages should be encoded to the final recipient. Messages sitting on the lxmf servers need to be encrypted in a way that physically getting that server does not allow access to the contents.

Clients could auto check in with their favorite LXMF server once a day or however often, like Meshchat already knows how to do today. Core issues would be what if 100 peers ask to get caught up on the same group with 10 meg messages all at once? In my brain we have to have a way to say come back later, I'm busy. Maybe even spread-schedule a future time to come back if the node is busy so it's spreading out the load over time.

A client could register with an LXMF node and let it know that it prefers to do a last hop pull because it is 99% offline.
A client that moves around and casually uses an LXMF node once in a while in different places would set the interaction to pull always.
A client that is up all the time on a reliable link could register as a push, so as soon as the LXMF node got it, it would queue it to go out as soon as reasonably possible.

The other beauty of this system is that if parts of the network go away... it all self recovers when it comes back up. There are more copies that can be auto-discovered in LXMF and the "few weeks" of messages can all get re-built.

For a given group, denoted by an lxmf address in my brain, the specific server does not store that group at all if nobody is asking for it from that server. It only stores the master list of groups and their members, but does not sync a group that no clients have asked it for.

Just ideas for now.

[LinuxinaBit]

LXMF is designed such that it is not reliant on Propagation Nodes to function at all, and they are only used in extraneous situations where there is effectively no other option.
LXMF is a message format first. Propagation Nodes are an add-on feature that is not necessary for core functionality.
This should be maintained in any kind of group chat system.

LXMF Propagation Nodes are not Transport Nodes.
They live on two separate layers of the network.
I linked to my explainer earlier in this discussion, hoping it would clear up some of your previous confusion on the subject, but it evidently did not.
Is there anything that I could explain further to help it make more sense?

[KenSamson]

So if 50% of your group destination recipients are offline 99% of the time, where will all of those messages be sitting?

[LinuxinaBit]

Nowhere. That is to be handled on the application layer
Group Destinations are not Group Chats.

Group Chats will be part of the LXMF protocol. That will manage what happens when people are offline.
Group Destinations will be part of the Reticulum protocol. They are simply trying to get data packets to everyone who is online when a packet is sent.

This is why the distinction between the LXMF and the Reticulum is so important to understand.
Without that distinction, nobody would have any idea what is going on. They are very separate things that do very different things.

The LXMF Group Chat system will need to be dynamic between peers and (optionally) Propagation Nodes, transitioning smoothly and making sure everyone gets messages. But this conversation is not concerned with that.
This discussion is supposed to be about Reticulum Group Destinations which are simply concerned with receiving packets. It’s essentially just a multicast mode for Reticulum.

Does that make some more sense?

[KenSamson]

So the LXMF implementation is an application layer activity, and format, just like DNS is an application layer, built mostly on UDP.

That does make sense. Nobody tries to hold DNS entries in an IP router. Routers queue as needed based on link congestion, but nobody would really build a "store and forward" router. Holding on to a packet for days is not what routers or switches do.

The application layer multicast overlay services in that same multicast article are part of how the shadow of application layer efforts is also part of the multicast solutions world. In that layer store and forward has to be a design consideration, as you mention, or the solution becomes unreliable. Pub/sub like MQTT especially in something like MQTT2MULTICAST or MQTT/UDP implementations starts to get interesting too, because people use those toolsets to get multicast functionality.

As you are trying to "make it work", it does make sense that you filter out the noise of the application layer activities and thoughts.

One message making many messages with even a little abuse in the wild can be very powerful and very dangerous, for sure.

[LinuxinaBit]

You have to do multicast on the Reticulum level, otherwise it’s not going to be efficient.
Doing so can cause issues and open up opportunities for abuse, but there are ways to mitigate them.

Other than that I think you understand now ;)

Sidenote: I have been kindof categorizing Reticulum using terms from the OSI Model, but it doesn’t technically fit that nicely.
Just know that there is a very purposeful separation between LXMF and Reticulum to specifically allow other paradigms to come and use Reticulum too.