Distributed secure routing in permissionless flat networks

title: Distributed secure routing in permissionless flat networks
class: animation-fade
layout: true

.bottom-bar[
 {{title}}
]

---

---

.col-3[
<img width="120" src="assets/hermies-gift.gif"></img>
]
.col-3[
<img width="100" src="assets/aether.png"></img>
]
.col-3[
<img width="100" src="assets/dat.png"></img>
]
.col-3[
<img width="100" src="assets/ipfs.svg"></img>
]

.col-2[
.big[.big[]]
]
.col-2[
.big[.big[]]
]
.col-2[
.big[.big[]]
]
.col-2[
.big[.big[]]
]
.col-2[
.big[.big[]]
]
.col-2[
.big[.big[]]
]

---

# Internet BGP inter-domain routing

---

.small[For a large network to scale, it must be subnetted into smaller, more easily manageable networks, which then must in turn be networked together (to form a network of networks from inter-network connections, i.e. the internet). This requires some level of expertise and planning to do, and ] .big[tends to favor hierarchies wherein small networks are largely at the mercy of a larger network] .small[(e.g. the only connection your LAN has to another network is your connection to an ISP, and “peering” or directly connecting to your neighbor’s LAN is virtually unheard of).]

.soft[.small[.small[_ Arceliar, Yggdrasil: The World Tree, https://yggdrasil-network.github.io/2018/07/17/world-tree.html_]]]

---

---

---

## Compact routing

in comparison to BGP inter-domain routing

- Keep small amounts of routing state at each router, rather than piling all that work onto the core network infrastructure

- Without the full network view, a node cannot always determine shortest path 
 .em[e.g. Dijkstra's algorithm as in OSPF]

- Have routing table grow sublinearly with number of nodes, while getting close to shortest path routing with upper bound

- Name-independent schemes that require no pre-processing are suitable for an unmanaged permissionless  network

---

- Auto-configure overlay network

- Secure all network traffic with end-to-end encryption:
  - .alt[Curve25519] .small[encryption keys]
  - .alt[Ed25519] .small[signatures]
  - .alt[XSalsa20] .small[stream cipher]
  - .alt[Poly1305] .small[MAC]

- Self-assign IPv6 in `fc00::/8` from cryptographic keys

- Source route with Kademlia-like distributed hash table
]

---

## Self-assignment of IP addresses
 for permissionless network participation

- Perform two rounds of SHA-512 on .alt[Curve25519 public key] then truncate to derive IPv6 address

- `fc00::/8` address space has 2120 addresses

### Birthday problem

>1 in 1,329,227,995,784,915,872,903,807,060,280,344,576 chance of generating the same IPv6. Feeling Lucky?

---

---

### Laying out IP addresses

<img width="770" src="assets/kademlia-map.png"></img>
]

- Node .code[.hi1[0011]] learns paths to _every_ neighbourhood

- Each node keeps a routing table at each .alt[XOR distance]

- Each node knows its neighbourhood well relative to distant ones
]

---

<img width="580" src="assets/kademlia-search.png"></img> 
.small[_ https://pdos.csail.mit.edu/~petar/papers/maymounkov-kademlia-lncs.pdf_]
]

- .code[.hi1[0011]] knows path to .code[.hi3[101]] and makes first query to learn .code[.em[1101]]

- .code[.hi1[0011]] makes successive queries .code[1] to .code[4] to reach .code[.hi2[1110]]

- .code[.hi1[0011]] calculates XOR distance:

>.code[.hi1[0011]] 
 >.code[.hi2[1110]] 
 >.code[.em[----.small[]]] 
 >.code[.alt[**1**101]] .em[.small[ XOR distance]]

- .code[.hi1[0011]] adds newly learnt path to its routing table at .code[.alt[**1**---]] bucket
]

---

---

#

---

## Source routing

#### Rick assembles the set of directors and sends to his peer Morty

| | | | | | | |
|:--|:--|:--|:--|:--|:--|:--|
| `0000000000000000000000000` | `0001` | `101011` | `011010` | `100101101` | `10111` | .code[.hi1[**0100011**]] |
| .big[] unused space | .big[] | .big[] | .big[] | .big[] | .big[] | .big[.hi1[]] |

#### Morty pops the .hi1[] director and sends it down the .hi1[] network interface

| | | | | | | |
|:--|:--|:--|:--|:--|:--|:--|
| .code[.hi1[**1000000**]] | `0000000000000000000000000` | `0001` | `101011` | `011010` | `100101101` | .code[.hi2[**10111**]] |
| .big[.hi1[]] | .big[] unused space | .big[] | .big[] | .big[] | .big[] | .big[.hi2[]] |

#### The reaches Morty's .hi1[] peer, Summer, and she sees the .hi2[] director

---

---

# Hyperboria
 with more than 1000 nodes mostly tunneled over Internet links

### DHT source routing limitations

- XOR address space distance and DHT does not resemble physical network topology

- Nodes lack local visibility to link quality typical of wireless links

- 64-bit packet header cannot fit all the directors for long paths with many hops

### Supernodes

- Supernodes have full network view and offer path discovery service to subnodes

- Traffic is still source routed and distributed throughout the mesh

---

# Yggdrasil Network

- Auto-configure a self-addressing encrypted network similar to cjdns

- Route traffic via paths resembling physical topology

- Allow all nodes to make the same assumptions about the network topology without keeping a full view

- Guarantee a path to every node, which although unbound in theory, is usually close to the shortest path
]

.small[_ https://en.wikipedia.org/wiki/Yggdrasil#/media/File:The_Ash_Yggdrasil_by_Friedrich_Wilhelm_Heine.jpg_]

---

## Routing in Yggdrasil

- Switch layer creates a .alt[globally agreed spanning tree ]

- A DHT is used to look up the .alt[] coordinates for a given IP address

- .alt[] edges are always direct peers, selected based on peering stability

- .alt[] coordinates are shared with peers and cryptographically verifiable from .alt[] root

- Switch layer uses .alt[] coordinate system for greedy embedded routing

- Each node keeps a partial view of .alt[] where locally stored state information scale at `O(p*log(n))` for `p` peers in a network with `n` nodes

- Routing traffic by walking .alt[] represents a worst-case path with guaranteed reachablity, since greedy routing often take shortcuts not shown on .alt[]

---

## Yggdrasil global spanning tree
 view from node .hi2[.code[**3efd**] .small[ .code[[ 3 ]]]]
.center[<img width="1100" src="assets/yggdrasil-map-1.png"></img>]

to .hi1[.code[**d40c**] .small[ .code[[ 3 5 2 ]]]]

- Tree path: .hi2[.code[[ 3 ]]] .small[] .em[.code[[ 3 5 ]]] .small[] .hi1[.code[[ 3 5 2 ]]]
--

- Greedy path: .hi2[.code[[ 3 ]]] .small[] .hi1[.code[[ 3 5 2 ]]]

---

---

<img width="600" src="assets/teeohmeeh.png"></img> 
.code[.soft[.big[**\#tomesh:tomesh.net**] .small[.small[] **freenode/\#tomesh**]]] 
.soft[.small[]] 
.code[.soft[**\#cjdns:matrix.org** .small[.small[] **efnet/\#cjdns**]]] 
.code[.soft[**\#yggdrasil:matrix.org** .small[.small[] **freenode/\#yggdrasil**]]]