V2 Prefixes

[446564]

Here goes nothing.

Problem

We currently have 256 available, 1 byte, prefixes. These are taken from the repeater public key and used in pathing and traces (traces can now be longer prefixes).

While this has no major impact on the functionality of the mesh, as long as two conflicting prefixes are not zero-hop neighbors, it does cause confusion about paths taken and also presents a problem with analytic data accuracy.

Existing Discussions

• let's fix ID collision #562
• Proposal for v2: Support variable-length path segment sizes #1083
• The Case for Expanding Repeater IDs Beyond 1 Byte #1613

Liam on discord:

I'd probably opt for the path bytes to be dynamic length. so it can be changed in a future update, >or decided on a per request basis, while being backwards compatible (with future versions). here's >the numbers, for max hops, vs path bytes length per hop if it was changed. this is based on a >maximum of 64 bytes for the entire path

• 64 hops = 1 byte per hop
• 32 hops = 2 bytes per hop
• 16 hops = 4 bytes per hop
• 8 hops = 8 bytes per hop
• 4 hops = 16 bytes per hop
• 2 hops = 32 bytes per hop
• 1 hops = 64 bytes per hop

if the packet itself could say the length of bytes for each hop, then each hop could append that >many bytes from it's own id. but this would likely require a bit of work in the firmware, and >probably the app too.`

Proposal

Change to allow companion radios to configure their prefix resolution (in bytes), with a default of 2 and add a path_len to packets to store that resolution. ref: #1083 (comment).

This allows users to choose to use single byte but sets up new users to use a more robust prefix set.

Action Plan

There should be an intermediate firmware release early on that can handle and forward both packet formats, but not support to enable a different length at the companion level. This should be in the wild for a period of a few months at least (ideally more like 6). After this period we can release the changes to allow companions to set their resolution and have the default set at 2 bytes.

This should allow repeater owners enough time to get firmware updated before companions start trying to use new prefix resolutions.

The we can later phase out V1 support after we are relatively certain the majority of the meshes have updated.

Other Considerations

This should probably coincide with any changes to routing, if any, for V2. With a similar dual support early release.

[mepholic]

I believe that with increased prefix size, privacy conscious repeater operators are more likely to just not include a location in their repeater's adverts at all (or they will turn off adverts entirely), which has a similar impact on observability as not being able to correlate the path to individual repeaters in the first place.

I'm still not a fan of the repeater's public key being used to determine the path prefix, as there's no real reason to use the same values, and because changing the repeater's keys is much more difficult than just changing a value in flash which is used for the repeater prefix. Mishandled key rotations have a chance of locking repeater operators out of remote control of their repeaters.

Anyways, I feel that I've beat this drum enough at this point, and I'll leave it at that.

[446564]

I understand that but also repeaters should not be considered private generally, they are the cell towers of mesh. ofc small backyard repeaters can exclude location and many do, but ya that would be a whole different change, which could also be explored.

I like the alternate UUID thing for paths, like an address.

[hpux735]

I understand that but also repeaters should not be considered private generally, they are the cell towers of mesh. ofc small backyard repeaters can exclude location and many do, but ya that would be a whole different change, which could also be explored.

I like the alternate UUID thing for paths, like an address.

It's not whether the repeater is public, but you can often use repeater paths (which, yes, are public) to geolocate users, even those that don't share location data. I don't think that packet paths should be in clear-text ever. If you want to do a trace, there's a trace packet for that.

[MrAlders0n]

But it's trivially easy to locate a repeater by tracing its SNR, so by that same logic, SNR and RSSI should be obscured as well.

Anyone who believes that obscuring the repeater ID in the path provides them with anonymity or privacy is being given a false sense of security, and I think that's far more damaging.

[LitBomb]

It's not whether the repeater is public, but you can often use repeater paths (which, yes, are public) to geolocate users, even those that don't share location data. I don't think that packet paths should be in clear-text ever.

Being able to triangulated a companion's approximate location using repeater IDs in a message path is part of the meshcore's design. Those cats are already out of the bag, ships sailed, etc. We are not all of a sudden somehow decide a companion cannot be triangulated by the path its messages is sent. If it is, that is not a path ID issue. It would be a privacy issue. And if this is a problem for a user, meshcore is not for them.

If you want to do a trace, there's a trace packet for that.

If you want to keep your location untraceable, don't use meshcore.

[skyepn]

