lib/content/src/model.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2
3 pub const digest_bytes: usize = 32;
4 pub const maximum_extent_bytes: u32 = std.math.maxInt(u32);
5
6 /// The hash algorithm offers two choices, BLAKE3 and SHA-256, which a caller
7 /// picks to name content when it derives an identifier or a reference. The
8 /// algorithm runs over the complete bytes as they are, with no length prefix or
9 /// other framing added.
10 pub const Algorithm = enum(u8) {
11 blake3 = 1,
12 sha256 = 2,
13 };
14
15 /// Carries the identity of content, and nothing else about it, so a caller
16 /// compares identifiers to decide whether two byte strings are the same. The
17 /// struct holds two fields: the algorithm and its 32-byte digest, so it names
18 /// no location, no provider, and no type.
19 pub const Identifier = struct {
20 algorithm: Algorithm,
21 digest: [digest_bytes]u8,
22
23 /// Derives an identifier from the complete bytes by running the chosen hash
24 /// over every byte and pairing the digest with the algorithm tag.
25 pub fn fromBytes(algorithm: Algorithm, bytes: []const u8) Identifier {
26 var digest: [digest_bytes]u8 = undefined;
27 switch (algorithm) {
28 .blake3 => std.crypto.hash.Blake3.hash(bytes, &digest, .{}),
29 .sha256 => std.crypto.hash.sha2.Sha256.hash(bytes, &digest, .{}),
30 }
31 return .{ .algorithm = algorithm, .digest = digest };
32 }
33
34 /// Reports whether two identifiers carry the same algorithm and the same
35 /// digest, which is how a provider looks for an identifier among the ones
36 /// it holds. The check compares the digests in constant time, so the answer
37 /// leaks nothing about where they first differ.
38 pub fn eql(left: Identifier, right: Identifier) bool {
39 const algorithm_matches = left.algorithm == right.algorithm;
40 const digest_matches = std.crypto.timing_safe.eql(
41 [digest_bytes]u8,
42 left.digest,
43 right.digest,
44 );
45 return algorithm_matches and digest_matches;
46 }
47
48 /// Checks bytes a provider staged or read by rehashing them with this
49 /// identifier's algorithm and reporting whether the digests agree.
50 pub fn matches(self: Identifier, bytes: []const u8) bool {
51 return self.eql(fromBytes(self.algorithm, bytes));
52 }
53 };
54
55 pub const ReferenceError = error{
56 ContentExtentExceeded,
57 ContentExtentMismatch,
58 ContentIdentifierMismatch,
59 };
60
61 /// An extent gives the exact byte length of one piece of content to size the
62 /// buffer a read will fill. The struct holds that length as a `u32`, which puts
63 /// the largest representable content at `maximum_extent_bytes`.
64 pub const Extent = struct {
65 bytes: u32,
66
67 /// Converts a byte length a caller measured on the host into the extent a
68 /// reference carries, and returns `ContentExtentExceeded` when the length
69 /// is wider than the `u32` an extent holds.
70 pub fn fromUsize(bytes: usize) ReferenceError!Extent {
71 return .{
72 .bytes = std.math.cast(u32, bytes) orelse
73 return error.ContentExtentExceeded,
74 };
75 }
76
77 /// Widens an extent to the host's `usize`, for a caller slicing a buffer to
78 /// the content's length.
79 pub fn toUsize(self: Extent) usize {
80 return @intCast(self.bytes);
81 }
82 };
83
84 /// The name of one piece of content passed by a caller to every read and every
85 /// publication: what it hashes to and how long it is. The struct holds an
86 /// identifier and an extent as plain values that copy freely.
87 pub const Reference = struct {
88 identifier: Identifier,
89 extent: Extent,
90
91 /// Derives both halves of a reference from the complete bytes, as a caller
92 /// does before publishing them, and returns `ContentExtentExceeded` when
93 /// the byte length does not fit an extent.
94 pub fn fromBytes(
95 algorithm: Algorithm,
96 bytes: []const u8,
97 ) ReferenceError!Reference {
98 return .{
99 .identifier = Identifier.fromBytes(algorithm, bytes),
100 .extent = try Extent.fromUsize(bytes.len),
101 };
102 }
103
104 /// Checks borrowed bytes against this reference before a sink hands them to
105 /// a provider, or when a caller receives bytes elsewhere. The function
106 /// returns `ContentExtentMismatch` when the byte length differs from the
107 /// extent, and `ContentIdentifierMismatch` when the digest of the bytes
108 /// differs from the identifier.
109 pub fn verify(self: Reference, bytes: []const u8) ReferenceError!void {
110 if (bytes.len != self.extent.toUsize()) {
111 return error.ContentExtentMismatch;
112 }
113 if (!self.identifier.matches(bytes)) {
114 return error.ContentIdentifierMismatch;
115 }
116 }
117 };
118
119 /// Holds the three numbers a caller fills in to describe how large a store it
120 /// wants before any storage is sized: the object count, the bytes allowed for
121 /// one object, and the total content bytes.
122 pub const Limits = struct {
123 objects: u32,
124 object_bytes: u32,
125 total_bytes: u64,
126 };
127
128 pub const CapacityError = error{
129 CapacityArithmeticOverflow,
130 ObjectLimitEmpty,
131 TotalByteLimitExceeded,
132 TotalByteLimitTooSmall,
133 };
134
135 const Metadata = struct {
136 reference: Reference,
137 offset: u64,
138 };
139
140 pub const metadata_entry_bytes: usize = @sizeOf(Metadata);
141
142 /// The sizes and the work counts a store was built with, carried by a caller
143 /// from derivation into the store it builds and re-read by every capability to
144 /// admit a reference. The struct holds the limits it came from, the retained
145 /// metadata and storage byte counts, and a worst-case work count for a read, a
146 /// publication, and teardown.
147 pub const Capacity = struct {
148 limits: Limits,
149 metadata_bytes: u64,
150 storage_bytes: u64,
151 read_work: u64,
152 publication_work: u64,
153 teardown_work: u64,
154
155 pub const DeriveError: type = CapacityError;
156
157 /// Turns caller limits into the byte counts and work counts of a store,
158 /// called once before a caller lays out storage so it learns how many bytes
159 /// the store needs and how much work its operations can cost. The
160 /// calculation returns `ObjectLimitEmpty` for a store of no objects,
161 /// `TotalByteLimitTooSmall` when the total is below one object,
162 /// `TotalByteLimitExceeded` when the total is above the object count times
163 /// the bytes per object, and `CapacityArithmeticOverflow` when any of the
164 /// products or sums does not fit a `u64`. The function sizes retained
165 /// storage as one metadata entry per object, plus the total content bytes,
166 /// plus one more object for the staging region. Work counts bound one read
167 /// at the object count plus twice the bytes of one object, one publication
168 /// at the object count plus six times the bytes of one object, which covers
169 /// four hashing passes and two copies, and teardown at one step per object.
170 pub fn derive(limits: Limits) DeriveError!Capacity {
171 if (limits.objects == 0) return error.ObjectLimitEmpty;
172 if (limits.total_bytes < limits.object_bytes) {
173 return error.TotalByteLimitTooSmall;
174 }
175 const possible_total = multiplied(limits.objects, limits.object_bytes);
176 if (possible_total < limits.total_bytes) {
177 return error.TotalByteLimitExceeded;
178 }
179 const metadata_bytes = try multipliedChecked(
180 limits.objects,
181 @sizeOf(Metadata),
182 );
183 const staged_storage = try added(metadata_bytes, limits.total_bytes);
184 const storage_bytes = try added(staged_storage, limits.object_bytes);
185 const read_bytes = try multipliedChecked(limits.object_bytes, 2);
186 const read_work = try added(limits.objects, read_bytes);
187 const publication_hash_passes: u8 = 4;
188 const publication_copy_passes: u8 = 2;
189 const publication_byte_passes = publication_hash_passes +
190 publication_copy_passes;
191 const publication_bytes = try multipliedChecked(
192 limits.object_bytes,
193 publication_byte_passes,
194 );
195 const publication_work = try added(limits.objects, publication_bytes);
196 return .{
197 .limits = limits,
198 .metadata_bytes = metadata_bytes,
199 .storage_bytes = storage_bytes,
200 .read_work = read_work,
201 .publication_work = publication_work,
202 .teardown_work = limits.objects,
203 };
204 }
205
206 /// Checks one reference against the store's per-object byte limit, called
207 /// first by both capabilities so a reference that is too large for the
208 /// store never reaches the provider. The check returns
209 /// `ContentExtentExceeded` when the reference's extent is above that limit.
210 pub fn validateReference(
211 self: Capacity,
212 reference: Reference,
213 ) ReferenceError!void {
214 if (reference.extent.bytes > self.limits.object_bytes) {
215 return error.ContentExtentExceeded;
216 }
217 }
218 };
219
220 fn added(left: anytype, right: anytype) CapacityError!u64 {
221 const bounded_left: u64 = @intCast(left);
222 const bounded_right: u64 = @intCast(right);
223 return std.math.add(u64, bounded_left, bounded_right) catch
224 error.CapacityArithmeticOverflow;
225 }
226
227 fn multiplied(left: u32, right: u32) u64 {
228 return @as(u64, left) * @as(u64, right);
229 }
230
231 fn multipliedChecked(left: anytype, right: anytype) CapacityError!u64 {
232 const bounded_left: u64 = @intCast(left);
233 const bounded_right: u64 = @intCast(right);
234 return std.math.mul(u64, bounded_left, bounded_right) catch
235 error.CapacityArithmeticOverflow;
236 }
237
238 test "raw content identifiers pin exact bytes for both algorithms" {
239 const bytes = "canonical\x00bytes";
240 const blake3 = Identifier.fromBytes(.blake3, bytes);
241 const sha256 = Identifier.fromBytes(.sha256, bytes);
242 try std.testing.expectEqualStrings(
243 "9fd9b60f5c6c808a12757443704f8e1b2d4cf5a511ff1841129208f9ee3218a0",
244 &std.fmt.bytesToHex(blake3.digest, .lower),
245 );
246 try std.testing.expectEqualStrings(
247 "ded1e706e43e320165bf4f6fec349cb8443c0947c42db69e8577e498b95d6207",
248 &std.fmt.bytesToHex(sha256.digest, .lower),
249 );
250 try std.testing.expect(blake3.matches(bytes));
251 try std.testing.expect(sha256.matches(bytes));
252 try std.testing.expect(!blake3.eql(sha256));
253 }
254
255 test "reference verification separates extent and identifier failures" {
256 const reference = try Reference.fromBytes(.sha256, "bytes");
257 try reference.verify("bytes");
258 try std.testing.expectError(
259 error.ContentExtentMismatch,
260 reference.verify("byte"),
261 );
262 var changed = reference;
263 changed.identifier.digest[0] ^= 1;
264 try std.testing.expectError(
265 error.ContentIdentifierMismatch,
266 changed.verify("bytes"),
267 );
268 }
269
270 test "content capacity accepts exact maxima and rejects hostile limits" {
271 const exact = try Capacity.derive(.{
272 .objects = 1,
273 .object_bytes = maximum_extent_bytes,
274 .total_bytes = maximum_extent_bytes,
275 });
276 try std.testing.expectEqual(maximum_extent_bytes, exact.limits.object_bytes);
277 try std.testing.expect(exact.metadata_bytes > 0);
278 try std.testing.expectEqual(
279 @as(u64, 1) + @as(u64, maximum_extent_bytes) * 6,
280 exact.publication_work,
281 );
282 if (@sizeOf(usize) > @sizeOf(u32)) {
283 try std.testing.expectError(
284 error.ContentExtentExceeded,
285 Extent.fromUsize(@as(usize, maximum_extent_bytes) + 1),
286 );
287 }
288 try std.testing.expectError(
289 error.ObjectLimitEmpty,
290 Capacity.derive(.{ .objects = 0, .object_bytes = 1, .total_bytes = 1 }),
291 );
292 try std.testing.expectError(
293 error.TotalByteLimitTooSmall,
294 Capacity.derive(.{ .objects = 2, .object_bytes = 2, .total_bytes = 1 }),
295 );
296 try std.testing.expectError(
297 error.TotalByteLimitExceeded,
298 Capacity.derive(.{ .objects = 2, .object_bytes = 2, .total_bytes = 5 }),
299 );
300 try std.testing.expectError(
301 error.CapacityArithmeticOverflow,
302 Capacity.derive(.{
303 .objects = std.math.maxInt(u32),
304 .object_bytes = std.math.maxInt(u32),
305 .total_bytes = @as(u64, std.math.maxInt(u32)) *
306 @as(u64, std.math.maxInt(u32)),
307 }),
308 );
309 }