tiny.reticulum.packet.receipt

1const std = @import("std");2const alloc_phase = @import("alloc_phase");3const reticulum = @import("../root.zig");45const identity = reticulum.identity;6const packet = reticulum.packet;7const wire = reticulum.wire;89pub const Seconds = u64;1011/// Records how one sent Reticulum datagram (*packet*) stands, so a caller12/// learns what became of it: failed, sent, delivered, or culled, following13/// Reticulum@1.5.0 RNS/Packet.py:396-400.14pub const Status = enum(u8) {15    failed = 0,16    sent = 1,17    delivered = 2,18    culled = 0xff,19};2021/// The largest value a timeout holds marks the record of one sent datagram22/// (*receipt*) for culling, so a caller tells a receipt dropped to make room23/// from one that timed out. The reference marks the same condition with a24/// negative timeout, and seconds here are unsigned, following Reticulum@1.5.025/// RNS/Packet.py:540-543.26pub const culling_timeout: Seconds = std.math.maxInt(Seconds);2728pub 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,3637    /// Checks an arriving signature datagram (*proof*) against the sent packet38    /// record (*receipt*) and marks the packet delivered when it holds, so the39    /// node learns the packet arrived, following Reticulum@1.5.040    /// RNS/Packet.py:485-520. A 96-byte proof (*explicit proof*) has to carry41    /// the receipt's own full hash beside a signature over it, and a 64-byte42    /// proof (*implicit proof*) has to carry a signature over that hash. A43    /// 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) and52                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    }6061    /// Moves the record of a sent datagram (*receipt*) out of the sent state62    /// once its wait has run out, and records the second it concluded, so the63    /// node gives up on a packet nothing answered, following Reticulum@1.5.064    /// RNS/Packet.py:537-548. A receipt that already concluded is left as it65    /// is. A receipt whose timeout holds the culling value is marked culled at66    /// 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};8081/// Returns how long a sent datagram (*packet*) may wait for a proof, so the82/// wait grows with the distance the packet travels: the first-hop wait plus six83/// seconds for each hop, following Reticulum@1.5.0 RNS/Packet.py:115,420-42384/// and Reticulum@1.5.0 RNS/Reticulum.py:142. Both additions saturate, so a85/// large count of hops (*hop count*) gives the largest value the type holds.86pub fn timeoutFor(first_hop: Seconds, hops: u8) Seconds {87    const hop_timeout = @as(Seconds, hops) *| 6;88    return first_hop +| hop_timeout;89}9091const TableLimits = struct {92    receipts_max: usize,93};9495const TableCapacity = struct {96    receipts_max: usize,97    storage_bytes: usize,9899    pub const DeriveError = error{ InvalidLimit, CapacityOverflow };100101    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};112113pub const Table = struct {114    phase: alloc_phase.capacity.Phase,115    capacity: Capacity,116    storage: Storage,117    entries: []Receipt,118    len: usize = 0,119120    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    };200201    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    }211212    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    }217218    /// Stores the record of a sent datagram (*receipt*) and returns the one it219    /// culled, or null when it culled none, so the node learns which older220    /// 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*) that222    /// 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 new224    /// 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    }243244    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    }251252    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    }260261    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    }275276    pub fn count(self: *const Table) usize {277        std.debug.assert(self.phase == .steady);278        return self.len;279    }280281    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};289290comptime {291    alloc_phase.capacity.requireProvisionedExactOwnerShape(Table);292}293294fn 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}303304test "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}330331test "Reticulum@1.5.0 RNS/Packet.py:420-423 computes receipt timeout" {332    try std.testing.expectEqual(@as(Seconds, 12), timeoutFor(6, 1));333}334335test "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}348349test "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}370371test "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}

1pub const receipt = @import("receipt.zig");