lib/reticulum/src/properties/link.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const hypothesis = @import("hypothesis");
3 const reticulum = @import("reticulum");
4
5 const wire = reticulum.wire;
6 const link = wire.link;
7
8 const rtt_round_trip_seed: u64 = 0x5237_4c49_4e4b_0001;
9 const rtt_plaintext_seed: u64 = 0x5237_4c49_4e4b_0002;
10 const layouts_seed: u64 = 0x5237_4c49_4e4b_0003;
11 const link_id_seed: u64 = 0x5237_4c49_4e4b_0004;
12 const deadlines_seed: u64 = 0x5237_4c49_4e4b_0005;
13 const link_faults_seed: u64 = 0x5237_4c49_4e4b_0006;
14
15 const sign_bit: u64 = 1 << 63;
16 const exponent_mask: u64 = 0x7ff << 52;
17
18 fn settings(seed: u64) hypothesis.Settings {
19 return hypothesis.Settings.quick()
20 .withSeed(seed)
21 .withDatabase("zig-out/hypothesis-failures/reticulum");
22 }
23
24 fn drawBits(data: *hypothesis.ConjectureData) !u64 {
25 const bits = std.mem.readInt(u64, (try data.drawBytes(8, 8))[0..8], .little);
26 return switch (try data.drawInteger(0, 3, 0)) {
27 0 => bits,
28 1 => bits | exponent_mask,
29 2 => bits | sign_bit,
30 else => bits & ~sign_bit,
31 };
32 }
33
34 fn acceptedBits(bits: u64) bool {
35 const seconds: f64 = @bitCast(bits);
36 return std.math.isFinite(seconds) and !std.math.signbit(seconds);
37 }
38
39 const RttRoundTrip = struct {
40 pub fn property(data: *hypothesis.ConjectureData, _: std.mem.Allocator) !void {
41 const bits = try drawBits(data);
42 var plaintext: [link.rtt_bytes]u8 = undefined;
43 plaintext[0] = 0xcb;
44 std.mem.writeInt(u64, plaintext[1..link.rtt_bytes], bits, .big);
45 const seconds = link.decodeRtt(&plaintext) catch {
46 try std.testing.expect(!acceptedBits(bits));
47 return;
48 };
49 try std.testing.expect(acceptedBits(bits));
50 try std.testing.expectEqual(bits, @as(u64, @bitCast(seconds)));
51 try std.testing.expectEqualSlices(u8, &plaintext, &link.encodeRtt(seconds));
52 }
53 };
54
55 test "property: the RTT codec round-trips every finite float64 with a clear sign bit" {
56 try hypothesis.checkNamed(
57 RttRoundTrip,
58 "reticulum-link-rtt-round-trip",
59 settings(rtt_round_trip_seed),
60 );
61 }
62
63 fn drawPlaintext(data: *hypothesis.ConjectureData, out: *[16]u8) ![]const u8 {
64 switch (try data.drawInteger(0, 2, 0)) {
65 0 => {
66 const drawn = try data.drawBytes(0, out.len);
67 @memcpy(out[0..drawn.len], drawn);
68 return out[0..drawn.len];
69 },
70 1 => {
71 out[0] = 0xcb;
72 std.mem.writeInt(u64, out[1..link.rtt_bytes], try drawBits(data), .big);
73 return out[0..link.rtt_bytes];
74 },
75 else => {
76 const drawn = try data.drawBytes(link.rtt_bytes, link.rtt_bytes);
77 @memcpy(out[0..link.rtt_bytes], drawn);
78 return out[0..link.rtt_bytes];
79 },
80 }
81 }
82
83 const RttPlaintexts = struct {
84 pub fn property(data: *hypothesis.ConjectureData, _: std.mem.Allocator) !void {
85 var storage: [16]u8 = undefined;
86 const plaintext = try drawPlaintext(data, &storage);
87 const valid = plaintext.len == link.rtt_bytes and plaintext[0] == 0xcb and
88 acceptedBits(std.mem.readInt(u64, plaintext[1..link.rtt_bytes], .big));
89 const seconds = link.decodeRtt(plaintext) catch {
90 try std.testing.expect(!valid);
91 return;
92 };
93 try std.testing.expect(valid);
94 try std.testing.expectEqualSlices(u8, plaintext, &link.encodeRtt(seconds));
95 }
96 };
97
98 test "property: RTT decoding accepts only the nine-byte float64 form" {
99 try hypothesis.checkNamed(
100 RttPlaintexts,
101 "reticulum-link-rtt-plaintexts",
102 settings(rtt_plaintext_seed),
103 );
104 }
105
106 fn expectSignalling(bytes: [link.signalling_bytes]u8, value: link.Signalling) !void {
107 const joined = (@as(u32, bytes[0]) << 16) + (@as(u32, bytes[1]) << 8) + bytes[2];
108 try std.testing.expectEqual(joined & 0x1f_ffff, @as(u32, value.mtu));
109 try std.testing.expectEqual((bytes[0] & 0xe0) >> 5, @as(u8, @backingInt(value.mode)));
110 }
111
112 const Layouts = struct {
113 pub fn property(data: *hypothesis.ConjectureData, _: std.mem.Allocator) !void {
114 const payload = try data.drawBytes(0, 128);
115 var out: [link.signalled_proof_bytes]u8 = undefined;
116 if (link.Request.decode(payload)) |request| {
117 try std.testing.expectEqualSlices(u8, payload[0..32], &request.encryption_public);
118 try std.testing.expectEqualSlices(u8, payload[32..64], &request.signing_public);
119 if (request.signalling) |value| try expectSignalling(payload[64..67].*, value);
120 try std.testing.expectEqualSlices(u8, payload, try request.encode(&out));
121 } else |_| {
122 try std.testing.expect(payload.len != link.request_bytes);
123 try std.testing.expect(payload.len != link.signalled_request_bytes);
124 }
125 if (link.Proof.decode(payload)) |proof| {
126 try std.testing.expectEqualSlices(u8, payload[0..64], &proof.signature);
127 try std.testing.expectEqualSlices(u8, payload[64..96], &proof.encryption_public);
128 if (proof.signalling) |value| {
129 try expectSignalling(payload[96..99].*, value);
130 const mode: u8 = @backingInt(link.proofMode(payload));
131 try std.testing.expectEqual(payload[96] >> 5, mode);
132 }
133 try std.testing.expectEqualSlices(u8, payload, try proof.encode(&out));
134 } else |_| {
135 try std.testing.expect(payload.len != link.proof_bytes);
136 try std.testing.expect(payload.len != link.signalled_proof_bytes);
137 }
138 const signalling = (try data.drawBytes(3, 3))[0..3].*;
139 const decoded = link.Signalling.decode(signalling);
140 try expectSignalling(signalling, decoded);
141 try std.testing.expectEqual(signalling, decoded.encode());
142 }
143 };
144
145 test "property: Reticulum@1.5.0 RNS/Link.py:144-187,399-406 link layouts split and round trip" {
146 try hypothesis.checkNamed(
147 Layouts,
148 "reticulum-link-layouts",
149 settings(layouts_seed),
150 );
151 }
152
153 fn requestFrame(
154 payload: []const u8,
155 transport_id: ?[16]u8,
156 destination: [16]u8,
157 hops: u8,
158 out: *[wire.mtu]u8,
159 ) ![]const u8 {
160 return wire.encode(.{
161 .ifac = 0,
162 .header = if (transport_id == null) .one else .two,
163 .context_flag = 0,
164 .transport = if (transport_id == null) .broadcast else .transport,
165 .destination_type = .single,
166 .packet_type = .link_request,
167 .hops = hops,
168 .transport_id = transport_id,
169 .destination = destination,
170 .context = .none,
171 .payload = payload,
172 }, out);
173 }
174
175 const LinkIds = struct {
176 pub fn property(data: *hypothesis.ConjectureData, _: std.mem.Allocator) !void {
177 const extra_max = wire.mtu - wire.header_two_bytes - link.request_bytes;
178 const payload = try data.drawBytes(link.request_bytes, link.request_bytes + extra_max);
179 const destination = (try data.drawBytes(16, 16))[0..16].*;
180 const transport_id = (try data.drawBytes(16, 16))[0..16].*;
181 const hops: u8 = @intCast(try data.drawInteger(0, wire.pathfinder_hops - 1, 0));
182 var frames: [3][wire.mtu]u8 = undefined;
183 const key_bytes = payload[0..link.request_bytes];
184 const keys = try requestFrame(key_bytes, null, destination, 0, &frames[0]);
185 const direct = try requestFrame(payload, null, destination, hops, &frames[1]);
186 const inserted = try requestFrame(payload, transport_id, destination, hops, &frames[2]);
187 const expected = try wire.hash.truncated(keys);
188 try std.testing.expectEqualSlices(u8, &expected, &try link.linkId(direct));
189 try std.testing.expectEqualSlices(u8, &expected, &try link.linkId(inserted));
190 }
191 };
192
193 test "property: Reticulum@1.5.0 RNS/Link.py:335-342 link ids ignore trailing bytes and HEADER_2" {
194 try hypothesis.checkNamed(
195 LinkIds,
196 "reticulum-link-ids",
197 settings(link_id_seed),
198 );
199 }
200
201 const node = reticulum.node;
202 const fixture = node.fixture;
203
204 const Session = reticulum.conformance.link.ThreeNodeVector;
205
206 /// Reticulum@1.5.0 RNS/Link.py:76,83,92-93,98 sets the keepalive bounds and the stale factor.
207 const keepalive_max: f64 = 360;
208 const keepalive_min: f64 = 5;
209 const keepalive_max_rtt: f64 = 1.75;
210 const stale_factor: f64 = 2;
211 /// RNS/Link.py:88,108,754,775 caps the delay between stale and close at five seconds.
212 const stale_grace: u64 = 5;
213 const initiator_establishment_seconds: u64 = 18;
214
215 fn session() Session {
216 const vectors = reticulum.conformance.link.three_node_vectors;
217 std.debug.assert(vectors.len == 1);
218 return vectors[0];
219 }
220
221 /// The keepalive period of a link with this round trip time, in float64 seconds, as
222 /// Reticulum@1.5.0 RNS/Link.py:795-797 computes it.
223 fn keepalivePeriod(rtt: f64) f64 {
224 return @max(@min(rtt * (keepalive_max / keepalive_max_rtt), keepalive_max), keepalive_min);
225 }
226
227 /// Reports whether `whole` is the least whole second at or after `instant`, which is what every
228 /// port link deadline has to be so that a port node never acts before the reference would.
229 fn leastSecondAtOrAfter(whole: u64, instant: f64) bool {
230 const value: f64 = @floatFromInt(whole);
231 if (value < instant) return false;
232 if (whole == 0) return true;
233 return value - 1 < instant;
234 }
235
236 /// Opens the recorded three-node link session in a world, with the relayed link proof held back
237 /// `delay` seconds so that A measures a round trip of exactly `delay`.
238 fn openSession(world: *fixture.World, delay: u64) !void {
239 const link_session = session();
240 try world.init(.{
241 .start = link_session.start_clock,
242 .transport_hash = link_session.transport_identity_hash[0..16].*,
243 .entropy = .{
244 .a = link_session.rtt_entropy[0..32].*,
245 .c = link_session.responder_entropy[0..32].*,
246 },
247 });
248 const owner = world.at(.c);
249 owner.identities[0] = reticulum.identity.Private.fromBytes(
250 link_session.destination_private_key[0..64].*,
251 );
252 try owner.destinations.register(.{
253 .hash = link_session.destination_hash[0..16].*,
254 .name_hash = link_session.destination_name_hash[0..10].*,
255 .kind = .single,
256 .proof_strategy = .all,
257 .identity_index = 0,
258 });
259 try world.step(.c, .{ .application_announce = .{
260 .destination = link_session.destination_hash[0..16].*,
261 .app_data = link_session.destination_app_data,
262 .random = link_session.announce_random_hash[0..5].*,
263 .fresh_rotating_key = null,
264 .now = world.clock,
265 .path_response = null,
266 } });
267 try world.runTo(link_session.retry_clock);
268 if (delay > 0) {
269 world.linkAt(.b_to_a).fault(.{ .delay = .{ .ordinal = 2, .seconds = delay } });
270 }
271 try world.runTo(link_session.request_clock);
272 try world.step(.a, .{ .application_link_open = .{
273 .destination = link_session.destination_hash[0..16].*,
274 .encryption_private = link_session.initiator_encryption_private_key[0..32].*,
275 .signing_private = link_session.initiator_signing_private_key[0..32].*,
276 .now = world.clock,
277 .proof_strategy = .all,
278 } });
279 try world.runTo(link_session.request_clock + delay);
280 }
281
282 fn linkTimerDeadline(world: *const fixture.World) !u64 {
283 var found: ?u64 = null;
284 for (world.records()) |entry| {
285 if (entry.owner != .a or entry.kind != .timer) continue;
286 if (entry.tag != .link) continue;
287 found = entry.deadline;
288 }
289 return found orelse error.MissingLinkTimer;
290 }
291
292 const LinkDeadlines = struct {
293 pub fn property(data: *hypothesis.ConjectureData, _: std.mem.Allocator) !void {
294 const delay = try data.drawInteger(0, initiator_establishment_seconds - 1, 0);
295 var world: fixture.World = undefined;
296 try openSession(&world, delay);
297 defer world.deinit();
298 const id = session().link_id[0..16].*;
299 const entry = world.at(.a).transport.links.find(id) orelse return error.MissingLink;
300 try std.testing.expectEqual(node.transport.links.Status.active, entry.status);
301 const rtt: f64 = @floatFromInt(delay);
302 try std.testing.expectEqual(rtt, entry.rtt);
303 const quiet: f64 = @floatFromInt(world.clock);
304 const period = keepalivePeriod(rtt);
305 try std.testing.expect(leastSecondAtOrAfter(
306 try linkTimerDeadline(&world),
307 quiet + period,
308 ));
309 const stale = world.clock + @as(u64, @intFromFloat(@ceil(period * stale_factor)));
310 world.linkAt(.b_to_a).fault(.{ .partition = .{
311 .from = world.clock + 1,
312 .until = stale + stale_grace,
313 } });
314 try world.runTo(stale + stale_grace);
315 const closed = world.lastRecord(.a, .link_closed) orelse return error.MissingLinkClose;
316 try std.testing.expectEqual(node.LinkCloseReason.timeout, closed.reason.?);
317 try std.testing.expect(leastSecondAtOrAfter(
318 closed.at - stale_grace,
319 quiet + period * stale_factor,
320 ));
321 }
322 };
323
324 test "property: every keepalive, stale, and close deadline is the least whole second at or after" {
325 try hypothesis.checkNamed(
326 LinkDeadlines,
327 "reticulum-link-deadlines",
328 settings(deadlines_seed),
329 );
330 }
331
332 fn drawLinkFault(data: *hypothesis.ConjectureData, offered: u32) !fixture.Fault {
333 const ordinal = offered + @as(u32, @intCast(try data.drawInteger(0, 3, 0)));
334 return switch (try data.drawInteger(0, 2, 0)) {
335 0 => .{ .drop = ordinal },
336 1 => .{ .delay = .{
337 .ordinal = ordinal,
338 .seconds = try data.drawInteger(1, 8, 1),
339 } },
340 else => .{ .swap = .{
341 .first = ordinal,
342 .second = offered + @as(u32, @intCast(try data.drawInteger(0, 3, 0))),
343 } },
344 };
345 }
346
347 const SeededLinkFaults = struct {
348 pub fn property(data: *hypothesis.ConjectureData, _: std.mem.Allocator) !void {
349 const link_session = session();
350 var world: fixture.World = undefined;
351 try openSession(&world, 1);
352 defer world.deinit();
353 inline for (.{ .a_to_b, .b_to_a, .b_to_c, .c_to_b }) |id| {
354 const wire_link = world.linkAt(id);
355 const offered = wire_link.offered;
356 const count = try data.drawInteger(0, 2, 0);
357 var index: u64 = 0;
358 while (index < count) : (index += 1) {
359 const value = try drawLinkFault(data, offered);
360 if (value == .swap and value.swap.first == value.swap.second) continue;
361 wire_link.fault(value);
362 }
363 }
364 const id = link_session.link_id[0..16].*;
365 const start = world.clock + 1;
366 for (0..2) |salt| {
367 try world.runTo(start + salt);
368 if (world.at(.a).transport.links.find(id) == null) break;
369 var iv = link_session.data_iv[0..16].*;
370 iv[15] ^= @as(u8, @intCast(salt));
371 try world.step(.a, .{ .application_link_send = .{
372 .link_id = id,
373 .plaintext = link_session.data_plaintext,
374 .iv = iv,
375 .now = world.clock,
376 } });
377 }
378 try world.runTo(start + 30);
379 try std.testing.expect(world.records().len <= fixture.records_max);
380 inline for (.{ .a_to_b, .b_to_a, .b_to_c, .c_to_b }) |id_at| {
381 try std.testing.expect(world.frameCount(id_at) <= fixture.deliveries_max);
382 }
383 }
384 };
385
386 test "property: seeded loss, delay, and reorder settle an active three-node link" {
387 try hypothesis.checkNamed(
388 SeededLinkFaults,
389 "reticulum-link-faults-settle",
390 settings(link_faults_seed),
391 );
392 }