lib/machine/src/fabric/canon.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const admission = @import("../admission/root.zig");
2 const fault = @import("../fault/root.zig");
3 const instance = @import("../instance/root.zig");
4 const os = @import("os");
5 const profile = @import("../profile/root.zig");
6 const std = @import("std");
7 const types = @import("types.zig");
8
9 const Sha256 = std.crypto.hash.sha2.Sha256;
10 const basis_domain = "TINYMACHINEFABRICBASIS1\x00";
11 const entry_domain = "TINYMACHINEFABRICENTRY3\x00";
12 const fault_initial_domain = "TINYMACHINEFABRICFAULTINITIAL1\x00";
13 const fault_subject_domain = "TINYMACHINEFABRICFAULTSUBJECT1\x00";
14 const initial_domain = "TINYMACHINEFABRICINITIAL3\x00";
15 const packet_domain = "TINYMACHINEFABRICPACKET1\x00";
16 const root_domain = "TINYMACHINEFABRICROOT3\x00";
17
18 const StateError = error{
19 AdmissionCapacityExceeded,
20 EntrySequenceExhausted,
21 FabricStateInvalid,
22 InvalidNode,
23 InvalidPacket,
24 InvalidWorld,
25 NodeCapacityExceeded,
26 NodeStateMismatch,
27 NodesNotCanonical,
28 PacketCapacityExceeded,
29 RootMismatch,
30 };
31
32 pub const Error = admission.Error || fault.Error || StateError;
33
34 pub fn initialize(state: *types.State) Error!void {
35 try validateShape(state.*);
36 state.ledger_digest = initialDigest(state.*);
37 state.fault_digest = initialFaultDigest(state.*);
38 state.root = rootFor(state.*);
39 try validate(state.*);
40 }
41
42 pub fn validate(state: types.State) Error!void {
43 try validateShape(state);
44 if (state.root.dialect != .ordered_effect_fabric_v3 or
45 state.root.entry_frontier != state.entry_frontier or
46 state.root.admission_frontier != state.admission_frontier or
47 state.root.fault_frontier != state.fault_frontier or
48 !std.meta.eql(state.root.machine_contract, state.contract))
49 {
50 return error.FabricStateInvalid;
51 }
52 if (!std.meta.eql(state.root, rootFor(state))) return error.RootMismatch;
53 if (state.pending) |pending| {
54 if (!std.mem.eql(u8, &pending.delivery_root, &state.root.digest)) {
55 return error.FabricStateInvalid;
56 }
57 }
58 }
59
60 pub fn rootFor(state: types.State) types.Root {
61 var hasher = Sha256.init(.{});
62 hasher.update(root_domain);
63 hashInteger(&hasher, @backingInt(types.Dialect.ordered_effect_fabric_v3));
64 hasher.update(&state.contract.digest);
65 hasher.update(&state.world);
66 hashInteger(&hasher, state.entry_frontier);
67 hashInteger(&hasher, state.admission_frontier);
68 hashInteger(&hasher, state.fault_frontier);
69 hashInteger(&hasher, state.admission_limit);
70 hashInteger(&hasher, state.virtual_time_tick);
71 hashInteger(&hasher, state.entropy_frontier);
72 hashInteger(&hasher, state.entropy_bytes);
73 hashInteger(&hasher, state.packet_next_id);
74 hashInteger(&hasher, state.partition_bits);
75 hashInteger(&hasher, state.capacity_bits);
76 hashInteger(&hasher, state.node_count);
77 for (state.nodes[0..state.node_count]) |node| hashNode(&hasher, node);
78 hashPending(&hasher, state.pending);
79 hashInteger(&hasher, state.packet_count);
80 for (state.packets[0..state.packet_count]) |queued| {
81 hashPacket(&hasher, queued.packet);
82 hashInteger(&hasher, @as(u8, @intFromBool(queued.ready)));
83 hashInteger(&hasher, queued.ready_at_tick);
84 hashInteger(&hasher, queued.order);
85 }
86 hasher.update(&state.ledger_digest);
87 hasher.update(&state.fault_digest);
88 var digest: os.abi.Digest = undefined;
89 hasher.final(&digest);
90 return .{
91 .digest = digest,
92 .dialect = .ordered_effect_fabric_v3,
93 .machine_contract = state.contract,
94 .entry_frontier = state.entry_frontier,
95 .admission_frontier = state.admission_frontier,
96 .fault_frontier = state.fault_frontier,
97 };
98 }
99
100 pub fn advanceLedger(
101 previous: os.abi.Digest,
102 entry: types.Entry,
103 ) (fault.Error || error{InvalidQuiescenceReceipt})!os.abi.Digest {
104 var hasher = Sha256.init(.{});
105 hasher.update(entry_domain);
106 hasher.update(&previous);
107 hashRoot(&hasher, entry.previous);
108 hashInteger(&hasher, entry.sequence);
109 switch (entry.value) {
110 .admission => |value| {
111 hashInteger(&hasher, @as(u8, 1));
112 hasher.update(&value.node.bytes);
113 hasher.update(&value.admission.receipt.digest);
114 switch (value.effect) {
115 .direct => hashInteger(&hasher, @as(u8, 1)),
116 .packet_send => |packet_value| {
117 hashInteger(&hasher, @as(u8, 2));
118 hashPacket(&hasher, packet_value);
119 },
120 .packet_delivery => |packet_id| {
121 hashInteger(&hasher, @as(u8, 3));
122 hashInteger(&hasher, packet_id);
123 },
124 }
125 try hashAdmissionFault(&hasher, value.fault);
126 },
127 .settlement => |value| {
128 hashInteger(&hasher, @as(u8, 2));
129 hasher.update(&value.node.bytes);
130 const digest = try instance.semanticReceiptDigest(value.receipt);
131 hasher.update(&digest);
132 },
133 .fault => |value| {
134 hashInteger(&hasher, @as(u8, 3));
135 hashFaultEffect(&hasher, value.effect);
136 try fault.verifyDecision(value.decision);
137 hasher.update(&value.decision.digest);
138 },
139 }
140 var digest: os.abi.Digest = undefined;
141 hasher.final(&digest);
142 return digest;
143 }
144
145 pub fn makePacket(
146 id: u64,
147 source: types.NodeId,
148 request: admission.EffectRequest,
149 input: types.PacketInput,
150 ) Error!types.Packet {
151 if (input.bytes.len > types.packet_bytes_max) {
152 return error.PayloadCapacityExceeded;
153 }
154 if (id == 0 or input.channel == 0 or input.bytes.len == 0 or
155 sameNode(source, input.destination))
156 {
157 return error.InvalidPacket;
158 }
159 try validateNodeId(source);
160 try validateNodeId(input.destination);
161 var value: types.Packet = .{
162 .id = id,
163 .source = source,
164 .destination = input.destination,
165 .channel = input.channel,
166 .request = request,
167 .length = @intCast(input.bytes.len),
168 .storage = @splat(0),
169 .digest = undefined,
170 };
171 @memcpy(value.storage[0..input.bytes.len], input.bytes);
172 value.digest = packetDigest(value);
173 return value;
174 }
175
176 pub fn packetDigest(value: types.Packet) os.abi.Digest {
177 var hasher = Sha256.init(.{});
178 hasher.update(packet_domain);
179 hashPacketMaterial(&hasher, value);
180 var digest: os.abi.Digest = undefined;
181 hasher.final(&digest);
182 return digest;
183 }
184
185 pub fn basisDigest(value: admission.Basis) os.abi.Digest {
186 var hasher = Sha256.init(.{});
187 hasher.update(basis_domain);
188 hashBasis(&hasher, value);
189 var digest: os.abi.Digest = undefined;
190 hasher.final(&digest);
191 return digest;
192 }
193
194 pub fn faultPoint(
195 root: types.Root,
196 effect: types.FaultEffect,
197 ) Error!fault.Point {
198 const subject = faultSubject(effect);
199 return fault.prepare(root.digest, std.meta.activeTag(effect), subject);
200 }
201
202 pub fn verifyFaultDecision(
203 root: types.Root,
204 effect: types.FaultEffect,
205 decision: fault.Decision,
206 ) Error!void {
207 try fault.verifyDecision(decision);
208 const expected = try faultPoint(root, effect);
209 if (!std.meta.eql(expected, decision.point)) {
210 return error.InvalidFaultPoint;
211 }
212 }
213
214 pub fn advanceFault(
215 previous: os.abi.Digest,
216 decision: fault.Decision,
217 ) fault.Error!os.abi.Digest {
218 return fault.advance(previous, decision);
219 }
220
221 pub fn sameNode(left: types.NodeId, right: types.NodeId) bool {
222 return std.mem.eql(u8, &left.bytes, &right.bytes);
223 }
224
225 pub fn lessNode(left: types.NodeId, right: types.NodeId) bool {
226 return std.mem.order(u8, &left.bytes, &right.bytes) == .lt;
227 }
228
229 pub fn validateNodeId(value: types.NodeId) Error!void {
230 if (os.abi.wire.allZero(&value.bytes)) return error.InvalidNode;
231 }
232
233 fn validateShape(state: types.State) Error!void {
234 if (state.node_count == 0 or state.node_count > types.node_limit) {
235 return error.NodeCapacityExceeded;
236 }
237 if (state.admission_limit != types.admission_limit) {
238 return error.FabricStateInvalid;
239 }
240 if (os.abi.wire.allZero(&state.world)) return error.InvalidWorld;
241 if (state.admission_frontier > state.admission_limit) {
242 return error.AdmissionCapacityExceeded;
243 }
244 if (state.fault_frontier > state.admission_frontier or
245 state.partition_bits & ~partitionMask(state.node_count) != 0 or
246 state.capacity_bits & ~@as(u8, 0b11) != 0)
247 {
248 return error.FabricStateInvalid;
249 }
250 os.abi.wire.validateDigest(state.fault_digest) catch
251 return error.FabricStateInvalid;
252 if (state.packet_count > types.packet_limit) {
253 return error.PacketCapacityExceeded;
254 }
255 try validateNodes(state);
256 try validatePackets(state);
257 if (state.pending) |pending| try validatePending(state, pending);
258 }
259
260 fn validateNodes(state: types.State) Error!void {
261 var previous: ?types.NodeId = null;
262 for (state.nodes[0..state.node_count]) |node| {
263 try validateNodeId(node.id);
264 if (previous) |value| {
265 if (!lessNode(value, node.id)) return error.NodesNotCanonical;
266 }
267 try admission.validateBasis(node.basis);
268 if (!std.meta.eql(node.basis.contract, state.contract) or
269 node.basis.frontiers.virtual_time_tick > state.virtual_time_tick)
270 {
271 return error.NodeStateMismatch;
272 }
273 os.abi.wire.validateDigest(node.machine.digest) catch
274 return error.NodeStateMismatch;
275 previous = node.id;
276 }
277 }
278
279 fn validatePackets(state: types.State) Error!void {
280 var greatest_id: u64 = 0;
281 for (state.packets[0..state.packet_count], 0..) |queued, index| {
282 const value = queued.packet;
283 if (value.id == 0 or value.id <= greatest_id or value.channel == 0 or
284 value.length == 0 or value.length > value.storage.len or
285 queued.order == 0 or (!queued.ready and queued.ready_at_tick != 0) or
286 sameNode(value.source, value.destination) or
287 !hasNode(state, value.source) or !hasNode(state, value.destination) or
288 !os.abi.wire.allZero(value.storage[value.length..]) or
289 !std.mem.eql(u8, &value.digest, &packetDigest(value)))
290 {
291 return error.InvalidPacket;
292 }
293 for (state.packets[0..index]) |earlier| {
294 if (earlier.order == queued.order) return error.InvalidPacket;
295 }
296 greatest_id = value.id;
297 }
298 if (greatest_id > state.packet_next_id) return error.InvalidPacket;
299 }
300
301 fn validatePending(state: types.State, pending: types.Pending) Error!void {
302 const node = findNode(state, pending.node) orelse return error.InvalidNode;
303 if (!node.available) return error.NodeStateMismatch;
304 try admission.verify(node.basis, &pending.admission);
305 switch (pending.effect) {
306 .direct, .packet_delivery => {},
307 .packet_send => |packet_id| {
308 const queued = findPacket(state, packet_id) orelse
309 return error.InvalidPacket;
310 if (queued.ready) return error.InvalidPacket;
311 },
312 }
313 }
314
315 fn initialDigest(state: types.State) os.abi.Digest {
316 var hasher = Sha256.init(.{});
317 hasher.update(initial_domain);
318 hashInteger(&hasher, @backingInt(types.Dialect.ordered_effect_fabric_v3));
319 hasher.update(&state.contract.digest);
320 hasher.update(&state.world);
321 hashInteger(&hasher, state.virtual_time_tick);
322 hashInteger(&hasher, state.admission_limit);
323 hashInteger(&hasher, state.partition_bits);
324 hashInteger(&hasher, state.capacity_bits);
325 hashInteger(&hasher, state.node_count);
326 for (state.nodes[0..state.node_count]) |node| hashNode(&hasher, node);
327 var digest: os.abi.Digest = undefined;
328 hasher.final(&digest);
329 return digest;
330 }
331
332 fn initialFaultDigest(state: types.State) os.abi.Digest {
333 var hasher = Sha256.init(.{});
334 hasher.update(fault_initial_domain);
335 hasher.update(&state.contract.digest);
336 hasher.update(&state.world);
337 hasher.update(&state.ledger_digest);
338 var digest: os.abi.Digest = undefined;
339 hasher.final(&digest);
340 return digest;
341 }
342
343 fn faultSubject(effect: types.FaultEffect) os.abi.Digest {
344 var hasher = Sha256.init(.{});
345 hasher.update(fault_subject_domain);
346 hashFaultEffect(&hasher, effect);
347 var digest: os.abi.Digest = undefined;
348 hasher.final(&digest);
349 return digest;
350 }
351
352 fn hashNode(hasher: *Sha256, node: types.NodeState) void {
353 hasher.update(&node.id.bytes);
354 hashBasis(hasher, node.basis);
355 hashInteger(hasher, @backingInt(node.machine.kind));
356 hasher.update(&node.machine.digest);
357 hashInteger(hasher, @as(u8, @intFromBool(node.available)));
358 }
359
360 fn hashBasis(hasher: *Sha256, value: admission.Basis) void {
361 hasher.update(&value.contract.digest);
362 hasher.update(&value.source_root);
363 hashInteger(hasher, value.frontiers.input);
364 hashInteger(hasher, value.frontiers.terminal_input_offset);
365 hashInteger(hasher, value.frontiers.virtual_time_tick);
366 hashInteger(hasher, value.frontiers.entropy_generation);
367 hashInteger(hasher, value.frontiers.effect);
368 const request = value.outstanding_effect orelse {
369 hashInteger(hasher, @as(u8, 0));
370 return;
371 };
372 hashInteger(hasher, @as(u8, 1));
373 hasher.update(&request.receipt.digest);
374 hashInteger(hasher, request.correlation);
375 }
376
377 fn hashPending(hasher: *Sha256, value: ?types.Pending) void {
378 const pending = value orelse {
379 hashInteger(hasher, @as(u8, 0));
380 return;
381 };
382 hashInteger(hasher, @as(u8, 1));
383 hasher.update(&pending.node.bytes);
384 hasher.update(&pending.admission.receipt.digest);
385 switch (pending.effect) {
386 .direct => hashInteger(hasher, @as(u8, 1)),
387 .packet_send => |packet_id| {
388 hashInteger(hasher, @as(u8, 2));
389 hashInteger(hasher, packet_id);
390 },
391 .packet_delivery => |packet_id| {
392 hashInteger(hasher, @as(u8, 3));
393 hashInteger(hasher, packet_id);
394 },
395 }
396 }
397
398 fn hashAdmissionFault(
399 hasher: *Sha256,
400 value: ?types.AdmissionFault,
401 ) fault.Error!void {
402 const admission_fault = value orelse {
403 hashInteger(hasher, @as(u8, 0));
404 return;
405 };
406 try fault.verifyDecision(admission_fault.decision);
407 hashInteger(hasher, @as(u8, 1));
408 hashFaultEffect(hasher, admission_fault.effect);
409 hasher.update(&admission_fault.decision.digest);
410 }
411
412 fn hashFaultEffect(hasher: *Sha256, effect: types.FaultEffect) void {
413 hashInteger(hasher, @backingInt(std.meta.activeTag(effect)));
414 switch (effect) {
415 .machine_crash => |node| hasher.update(&node.bytes),
416 .process_crash => |value| {
417 hasher.update(&value.node.bytes);
418 hashInteger(hasher, value.process);
419 },
420 .io_error => |value| hashFaultAlternatives(hasher, value),
421 .packet_loss => |packet_id| hashInteger(hasher, packet_id),
422 .packet_delay => |value| {
423 hashInteger(hasher, value.packet);
424 hashInteger(hasher, value.until_tick);
425 },
426 .packet_reorder => |value| {
427 hashInteger(hasher, value.first);
428 hashInteger(hasher, value.second);
429 },
430 .partition => |value| {
431 hasher.update(&value.first.bytes);
432 hasher.update(&value.second.bytes);
433 hashInteger(hasher, @as(u8, @intFromBool(value.active)));
434 },
435 .clock_jump => |to_tick| hashInteger(hasher, to_tick),
436 .entropy_choice => |value| hashFaultAlternatives(hasher, value),
437 .capacity_exhaustion => |value| {
438 hashInteger(hasher, @backingInt(value.resource));
439 hashInteger(hasher, @as(u8, @intFromBool(value.active)));
440 },
441 .host_service_failure => |value| hashFaultAlternatives(hasher, value),
442 }
443 }
444
445 fn hashFaultAlternatives(
446 hasher: *Sha256,
447 value: types.FaultAlternatives,
448 ) void {
449 hasher.update(&value.node.bytes);
450 hasher.update(&value.bypass);
451 hasher.update(&value.inject);
452 }
453
454 fn hashPacket(hasher: *Sha256, value: types.Packet) void {
455 hashPacketMaterial(hasher, value);
456 hasher.update(&value.digest);
457 }
458
459 fn hashPacketMaterial(hasher: *Sha256, value: types.Packet) void {
460 hashInteger(hasher, value.id);
461 hasher.update(&value.source.bytes);
462 hasher.update(&value.destination.bytes);
463 hashInteger(hasher, value.channel);
464 hasher.update(&value.request.receipt.digest);
465 hashInteger(hasher, value.request.correlation);
466 hashBytes(hasher, value.storage[0..value.length]);
467 }
468
469 fn hashRoot(hasher: *Sha256, value: types.Root) void {
470 hasher.update(&value.digest);
471 hashInteger(hasher, @backingInt(value.dialect));
472 hasher.update(&value.machine_contract.digest);
473 hashInteger(hasher, value.entry_frontier);
474 hashInteger(hasher, value.admission_frontier);
475 hashInteger(hasher, value.fault_frontier);
476 }
477
478 fn hashBytes(hasher: *Sha256, value: []const u8) void {
479 hashInteger(hasher, @as(u16, @intCast(value.len)));
480 hasher.update(value);
481 }
482
483 fn hashInteger(hasher: *Sha256, value: anytype) void {
484 var encoded: [@sizeOf(@TypeOf(value))]u8 = undefined;
485 std.mem.writeInt(@TypeOf(value), &encoded, value, .little);
486 hasher.update(&encoded);
487 }
488
489 fn hasNode(state: types.State, id: types.NodeId) bool {
490 return findNode(state, id) != null;
491 }
492
493 fn findNode(state: types.State, id: types.NodeId) ?types.NodeState {
494 for (state.nodes[0..state.node_count]) |node| {
495 if (sameNode(node.id, id)) return node;
496 }
497 return null;
498 }
499
500 fn findPacket(state: types.State, id: u64) ?types.QueuedPacket {
501 for (state.packets[0..state.packet_count]) |packet_value| {
502 if (packet_value.packet.id == id) return packet_value;
503 }
504 return null;
505 }
506
507 fn partitionMask(node_count: u8) u8 {
508 const pair_count = @divExact(node_count * (node_count - 1), 2);
509 var mask: u8 = 0;
510 for (0..pair_count) |index| {
511 mask |= @as(u8, 1) << @intCast(index);
512 }
513 return mask;
514 }
515
516 comptime {
517 const contract = profile.interpretedContinuationTestV1().contract;
518 std.debug.assert(types.node_limit == contract.instance_limit);
519 std.debug.assert(
520 types.node_limit * (types.node_limit - 1) / 2 <= @bitSizeOf(u8),
521 );
522 std.debug.assert(
523 @backingInt(types.CapacityResource.packet) <= @bitSizeOf(u8),
524 );
525 std.debug.assert(types.packet_limit == contract.transport.event_records);
526 std.debug.assert(types.packet_bytes_max == contract.transport.effect_result_bytes);
527 std.debug.assert(types.admission_limit == contract.admission_limit);
528 std.debug.assert(types.packet_bytes_max <= std.math.maxInt(u16));
529 }