micropycelium

A Mesh Network in MicroPython

Overview

  • Routable mesh network
  • MicroPython
  • ESP32 / ESP-NOW
  • Plugin system
    • Network interface adapters
    • Applications
  • Encapsulation mechanisms
  • Spanning tree embedding and greedy routing
  • ~6k lines of code and ~3k lines of tests

Goals

  • Decentralized from the ground up
  • Cheap, easy, and quick to deploy
  • Automatic network configuration
  • Reliable transmission mechanisms
  • Hobbyist-friendly tech stack
  • Eventual support for LoRa and other tx media

Architecture Overview

  • Currently supports ESP32
  • Interface adapter for ESP-NOW (802.11)
  • Requires building MicroPython firmware with custom modules
  • Async core + plugin system
  • Reference node with console interface via serial TTY

Spanning Tree Embedding

  • Based on VOUTE's representation of PIE
    notPIE
  • Constructs a logical spanning tree
  • Addresses are serialized coordinates

Spanning Tree Algorithm Overview

  1. Elect a root with an empty coordinate set.
  2. Root assigns a unique coordinate to each neighbor.
  3. They assign additional coordinates to their neighbors, etc.
    • Address is the encoded coordinates.
  4. Conduct periodic tree maintenance/recalculation

Coordinates and Addresses

root = []
root_addr = '::'
child1 = [1]
child1_addr = '10::'
child2_of_child1 = [1, 2]
child_2_of_child1_addr = '12::'
  • Up to 32 coords in an address (128 bits)
  • Encode 1-7 in a nibble or 8-135 in a byte
  • 32 tree levels with 7 children per parent
  • 16 tree levels with 135 children per parent
  • Tree membership between 1.1x10^27 and 1.2x10^34 nodes

diagram

Greedy Routing

  1. Select distance metric from packet header
  2. Calculate distance of each neighbor from the destination address
  3. Forward packet to neighbor with lowest distance

Greedy Routing: Common Prefix Length

class Address:
  ...
  @staticmethod
  def cpl(x1: list[int,], x2: list[int,]) -> int:
    """Calculate the common prefix length of two addresses."""
    cpl = 0
    for i in range(min(len(x1), len(x2))):
      if x1[i] != x2[i]:
        break
      cpl += 1
    return cpl
  • Used by both distance metrics
  • Example: cpl([1,2,3,0], [1,2,1,2]) == 2

Greedy Routing: dTree metric

class Address:
  ...
  def dTree_coords(self) -> list[int,]:
    """Return the routable coordinates for tree distance."""
    if 0 in self.coords:
      return self.coords[:self.coords.index(0)]
    return self.coords

  @staticmethod
  def dTree(x1: 'Address', x2: 'Address') -> int:
    """Calculate the tree distance between two addresses."""
    x1 = x1.dTree_coords()
    x2 = x2.dTree_coords()
    return len(x1) + len(x2) - 2 * Address.cpl(x1, x2)
  • E.g.: dTree([3,1,2,4], [3,1,3,6]) == 4

Greedy Routing: dCPL metric

class Address:
  ...
  def dCPL_coords(self) -> list[int,]:
    """Return the routable coordinates for CPL distance."""
    if len(self.coords) == 32:
      return self.coords
    return self.coords + [0] * (32 - len(self.coords))

  @staticmethod
  def dCPL(x1: 'Address', x2: 'Address') -> int:
    """Calculate the CPL distance between two addresses."""
    x1l, x2l = len(x1.coords), len(x2.coords)
    x1, x2 = x1.dCPL_coords(), x2.dCPL_coords()
    if x1 == x2:
      return 0
    return 33 - Address.cpl(x1, x2) - 1 / (x1l + x2l + 1)
  • E.g.: dCPL([3,1,2,...], [3,1,3,...]) == 31 - 1/7

Routing Comparison

img

[Turbo]Encapsulator

Encapsulation and Transmission

|-- Packet/sequence of packets --------|
|  |-- Package ---------------------|  |
|  |      app_id: 16                |  |
|  |      half_sha256: 16           |  |
|  |  |-- blob: variable --------|  |  |
|  |  |   Application Message    |  |  |
|  |  |--------------------------|  |  |
|  |------------------------------- |  |
|--------------------------------------|
  • Compact packet schemas
  • Sequencer for large messages
  • RNS/NIA, ASK/ACK, and RTX flags for transmission reliability
  • Broadcast, unicast, and gossip

Packet Schema: Fields

