1 Kademlia Routing with Standard Protocols
2 ========================================
4 On top of the standard prefix TBD1::/32 for 6bed4, a list of alternative
5 prefixes was proposed, including `fc64::/16` for local interpretation
6 as `fc64:<netid>:<ipv4>::/64`, a variant of the globally acceptable
7 interpretation of `TBD1:<ipv4>::/32`.
9 A highly interesting option is the `fd00::/8` prefix, which is extended
10 to a /48 by adding 40 random bits. Or, as we tend to do, with 56 random
11 bits to form a prefix `fdXX:XXXX:XXXX:XXXX::/64`. This is an interesting
12 notation for a network node that might be routed under local policy, for
13 instance using a Kademlia variant.
19 Kademlia is a peer-to-peer protocol, and it routes over varying and possibly
20 pervasive infrastructure. A variant to Kademlia is found in GNUnet, which
21 precedes a Kademlia address with a few extra bits that scatter messages out
22 over random routes before they recollect and find their way to the intended
25 Kademlia nodes have an address, and so do their peers. By computing the
26 exclusive or between a targeted destination address and its own address,
27 Kademlia can find progressive paths to close in on the destination. The
28 trick is that it favours the longest prefix, and only stores those that
29 start their exclusive or pattern with zeroes and a single one bit. In
30 other words, Kademlia looks one level down from its own address, at every
33 The scattering that initiates this search in GNUnet is easily added by
34 prefixing the target address with random bits, and treating those
35 addresses as proper recipient addresses to route.
38 Kademlia and the fdXX::/16 Prefix
39 ---------------------------------
41 As explained, we add 56 random bits to the `fd00::/8` prefix to find a
42 node address. Usually, this node address will be stable, so as to not
43 disservice clients and neighbours on the network.
45 When a packet arrives that is targeted at an address under a different
46 prefix, say `fdYY:YYYY:YYYY:YYYY::/64`, we can look for overlap with
47 the local nodes' `fdXX:XXXX:XXXX:XXXX::/64` and find the nodes that
48 service it one step down.
50 To add initial scatter in the style of GNUnet, we might choose to distort
51 the initial 8 bits of the address, but only after having made the routing
52 decision to enter Kademlia. This scattering would turn the address prefix
53 into `ZZYY:YYYY:YYYY:YYYY::/64`, which must only be done upon entry of the
54 Kademlia system, and only within a networking namespace that tolerates such
55 random initiations and searches for them in the Kademlia network. In fact,
56 the local node uses a somewhat more random prefix `XXXX:XXXX:XXXX:XXXX::/64`
57 and the target uses `YYYY:YYYY:YYYY:YYYY::/64` as its prefix.
59 We now have a routing key of 64 bits; the initial 8 bits scatter as well
60 as the `ZZ` are random, and the following 56 bits `YY:YYYY:YYYY:YYYY` close
61 in on the target, but only after having reached the scattered address.
62 The routing key is now treated as customary under Kademlia.
64 The router is assumed to have tunnels to the various nodes in the network.
65 In fact, there is usually a bag of multiple nodes to connect to, as part
66 of the resilient design of Kademlia. (It is worth investigating if the
67 initial scatter makes this less of a requisite.)
69 We can use any standard linking mechanism; since we are now in server land
70 we may choose a simple mechanism such as IP-in-IP or GRE. Indeed, it would
71 be useful to benefit from dual-stack routing, and support routes going over
72 IPv4 as well as over IPv6.
74 The storage required to perform this routing is simply this: for each of
75 the 64 address bits a bucket of (say 20) routers that may be contacted as
76 a remote tunnel endpoint. This setup is highly dynamic, and therefore less
77 practical to do in kernel space.
80 Building the Routing Table
81 --------------------------
83 **TODO: WORK IN PROGRESS**
85 Routing may be doable, but we still need to build the routing table. All
86 this starts with one or more seeds that allow entry into the Kademlia
87 network; those seeds define the realm that we enter. These seeds do not
88 exercise control of any kind; any node in the network may serve as a seed
89 and control quickly passes on to the other nodes.
91 As it turns out, standard ICMPv6 messages suffice, together with the notion
92 of link-local addresses that can store up to 64 bits of addressing information
93 with a link-specific interpretation.
95 We shall use `fe80::/64` addresses to indicate the remote end point, with
96 the following additional information:
98 * **TODO:** how; specifically, IPv6 addresses don't fit in here!
100 Kademlia uses a number of messages:
102 * `ping` to verify that a node is alive. This may be done using an ICMPv6
103 message sent to the address that we know lives on the other end.
104 * `store` to pass a mapping from an `fd00::/8` prefix to a routing address
105 to another node. This may be done using Router Advertisement.
106 * **TODO:** `find_node` and `find_value` map to Router Solicitation.
112 It is important to understand that the client is not forced to depend solely
113 on one hosted node. There is an option of diverging to other routers, albeit
114 that this changes the client's address. The lower part of the address does
115 not always change, but that is not a reliable assumption due to the diverse
118 Clients however, can have more than one address and can switch as they like,
119 thereby changing the upstream party that they rely on.
121 **TODO:** We might also exploit diversity through scattering, but only when
122 the client can be sure to sit on just a peer-to-peer network, without any
123 native routing or other prefixes being used than `fd00::/8`.
129 Nodes should communicate securely, and the best way to do this is through
130 IPsec; use AH for just authentication, or ESP for both authentication and
131 encryption of traffic.
133 It is worth noting that a UDP port has been
134 [set aside](https://tools.ietf.org/html/rfc3948) for ESP operation,
135 namely port 4500. When sending, both sender and recipient ports are
136 set to 4500, though on arrival it may only be set to 4500 for the recipient
137 port, due to NAT traversal.
139 The same port is used for both ESP encapsulation and IKE, so there are no
140 issues of any kind with NAT traversal.
142 **TODO:** All this does not matter much; we need to see the IPv6 header,
143 and only the layers after that can be protected with ESP. This is common.
144 What it does say however, is that we are not in search for an ESP transport,
145 but for an IPv6 transport. We end up wanting 6bed4... which we started with
148 It is strongly advised to protect the layers beyond IPv6 in a generic manner,
149 that is, using ESP. It is up to the application how to use ESP — in
150 tunnel mode, transport mode, or as part of the Host Identity Protocol.
152 It is very common in peer-to-peer networks to consider a public key as the
153 identity of a client. This is the private substitute for an email address.
156 Client Address Privacy
157 ----------------------
159 When working on a client's privacy, we should not reveal their address to
160 the world. And since the lower half of the address is only up for
161 interpretation by others using the same /64 prefix, this defines a good
164 The node offering the `fdXX:XXXX:XXXX:XXXX::/64` prefix should apply a
165 form of encryption to the lower half that is unwrapped when it sends
166 traffic over IPv4/UDP using the 6bed4 protocol. The encryption would
167 be reapplied when passing it on to another Kademlia node. The top half
168 of the address (plus, possibly, time) define the encryption applied.
170 This leaves a client address visible to other clients under the same
171 `fdXX:XXXX:XXXX:XXXX::/64` prefix, which may be acceptable (for a
172 company's node) or not (for a public server node). The client can
173 choose to always use another prefix than that in use by a targeted
174 peer. This is always possible for a peer with at least two prefixes.
176 Interestingly, when we designed 6bed4 we set the purpose of avoiding
177 trapezium-shaped routing and instead we preferred direct peering.
178 In a peer-to-peer network there may be choices that prefer to go
179 through at least two fallback routers; one to encrypt our own
180 lower address half, and another to decrypt the target's lower half.
181 And the opposite on reply traffic, of course.
projects / 6bed4 / blob