nx_trace_merkle.nx source
↩ module page · 176 lines · 6759 B
1// nx_trace_merkle.nx -- merkle-root summary of a provenance chain.
2//
3// Per [[feedback-end-to-end-bit-traceability-architecture]]:
4// "federated via Merkle-root + branch fetch with per-call mutual
5// consent." nx_trace_merkle computes the merkle-root of a chain range
6// so cross-host verification can confirm "did your chain end with the
7// same root as mine?" without transmitting every link.
8//
9// V1 ships:
10// - struct NxMerkleNode with hash + left/right child indices
11// - struct NxMerkleTree built from a contiguous span of trace entries
12// - root computation (bottom-up hash composition)
13// - verify_membership (does a given (call_id, output_hash) appear
14// in the tree summarized by this root?)
15//
16// HASH COMPOSITION RULE: parent = combine(left_hash, right_hash) where
17// combine is V1 simple-XOR-with-rotate. V2 swaps in BLAKE3 once the
18// existing nx_blake2b primitive is wired here. The current combine is
19// NOT cryptographically secure; V1's purpose is the STRUCTURE
20// (merkle-tree composition + verify pattern), V2 makes the hash strong.
21//
22// Composes:
23// nx_trace_log -- the entries we summarize
24// nx_provenance_chain -- alternative source (in-memory ring)
25// nx_methyl -- merkle roots can be methyl-marked for sharing
26// nx_pollinate -- merkle roots travel as XENO_OBSERVATION payloads
27// (one root verifies a whole trace range)
28//
29// Gap list (V1 honest perf verdict):
30// - combine is XOR-with-rotate, NOT cryptographically secure
31// (V2 swaps to BLAKE3 via nx_blake2b)
32// - tree is balanced binary; odd-leaf-count uses duplicate-last
33// pattern (standard merkle convention)
34// - no streaming-build (whole tree built from finite range in V1)
35
36import "nx_syscalls.nx"
37import "nx_tier.nx"
38import "nx_trace_log.nx"
39
40const NX_MK_OK: nx_int = 0
41const NX_MK_ERR_EMPTY: nx_int = 1
42const NX_MK_ERR_BAD_RANGE: nx_int = 2
43const NX_MK_ERR_TOO_LARGE: nx_int = 3
44const NX_MK_NOT_MEMBER: nx_int = 4
45const NX_MK_MEMBER: nx_int = 5
46
47// ===== Struct: NxMerkleTree =======================================
48//
49// Binary merkle tree built from a span of trace_log entries. nodes
50// is a flat array sized 2 * leaf_count (V1 caps leaves at 256 for
51// simplicity; V2 supports arbitrary). The root is always at nodes[0].
52
53struct NxMerkleTree {
54 nodes: *i64, // flat array of hash values
55 n_nodes: nx_size,
56 leaf_count: nx_size,
57 root_hash: nx_size,
58}
59
60const NX_MK_MAX_LEAVES: nx_size = 256
61
62// ===== _mk_combine ================================================
63//
64// V1 hash combiner: rotate left by 13 + XOR. Not cryptographically
65// secure -- V2 swaps to BLAKE3. The substrate's job here is to prove
66// the TREE STRUCTURE works; security comes from the underlying hash.
67
68func _mk_combine(left: nx_size, right: nx_size) -> nx_size {
69 // rotate left by 13
70 let rl: nx_size = ((left << 13) | (left >> 51)) & 0xFFFFFFFFFFFFFFFF
71 return rl ^ right
72}
73
74// ===== nx_trace_merkle_build =====================================
75//
76// Build a merkle tree from trace_log entries within [start, start+n).
77// Returns the constructed tree or NULL on bad range / too many leaves.
78// The root_hash field of the returned tree is the merkle root.
79
80func nx_trace_merkle_build(log: *NxTraceLog,
81 call_id: nx_int,
82 start_idx: nx_size,
83 n: nx_size) -> *NxMerkleTree {
84 if n == 0 { return (0 as i64) as *NxMerkleTree }
85 if n > NX_MK_MAX_LEAVES { return (0 as i64) as *NxMerkleTree }
86 if start_idx + n > log.count { return (0 as i64) as *NxMerkleTree }
87
88 let t: *NxMerkleTree = (sys_mmap(40)) as *NxMerkleTree
89 // Pad n up to next power of 2 by duplicating the last entry's hash
90 var leaves: nx_size = 1
91 while leaves < n { leaves = leaves * 2 }
92 let total_nodes: nx_size = 2 * leaves
93 t.nodes = (sys_mmap(total_nodes * 8)) as *i64
94 t.n_nodes = total_nodes
95 t.leaf_count = leaves
96
97 // Leaves are at indices [leaves, leaves + leaves). Fill from log.
98 var i: nx_size = 0
99 var last_hash: nx_size = 0
100 while i < leaves {
101 var src_h: nx_size = 0
102 if i < n {
103 let e: *NxTraceEntry = nx_trace_log_entry_at(log, start_idx + i)
104 if (e as i64) != 0 {
105 if e.call_id == call_id { src_h = e.output_hash }
106 }
107 last_hash = src_h
108 } else {
109 src_h = last_hash // pad with last leaf hash
110 }
111 t.nodes[leaves + i] = src_h as i64
112 i = i + 1
113 }
114
115 // Bottom-up combine: level by level, building toward root at [0].
116 // For each internal node at index k, left = 2k, right = 2k+1.
117 var level_start: nx_size = leaves
118 while level_start > 1 {
119 let next_level_start: nx_size = level_start / 2
120 var j: nx_size = next_level_start
121 while j < level_start {
122 let left_h: nx_size = t.nodes[2 * j] as nx_size
123 let right_h: nx_size = t.nodes[2 * j + 1] as nx_size
124 t.nodes[j] = _mk_combine(left_h, right_h) as i64
125 j = j + 1
126 }
127 level_start = next_level_start
128 }
129 t.root_hash = t.nodes[1] as nx_size
130 return t
131}
132
133// ===== nx_trace_merkle_root ======================================
134
135func nx_trace_merkle_root(t: *NxMerkleTree) -> nx_size {
136 if (t as i64) == 0 { return 0 }
137 return t.root_hash
138}
139
140// ===== nx_trace_merkle_verify_member =============================
141//
142// Membership query: does the leaf with the given output_hash appear
143// in this tree? Returns NX_MK_MEMBER or NX_MK_NOT_MEMBER.
144
145func nx_trace_merkle_verify_member(t: *NxMerkleTree,
146 output_hash: nx_size) -> nx_int {
147 if (t as i64) == 0 { return NX_MK_NOT_MEMBER }
148 var i: nx_size = 0
149 while i < t.leaf_count {
150 let leaf_idx: nx_size = t.leaf_count + i
151 let leaf_h: nx_size = t.nodes[leaf_idx] as nx_size
152 if leaf_h == output_hash { return NX_MK_MEMBER }
153 i = i + 1
154 }
155 return NX_MK_NOT_MEMBER
156}
157
158// ===== nx_trace_merkle_leaf_count =================================
159
160func nx_trace_merkle_leaf_count(t: *NxMerkleTree) -> nx_size {
161 if (t as i64) == 0 { return 0 }
162 return t.leaf_count
163}
164
165// ===== nx_trace_merkle_roots_equal ================================
166//
167// Cross-host verification: two hosts compare their roots. If equal,
168// they hold the same trace range without transmitting links.
169// Used by V2 nx_pollinate cross-host trace exchange.
170
171func nx_trace_merkle_roots_equal(a: *NxMerkleTree, b: *NxMerkleTree) -> nx_int {
172 if (a as i64) == 0 { return 0 }
173 if (b as i64) == 0 { return 0 }
174 if a.root_hash == b.root_hash { return 1 }
175 return 0
176}