Proposal for v2: Support variable-length path segment sizes

[michaelhart]

Currently, path entries use a fixed 1-byte hash size. This can be extended to support 2-byte hashes by encoding the segment size in the upper 2 bits of path_len.

Proposal

You have 1 byte (8 bits = 256 possible states) for path_len. Encode:

• Lower 6 bits (0-63): Number of path entries (hops)
• Upper 2 bits: Path segment size selector

Upper 2 bits	Segment Size	Max Hops	Total Path Bytes
0b00 (0)	1 byte	64	64
0b01 (1)	2 bytes	32	64
0b10 (2)	reserved/future	varies	varies
0b11 (3)	extension	-	-

Extension Mechanism

To achieve full 64-byte path capacity, 0b11 indicates extension mode:

Extension Encoding:

• 0b11000001 → 1-byte segments, 64 hops (63 base + 1 extension)
• 0b11010001 → 2-byte segments, 32 hops (31 base + 1 extension)

When upper bits = 0b11:

• Bits 5-4: Segment type (00=1byte, 01=2byte, 10=reserved)
• Bits 3-0: Extension amount (add to max base value)

Implementation

1. Encoding (Packet.cpp)

uint8_t seg_code = ...; // 0=1byte, 1=2byte
uint8_t hop_count = ...;
uint8_t max_base = (seg_code == 0) ? 63 : 31;

if (hop_count <= max_base) {
  // Standard encoding
  path_len = (seg_code << 6) | hop_count;
} else {
  // Extension encoding for max hops
  uint8_t extension = hop_count - max_base;
  path_len = (0b11 << 6) | (seg_code << 4) | extension;
}

2. Decoding - Extract both values:

uint8_t path_byte = src[i++];
uint8_t upper = (path_byte >> 6) & 0x03;

if (upper != 0b11) {
  // Standard encoding
  seg_code = upper;
  hop_count = path_byte & 0x3F;
} else {
  // Extension mode
  seg_code = (path_byte >> 4) & 0x03;
  uint8_t extension = path_byte & 0x0F;
  uint8_t max_base = (seg_code == 0) ? 63 : 31;
  hop_count = max_base + extension;
}

seg_size = (1 << seg_code);  // 1 or 2 bytes
path_len = hop_count * seg_size;

3. Update PATH_HASH_SIZE

Make it variable based on packet version.

4. Update Path Operations

All path operations in Mesh.cpp that use PATH_HASH_SIZE need to be segment-size-aware.

Benefits

• Better collision resistance: 2-byte hashes reduce collisions significantly
• Privacy vs. traceability controls: Each packet can be sent at any size, offering either maximum privacy or maximum traceability
• Future-proof: Can support larger node networks

Challenges

• Backward compatibility: Old firmware won't understand the new encoding - requires a new packet version and a phased rollout strategy
• Code complexity: Every place that manipulates paths needs to understand variable segment sizes

[ripplebiz]

I like this encoding proposal. I was thinking similar, in that not all bits in path_len are currently used/needed.

[hpux735]

This is nice and clean. It doesn't help with the collision issue with 64-entries, of course, but that really can't be helped without making the field larger.

Is the intent that the sender would know whether that the path has to be a certain size, and sets it when the packet is created, and/or when a repeater adds itself to the path and it would exceed 16 hops it "compresses" the path into 2-byte, then again at 64?

[michaelhart]

Is the intent that the sender would know whether that the path has to be a certain size, and sets it when the packet is created, and/or when a repeater adds itself to the path and it would exceed 16 hops it "compresses" the path into 2-byte, then again at 64?

My thinking is that the sender would have a companion radio setting (like the double acks setting) that they can specify their preferred path segment size. Default to 1, the existing v1 behavior, and then they can change it to one of the supported values. A repeater compatible with these v2 packets would need to understand this field so that when it adds its prefix to the list of hops, it adds the correct number of bytes and updates the path_len field of the packet correctly.

So it's something that the sender would be 100% in control of, including always staying on 1 byte segments for maximum privacy or maximum hop count (full 64).

[hofmand]

Changing path_len to mean something other than "the number of bytes following" is risky because it could easily lead to devices of incompatible versions reading past the end of the buffer.

[michaelhart]

@hofmand This would require a new packet version, and old firmware should not interact with these packets anyway. They do not know how to handle the requirements/behavior of future versions, and so in my view any use/repeating/consumption of of v2 packets by v1-only firmware would be incorrect. If v1 firmware consumes v2 packets this way today, in my view that is an incorrect implementation and should be fixed as a bug.

The rollout strategy would require adding dual read support to firmware for some time before the firmware to create v2 packets is released.

[hpux735]

So it's something that the sender would be 100% in control of, including always staying on 1 byte segments for maximum privacy or maximum hop count (full 64).

