lib/reticulum/src/identity/known.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const alloc_phase = @import("alloc_phase");
3 const reticulum = @import("../root.zig");
4
5 const destination = reticulum.destination;
6 const packet = reticulum.packet;
7
8 /// 333 bytes: the most application data one remembered announce keeps, the room
9 /// a 19-byte-header announce leaves for it, so a caller sizes that application
10 /// data, following Reticulum@1.5.0 RNS/Identity.py:511-578.
11 pub const app_bytes_max: usize = destination.announce.received_app_bytes_max;
12 /// 30 days in seconds: after that long a peer's rotating key stops being handed
13 /// out, so a caller works out how long that key stays usable, following
14 /// Reticulum@1.5.0 RNS/Identity.py:69.
15 pub const ratchet_expiry: u64 = 60 * 60 * 24 * 30;
16
17 pub const IdentityEntry = struct {
18 destination_hash: [16]u8,
19 public_key: reticulum.identity.KeyBytes,
20 announce_packet_hash: packet.Hash,
21 received: u64,
22 app_len: u16,
23 app_data: [app_bytes_max]u8,
24
25 pub fn applicationData(self: *const IdentityEntry) []const u8 {
26 std.debug.assert(self.app_len <= app_bytes_max);
27 return self.app_data[0..self.app_len];
28 }
29
30 pub fn public(self: *const IdentityEntry) reticulum.identity.Public {
31 return reticulum.identity.Public.fromBytes(self.public_key);
32 }
33 };
34
35 const IdentityLimits = struct {
36 identities_max: usize,
37 };
38
39 const IdentityCapacity = struct {
40 identities_max: usize,
41 storage_bytes: usize,
42
43 pub const DeriveError = error{ InvalidLimit, CapacityOverflow };
44
45 pub fn derive(limits: IdentityLimits) DeriveError!IdentityCapacity {
46 if (limits.identities_max == 0) return error.InvalidLimit;
47 const identities_max = limits.identities_max;
48 const storage_bytes = alloc_phase.capacity.mul(
49 usize,
50 identities_max,
51 @sizeOf(IdentityEntry),
52 ) catch return error.CapacityOverflow;
53 return .{ .identities_max = identities_max, .storage_bytes = storage_bytes };
54 }
55 };
56
57 pub const RememberIdentity = struct {
58 destination_hash: [16]u8,
59 public_key: reticulum.identity.KeyBytes,
60 announce_packet_hash: packet.Hash,
61 received: u64,
62 app_data: []const u8 = &.{},
63 };
64
65 /// The bounded store of what the node learned about other destinations from
66 /// their announcements, so a node looks a peer up here before it encrypts to
67 /// that peer or checks a signature from it, following Reticulum@1.5.0
68 /// RNS/Identity.py:101-160. One entry holds the destination hash, the 64 public
69 /// bytes of the identity, the hash of the announce it came from, the second it
70 /// arrived, and that announce's application data. An announce for a destination
71 /// already stored overwrites its entry, and once the store is full the entry
72 /// that arrived earliest is the one overwritten. Remembering application data
73 /// longer than 333 bytes returns `error.AppDataTooLong` and leaves the store as
74 /// it was.
75 pub const Identities = struct {
76 phase: alloc_phase.capacity.Phase,
77 capacity: Capacity,
78 storage: Storage,
79 entries: []IdentityEntry,
80 len: usize = 0,
81
82 pub const storage_alignment: usize = 8;
83 pub const Storage = []align(storage_alignment) u8;
84 pub const Limits: type = IdentityLimits;
85 pub const Capacity: type = IdentityCapacity;
86 pub const InitError = Capacity.DeriveError || error{StorageLengthMismatch};
87 pub const RememberError = error{AppDataTooLong};
88 pub const work_limits: alloc_phase.capacity.WorkLimits = .{
89 .transition_steps_max = 65_536,
90 .cleanup_steps_per_call_max = 0,
91 .cleanup_calls_at_capacity_max = 0,
92 };
93 pub const claim: alloc_phase.capacity.Declaration = .{
94 .source = .{
95 .id = "reticulum.known_identities",
96 .kind = .phase_static,
97 .limit_source = .caller,
98 .storage = .{
99 .covered = &.{.{
100 .id = "caller_known_identity_table",
101 .lifetime = .transferred,
102 .detail = "caller storage for known peer identities and announce data",
103 }},
104 .excluded = &.{
105 "borrowed lookup hashes",
106 "persistent identity records and storage effects",
107 },
108 },
109 .capacity = .{
110 .inputs = &.{alloc_phase.capacity.bindInput(
111 IdentityLimits,
112 "identities_max",
113 "identities_max",
114 )},
115 .type_selectors = &.{alloc_phase.capacity.bindType(
116 IdentityEntry,
117 "identity",
118 )},
119 .nodes = &.{
120 .{ .input = 0 },
121 .{ .scale = .{
122 .node = 0,
123 .coefficient = .{ .size_of_concrete_type = 0 },
124 } },
125 },
126 .assertions = &.{.{
127 .scope = .closure_total,
128 .measure = .retained,
129 .relation = .exact,
130 .expression = 1,
131 }},
132 },
133 .overload = .{
134 .kind = .not_applicable,
135 .detail = "a new identity replaces the oldest identity when full",
136 },
137 .risks = .{
138 .transitive = .{
139 .status = .excluded,
140 .detail = "known identity operations call no allocating owner",
141 },
142 .foreign = .{
143 .status = .excluded,
144 .detail = "known identity storage crosses no foreign boundary",
145 },
146 },
147 .work = .{ .equation = "operations scan at most identities_max entries" },
148 .obligations = &.{
149 .{ .key = "reticulum_known_identities_capacity", .role = .capacity_model },
150 .{ .key = "reticulum_known_identities_replace", .role = .overload },
151 .{ .key = "reticulum_known_identities_work", .role = .work_bound },
152 },
153 },
154 .bindings = .{
155 .owner = @This(),
156 .seal = .{
157 .family = alloc_phase.capacity.selector(@This().activate),
158 .premise = .{ .class = .checked_semantic_fact, .authority = .checker },
159 },
160 .teardown = .{
161 .family = alloc_phase.capacity.selector(@This().deinit),
162 .premise = .{ .class = .checked_semantic_fact, .authority = .checker },
163 },
164 },
165 };
166
167 pub fn init(storage: Storage, limits: Limits) InitError!Identities {
168 const capacity = try Capacity.derive(limits);
169 if (storage.len != capacity.storage_bytes) return error.StorageLengthMismatch;
170 return .{
171 .phase = .initialization,
172 .capacity = capacity,
173 .storage = storage,
174 .entries = std.mem.bytesAsSlice(IdentityEntry, storage),
175 };
176 }
177
178 pub fn activate(self: *Identities) void {
179 std.debug.assert(self.phase == .initialization);
180 std.debug.assert(self.len == 0);
181 self.phase = .steady;
182 }
183
184 pub fn remember(self: *Identities, value: RememberIdentity) RememberError!void {
185 std.debug.assert(self.phase == .steady);
186 if (value.app_data.len > app_bytes_max) return error.AppDataTooLong;
187 const target = self.mutable(value.destination_hash) orelse self.replacement();
188 target.* = .{
189 .destination_hash = value.destination_hash,
190 .public_key = value.public_key,
191 .announce_packet_hash = value.announce_packet_hash,
192 .received = value.received,
193 .app_len = @intCast(value.app_data.len),
194 .app_data = @splat(0),
195 };
196 @memcpy(target.app_data[0..value.app_data.len], value.app_data);
197 }
198
199 pub fn recall(self: *const Identities, hash: [16]u8) ?*const IdentityEntry {
200 std.debug.assert(self.phase == .steady);
201 for (self.entries[0..self.len]) |*entry| {
202 if (std.mem.eql(u8, &entry.destination_hash, &hash)) return entry;
203 }
204 return null;
205 }
206
207 /// Returns the stored entry whose identity hashes to the given identity
208 /// hash, so a caller holding an identity hash finds the entry it names,
209 /// following Reticulum@1.5.0 RNS/Identity.py:129-141. The call hashes each
210 /// stored key in turn, so it costs one pass over the store. The call
211 /// returns null when no entry matches.
212 pub fn recallByIdentityHash(
213 self: *const Identities,
214 identity_hash: [16]u8,
215 ) ?*const IdentityEntry {
216 std.debug.assert(self.phase == .steady);
217 for (self.entries[0..self.len]) |*entry| {
218 const candidate = reticulum.hash.truncated(&entry.public_key);
219 if (std.mem.eql(u8, &candidate, &identity_hash)) return entry;
220 }
221 return null;
222 }
223
224 pub fn count(self: *const Identities) usize {
225 std.debug.assert(self.phase == .steady);
226 return self.len;
227 }
228
229 pub fn deinit(self: *Identities) Storage {
230 std.debug.assert(self.phase == .steady);
231 self.phase = .teardown;
232 const storage = self.storage;
233 self.* = undefined;
234 return storage;
235 }
236
237 fn mutable(self: *Identities, hash: [16]u8) ?*IdentityEntry {
238 for (self.entries[0..self.len]) |*entry| {
239 if (std.mem.eql(u8, &entry.destination_hash, &hash)) return entry;
240 }
241 return null;
242 }
243
244 fn replacement(self: *Identities) *IdentityEntry {
245 if (self.len < self.capacity.identities_max) {
246 const target = &self.entries[self.len];
247 self.len += 1;
248 return target;
249 }
250 var oldest: usize = 0;
251 for (1..self.len) |index| {
252 if (self.entries[index].received < self.entries[oldest].received) oldest = index;
253 }
254 return &self.entries[oldest];
255 }
256 };
257
258 pub const RatchetEntry = struct {
259 destination_hash: [16]u8,
260 public_key: [32]u8,
261 received: u64,
262 };
263
264 const RatchetLimits = struct {
265 ratchets_max: usize,
266 };
267
268 const RatchetCapacity = struct {
269 ratchets_max: usize,
270 storage_bytes: usize,
271
272 pub const DeriveError = error{ InvalidLimit, CapacityOverflow };
273
274 pub fn derive(limits: RatchetLimits) DeriveError!RatchetCapacity {
275 if (limits.ratchets_max == 0) return error.InvalidLimit;
276 const ratchets_max = limits.ratchets_max;
277 const storage_bytes = alloc_phase.capacity.mul(
278 usize,
279 ratchets_max,
280 @sizeOf(RatchetEntry),
281 ) catch return error.CapacityOverflow;
282 return .{ .ratchets_max = ratchets_max, .storage_bytes = storage_bytes };
283 }
284 };
285
286 pub const Ratchets = struct {
287 phase: alloc_phase.capacity.Phase,
288 capacity: Capacity,
289 storage: Storage,
290 entries: []RatchetEntry,
291 len: usize = 0,
292
293 pub const storage_alignment: usize = 8;
294 pub const Storage = []align(storage_alignment) u8;
295 pub const Limits: type = RatchetLimits;
296 pub const Capacity: type = RatchetCapacity;
297 pub const InitError = Capacity.DeriveError || error{StorageLengthMismatch};
298 pub const work_limits: alloc_phase.capacity.WorkLimits = .{
299 .transition_steps_max = 65_536,
300 .cleanup_steps_per_call_max = 65_536,
301 .cleanup_calls_at_capacity_max = 1,
302 };
303 pub const claim: alloc_phase.capacity.Declaration = .{
304 .source = .{
305 .id = "reticulum.known_ratchets",
306 .kind = .phase_static,
307 .limit_source = .caller,
308 .storage = .{
309 .covered = &.{.{
310 .id = "caller_known_ratchet_table",
311 .lifetime = .transferred,
312 .detail = "caller storage for known peer rotating public keys",
313 }},
314 .excluded = &.{
315 "borrowed destination hashes",
316 "persistent rotating-key records and storage effects",
317 },
318 },
319 .capacity = .{
320 .inputs = &.{alloc_phase.capacity.bindInput(
321 RatchetLimits,
322 "ratchets_max",
323 "ratchets_max",
324 )},
325 .type_selectors = &.{alloc_phase.capacity.bindType(
326 RatchetEntry,
327 "ratchet",
328 )},
329 .nodes = &.{
330 .{ .input = 0 },
331 .{ .scale = .{
332 .node = 0,
333 .coefficient = .{ .size_of_concrete_type = 0 },
334 } },
335 },
336 .assertions = &.{.{
337 .scope = .closure_total,
338 .measure = .retained,
339 .relation = .exact,
340 .expression = 1,
341 }},
342 },
343 .overload = .{
344 .kind = .not_applicable,
345 .detail = "a new peer key replaces the oldest peer key when full",
346 },
347 .risks = .{
348 .transitive = .{
349 .status = .excluded,
350 .detail = "known rotating-key operations call no allocating owner",
351 },
352 .foreign = .{
353 .status = .excluded,
354 .detail = "known rotating-key storage crosses no foreign boundary",
355 },
356 },
357 .work = .{ .equation = "operations scan at most ratchets_max entries" },
358 .obligations = &.{
359 .{ .key = "reticulum_known_ratchets_capacity", .role = .capacity_model },
360 .{ .key = "reticulum_known_ratchets_replace", .role = .overload },
361 .{ .key = "reticulum_known_ratchets_work", .role = .work_bound },
362 },
363 },
364 .bindings = .{
365 .owner = @This(),
366 .seal = .{
367 .family = alloc_phase.capacity.selector(@This().activate),
368 .premise = .{ .class = .checked_semantic_fact, .authority = .checker },
369 },
370 .teardown = .{
371 .family = alloc_phase.capacity.selector(@This().deinit),
372 .premise = .{ .class = .checked_semantic_fact, .authority = .checker },
373 },
374 },
375 };
376
377 pub fn init(storage: Storage, limits: Limits) InitError!Ratchets {
378 const capacity = try Capacity.derive(limits);
379 if (storage.len != capacity.storage_bytes) return error.StorageLengthMismatch;
380 return .{
381 .phase = .initialization,
382 .capacity = capacity,
383 .storage = storage,
384 .entries = std.mem.bytesAsSlice(RatchetEntry, storage),
385 };
386 }
387
388 pub fn activate(self: *Ratchets) void {
389 std.debug.assert(self.phase == .initialization);
390 std.debug.assert(self.len == 0);
391 self.phase = .steady;
392 }
393
394 /// Stores a peer's rotating key against its destination hash, so a node
395 /// records the rotating key it read out of a peer's announce, following
396 /// Reticulum@1.5.0 RNS/Identity.py:410-425. A key already stored for that
397 /// destination is overwritten, and once the store is full the key that
398 /// arrived earliest is the one overwritten.
399 pub fn remember(self: *Ratchets, value: RatchetEntry) void {
400 std.debug.assert(self.phase == .steady);
401 const target = self.mutable(value.destination_hash) orelse self.replacement();
402 target.* = value;
403 }
404
405 /// Returns a peer's rotating key against its destination hash when one is
406 /// stored and has yet to expire, so a sender asks whether it has a rotating
407 /// key fresh enough to encrypt to, following Reticulum@1.5.0
408 /// RNS/Identity.py:485-508. A key that arrived more than 30 days before the
409 /// given second gives null. The call returns null when no key is stored for
410 /// that destination.
411 pub fn get(self: *const Ratchets, hash: [16]u8, now: u64) ?[32]u8 {
412 std.debug.assert(self.phase == .steady);
413 for (self.entries[0..self.len]) |entry| {
414 if (!std.mem.eql(u8, &entry.destination_hash, &hash)) continue;
415 if (expired(entry.received, now)) return null;
416 return entry.public_key;
417 }
418 return null;
419 }
420
421 pub fn clean(self: *Ratchets, now: u64) void {
422 std.debug.assert(self.phase == .steady);
423 var index: usize = 0;
424 for (0..self.capacity.ratchets_max) |_| {
425 if (index == self.len) return;
426 if (!expired(self.entries[index].received, now)) {
427 index += 1;
428 continue;
429 }
430 std.mem.copyForwards(
431 RatchetEntry,
432 self.entries[index .. self.len - 1],
433 self.entries[index + 1 .. self.len],
434 );
435 self.len -= 1;
436 }
437 }
438
439 pub fn count(self: *const Ratchets) usize {
440 std.debug.assert(self.phase == .steady);
441 return self.len;
442 }
443
444 pub fn deinit(self: *Ratchets) Storage {
445 std.debug.assert(self.phase == .steady);
446 self.phase = .teardown;
447 const storage = self.storage;
448 self.* = undefined;
449 return storage;
450 }
451
452 fn mutable(self: *Ratchets, hash: [16]u8) ?*RatchetEntry {
453 for (self.entries[0..self.len]) |*entry| {
454 if (std.mem.eql(u8, &entry.destination_hash, &hash)) return entry;
455 }
456 return null;
457 }
458
459 fn replacement(self: *Ratchets) *RatchetEntry {
460 if (self.len < self.capacity.ratchets_max) {
461 const target = &self.entries[self.len];
462 self.len += 1;
463 return target;
464 }
465 var oldest: usize = 0;
466 for (1..self.len) |index| {
467 if (self.entries[index].received < self.entries[oldest].received) oldest = index;
468 }
469 return &self.entries[oldest];
470 }
471 };
472
473 fn expired(received: u64, now: u64) bool {
474 if (now < received) return false;
475 return now - received >= ratchet_expiry;
476 }
477
478 comptime {
479 alloc_phase.capacity.requireProvisionedExactOwnerShape(Identities);
480 }
481
482 comptime {
483 alloc_phase.capacity.requireProvisionedExactOwnerShape(Ratchets);
484 }
485
486 fn identityValue(value: u8, received: u64, app_data: []const u8) RememberIdentity {
487 return .{
488 .destination_hash = @splat(value),
489 .public_key = @splat(value + 1),
490 .announce_packet_hash = @splat(value + 2),
491 .received = received,
492 .app_data = app_data,
493 };
494 }
495
496 test "known identities admit maximum and evict oldest at maximum plus one" {
497 comptime {
498 @stardustClaim(alloc_phase.capacity.witness(
499 Identities,
500 "reticulum_known_identities_capacity",
501 ), null, null, null, null, null, null);
502 @stardustClaim(alloc_phase.capacity.witness(
503 Identities,
504 "reticulum_known_identities_replace",
505 ), null, null, null, null, null, null);
506 @stardustClaim(alloc_phase.capacity.witness(
507 Identities,
508 "reticulum_known_identities_work",
509 ), null, null, null, null, null, null);
510 }
511 const capacity = comptime IdentityCapacity.derive(.{ .identities_max = 3 }) catch unreachable;
512 var bytes: [capacity.storage_bytes]u8 align(Identities.storage_alignment) = undefined;
513 var table = try Identities.init(&bytes, .{ .identities_max = 3 });
514 table.activate();
515 defer _ = table.deinit();
516 try table.remember(identityValue(1, 10, "one"));
517 try table.remember(identityValue(2, 20, "two"));
518 try table.remember(identityValue(3, 30, "three"));
519 try table.remember(identityValue(4, 40, "four"));
520 try std.testing.expect(table.recall(@splat(1)) == null);
521 try std.testing.expectEqual(@as(usize, 3), table.count());
522 }
523
524 test "Reticulum@1.5.0 RNS/Identity.py:101-160 recalls and replaces identities" {
525 const capacity = comptime IdentityCapacity.derive(.{ .identities_max = 3 }) catch unreachable;
526 var bytes: [capacity.storage_bytes]u8 align(Identities.storage_alignment) = undefined;
527 var table = try Identities.init(&bytes, .{ .identities_max = 3 });
528 table.activate();
529 defer _ = table.deinit();
530 try table.remember(identityValue(1, 10, "old"));
531 const original = table.recall(@splat(1)).?;
532 const identity_hash = reticulum.hash.truncated(&original.public_key);
533 try std.testing.expect(table.recallByIdentityHash(identity_hash) != null);
534 try table.remember(identityValue(1, 20, "new"));
535 try std.testing.expectEqualSlices(u8, "new", table.recall(@splat(1)).?.applicationData());
536 try std.testing.expectEqual(@as(usize, 1), table.count());
537 }
538
539 test "known ratchets admit maximum and evict oldest at maximum plus one" {
540 comptime {
541 @stardustClaim(alloc_phase.capacity.witness(
542 Ratchets,
543 "reticulum_known_ratchets_capacity",
544 ), null, null, null, null, null, null);
545 @stardustClaim(alloc_phase.capacity.witness(
546 Ratchets,
547 "reticulum_known_ratchets_replace",
548 ), null, null, null, null, null, null);
549 @stardustClaim(alloc_phase.capacity.witness(
550 Ratchets,
551 "reticulum_known_ratchets_work",
552 ), null, null, null, null, null, null);
553 }
554 const capacity = comptime RatchetCapacity.derive(.{ .ratchets_max = 3 }) catch unreachable;
555 var bytes: [capacity.storage_bytes]u8 align(Ratchets.storage_alignment) = undefined;
556 var table = try Ratchets.init(&bytes, .{ .ratchets_max = 3 });
557 table.activate();
558 defer _ = table.deinit();
559 for (1..5) |value| table.remember(.{
560 .destination_hash = @splat(@as(u8, @intCast(value))),
561 .public_key = @splat(@as(u8, @intCast(value + 10))),
562 .received = value,
563 });
564 try std.testing.expect(table.get(@splat(1), 4) == null);
565 try std.testing.expectEqual(@as(usize, 3), table.count());
566 }
567
568 test "Reticulum@1.5.0 RNS/Identity.py:69,463,494 expires peer ratchets exactly" {
569 const capacity = comptime RatchetCapacity.derive(.{ .ratchets_max = 3 }) catch unreachable;
570 var bytes: [capacity.storage_bytes]u8 align(Ratchets.storage_alignment) = undefined;
571 var table = try Ratchets.init(&bytes, .{ .ratchets_max = 3 });
572 table.activate();
573 defer _ = table.deinit();
574 table.remember(.{ .destination_hash = @splat(1), .public_key = @splat(2), .received = 10 });
575 try std.testing.expect(table.get(@splat(1), 10 + ratchet_expiry - 1) != null);
576 try std.testing.expect(table.get(@splat(1), 10 + ratchet_expiry) == null);
577 table.clean(10 + ratchet_expiry);
578 try std.testing.expectEqual(@as(usize, 0), table.count());
579 }