lib/reticulum/src/packet/receipt.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const alloc_phase = @import("alloc_phase");
3 const reticulum = @import("../root.zig");
4
5 const identity = reticulum.identity;
6 const packet = reticulum.packet;
7 const wire = reticulum.wire;
8
9 pub const Seconds = u64;
10
11 /// Records how one sent Reticulum datagram (*packet*) stands, so a caller
12 /// learns what became of it: failed, sent, delivered, or culled, following
13 /// Reticulum@1.5.0 RNS/Packet.py:396-400.
14 pub const Status = enum(u8) {
15 failed = 0,
16 sent = 1,
17 delivered = 2,
18 culled = 0xff,
19 };
20
21 /// The largest value a timeout holds marks the record of one sent datagram
22 /// (*receipt*) for culling, so a caller tells a receipt dropped to make room
23 /// from one that timed out. The reference marks the same condition with a
24 /// negative timeout, and seconds here are unsigned, following Reticulum@1.5.0
25 /// RNS/Packet.py:540-543.
26 pub const culling_timeout: Seconds = std.math.maxInt(Seconds);
27
28 pub const Receipt = struct {
29 hash: packet.Hash,
30 truncated: [16]u8,
31 destination: [16]u8,
32 sent_at: Seconds,
33 timeout: Seconds,
34 status: Status = .sent,
35 concluded_at: ?Seconds = null,
36
37 /// Checks an arriving signature datagram (*proof*) against the sent packet
38 /// record (*receipt*) and marks the packet delivered when it holds, so the
39 /// node learns the packet arrived, following Reticulum@1.5.0
40 /// RNS/Packet.py:485-520. A 96-byte proof (*explicit proof*) has to carry
41 /// the receipt's own full hash beside a signature over it, and a 64-byte
42 /// proof (*implicit proof*) has to carry a signature over that hash. A
43 /// proof that fails either check leaves the receipt as it was.
44 pub fn validateProof(
45 self: *Receipt,
46 value: wire.proof.Proof,
47 public: *const identity.Public,
48 now: Seconds,
49 ) bool {
50 const valid = switch (value) {
51 .explicit => |explicit| std.mem.eql(u8, &explicit.packet_hash, &self.hash) and
52 public.validate(explicit.signature, &self.hash),
53 .implicit => |implicit| public.validate(implicit.signature, &self.hash),
54 };
55 if (!valid) return false;
56 self.status = .delivered;
57 self.concluded_at = now;
58 return true;
59 }
60
61 /// Moves the record of a sent datagram (*receipt*) out of the sent state
62 /// once its wait has run out, and records the second it concluded, so the
63 /// node gives up on a packet nothing answered, following Reticulum@1.5.0
64 /// RNS/Packet.py:537-548. A receipt that already concluded is left as it
65 /// is. A receipt whose timeout holds the culling value is marked culled at
66 /// once.
67 pub fn checkTimeout(self: *Receipt, now: Seconds) void {
68 if (self.status != .sent) return;
69 if (self.timeout == culling_timeout) {
70 self.status = .culled;
71 self.concluded_at = now;
72 return;
73 }
74 if (now <= self.sent_at) return;
75 if (now - self.sent_at <= self.timeout) return;
76 self.status = .failed;
77 self.concluded_at = now;
78 }
79 };
80
81 /// Returns how long a sent datagram (*packet*) may wait for a proof, so the
82 /// wait grows with the distance the packet travels: the first-hop wait plus six
83 /// seconds for each hop, following Reticulum@1.5.0 RNS/Packet.py:115,420-423
84 /// and Reticulum@1.5.0 RNS/Reticulum.py:142. Both additions saturate, so a
85 /// large count of hops (*hop count*) gives the largest value the type holds.
86 pub fn timeoutFor(first_hop: Seconds, hops: u8) Seconds {
87 const hop_timeout = @as(Seconds, hops) *| 6;
88 return first_hop +| hop_timeout;
89 }
90
91 const TableLimits = struct {
92 receipts_max: usize,
93 };
94
95 const TableCapacity = struct {
96 receipts_max: usize,
97 storage_bytes: usize,
98
99 pub const DeriveError = error{ InvalidLimit, CapacityOverflow };
100
101 pub fn derive(limits: TableLimits) DeriveError!TableCapacity {
102 if (limits.receipts_max == 0) return error.InvalidLimit;
103 const receipts_max = limits.receipts_max;
104 const storage_bytes = alloc_phase.capacity.mul(
105 usize,
106 receipts_max,
107 @sizeOf(Receipt),
108 ) catch return error.CapacityOverflow;
109 return .{ .receipts_max = receipts_max, .storage_bytes = storage_bytes };
110 }
111 };
112
113 pub const Table = struct {
114 phase: alloc_phase.capacity.Phase,
115 capacity: Capacity,
116 storage: Storage,
117 entries: []Receipt,
118 len: usize = 0,
119
120 pub const storage_alignment: usize = 8;
121 pub const Storage = []align(storage_alignment) u8;
122 pub const Limits: type = TableLimits;
123 pub const Capacity: type = TableCapacity;
124 pub const InitError = Capacity.DeriveError || error{StorageLengthMismatch};
125 pub const work_limits: alloc_phase.capacity.WorkLimits = .{
126 .transition_steps_max = 1_025,
127 .cleanup_steps_per_call_max = 0,
128 .cleanup_calls_at_capacity_max = 0,
129 };
130 pub const claim: alloc_phase.capacity.Declaration = .{
131 .source = .{
132 .id = "reticulum.receipts",
133 .kind = .phase_static,
134 .limit_source = .caller,
135 .storage = .{
136 .covered = &.{.{
137 .id = "caller_receipt_table",
138 .lifetime = .transferred,
139 .detail = "caller storage for bounded delivery receipts",
140 }},
141 .excluded = &.{
142 "borrowed proof identities",
143 "proof packet bytes and application callbacks",
144 },
145 },
146 .capacity = .{
147 .inputs = &.{alloc_phase.capacity.bindInput(
148 Limits,
149 "receipts_max",
150 "receipts_max",
151 )},
152 .type_selectors = &.{alloc_phase.capacity.bindType(Receipt, "receipt")},
153 .nodes = &.{
154 .{ .input = 0 },
155 .{ .scale = .{
156 .node = 0,
157 .coefficient = .{ .size_of_concrete_type = 0 },
158 } },
159 },
160 .assertions = &.{.{
161 .scope = .closure_total,
162 .measure = .retained,
163 .relation = .exact,
164 .expression = 1,
165 }},
166 },
167 .overload = .{
168 .kind = .not_applicable,
169 .detail = "full insertion culls and replaces the oldest receipt",
170 },
171 .risks = .{
172 .transitive = .{
173 .status = .excluded,
174 .detail = "receipt operations call no allocating owner",
175 },
176 .foreign = .{
177 .status = .excluded,
178 .detail = "receipt storage crosses no foreign boundary",
179 },
180 },
181 .work = .{ .equation = "table operations scan at most receipts_max entries" },
182 .obligations = &.{
183 .{ .key = "reticulum_receipts_capacity", .role = .capacity_model },
184 .{ .key = "reticulum_receipts_replace", .role = .overload },
185 .{ .key = "reticulum_receipts_work", .role = .work_bound },
186 },
187 },
188 .bindings = .{
189 .owner = @This(),
190 .seal = .{
191 .family = alloc_phase.capacity.selector(@This().activate),
192 .premise = .{ .class = .checked_semantic_fact, .authority = .checker },
193 },
194 .teardown = .{
195 .family = alloc_phase.capacity.selector(@This().deinit),
196 .premise = .{ .class = .checked_semantic_fact, .authority = .checker },
197 },
198 },
199 };
200
201 pub fn init(storage: Storage, limits: Limits) InitError!Table {
202 const capacity = try Capacity.derive(limits);
203 if (storage.len != capacity.storage_bytes) return error.StorageLengthMismatch;
204 return .{
205 .phase = .initialization,
206 .capacity = capacity,
207 .storage = storage,
208 .entries = std.mem.bytesAsSlice(Receipt, storage),
209 };
210 }
211
212 pub fn activate(self: *Table) void {
213 std.debug.assert(self.phase == .initialization);
214 std.debug.assert(self.len == 0);
215 self.phase = .steady;
216 }
217
218 /// Stores the record of a sent datagram (*receipt*) and returns the one it
219 /// culled, or null when it culled none, so the node learns which older
220 /// record that cost it, following Reticulum@1.5.0 RNS/Transport.py:716-732.
221 /// A receipt for the 32-byte digest naming a packet (*packet hash*) that
222 /// the table already holds replaces the stored one. Once the table is full,
223 /// the oldest receipt is culled and handed back, marked culled at the new
224 /// receipt's send time.
225 pub fn insert(self: *Table, value: Receipt) ?Receipt {
226 std.debug.assert(self.phase == .steady);
227 if (self.find(value.hash)) |existing| {
228 existing.* = value;
229 return null;
230 }
231 if (self.len < self.capacity.receipts_max) {
232 self.entries[self.len] = value;
233 self.len += 1;
234 return null;
235 }
236 var culled = self.entries[0];
237 culled.timeout = culling_timeout;
238 culled.checkTimeout(value.sent_at);
239 std.mem.copyForwards(Receipt, self.entries[0 .. self.len - 1], self.entries[1..self.len]);
240 self.entries[self.len - 1] = value;
241 return culled;
242 }
243
244 pub fn find(self: *Table, hash: packet.Hash) ?*Receipt {
245 std.debug.assert(self.phase == .steady);
246 for (self.entries[0..self.len]) |*entry| {
247 if (std.mem.eql(u8, &entry.hash, &hash)) return entry;
248 }
249 return null;
250 }
251
252 pub fn cullCandidate(self: *const Table, hash: packet.Hash) ?Receipt {
253 std.debug.assert(self.phase == .steady);
254 for (self.entries[0..self.len]) |entry| {
255 if (std.mem.eql(u8, &entry.hash, &hash)) return null;
256 }
257 if (self.len < self.capacity.receipts_max) return null;
258 return self.entries[0];
259 }
260
261 pub fn remove(self: *Table, hash: packet.Hash) bool {
262 std.debug.assert(self.phase == .steady);
263 for (self.entries[0..self.len], 0..) |*entry, index| {
264 if (!std.mem.eql(u8, &entry.hash, &hash)) continue;
265 std.mem.copyForwards(
266 Receipt,
267 self.entries[index .. self.len - 1],
268 self.entries[index + 1 .. self.len],
269 );
270 self.len -= 1;
271 return true;
272 }
273 return false;
274 }
275
276 pub fn count(self: *const Table) usize {
277 std.debug.assert(self.phase == .steady);
278 return self.len;
279 }
280
281 pub fn deinit(self: *Table) Storage {
282 std.debug.assert(self.phase == .steady);
283 self.phase = .teardown;
284 const storage = self.storage;
285 self.* = undefined;
286 return storage;
287 }
288 };
289
290 comptime {
291 alloc_phase.capacity.requireProvisionedExactOwnerShape(Table);
292 }
293
294 fn receipt(value: u8) Receipt {
295 return .{
296 .hash = @splat(value),
297 .truncated = @splat(value),
298 .destination = @splat(value),
299 .sent_at = value,
300 .timeout = 12,
301 };
302 }
303
304 test "receipts admit maximum and cull oldest at maximum plus one" {
305 comptime {
306 @stardustClaim(alloc_phase.capacity.witness(
307 Table,
308 "reticulum_receipts_capacity",
309 ), null, null, null, null, null, null);
310 @stardustClaim(alloc_phase.capacity.witness(
311 Table,
312 "reticulum_receipts_replace",
313 ), null, null, null, null, null, null);
314 @stardustClaim(alloc_phase.capacity.witness(
315 Table,
316 "reticulum_receipts_work",
317 ), null, null, null, null, null, null);
318 }
319 const capacity = comptime TableCapacity.derive(.{ .receipts_max = 3 }) catch unreachable;
320 var bytes: [capacity.storage_bytes]u8 align(Table.storage_alignment) = undefined;
321 var table = try Table.init(&bytes, .{ .receipts_max = 3 });
322 table.activate();
323 defer _ = table.deinit();
324 for (1..4) |value| try std.testing.expect(table.insert(receipt(@intCast(value))) == null);
325 const culled = table.insert(receipt(4)).?;
326 try std.testing.expectEqual(Status.culled, culled.status);
327 try std.testing.expect(table.find(@splat(1)) == null);
328 try std.testing.expectEqual(@as(usize, 3), table.count());
329 }
330
331 test "Reticulum@1.5.0 RNS/Packet.py:420-423 computes receipt timeout" {
332 try std.testing.expectEqual(@as(Seconds, 12), timeoutFor(6, 1));
333 }
334
335 test "Reticulum@1.5.0 RNS/Packet.py:537-543 uses a strict timeout deadline" {
336 var value = receipt(1);
337 value.sent_at = 10;
338 value.timeout = 12;
339 value.checkTimeout(22);
340 try std.testing.expectEqual(Status.sent, value.status);
341 value.checkTimeout(23);
342 try std.testing.expectEqual(Status.failed, value.status);
343 var culled = receipt(2);
344 culled.timeout = culling_timeout;
345 culled.checkTimeout(2);
346 try std.testing.expectEqual(Status.culled, culled.status);
347 }
348
349 test "Reticulum@1.5.0 RNS/Packet.py:485-520 validates both proof forms" {
350 var key_bytes: identity.KeyBytes = undefined;
351 for (&key_bytes, 0..) |*byte, index| byte.* = @intCast(index + 1);
352 var private = identity.Private.fromBytes(key_bytes);
353 defer private.zero();
354 var public = private.public();
355 defer public.zero();
356 var value = receipt(0xa5);
357 const signature = private.sign(&value.hash);
358 try std.testing.expect(value.validateProof(.{ .implicit = .{
359 .signature = signature,
360 } }, &public, 20));
361 try std.testing.expectEqual(Status.delivered, value.status);
362 value.status = .sent;
363 var foreign_hash: packet.Hash = @splat(0xa5);
364 foreign_hash[0] ^= 1;
365 try std.testing.expect(!value.validateProof(.{ .explicit = .{
366 .packet_hash = foreign_hash,
367 .signature = signature,
368 } }, &public, 21));
369 }
370
371 test "Reticulum@1.5.0 RNS/Packet.py:508-528 rejects a flipped implicit proof" {
372 const key_bytes: identity.KeyBytes = @splat(0x35);
373 var private = identity.Private.fromBytes(key_bytes);
374 defer private.zero();
375 var public = private.public();
376 defer public.zero();
377 var value = receipt(0x5a);
378 var signature = private.sign(&value.hash);
379 signature[0] ^= 1;
380 try std.testing.expect(!value.validateProof(.{ .implicit = .{
381 .signature = signature,
382 } }, &public, 20));
383 }