tiny.reticulum.identity.known

1const std = @import("std");2const alloc_phase = @import("alloc_phase");3const reticulum = @import("../root.zig");45const destination = reticulum.destination;6const packet = reticulum.packet;78/// 333 bytes: the most application data one remembered announce keeps, the room9/// a 19-byte-header announce leaves for it, so a caller sizes that application10/// data, following Reticulum@1.5.0 RNS/Identity.py:511-578.11pub 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 handed13/// out, so a caller works out how long that key stays usable, following14/// Reticulum@1.5.0 RNS/Identity.py:69.15pub const ratchet_expiry: u64 = 60 * 60 * 24 * 30;1617pub 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,2425    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    }2930    pub fn public(self: *const IdentityEntry) reticulum.identity.Public {31        return reticulum.identity.Public.fromBytes(self.public_key);32    }33};3435const IdentityLimits = struct {36    identities_max: usize,37};3839const IdentityCapacity = struct {40    identities_max: usize,41    storage_bytes: usize,4243    pub const DeriveError = error{ InvalidLimit, CapacityOverflow };4445    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};5657pub 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};6465/// The bounded store of what the node learned about other destinations from66/// their announcements, so a node looks a peer up here before it encrypts to67/// that peer or checks a signature from it, following Reticulum@1.5.068/// RNS/Identity.py:101-160. One entry holds the destination hash, the 64 public69/// bytes of the identity, the hash of the announce it came from, the second it70/// arrived, and that announce's application data. An announce for a destination71/// already stored overwrites its entry, and once the store is full the entry72/// that arrived earliest is the one overwritten. Remembering application data73/// longer than 333 bytes returns `error.AppDataTooLong` and leaves the store as74/// it was.75pub const Identities = struct {76    phase: alloc_phase.capacity.Phase,77    capacity: Capacity,78    storage: Storage,79    entries: []IdentityEntry,80    len: usize = 0,8182    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    };166167    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    }177178    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    }183184    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    }198199    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    }206207    /// Returns the stored entry whose identity hashes to the given identity208    /// 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 each210    /// stored key in turn, so it costs one pass over the store. The call211    /// 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    }223224    pub fn count(self: *const Identities) usize {225        std.debug.assert(self.phase == .steady);226        return self.len;227    }228229    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    }236237    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    }243244    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};257258pub const RatchetEntry = struct {259    destination_hash: [16]u8,260    public_key: [32]u8,261    received: u64,262};263264const RatchetLimits = struct {265    ratchets_max: usize,266};267268const RatchetCapacity = struct {269    ratchets_max: usize,270    storage_bytes: usize,271272    pub const DeriveError = error{ InvalidLimit, CapacityOverflow };273274    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};285286pub const Ratchets = struct {287    phase: alloc_phase.capacity.Phase,288    capacity: Capacity,289    storage: Storage,290    entries: []RatchetEntry,291    len: usize = 0,292293    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    };376377    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    }387388    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    }393394    /// Stores a peer's rotating key against its destination hash, so a node395    /// records the rotating key it read out of a peer's announce, following396    /// Reticulum@1.5.0 RNS/Identity.py:410-425. A key already stored for that397    /// destination is overwritten, and once the store is full the key that398    /// 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    }404405    /// Returns a peer's rotating key against its destination hash when one is406    /// stored and has yet to expire, so a sender asks whether it has a rotating407    /// key fresh enough to encrypt to, following Reticulum@1.5.0408    /// RNS/Identity.py:485-508. A key that arrived more than 30 days before the409    /// given second gives null. The call returns null when no key is stored for410    /// 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    }420421    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    }438439    pub fn count(self: *const Ratchets) usize {440        std.debug.assert(self.phase == .steady);441        return self.len;442    }443444    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    }451452    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    }458459    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};472473fn expired(received: u64, now: u64) bool {474    if (now < received) return false;475    return now - received >= ratchet_expiry;476}477478comptime {479    alloc_phase.capacity.requireProvisionedExactOwnerShape(Identities);480}481482comptime {483    alloc_phase.capacity.requireProvisionedExactOwnerShape(Ratchets);484}485486fn 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}495496test "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}523524test "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}538539test "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}567568test "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}

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