I'm still not a fan of the repeater's public key being used to determine the path prefix, as there's no real reason to use the same values, and because changing the repeater's keys is much more difficult than just changing a value in flash which is used for the repeater prefix. Mishandled key rotations have a chance of locking repeater operators out of remote control of their repeaters.

Agreed, I think this should be part of the Proposal, the Web Key Generator is a nice hack but should not be necessary.

[MrAlders0n]

I believe that with increased prefix size, privacy conscious repeater operators are more likely to just not include a location in their repeater's adverts at all, which has a similar impact on observability as not being able to correlate the path to individual repeaters in the first place.

I'm still not a fan of the repeater's public key being used to determine the path prefix, as there's no real reason to use the same values, and because changing the repeater's keys is much more difficult than just changing a value in flash which is used for the repeater prefix. Mishandled key rotations have a chance of locking repeater operators out of remote control of their repeaters.

Anyways, I feel that I've beat this drum enough at this point, and I'll leave it at that.

Unique IDs would make repeaters easier to locate, but that ship has already sailed. With noise floor and SNR data alone, which is readily available to anyone listening on the mesh, you can already pinpoint the approximate location of every repeater in an area quite easily. Mapping tools like MeshMapper have actually had to mask some of this signal data for exactly this reason. Keeping repeater IDs short and ambiguous doesn't meaningfully protect location privacy when the RF characteristics already give it away.

Take a guess where the below repeater is actually, and that's just based on noise-floor :)

[bryantkelley]

This change would functionally add a TTL to packets. Should we consider an explicit TTL so that the resolution would be able to decrease as the path fills up? Up to 64B for the first hop, 32B for the second, 16B for the third and fourth, etc.

[mepholic]

I am in favor of a more explicit TTL, I think it could be useful for a number of different situations. One way I've thought of to implement this is to use the reserved FF prefix to mean, "flood this packet for one hop". I think this could essentially act as a wildcard hop in existing paths.

To "flood" a packet for 3 hops and only 3 hops, one could specify the path FF, FF, FF. A path of 3A, FF, FF could be used to have the packet first go through repeater 3A, and then "flood" for 2 hops. Other iterations of this are feasible, such as FF, AA, BB, CC to have a packet be repeated by all directs first, and then try take a specific path afterwards.

[skyepn]

One way I've thought of to implement this is to use the reserved FF prefix to mean, "flood this packet for one hop". I think this could essentially act as a wildcard hop in existing paths.

Is there an open Feature Request issue for this? Seems like a really good idea.

[AI7NC]

What's the airtime utilization impact of this proposal. Sending 64 bytes for path data ever time seems like it's going to drasticlly impact our airtime utilization.

I'm absolutely in favor of finding a way to address the uniqueness problem but I'm skeptical this is the answer due to airtime use.

