lib/reticulum/src/node/transport/link/relay.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 //! A node running this code passes encrypted sessions that belong to other
2 //! pairs of nodes through itself.
3 //!
4 //! Two programs that want an encrypted session between them may sit many hops
5 //! apart, so the nodes in between have to pass the request outward, the answer
6 //! back, and then every packet of the session in both directions. A node in the
7 //! middle holds none of the session keys and reads none of the traffic.
8 //!
9 //! The node cannot read a session packet, so it decides which way the packet
10 //! goes from the hop count (the byte in the packet header that rises by one at
11 //! every node the packet passes through) and the network interface it arrived
12 //! on. Only the hops byte may change on a carried packet, so the node rewrites
13 //! that byte and leaves the rest of the frame untouched. A session that is
14 //! requested and never answered would hold its record for good, so each record
15 //! carries a deadline of six seconds for every hop that still remains. The
16 //! record store holds a fixed number of records, so a request that arrives with
17 //! the store full is dropped whole, leaving no half-written record.
18 //!
19 //! Reticulum 1.5.0, the reference implementation this package is a port of,
20 //! pinned to one upstream commit, keeps a record per carried session at every
21 //! node that carries traffic for others, keyed by the 16-byte id both ends
22 //! derive from the request. Each record carries a deadline per remaining hop
23 //! for the signed answer, and a sweep drops records past their deadline. This
24 //! port follows that design and cites the reference by file and line
25 //! throughout. An arriving session request goes out one hop nearer its
26 //! destination, and the node writes down what it did, as
27 //! Reticulum@1.5.0 RNS/Transport.py:1968-2010 lays out. The signed answer to
28 //! the request travels back the other way, and the record it answers is marked
29 //! as having passed that answer back toward the end that opened the session,
30 //! following Reticulum@1.5.0 RNS/Transport.py:2535-2600. Every later packet of
31 //! the session moves to whichever side it is bound for, as
32 //! Reticulum@1.5.0 RNS/Transport.py:2030-2077 does. A record leaves the store
33 //! once its clock runs out, following
34 //! Reticulum@1.5.0 RNS/Transport.py:843-856,902. The lineage is checkable in
35 //! this tree: the package README pins the upstream commit the port follows, and
36 //! the conformance corpus under src/conformance is generated from that release
37 //! and drives the differential tests.
38 //!
39 //! This node passes each encrypted session between two endpoints, named by a
40 //! 16-byte id that both ends derive from the request packet (a *link*). For
41 //! each link that crosses it, the node keeps a record holding both network
42 //! interfaces, the hop count in each direction, and the deadline by which the
43 //! signed answer must arrive (a *relay*). Each request waits for a signed
44 //! packet returned to confirm an earlier packet, which for a link request is
45 //! the receiving end accepting the link (a *proof*).
46 //!
47 //! The first departure concerns frame size. A link request or its proof may
48 //! carry three bytes past its fixed body (*signalling bytes*). Every network
49 //! interface in this package leaves its frame size unstated, so the node takes
50 //! the signalling bytes off each request it passes on and resizes nothing. A
51 //! network interface at Reticulum@1.5.0 RNS/Transport.py:1977-1996 may state a
52 //! frame size, and a relay there resizes a request toward any interface that
53 //! states one.
54 //!
55 //! The second departure concerns how a refusal reaches the caller. This node
56 //! reports each refusal in a record the step appends, naming why it turned the
57 //! packet away (a *diagnostic*). These are `link_relay_early` for a packet on a
58 //! relay whose proof has yet to pass, `link_relay_no_direction` for one whose
59 //! hop count fits neither side, and `link_entries_full` for a request that
60 //! arrives with the store full. Reticulum@1.5.0 RNS/Transport.py:2036-2037,2074
61 //! writes a warning to a log or raises a protocol violation for those same
62 //! three cases.
63 //!
64 //! The third departure concerns when a relay leaves the store. This node asks
65 //! its caller to wake it at the soonest deadline any relay holds (a *node
66 //! timer*), so each relay goes at the second it named.
67 //! Reticulum@1.5.0 RNS/Transport.py:245,843-856 wakes once a second and clears
68 //! every relay whose deadline has passed by then.
69 //!
70 //! The fourth departure concerns what a dead relay says about its path. This
71 //! node keeps what it learned from a destination's broadcast about reaching
72 //! that destination: the network interface to send on, the neighbor to name as
73 //! the next hop, and how many hops away the destination sits (a *path*). A
74 //! relay that goes without its proof leaves the path to its destination marked
75 //! as failed at once, which lets a farther broadcast take the path over, and
76 //! this node queues no path request.
77 //! Reticulum@1.5.0 RNS/Transport.py:858-865,904-926 marks the path only once
78 //! enough time has passed since it last asked after one, an instant this node
79 //! keeps no record of while it carries traffic for others.
80 //!
81 //! The fifth departure concerns a repeated request. A link request whose id
82 //! already sits in the store leaves every relay standing and reports
83 //! `link_request_duplicate`. Reticulum@1.5.0 RNS/Transport.py:2009 writes the
84 //! new relay over the one already there.
85 //!
86 //! - *link id*: the 16-byte name of one link, the same at every node the link
87 //! crosses.
88 //! - *carrier*: one network interface the node sends and receives over, named
89 //! by a small integer index.
90 //! - *destination*: the 16-byte hash that names one addressable endpoint on the
91 //! network.
92 //! - *initiator*: the end of a link that sent the request.
93 //! - *responder*: the end of a link the request was sent to.
94 //! - *transport node*: a node that carries traffic on behalf of other nodes, as
95 //! well as sending and receiving its own.
96 //! - *validated*: the mark a relay takes once this node has passed the
97 //! answering proof back toward the initiator.
98 //! - *unresponsive*: the mark a path carries once something that used it
99 //! failed, which lets a farther announce take the path over.
100 //! - *announce*: a packet carrying a destination's public keys and a signature,
101 //! so any node that hears it learns that destination and how far away it
102 //! sits.
103
104 const std = @import("std");
105 const reticulum = @import("../../../root.zig");
106
107 const node = reticulum.node;
108 const packet = reticulum.packet;
109 const wire = reticulum.wire;
110
111 const link_entries = node.transport.link.entries;
112 const Ed25519 = std.crypto.sign.Ed25519;
113
114 /// Sets how long a forwarded request may stay unanswered before its relay is
115 /// dropped: six seconds for each hop that still remains, the allowance
116 /// Reticulum@1.5.0 RNS/Link.py:96 gives a request proof.
117 const per_hop_timeout: node.Seconds = 6;
118
119 /// Answers whether an arriving link request is one for this node to pass on,
120 /// for the receive path to tell a request this node should carry from one it
121 /// should answer itself. That holds when the node carries traffic for others,
122 /// the packet names a node it is crossing, and the destination belongs to no
123 /// address of this node.
124 pub fn appliesToRequest(node_owner: *node.Node, value: wire.Packet) bool {
125 std.debug.assert(value.packet_type == .link_request);
126 if (!node_owner.transport.enabled) return false;
127 if (value.transport_id == null) return false;
128 return node_owner.destinations.find(value.destination) == null;
129 }
130
131 /// Looks a link id up among the relays this node keeps for other pairs, so the
132 /// receive path tells whether an arriving packet belongs to a session this node
133 /// carries. A node that carries no traffic for others gives null.
134 pub fn find(node_owner: *node.Node, link_id: [16]u8) ?*link_entries.Entry {
135 if (!node_owner.transport.enabled) return null;
136 return node_owner.transport.link_entries.find(link_id);
137 }
138
139 fn strippedRequest(frame: []const u8, signalled: bool) []const u8 {
140 if (!signalled) return frame;
141 std.debug.assert(frame.len > wire.link.signalling_bytes);
142 return frame[0 .. frame.len - wire.link.signalling_bytes];
143 }
144
145 fn arm(node_owner: *node.Node) node.StepError!void {
146 const soonest = node_owner.transport.link_entries.earliest() orelse {
147 _ = node_owner.timers.cancel(.link_entries);
148 return;
149 };
150 if (node_owner.timers.scheduledAt(.link_entries)) |at| {
151 if (at == soonest) return;
152 }
153 node_owner.timers.schedule(.link_entries, soonest) catch return error.TimerFull;
154 node_owner.effects.push(.{ .schedule_timer = .{
155 .id = .link_entries,
156 .at = soonest,
157 } }) catch return error.EffectsFull;
158 }
159
160 /// Sends an arriving link request on toward its destination and writes the
161 /// relay that lets the proof and the later traffic find their way, as
162 /// Reticulum@1.5.0 RNS/Transport.py:1935-1946,1968-2010,2021-2022 does. What
163 /// leaves has the three signalling bytes taken off, and the link id the
164 /// initiator computed travels on unchanged. Six seconds for each hop still
165 /// between this node and the destination sets the deadline the relay holds its
166 /// proof to. A destination this node holds no path to reports `no_path`. A
167 /// store already holding `link_entries_max` relays reports `link_entries_full`,
168 /// and every relay in it stands.
169 pub fn request(
170 node_owner: *node.Node,
171 value: wire.Packet,
172 raw: []const u8,
173 frame: node.CarrierFrame,
174 hash: packet.Hash,
175 ) node.StepError!void {
176 std.debug.assert(appliesToRequest(node_owner, value));
177 const link_id = wire.link.linkId(raw) catch unreachable;
178 const path = node_owner.transport.paths.find(value.destination, frame.now) orelse
179 return node.inbound.diagnostic(node_owner, .no_path, hash);
180 std.debug.assert(path.hops >= 1);
181 if (node_owner.transport.link_entries.find(link_id) != null) {
182 return node.inbound.diagnostic(node_owner, .link_request_duplicate, hash);
183 }
184 if (node_owner.transport.link_entries.full()) {
185 return node.inbound.diagnostic(node_owner, .link_entries_full, hash);
186 }
187 const fanout: node.outbound.Fanout = .{ .one = path.carrier };
188 const carriers = node.outbound.frameCount(node_owner, fanout);
189 if (carriers == 0) return node.inbound.diagnostic(node_owner, .no_path, hash);
190 if (!node_owner.timers.canScheduleAfterCancel(.link_entries, null)) return error.TimerFull;
191 try node.outbound.reserve(node_owner, carriers + 1, carriers);
192 const rewritten = if (path.hops > 1)
193 node.transport.rewrite.forward(raw, value.hops, path.next_hop, node_owner.scratch)
194 else
195 node.transport.rewrite.strip(raw, value.hops, node_owner.scratch);
196 const signalled = value.payload.len == wire.link.signalled_request_bytes;
197 const forwarded = strippedRequest(rewritten, signalled);
198 const deadline = frame.now +| per_hop_timeout * @as(node.Seconds, @max(1, path.hops));
199 _ = node_owner.transport.link_entries.insert(.{
200 .link_id = link_id,
201 .destination = value.destination,
202 .next_hop = path.next_hop,
203 .timestamp = frame.now,
204 .proof_deadline = deadline,
205 .next_hop_carrier = path.carrier,
206 .receiving_carrier = frame.interface,
207 .remaining_hops = path.hops,
208 .taken_hops = value.hops,
209 .validated = false,
210 }) catch unreachable;
211 path.timestamp = frame.now;
212 try arm(node_owner);
213 try node.outbound.transmit(node_owner, fanout, forwarded);
214 }
215
216 fn direction(entry: *const link_entries.Entry, value: wire.Packet, received: u8) ?u8 {
217 if (entry.next_hop_carrier == entry.receiving_carrier) {
218 if (value.hops == entry.remaining_hops or value.hops == entry.taken_hops) {
219 return entry.next_hop_carrier;
220 }
221 return null;
222 }
223 if (received == entry.next_hop_carrier and value.hops == entry.remaining_hops) {
224 return entry.receiving_carrier;
225 }
226 if (received == entry.receiving_carrier and value.hops == entry.taken_hops) {
227 return entry.next_hop_carrier;
228 }
229 return null;
230 }
231
232 /// Moves one packet of a relayed link to the side it is bound for, as
233 /// Reticulum@1.5.0 RNS/Transport.py:2030-2077 does. Which side that is follows
234 /// from the packet hop count together with the carrier it came in on. The hop
235 /// count is the one byte the node writes over. A packet is marked seen only
236 /// after the node has a side to send it to, so one overheard on a carrier both
237 /// sides share still moves. A packet arriving on a relay whose proof has yet to
238 /// pass reports `link_relay_early`.
239 pub fn traffic(
240 node_owner: *node.Node,
241 entry: *link_entries.Entry,
242 value: wire.Packet,
243 raw: []const u8,
244 frame: node.CarrierFrame,
245 hash: packet.Hash,
246 ) node.StepError!void {
247 std.debug.assert(node_owner.transport.enabled);
248 if (!entry.validated) {
249 return node.inbound.diagnostic(node_owner, .link_relay_early, hash);
250 }
251 const outgoing = direction(entry, value, frame.interface) orelse {
252 return node.inbound.diagnostic(node_owner, .link_relay_no_direction, hash);
253 };
254 const fanout: node.outbound.Fanout = .{ .one = outgoing };
255 const carriers = node.outbound.frameCount(node_owner, fanout);
256 if (carriers == 0) return node.inbound.diagnostic(node_owner, .no_path, hash);
257 if (!node_owner.timers.canScheduleAfterCancel(.link_entries, null)) return error.TimerFull;
258 try node.outbound.reserve(node_owner, carriers + 1, carriers);
259 _ = node_owner.duplicate_hashes.insert(hash);
260 const forwarded = node.transport.rewrite.rehop(raw, value.hops, node_owner.scratch);
261 entry.timestamp = frame.now;
262 try arm(node_owner);
263 try node.outbound.transmit(node_owner, fanout, forwarded);
264 }
265
266 fn validates(node_owner: *node.Node, entry: *const link_entries.Entry, payload: []const u8) bool {
267 const known = node_owner.known_identities.recall(entry.destination) orelse return false;
268 const decoded = wire.link.Proof.decode(payload) catch return false;
269 var signed: [wire.link.signed_proof_bytes_max]u8 = undefined;
270 const message = wire.link.signedProof(
271 entry.link_id,
272 decoded.encryption_public,
273 known.public_key[32..64].*,
274 decoded.signalling,
275 &signed,
276 );
277 const signer = Ed25519.PublicKey.fromBytes(known.public_key[32..64].*) catch return false;
278 Ed25519.Signature.fromBytes(decoded.signature).verify(message, signer) catch return false;
279 return true;
280 }
281
282 /// Sends the signed link request proof back toward the initiator, as
283 /// Reticulum@1.5.0 RNS/Transport.py:2535-2600 does. A proof arriving at a
284 /// different hop count than the relay expects, whose signature checks out,
285 /// first resets the relay and the path to the distance that proof traveled, as
286 /// Reticulum@1.5.0 RNS/Transport.py:2540-2562 does. A proof that arrives at the
287 /// expected hop count on the carrier the path leads out over, and checks out
288 /// against the identity this node recalls for the destination, marks the relay
289 /// validated and goes back over the carrier the request came in on. The relay
290 /// timestamp stays at the second its request arrived, so one that is validated
291 /// and then carries nothing runs out 900 seconds after that second. Any other
292 /// proof is named in a diagnostic and goes no further. Nothing moves until the
293 /// last thing that could refuse has been checked, so a proof that finds no
294 /// carrier out, no free timer slot, or no room among the effects touches
295 /// neither the relay nor the path.
296 pub fn proof(
297 node_owner: *node.Node,
298 entry: *link_entries.Entry,
299 value: wire.Packet,
300 raw: []const u8,
301 frame: node.CarrierFrame,
302 hash: packet.Hash,
303 ) node.StepError!void {
304 std.debug.assert(node_owner.transport.enabled);
305 std.debug.assert(value.context == .lrproof);
306 const from_next_hop = frame.interface == entry.next_hop_carrier;
307 const rebalances = value.hops != entry.remaining_hops and from_next_hop and
308 !entry.validated and validates(node_owner, entry, value.payload);
309 if (!rebalances and value.hops != entry.remaining_hops) {
310 return node.inbound.diagnostic(node_owner, .link_relay_no_direction, hash);
311 }
312 if (!from_next_hop) {
313 return node.inbound.diagnostic(node_owner, .proof_relay_wrong_interface, hash);
314 }
315 if (!rebalances and !validates(node_owner, entry, value.payload)) {
316 return node.inbound.diagnostic(node_owner, .proof_rejected, hash);
317 }
318 const fanout: node.outbound.Fanout = .{ .one = entry.receiving_carrier };
319 const carriers = node.outbound.frameCount(node_owner, fanout);
320 if (carriers == 0) return node.inbound.diagnostic(node_owner, .no_path, hash);
321 if (!node_owner.timers.canScheduleAfterCancel(.link_entries, null)) return error.TimerFull;
322 try node.outbound.reserve(node_owner, carriers + 1, carriers);
323 const forwarded = node.transport.rewrite.rehop(raw, value.hops, node_owner.scratch);
324 if (rebalances) {
325 entry.remaining_hops = value.hops;
326 if (node_owner.transport.paths.find(entry.destination, frame.now)) |path| {
327 path.hops = value.hops;
328 }
329 }
330 entry.validated = true;
331 try arm(node_owner);
332 try node.outbound.transmit(node_owner, fanout, forwarded);
333 }
334
335 /// Answers whether a relay leaving the store should cast doubt on the path it
336 /// went out over. Reticulum@1.5.0 RNS/Transport.py:886-889,908-915 casts that
337 /// doubt when either the destination or the initiator sat a single hop off, on
338 /// the reading that a silent neighbor has moved.
339 fn marksUnresponsive(
340 node_owner: *node.Node,
341 entry: *const link_entries.Entry,
342 now: node.Seconds,
343 ) bool {
344 if (entry.validated) return false;
345 if (entry.taken_hops == 1) return true;
346 return node_owner.transport.paths.hopsTo(entry.destination, now) == 1;
347 }
348
349 /// Clears every relay whose second has come and arms the timer again at the
350 /// soonest second still ahead, as Reticulum@1.5.0 RNS/Transport.py:843-856
351 /// does. A relay that went without its proof leaves its destination path marked
352 /// unresponsive, which lets the next announce stamped at the same emission take
353 /// that path over, as Reticulum@1.5.0 RNS/Transport.py:902,2208-2212 arranges.
354 pub fn timerExpired(node_owner: *node.Node, value: node.TimerExpired) node.StepError!void {
355 std.debug.assert(value.id == .link_entries);
356 try node.outbound.reserve(node_owner, 1, 0);
357 _ = node_owner.timers.cancel(value.id);
358 while (node_owner.transport.link_entries.expired(value.now)) |entry| {
359 const destination = entry.destination;
360 const marks = marksUnresponsive(node_owner, entry, value.now);
361 const removed = node_owner.transport.link_entries.remove(entry.link_id);
362 std.debug.assert(removed);
363 if (!marks) continue;
364 _ = node_owner.transport.paths.markUnresponsive(destination, value.now);
365 }
366 try arm(node_owner);
367 }