lib/machine/src/explore/distributed/canon.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const explore = @import("../root.zig");
2 const fabric = @import("../../fabric/root.zig");
3 const profile = @import("../../profile/root.zig");
4 const state_owner = @import("state.zig");
5 const std = @import("std");
6 const types = @import("types.zig");
7 const world = @import("../../world/root.zig");
8
9 const Sha256 = std.crypto.hash.sha2.Sha256;
10 const state_domain = "tiny.machine.explore.distributed.state/v1";
11 const world_domain = "tiny.machine.explore.distributed.world/v1";
12 const build_domain = "tiny.machine.explore.distributed.build/v1";
13
14 pub fn initialRoot(contract: profile.ContractFingerprint) fabric.Root {
15 return .{
16 .digest = seedDigest(state_domain),
17 .dialect = .ordered_effect_fabric_v3,
18 .machine_contract = contract,
19 .entry_frontier = 0,
20 .admission_frontier = 0,
21 .fault_frontier = 0,
22 };
23 }
24
25 pub fn origin(contract: profile.ContractFingerprint) world.Root {
26 return .{
27 .digest = seedDigest(world_domain),
28 .dialect = .connected_world_v1,
29 .machine_contract = contract,
30 .fabric = initialRoot(contract),
31 .node_count = types.node_count,
32 };
33 }
34
35 pub fn builds() [types.node_count]explore.CapsuleBuildIdentity {
36 var result: [types.node_count]explore.CapsuleBuildIdentity = undefined;
37 for (&result, 0..) |*entry, index| {
38 var node: fabric.NodeId = .{ .bytes = @splat(0) };
39 node.bytes[node.bytes.len - 1] = @intCast(index + 1);
40 var hasher = Sha256.init(.{});
41 hasher.update(build_domain);
42 hasher.update(&node.bytes);
43 var digest: [Sha256.digest_length]u8 = undefined;
44 hasher.final(&digest);
45 std.debug.assert(node.bytes[node.bytes.len - 1] != 0);
46 entry.* = .{ .node = node, .execution = .{ .digest = digest } };
47 }
48 for (result[1..], result[0 .. result.len - 1]) |next, previous| {
49 std.debug.assert(std.mem.lessThan(u8, &previous.node.bytes, &next.node.bytes));
50 }
51 return result;
52 }
53
54 pub fn advance(
55 current: fabric.Root,
56 decision: explore.SearchDecision,
57 value: *const state_owner.State,
58 ) fabric.Root {
59 std.debug.assert(current.entry_frontier < std.math.maxInt(u64));
60 var next = current;
61 next.entry_frontier += 1;
62 next.admission_frontier += 1;
63 if (decision.site.stream == .fault) next.fault_frontier += 1;
64 next.digest = stateDigest(current.digest, decision, value);
65 std.debug.assert(next.fault_frontier <= next.admission_frontier);
66 std.debug.assert(next.admission_frontier <= next.entry_frontier);
67 return next;
68 }
69
70 fn stateDigest(
71 previous: [Sha256.digest_length]u8,
72 decision: explore.SearchDecision,
73 value: *const state_owner.State,
74 ) [Sha256.digest_length]u8 {
75 var hasher = Sha256.init(.{});
76 hasher.update(state_domain);
77 hasher.update(&previous);
78 hashDecision(&hasher, decision);
79 hashProtocol(&hasher, value);
80 var digest: [Sha256.digest_length]u8 = undefined;
81 hasher.final(&digest);
82 std.debug.assert(!allZero(&digest));
83 return digest;
84 }
85
86 fn hashDecision(hasher: *Sha256, decision: explore.SearchDecision) void {
87 hashInteger(hasher, @backingInt(decision.site.stream));
88 hashInteger(hasher, decision.site.sequence);
89 hashInteger(hasher, decision.site.virtual_time_tick);
90 hashInteger(hasher, decision.alternative);
91 hashInteger(hasher, decision.alternative_count);
92 switch (decision.choice) {
93 .input => |value| {
94 hashInteger(hasher, @as(u8, @backingInt(std.meta.activeTag(value.value))));
95 hashInteger(hasher, value.virtual_time_tick);
96 hashInteger(hasher, inputWord(value.value));
97 },
98 .schedule => |value| {
99 hashInteger(hasher, @as(u8, @backingInt(std.meta.activeTag(value.value))));
100 hashInteger(hasher, value.virtual_time_tick);
101 hashInteger(hasher, switch (value.value) {
102 .turn => |node| node,
103 .idle => @as(u8, types.node_count),
104 });
105 },
106 .topology => |value| {
107 hashInteger(hasher, @as(u8, @backingInt(std.meta.activeTag(value.value))));
108 hashInteger(hasher, value.virtual_time_tick);
109 },
110 .fault => |value| {
111 hashInteger(hasher, @as(u8, @backingInt(std.meta.activeTag(value.action))));
112 hashInteger(hasher, value.virtual_time_tick);
113 hashInteger(hasher, faultWord(value.action));
114 },
115 }
116 }
117
118 fn hashProtocol(hasher: *Sha256, value: *const state_owner.State) void {
119 hashInteger(hasher, value.round);
120 hashInteger(hasher, @intFromBool(value.open));
121 hashInteger(hasher, value.proposal);
122 hashInteger(hasher, value.acks);
123 hashInteger(hasher, value.ack_mask);
124 hashInteger(hasher, @intFromBool(value.committed));
125 hashInteger(hasher, value.committed_round);
126 hashInteger(hasher, value.committed_value);
127 hashInteger(hasher, value.hang_streak);
128 hashInteger(hasher, value.hung orelse types.node_count);
129 hashInteger(hasher, @intFromBool(value.delivery_blocked));
130 hashInteger(hasher, value.turn_node orelse types.node_count);
131 hashInteger(hasher, value.request);
132 for (value.nodes) |node| {
133 hashInteger(hasher, @intFromBool(node.accepted));
134 hashInteger(hasher, node.accepted_round);
135 hashInteger(hasher, node.accepted_value);
136 hashInteger(hasher, @intFromBool(node.hung));
137 }
138 hashInteger(hasher, value.messages.count);
139 for (value.messages.messages()) |message| {
140 hashInteger(hasher, @as(u8, @backingInt(message.kind)));
141 hashInteger(hasher, message.round);
142 hashInteger(hasher, message.value);
143 hashInteger(hasher, message.sender);
144 hashInteger(hasher, message.destination);
145 }
146 }
147
148 fn inputWord(value: explore.InputValue) u64 {
149 return switch (value) {
150 .wait, .terminal, .entropy, .packet => |word| word,
151 .service_result, .effect_result => |outcome| @backingInt(outcome),
152 };
153 }
154
155 fn faultWord(action: explore.FaultAction) u64 {
156 return switch (action) {
157 .healthy => 0,
158 .inject, .persist, .recover => |kind| @backingInt(kind),
159 };
160 }
161
162 fn hashInteger(hasher: *Sha256, value: anytype) void {
163 const Widened = if (@TypeOf(value) == u1) u8 else @TypeOf(value);
164 const widened: Widened = value;
165 var encoded: [@sizeOf(Widened)]u8 = undefined;
166 std.mem.writeInt(Widened, &encoded, widened, .little);
167 hasher.update(&encoded);
168 }
169
170 fn seedDigest(domain: []const u8) [Sha256.digest_length]u8 {
171 std.debug.assert(domain.len > 0);
172 var hasher = Sha256.init(.{});
173 hasher.update(domain);
174 hashInteger(&hasher, types.dialect_version);
175 hashInteger(&hasher, types.node_count);
176 var digest: [Sha256.digest_length]u8 = undefined;
177 hasher.final(&digest);
178 std.debug.assert(!allZero(&digest));
179 return digest;
180 }
181
182 fn allZero(bytes: []const u8) bool {
183 for (bytes) |byte| if (byte != 0) return false;
184 return true;
185 }