Name Size (bits)
version 8
reserved 8
schema 8
flags 8
packet_id 8 or 16
seq_id 8
seq_size 8 or 16
ttl 8
checksum 32
tree_state 8
to_addr 128
from_addr 128

Packet Schema: Header

0 1 2 3
version reserved schema flags

Built-In Apps

  • Beacon — Local peer (neighbor) discovery
  • Gossip — Message spreading (pseudo-flooding)
  • SpanningTree — Address assignment
  • Ping — Reachability checks
  • Debug — Network introspection and remote admin

Demo Time

screenshot

Dev Challenges

  • Undocumented differences within time and struct modules
    • Correct behavior from both in unit tests
    • time.time returns int instead of float, so async scheduler timings were off
    • struct.pack and struct.unpack are missing support for booleans
  • Cheap hardware is cheap, which is good when it doesn't work but even better when it does
    • E.g. fragmented heap causing RMT driver crash

Constraints

  • No ECC = no PKI yet
  • Memory and CPU performance limits
  • Modem sleep (machine.lightsleep) was buggy as hell

Remaining Work

  • Performance/reliability tuning and memory optimization
  • LoRa support via RYLR-998
  • Client lease addresses
  • Public key infrastructure (Beacon app)
    • Anyone familiar with libsodium?
    • Looking to extract Ed25519 core and port to MicroPython

Want to Contribute?

  • github.com/k98kurz/micropycelium
  • pycelium.com/community
  • Looking for:
    • Testers
    • Math nerds
    • Someone to help get libsodium ed25519 working in micropython

img

Credits / Shout-outs

  • VOUTE-Virtual Overlays Using Tree Embeddings, Stefanie Roos, Martin Beck, Thorsten Strufe
  • MicroPython community
  • Cedric for logos/artwork

</Presentation>

Questions?

- I did not use VOUTE's system because the address size would be up to 32x as large (32x128-bit coords=4096 bits vs just 128) - Fortunately, they represented PIE in a weird way that was much more pragmatic than the real thing - VOUTE's version of PIE is not isometric, and their distance metrics would not work on the original PIE - But their version is easier to encode and more practical in resource constrained systems like the ESP32

4. Track a tree state 1-byte checksum of the elected root's ID - Address buffer holds previous address to maintain routability across tree state transitions - Sounds good enough in theory that I implemented it, but it will require experimentation to prove utility and tune

- The child takes the parent's address with an appended coordinate. - Coordinates at a level in a sub-tree should be unique; parents just count up.

Example: root with empty coords; its children have two unique coords held in the first nibble of the address; their children have additional unique coords within their levels in their subtrees; etc. Dotted lines are non-tree connectivity.

Greedy routing requires only local data -- it does not require the full network graph to find a path as long as a path exists.

The basis for the distance metric is the common prefix length between two addresses. It is the number of preceeding coordinates that are identical.

dTree tends to prefer routing through nodes close to the tree root while dCPL may prefer longer routest hat avoid the tree root, instead forwarding to nodes in the same sub-tree.

The coordinates used for calculation are slightly different.

Example taken directly from the VOUTE paper demonstrating how the two routing metrics behave. Also used in unit tests.

As is the tradition of those who have come before, we have to discuss the core turbo encabulator that makes the whole project run.

Just kidding. But we will discuss encapsulation a bit.

The enacapsulation is conceptually simple: a Package intended for an Application contains the App's ID and a checksum, then it gets encapsulated in a Packet or Sequence of Packets from which it is reconstructed for delivery to the locally running Application. Applications can encapsulate Packages for other Apps; a real example of this is how Ping and DebugApp can send Packages encapsulated by Gossip.

All packets share a header, but the rest of the packet is determined according to the schema identified in the header. There are over twenty schemas right now for ESP-NOW and RYLR-998, and more can be made for additional interfaces.

All packets share a header, but the rest of the packet is determined according to the schema identified in the header. The idea was to have flexibility during development; we can trim the useless ones in the future if necessary.

- Beacon currently transmits locally-running App IDs but is intended to transmit public keys - Gossip is used by both Ping and DebugApp - Pin can use Gossip or routed mode

1. Modem sleep feature includes an intersection algorithm to ensure that a receiving node is awake before the data is sent. This requires further testing and dev work. 2. Implemented the micropython wrapper for TweetNaCl's ed25519 operations, but it was far too slow, ~1 second to create or verify a signature. TweetNaCl is optimized for compact code rather than performance.