Let's be very open-eyed about the privacy of MeshCore... Assume there is none. Even with one-byte routes, it's trivial to geolocate a user. This is especially true because we all work so hard to avoid repeater hash collisions that are nearby because the UI falls apart when there are collisions.

[michaelhart]

@hpux735 I mean simply it increases ambiguity. If I set my roof repeater to 7E (the same as Cougar which has 132 neighbors), my path information becomes significantly more ambiguous and difficult to understand. It requires a lot more effort to know if a 7E is actually Cougar or my now roof repeater, potentially even essentially impossible if you don't have any other perspectives of the packet.

[hpux735]

Yeh, I mean that's a pretty contrived example for how to maybe improve it.

What I'm saying is this: When paths are in packets, you'll never have privacy.

It's my belief that they shouldn't be there, to be honest. I think Reticulum makes the right call here.

[mepholic]

This kind of got buried in another thread, but I posted an extensive analysis on why I don't think the 1 byte repeater ID's are as much of a problem as they seem like. This is a UX issue, and we should work to solve the UX issue rather than mitigating it with deep down protocol changes:

#562 (comment)

#562 (comment)

[michaelhart]

I would rather not simply dismiss this as a "UX issue" when so many users would really like this to be done.

Ignoring one of the most common user requests will simply lead to a fork of MeshCore gaining popularity.

[hpux735]

Keep in mind thse bytes aren't pre-allocated, right? Just because the path can be 64-bytes long doesn't mean we should use all of them. Longer packets increase airtime utilization as well as increase the chance of interference causing packet loss.

[michaelhart]

Keep in mind thse bytes aren't pre-allocated, right? Just because the path can be 64-bytes long doesn't mean we should use all of them. Longer packets increase airtime utilization as well as increase the chance of interference causing packet loss.

I understand.

[mepholic]

@hpux735 I mean simply it increases ambiguity. If I set my roof repeater to 7E (the same as Cougar which has 132 neighbors), my path information becomes significantly more ambiguous and difficult to understand. It requires a lot more effort to know if a 7E is actually Cougar or my now roof repeater, potentially even essentially impossible if you don't have any other perspectives of the packet.

This is my point exactly. This ambiguity will always exist to an extent if we're trying to use a truncated pubkey that a repeater includes in its path to identify it amongst pubkeys stored in your contact database.

A good solution to this would be to extend the CONTROL packet payload type that Scott recently implemented to allow querying the exact public key of a repeater at a path. This will allow clients who care about which specific repeater they're bouncing off of to query the repeater for the info and receive an entirely unambiguous answer.

This would work without changing the path format at all, and due to the fact that repeaters will rarely have over 255 direct neighbor repeaters, that's not an issue for now.

Another UX hurdle is that when an ID collision does occur, the user is required to change their repeater's entire keypair to get a new repeater ID. This breaks management channel continuity, and could easily cause repeater admins to get locked out of their repeater.

With the above scheme of querying repeaters (at a specific path) for their pubkey when a user cares to see it, there's no reason for a repeater's ID to be related to it's public key. We could simply allow repeater operators to choose any unused ID, without having to rotate their keys.

Implementing this would also help with diagnostic functions such as detecting repeater ID collisions at a specific path, as both repeaters would respond to the request. Repeater ID collisions will always have a small random chance of happening (which yes, arguably diminishes if you make the numbers bigger), but there's always still a chance of collisions happening.

I personally don't have time to implement this right now as I'm busy with my dayjob and a Meshcore-derived side project, but I'm invested in the success of the protocol, and personally think that there are better solutions to the problems that we're having than breaking path compatibility.

We may need to increase the size of the path elements eventually, and while I think that the variable-length path element implementation is quite clever, it unfortunately introduces minor unnecessary complexities in terms of parsing the protocol, and much bigger complexities in terms of accurately representing the protocol in protocol definition languages like ASN.1

I think if we ever determine that more path element specificity is actually necessary, due to larger than expected neighbor repeater counts (for ex: we regularly start seeing repeaters in satellites or planes??), increasing the paths to 3 or 4 nibbles, and making them a static element size is probably the best option. At that point we'll need other protocol breaking changes anyways.

[michaelhart]

I disagree. This is a growth pain point for MeshCore. Ask users.

[LitBomb]

sorry @mepholic Dan <3, I think saying this is only an UX issue is a cop out. It is a real issue. true, it is not breaking the mesh, messages still go through. If meshcore was to EOL today and no more update iwould be made to it, yes, we can still use it. it is a deficiency that should be fixed. I think most meshcore users and the devs agree this should be updated to minimize collisions. @michaelhart has a sensible solution. many more tools like LetsMesh and Home Assistant MeshCore integration can be even better at what they do if they don't have to constantly patching and guessing which one of the many duplicated repeaters is the real one. Besides how awesome MeshCore already is, all the tools that are spawned off of MeshCore's openness is unique and MeshCore should continue to add more support to let these tools flourish.