nx_asset_merkle.nx source
↩ module page · 107 lines · 4267 B
1// nx_asset_merkle.nx -- UNIVERSAL ORGANIZATION TOOLING arc, R8: WHOLE-INVENTORY MERKLE ROOT.
2//
3// org_research.tsv merkle-integrity (CONFIRMED): a MERKLE DAG over the content makes the WHOLE
4// inventory tamper-evident + independently VERIFIABLE -- any byte change anywhere flips a single root
5// hash, cheap to re-prove (the property git + IPFS have; incumbent DAM/KM on mutable DBs do NOT).
6// R0 already gives PER-RECORD content-addressed integrity (each record's CID); this organ lifts it to
7// the WHOLE catalog: one root hash over the set of member record CIDs.
8//
9// PURE COMPOSITION (Rule 15), ZERO new crypto: leaves = the R1 catalog's member CIDs (cat_list); the
10// tree-hash is nx_canon_cid cid_of (the SAME sha256-based CID the records use). DETERMINISTIC +
11// ORDER-INDEPENDENT: the leaves are SORTED before pairing, so the root depends only on the SET of
12// records, never on insertion order -> the same inventory yields the same root on any machine.
13//
14// Construction: sort leaf CIDs; repeatedly pair adjacent nodes and hash parent = cid_of(left||right)
15// (an odd node duplicates with itself), until one root remains. 0 leaves -> a fixed EMPTY root;
16// 1 leaf -> cid_of(that leaf) so even a singleton inventory has a hashed root.
17// No hardware/persistent-firmware writes (Rule 26). license_tier: ORIGINAL
18import "nx_syscalls.nx"
19import "nx_canon_cid.nx"
20import "nx_asset_catalog.nx"
21const K_MAGIC_4096: i64 = 4096
22
23func mr_slen(s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } return n }
24
25// lexicographic compare of two NUL-terminated strings: -1 / 0 / 1.
26func mr_strcmp(a: *u8, b: *u8) -> i64 {
27 var i: i64 = 0
28 while 1 == 1 {
29 let ca: i64 = a[i]
30 let cb: i64 = b[i]
31 if ca != cb { if ca < cb { return 0 - 1 } return 1 }
32 if ca == 0 { return 0 }
33 i = i + 1
34 }
35 return 0
36}
37
38// insertion-sort a ptr array of NUL-terminated CID strings (so the root is order-independent).
39func mr_sort(cids: *i64, n: i64) -> i64 {
40 var i: i64 = 1
41 while i < n {
42 let key: i64 = cids[i]
43 var j: i64 = i - 1
44 var go: i64 = 1
45 while go == 1 {
46 if j < 0 { go = 0 } else {
47 if mr_strcmp(cids[j] as *u8, key as *u8) > 0 { cids[j + 1] = cids[j]; j = j - 1 } else { go = 0 }
48 }
49 }
50 cids[j + 1] = key
51 i = i + 1
52 }
53 return 0
54}
55
56// parent = cid_of(left_cid || right_cid).
57func mr_concat_hash(l: *u8, r: *u8, out: *u8) -> i64 {
58 let buf: *u8 = sys_mmap(256)
59 var o: i64 = 0
60 var i: i64 = 0
61 while l[i] != (0 as u8) { buf[o] = l[i]; o = o + 1; i = i + 1 }
62 i = 0
63 while r[i] != (0 as u8) { buf[o] = r[i]; o = o + 1; i = i + 1 }
64 cid_of(buf, o, out)
65 return 0
66}
67
68// THE ROOT over the catalog at `prefix`. Writes the NUL-terminated root CID into out_root.
69func mr_root(prefix: *u8, out_root: *u8) -> i64 {
70 let cur: *i64 = sys_mmap(8 * K_MAGIC_4096) as *i64
71 let n: i64 = cat_list(prefix, cur, K_MAGIC_4096)
72 if n == 0 { cid_of("NX-MERKLE-EMPTY\x00" as *u8, 15, out_root); return 0 }
73 mr_sort(cur, n)
74 if n == 1 { cid_of(cur[0] as *u8, mr_slen(cur[0] as *u8), out_root); return 0 }
75 var cnt: i64 = n
76 while cnt > 1 {
77 let nxt: *i64 = sys_mmap(8 * K_MAGIC_4096) as *i64
78 var w: i64 = 0
79 var i: i64 = 0
80 while i < cnt {
81 let l: *u8 = cur[i] as *u8
82 var r: *u8 = l
83 if (i + 1) < cnt { r = cur[i + 1] as *u8 } // odd tail duplicates with itself
84 let par: *u8 = sys_mmap(128)
85 mr_concat_hash(l, r, par)
86 nxt[w] = par as i64; w = w + 1
87 i = i + 2
88 }
89 var k: i64 = 0
90 while k < w { cur[k] = nxt[k]; k = k + 1 }
91 cnt = w
92 }
93 let root: *u8 = cur[0] as *u8
94 var i: i64 = 0
95 while root[i] != (0 as u8) { out_root[i] = root[i]; i = i + 1 }
96 out_root[i] = 0 as u8
97 return 0
98}
99
100// inclusion: is `cid` one of the catalog's member leaves? 1 yes / 0 no.
101func mr_contains(prefix: *u8, cid: *u8) -> i64 {
102 let lst: *i64 = sys_mmap(8 * K_MAGIC_4096) as *i64
103 let n: i64 = cat_list(prefix, lst, K_MAGIC_4096)
104 var i: i64 = 0
105 while i < n { if mr_strcmp(lst[i] as *u8, cid) == 0 { return 1 } i = i + 1 }
106 return 0
107}