code wiki / _hdl_build / nx_seg_merkle.nx
nx_seg_merkle.nx source
↩ module page · 59 lines · 3250 B
1// nx_seg_merkle.nx -- CAP-SEG-MERKLE: Merkle proof-of-inclusion over a sovereign store's records (IPLD /
2// certificate-transparency class). A verifier holding ONLY the 32-byte ROOT + a compact O(log n) PROOF can confirm a
3// record is in the store WITHOUT reading the store -- tamper-evident inclusion, portable (root+proof cross the
4// interop boundary that nx_seg_store's published spec opens). leaf = a 32-byte record hash; node = sha256(left||right);
5// odd tail duplicates itself (Bitcoin/CT convention). Composes nx_sha256. A LIBRARY (no main -> run its _gate).
6// license_tier: ORIGINAL
7import "nx_syscalls.nx"
8import "nx_sha256.nx"
9
10func mk_cpy(dst: *u8, src: *u8, n: i64) -> i64 { var i: i64=0; while i<n { dst[i]=src[i]; i=i+1 } return 0 }
11func mk_eq(a: *u8, b: *u8, n: i64) -> i64 { var i: i64=0; while i<n { if a[i]!=b[i] { return 0 } i=i+1 } return 1 }
12// parent = sha256(left[0..32] || right[0..32]) -> out[0..32]
13func mk_node(l: *u8, r: *u8, out: *u8) -> i64 { let b: *u8=sys_mmap(64); mk_cpy(b, l, 32); mk_cpy((b as i64 + 32) as *u8, r, 32); sha256_digest(b, 64, out); return 0 }
14
15// build the Merkle root from n leaves (leaves = contiguous n*32 bytes) -> root[0..32].
16func mk_root(leaves: *u8, n: i64, root: *u8) -> i64 {
17 if n == 0 { return 0 }
18 let cur: *u8 = sys_mmap(n*32 + 128); mk_cpy(cur, leaves, n*32)
19 var cnt: i64 = n
20 while cnt > 1 {
21 let nxt: *u8 = sys_mmap(cnt*32 + 128); var nc: i64=0; var i: i64=0
22 while i < cnt {
23 let l: *u8 = (cur as i64 + i*32) as *u8
24 var r: *u8 = l
25 if i+1 < cnt { r = (cur as i64 + (i+1)*32) as *u8 }
26 mk_node(l, r, (nxt as i64 + nc*32) as *u8); nc=nc+1; i=i+2
27 }
28 mk_cpy(cur, nxt, nc*32); cnt = nc
29 }
30 mk_cpy(root, cur, 32); return 0
31}
32// inclusion proof for leaf `idx`: proof[d*32..] = sibling hash at level d; dirs[d]=1 if sibling is on the LEFT.
33// returns the proof depth.
34func mk_proof(leaves: *u8, n: i64, idx: i64, proof: *u8, dirs: *i64) -> i64 {
35 let cur: *u8 = sys_mmap(n*32 + 128); mk_cpy(cur, leaves, n*32)
36 var cnt: i64 = n; var pos: i64 = idx; var depth: i64 = 0
37 while cnt > 1 {
38 var sib: i64 = pos + 1; var dir: i64 = 0
39 if (pos % 2) == 1 { sib = pos - 1; dir = 1 }
40 if sib >= cnt { sib = pos }
41 mk_cpy((proof as i64 + depth*32) as *u8, (cur as i64 + sib*32) as *u8, 32); dirs[depth]=dir; depth=depth+1
42 let nxt: *u8 = sys_mmap(cnt*32 + 128); var nc: i64=0; var i: i64=0
43 while i < cnt { let l: *u8=(cur as i64 + i*32) as *u8; var r: *u8=l; if i+1<cnt { r=(cur as i64 + (i+1)*32) as *u8 } mk_node(l, r, (nxt as i64 + nc*32) as *u8); nc=nc+1; i=i+2 }
44 mk_cpy(cur, nxt, nc*32); cnt=nc; pos = pos/2
45 }
46 return depth
47}
48// verify: fold `leaf` up through the proof; 1 if it recomputes to `root`, else 0.
49func mk_verify(leaf: *u8, proof: *u8, dirs: *i64, depth: i64, root: *u8) -> i64 {
50 let cur: *u8 = sys_mmap(64); mk_cpy(cur, leaf, 32)
51 var d: i64=0
52 while d < depth {
53 let sib: *u8 = (proof as i64 + d*32) as *u8
54 let out: *u8 = sys_mmap(64)
55 if dirs[d] == 1 { mk_node(sib, cur, out) } else { mk_node(cur, sib, out) }
56 mk_cpy(cur, out, 32); d=d+1
57 }
58 return mk_eq(cur, root, 32)
59}