Migration to GitLab
[6bed4] / KADEMLIA.MD
1 Kademlia Routing with Standard Protocols
2 ========================================
3
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`.
8
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.
14
15
16 Kademlia Routing
17 ----------------
18
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
23 recipient.
24
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
31 prefix length.
32
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.
36
37
38 Kademlia and the fdXX::/16 Prefix
39 ---------------------------------
40
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.
44
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.
49
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.
58
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.
63
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.)
68
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.
73
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.
78
79
80 Building the Routing Table
81 --------------------------
82
83 **TODO: WORK IN PROGRESS**
84
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.
90
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.
94
95 The link-local addresses used to convey Kademlia peers are not the usual
96 `fe80::/64` addresses, but they are 6bed4 address.  Depending on the
97 [prefix and its promises](PREFIXES.MD), there may be a globally routable
98 IPv6 address or not; there may or may not be an IPv4 address in the top
99 half address.  In any case, the lower half of the address can be interpreted
100 for 6bed4 peering, so this will lead to an IPv4 address and an UDP port.
101 It is not important if this lower half information points to an end user
102 or a Kademlia node; as long as it is usable for routing purposes.
103
104 This is perhaps the vital part of peer-to-peer routing, the ability of
105 end users to perform routing.  To this end, they should be clear about
106 their reachability, which usually hinges on either local port forwarding
107 or a fallback server that is reachable under an IPv4 address.
108
109 Note how the routability of an IPv6 prefix is not dependent on the
110 actual presence of a native IPv6 route to the Kademlia node; we created
111 6bed4 precisely to overcome that obstacle.  And `fc64::/16` is also
112 usable for the same purposes, as this clearly defines a local network
113 to be used.  When a routable IPv6 prefix is provided, especially when it
114 is a native one, then connectivity over IPv6 is also arranged, which
115 is desirable as an alternative to IPv4-based routing (using 6bed4).
116
117 At some point in the future, we may not be able to rely on IPv4 as a
118 routing layer; by then, the address 0.0.0.0 will be used in the lower
119 half of the address to indicate that situation.
120
121 Kademlia uses a limited number of
122 [protocol messages](https://en.wikipedia.org/wiki/Kademlia#Protocol_messages):
123
124   * `ping` to verify that a node is alive.  This may be done using an ICMPv6
125     message sent to the address that we know lives on the other end.
126   * `store` to pass a mapping from an `fd00::/8` prefix to a routing address
127     to another node.  This may be done using Router Advertisement.
128   * **TODO:** `find_node` and `find_value` map to Router Solicitation.
129
130
131 Client Resiliency
132 -----------------
133
134 It is important to understand that the client is not forced to depend solely
135 on one hosted node.  There is an option of diverging to other routers, albeit
136 that this changes the client's address.  The lower part of the address does
137 not always change, but that is not a reliable assumption due to the diverse
138 nature of NAT.
139
140 Clients however, can have more than one address and can switch as they like,
141 thereby changing the upstream party that they rely on.
142
143 **TODO:** We might also exploit diversity through scattering, but only when
144 the client can be sure to sit on just a peer-to-peer network, without any
145 native routing or other prefixes being used than `fd00::/8`.
146
147 **TODO:** Clients can route between networks if they like (and be present
148 on each of the connected networks).  Challenge is to swap encryption while
149 moving from one network to another.  ECDH may be part of the solution, or
150 the router may take do this for egress/ingress "local" network frames.
151
152
153 Privacy and Security
154 --------------------
155
156 Nodes should communicate securely, and the best way to do this is through
157 IPsec; use AH for just authentication, or ESP for both authentication and
158 encryption of traffic.
159
160 It is worth noting that a UDP port has been
161 [set aside](https://tools.ietf.org/html/rfc3948) for ESP operation,
162 namely port 4500.  When sending, both sender and recipient ports are
163 set to 4500, though on arrival it may only be set to 4500 for the recipient
164 port, due to NAT traversal.
165
166 The same port is used for both ESP encapsulation and IKE, so there are no
167 issues of any kind with NAT traversal.
168
169 **TODO:** All this does not matter much; we need to see the IPv6 header,
170 and only the layers after that can be protected with ESP.  This is common.
171 What it does say however, is that we are not in search for an ESP transport,
172 but for an IPv6 transport.  We end up wanting 6bed4... which we started with
173 anyway `;-)`
174
175 It is strongly advised to protect the layers beyond IPv6 in a generic manner,
176 that is, using ESP.  It is up to the application how to use ESP &mdash; in
177 tunnel mode, transport mode, or as part of the Host Identity Protocol.
178
179 It is very common in peer-to-peer networks to consider a public key as the
180 identity of a client.  This is the private substitute for an email address.
181
182
183 Client Address Privacy
184 ----------------------
185
186 **TODO:** This is probably overkill.  It was worth a shot, but leads to
187 a chaotic design of everything involved.  In general, join a group that
188 you trust, and want to contact directly.  Join many groups if you like.
189 Route between groups and make your concealment efforts at that point.
190
191 When working on a client's privacy, we should not reveal their address to
192 the world.  And since the lower half of the address is only up for
193 interpretation by others using the same /64 prefix, this defines a good
194 privacy method.
195
196 The node offering the `fdXX:XXXX:XXXX:XXXX::/64` prefix should apply a
197 form of encryption to the lower half that is unwrapped when it sends
198 traffic over IPv4/UDP using the 6bed4 protocol.  The encryption would
199 be reapplied when passing it on to another Kademlia node.  The top half
200 of the address (plus, possibly, time) define the encryption applied.
201
202 This leaves a client address visible to other clients under the same
203 `fdXX:XXXX:XXXX:XXXX::/64` prefix, which may be acceptable (for a
204 company's node) or not (for a public server node).  The client can
205 choose to always use another prefix than that in use by a targeted
206 peer.  This is always possible for a peer with at least two prefixes.
207
208 Interestingly, when we designed 6bed4 we set the purpose of avoiding
209 trapezium-shaped routing and instead we preferred direct peering.
210 In a peer-to-peer network there may be choices that prefer to go
211 through at least two fallback routers; one to encrypt our own
212 lower address half, and another to decrypt the target's lower half.
213 And the opposite on reply traffic, of course.
214
215 A much better solution to this problem is possible on a server.  This
216 recognises that the normal extension of `fd00::/8` is up to a /48
217 prefix, and that this is already considered sufficient protection from
218 clashes.  So, a server might reserve a few of the last bits of its /64
219 prefix for an index.  This might look like `fdXX:XXXX:XXXX:XXXA::/64`
220 and `fdXX:XXXX:XXXX:XXXB::/64` and perhaps more.  Kademlia routing
221 will make it easy to pickup on both addresses on the same node.
222 The trick is now to look at the addresses shown to a client and
223 make sure that a the source and destination address never come from
224 the same prefix.  It is easy enough for the router to bounce traffic
225 between its clients with altered encryption, if so desired.
226
227 **TODO:** Another task would be to control the visibility of addresses
228 in non-IP protocols such as DNS.  This may be more challenging, though
229 not undoable either, if this is the only way to find addresses.  The
230 problem probably is that this is not the case; all sorts of protocols
231 may pass around peer addresses and we might end up re-inventing NAT...
232