Have we thought about going to 2 bytes (because that's the minimum that needs to happen) and decoupling from the public key so if needed we can coordinate to avoid duplicates? You could designate some of the 2 byte pool to auto-generated addresses while reserving another portion for coordinated paths allowing for those of us running high level repeaters to ensure there isn't collision issues with other stations.

[AI7NC]

Forgive my ignorance, I'm very new to meshcore. Do we today use 64 bytes for the path segment of every packet?

[AI7NC]

Or is that just the largest it can get if you ran though 64 hops?

[AI7NC]

Because this table makes it seem that if you're sending 1-hop packet you're appending a 64 byte address to the packet which I don't think is what's happening today.

[mepholic]

Fixed-size 2 byte path elements seems like a good path forward to me. @AI7NC's suggestion of of reserving a certain pool of ID's for manual assignment seems like a good idea.

To clarify @446564's point: thankfully the proposal above trades off path specificity for hop count, so a path with a 64 byte hop ID would only be able to fit one hop, thus significantly reducing the global airtime utilization on the mesh as a whole (since a packet sent from a companion with a path in it is almost always a DIRECT, not a FLOOD).

@AI7NC's point about increased airtime utilization is a valid concern. For example:

Imagine you have 4 repeaters with the following 64 byte IDs:

92CA3F4A05D3778D5612B5FB7014DBF2EF534EB3F33E08252862EC4D668DAB9E4FECC45A3A6165C86918699B3D42D25CA94C597557BEDF9F0A9C3EC18EA74E94 
276394EC8CD4471B43CC0F5D32C467F2FEDFF885698A63CB4F798561D7091853E6A59DE7913DDD5D27514A466B994D163978DB4BC016CDFCC542624E2AAA2B9D 
73811E280623A3DD6AF5C087B17EA1981A34B5D4BA79ECF54339F1ECE8111475D6ACD492E8B2BF2BEB8151EAA1AD2B8A57626F9BE854EB9DD6716EAB567EC31D 
FC9B072FE68F64008AE4B4AF8F66C9E497F268EFA974EA8E75434A0400F457CE24B35D2966EFBDF2478059328D5FE79785ACDE695DB77F43B0BC7C52751CC484 

With the variable length path element proposal, there's 5 different ways to path through those repeaters, each with varying tradeoffs (increased airtime utilization and fewer max hops for better specificity/granularity)

1 byte IDs (4 bytes total, 60 hops remain) - Current implementation
  1 -> 92
  2 -> 27
  3 -> 73
  4 -> FC
2 byte IDs (8 bytes total, 28 hops remain)
  1 -> 92CA
  2 -> 2763
  3 -> 7381
  4 -> FC9B
4 byte IDs (16 bytes total, 12 hops remain)
  1 -> 92CA3F4A
  2 -> 276394EC
  3 -> 73811E28
  4 -> FC9B072F
8 byte IDs (32 bytes total, 4 hops remain)
  1 -> 92CA3F4A05D3778D
  2 -> 276394EC8CD4471B
  3 -> 73811E280623A3DD
  4 -> FC9B072FE68F6400
16 byte IDs (64 bytes total, 0 hops remain)
  1 -> 92CA3F4A05D3778D5612B5FB7014DBF2
  2 -> 276394EC8CD4471B43CC0F5D32C467F2
  3 -> 73811E280623A3DD6AF5C087B17EA198
  4 -> FC9B072FE68F64008AE4B4AF8F66C9E4

As you can see, you hit a point of diminishing returns pretty quickly. Considering the fact that 4 hops has been seen to carry packets hundreds of miles on some of the larger meshes, the added overhead and widespread airtime utilization impact from a user using 16 byte path elements is substantial. This seems like it could be rife for abuse.

Additionally, this "variable path element size" approach adds a lot of additional protocol level complexity. Both the companion and the repeaters in question would then be required to grapple with decisions regarding path element size.

The one simplifying factor here is that path element size can never be expanded on an in-flight packet which already contains path elements, because repeaters in the path should not attempt to guess (or "expand") unknown parts of other ID's in the path. As we have seen from previous attempts, trying to correlate truncated path elements with heard repeater adverts is error prone. A repeater guessing an expanded path element ID incorrectly will have devastating consequences on packet pathing and deliverability.

That all being said... repeaters could choose to truncate long path elements into shorter ones in certain cases without severely negatively impacting pathing and deliverability, which would honestly just further unnecessarily complicate matters.

[446564]

Thank you @mepholic, better explained than I.

And even if the firmware supports 1-64 hops, from the UX side we can choose to only offer a subset in the typical user facing apps. For example only resolution from 2-8 bytes, or 8-32 hops.

[LitBomb]

this has been an on-going discussion since just a couple months after the launch of meshcore almost a year ago. There are lots of good ideas on how to solve it. But at the end of the day, we need to hear what @ripplebiz' thinks about how he would like to solve this. Otherwise, we will just keep talking about this over and over again with no actionable solutions.

[446564]

We can also juat implement it

[MrAlders0n]

My fear is if not implemented someone will fork the project and implement and all of sudden the community is fractured.

[446564]

Unless they are kind and include backward compatibility. But I disagree that Scott has to be the one to decide, the community who uses and has helped build it to what it is should have just as much say. Or you will get exactly that, someone will fork and carry on.

[skyepn]

I'm in favour of whatever solution mitigates the id collision issue and also preserves the possibility of a 64 hop path.

I've seen several people suggest that reducing the maximum to 32 hops is enough, but I'm seeing screenshots from the UK that are already reaching 32. I think one of the big strengths of MeshCore is that it does not rely on a small number of long distance repeaters (decentralization), but the tradeoff is more hops.

[sveken]

In Australia we already have repeaters up on mountain tops and in good spots. We are already covering an area across 3 state/territorys and seeing close to 30 hops. The only way we can get better repeater locations is if we start making our own mountains. Decreasing the hop count would break these long distance connections to fix what is still a cosmetic bug.

[skyepn]

Decreasing the hop count would break these long distance connections to fix what is still a cosmetic bug

It's not just a cosmetic bug, it's causing real world issues with network planning.

But like anything else, it's a tradeoff: better region performance vs ability to route long distances.

The we can later phase out V1 support after we are relatively certain the majority of the meshes have updated.

Why phase out support for 1 byte routing? Maybe companions could have a setting for long distance mode.

Edit: I think I misunderstood, V1 is fixed 1 byte routing, V2 is variable byte routing including 1 byte routing.
So long distance is still possible, it just won't be the default client mode.
Explained here #1614 (reply in thread)

[sveken]

Decreasing the hop count would break these long distance connections to fix what is still a cosmetic bug

It's not just a cosmetic bug, it's causing real world issues with network planning.

But like anything else, it's a tradeoff: better region performance vs ability to route long distances.

The we can later phase out V1 support after we are relatively certain the majority of the meshes have updated.

Why phase out support for 1 byte routing? Maybe companions could have a setting for long distance mode.

Edit: I think I misunderstood, V1 is fixed 1 byte routing, V2 is variable byte routing including 1 byte routing.
So long distance is still possible, it just won't be the default client mode.
Explained here #1614 (reply in thread)

• Unsure what the planning issue is just need to make sure the neighbours do not collide, and yes, I have done network planning, connecting towns together and such.

[skyepn]

Unsure what the planning issue is just need to make sure the neighbours do not collide, and yes, I have done network planning, connecting towns together and such.

The issues have been described in great detail here #1613

[sveken]

Which I have read, pretty graphs and maps are handy, but I still don't see how it makes planning harder and is more cosmetic.

[GraphiteCA]

I think there's a pretty compelling "simple" argument for the new default to be atleast a 2 byte path.

I'm also for having some reserved space for "backbone" or "core" repeaters could be extremely useful, and hopefully provide some saving grace from someone randomly setting up a repeater and overlapping a major repeater.

In my case, I've spoken with folks from my local mesh (yyj) and the majority are fine for a hard cutover period of a few weeks where the mesh is a little broken as folks upgrade their software etc, in favour of resolving the duplicate issue more rapidly.

In the PNW we've seen 16-17 hops hit spans of 800+kms, I am not certain hop count is as pressing for us as the routing prefix issue is.

[dancollins]

I'm not familiar with the meshcore header. If we're proposing introducing a path-length field in the header, hopefully we're also going to keep it in 6 bits. If the plan was using 8 bits - well there's two more bits free in there for extended adresses (i.e. special-purpose addresses). Say, for example, we set the "I am a core repeater" bit - then there's no conflicts between 2a 2a and 2a 2a - because one of those two is a core repeater.

[dancollins]

I'm also not opposed to using TRACE packets specifically for testing the links. Regardless of 1 or 2-byte paths, we're still going to want comprehensive SNR/RSSI/Noise-floor measurements along a given path. That's a lot of info to cram into a general flood #public message..!

[liamcottle]

I'm also not opposed to using TRACE packets specifically for testing the links. Regardless of 1 or 2-byte paths, we're still going to want comprehensive SNR/RSSI/Noise-floor measurements along a given path. That's a lot of info to cram into a general flood #public message..!

Regarding the trace packets;

Trace packets were already updated in v1.11.0 firmware to allow for multi-byte path segments:
b33d226

e.g: 1-byte:[AA, BB, CC]
e.g: 2-byte: [AAAA, BBBB, CCCC]

I believe you can specify up to 4-byte path hashes. Of course this requires all repeaters in the trace to be on v1.11.0+
A future update to the mobile app will allow for selecting this.

[realtag-github]

@liamcottle why not allow to mix and match number of bytes? [AA, BBB, CCCC]? Use higher number of bits for when accuracy is needed and less when it's not. Is that feasible or am I missing something?

[WattleFoxxo]

@realtag-github thats not really feasible unfortunately

[446564]

The firmware has no way to tell what to parse from path length of 3 and a value of AABBBCCCC

[sveken]

The only problem is this by default would limit us to 32 hops?
In Australia we have only linked half way up the coast and we are already seeing low 20s in hop count

[mepholic]

If hop ID's were 3 nibbles (123, ABC, etc), the hop limit would go up to 42, and allow for 4096 unique IDs 😃

[446564]

The answer to life the universe and everything, 3 it is

[skyepn]

If hop ID's were 3 nibbles (123, ABC, etc), the hop limit would go up to 42, and allow for 4096 unique IDs 😃

Seems like enough but then you need double the number of bits to specify id_len in nibbles instead of bytes.

Also this Birthday Problem calculator says you only need 76 nodes for 50% chance of collision with 4096 unique IDs.
302 nodes for 50% chance of collision with 65536.

[sveken]

I agree with the idea of having dynamic prefix sizes but the default is the main point of concern.

I believe the best way to handle the default size is though the region defaults
eg. Australia (narrow) has 1 byte hops and EU/UK (narrow) has 2 byte hops,

this way new users wont be confused on why they cant talk to someone in Mount Gambia SA from Newcastle NSW.

Agreed, I fully support the variable idea. The main issue I am raising is the new default which could potentially break existing links. Wattles suggestion of having the default tied to the preset could be a nice way around it?

[tonurics]

I attempted to vote Yes, but not sure my vote was recorded.

My thoughts are that this should work akin to the CR option. Where the sender specifies the prefix size they want used on their message [via a single byte flag]. Each repeater would then append a prefix of the correct size.

• Packet observers can make informed decisions about reporting routing based on the prefix size flag.
• Senders who use larger prefix options run the risk of their messages not being decoded correctly.
• Appropriate prefix sizes should be communicated to users by network coordinators.

An optional repeater feature could be prefix size limits, either as a static value defined by the operator or one dynamically based on air time utilization. Any messages exceeding the limit would have the previous prefixes in the path truncated by the repeater.

[jhuebert]

I agree we need more than one byte for route prefixes. I'd suggest using variable-length prefixes in practice, even though the proposal allows for up to 64-byte prefixes. My concern is that while the proposal dynamical reduces the used prefix size, all 64 bytes of the path are still transmitted with every packet, which significantly increases airtime usage.

Instead, I'd recommend an adaptive approach with a maximum of 4 bytes per hop:
4-byte prefixes by default (up to 16 hops)
2-byte prefixes when exceeding 16 hops (up to 32 hops)
1-byte prefixes when exceeding 32 hops (up to 64 hops)

The goal is to minimize packet size for the most common scenarios (routes under 10 hops) while effectively eliminating the risk of prefix collisions. A 4-byte prefix should allow for billions of unique prefixes, which is more than sufficient. This approach scales bandwidth usage with path length—keeping overhead minimal for typical short routes while still supporting up to 64 hops when needed. I would also support the concept of reserved address ranges for manually specified addresses so they won't conflict accidentally for autogenerated addresses.

Additionally, companion devices should be able to specify their preferred prefix length when defining a path, allowing them to optimize based on their specific network topology and collision risk tolerance.

Another approach worth considering is a UTF-8-style encoding scheme that uses continuation bits to indicate whether additional bytes follow. This would allow each hop in the path to use a different prefix length as needed. To enhance privacy, repeater operators could specify a maximum number of bytes they're willing to add to the path of repeated packets, giving them control over the routing information they expose.

[446564]

Just a clarification, if the path is 2 hops and the prefix is 2 bytes we send 4 bytes not 64 bytes.

[DrakiaXYZ]

I like the "adaptive" approach; default to 2 or 4 bytes, then if the route is over the requisite hops to max out the path section of the packet, reduce the resolution of the path (And modify the path size flag) before passing it on to the next repeater

This seems like the best of both worlds, improved accuracy for local mesh maintenance, but still allow long haul packet transmission for areas that have sparse repeaters spanning large distances.

[GraphiteCA]

Conversely I'm a big fan of a defined approach. Default to 2 bytes, and if operators need 1/3/4 they can configure their networks of repeaters accordingly.

[tonurics]

I didn't see your comment yesterday and I ended up basically saying something very similar in my own comment. Having said that, I think this is the right approach.

I had the additional idea, where repeaters could dynamically reduce the prefix length based on the local air time utilization.

[awhite2000]

I operate a bot and an observer in Warsaw, PL metro area, where there are some 250 active repeaters. Occasionally when radio propagation is good we get packets from other major metro areas in Poland, hundreds of km away, and obviously with conflicting 1-byte prefixes.

I don't think I've ever spotted paths longer than 16 hops that would actually contribute in a meaningful way to discovery or communication - vast majority of them represent weird temporary pseudo-loops (packets bouncing around for so long that they are seen as "new" by the same repeaters), or contacts so far away that it's impossible to have any meaningful communication.

This is my long-winded way of saying that IMHO it would be totally fine to have 2-3 byte IDs and max 28-16 hops. :)