nx_bt_v2_merkle.nx source
↩ module page · 60 lines · 3214 B
1// nx_bt_v2_merkle.nx -- LIB: BitTorrent v2 (BEP 52) style SHA-256 MERKLE piece tree + INCLUSION PROOFS. Upgrades our
2// torrents from v1 (SHA-1 flat piece list) to v2: each leaf = SHA-256 of a block, internal node = SHA-256(left||right),
3// the root is the file's content hash (the basis for urn:btmh magnets). The killer feature is the inclusion PROOF:
4// a peer can verify ONE block belongs to the root using only log2(n) sibling hashes -- verifiable random access /
5// streaming, no need for the whole file. Composes nx_sha256 (our own). Leaf count assumed a power of two (BEP 52
6// zero-pads to that; padding is the trivial extension). No TLS. license_tier: ORIGINAL
7import "nx_sha256.nx"
8import "nx_syscalls.nx"
9
10func mk_memeq(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 }
11// leaf hash = SHA-256(block)
12func mk_leaf(block: *u8, len: i64, out32: *u8) -> i64 {
13 let ctx: *Sha256 = sys_mmap(256) as *Sha256
14 sha256_init(ctx); sha256_update(ctx, block, len); sha256_final(ctx, out32); return 0
15}
16// internal node = SHA-256(left32 || right32)
17func mk_node(l: *u8, r: *u8, out32: *u8) -> i64 {
18 let cat: *u8 = sys_mmap(64); var i: i64=0; while i<32 { cat[i]=l[i]; cat[32+i]=r[i]; i=i+1 }
19 let ctx: *Sha256 = sys_mmap(256) as *Sha256
20 sha256_init(ctx); sha256_update(ctx, cat, 64); sha256_final(ctx, out32); return 0
21}
22// merkle ROOT over n (power-of-two) contiguous 32-byte leaf hashes -> out32.
23func mk_root(leaves: *u8, n: i64, out32: *u8) -> i64 {
24 let cur: *u8 = sys_mmap(n*32 + 64); var i: i64=0; while i<n*32 { cur[i]=leaves[i]; i=i+1 }
25 var cnt: i64 = n
26 while cnt>1 {
27 var j: i64=0
28 while j<cnt/2 {
29 mk_node((cur as i64 + (2*j)*32) as *u8, (cur as i64 + (2*j+1)*32) as *u8, (cur as i64 + j*32) as *u8)
30 j=j+1
31 }
32 cnt = cnt/2
33 }
34 var k: i64=0; while k<32 { out32[k]=cur[k]; k=k+1 }
35 return 0
36}
37// inclusion PROOF for leaf `idx`: writes the sibling hash at each level into proof (np*32 bytes). Returns np (#levels).
38func mk_proof(leaves: *u8, n: i64, idx: i64, proof: *u8) -> i64 {
39 let cur: *u8 = sys_mmap(n*32 + 64); var i: i64=0; while i<n*32 { cur[i]=leaves[i]; i=i+1 }
40 var cnt: i64 = n; var pos: i64 = idx; var np: i64 = 0
41 while cnt>1 {
42 var sib: i64 = pos + 1; if (pos & 1)==1 { sib = pos - 1 }
43 var b: i64=0; while b<32 { proof[np*32 + b] = cur[sib*32 + b]; b=b+1 }
44 np = np+1
45 var j: i64=0; while j<cnt/2 { mk_node((cur as i64 + (2*j)*32) as *u8, (cur as i64 + (2*j+1)*32) as *u8, (cur as i64 + j*32) as *u8); j=j+1 }
46 cnt = cnt/2; pos = pos/2
47 }
48 return np
49}
50// VERIFY: recompute the root from leaf32 (at idx) + its proof siblings; return 1 iff it equals root32.
51func mk_verify(leaf32: *u8, idx: i64, proof: *u8, np: i64, root32: *u8) -> i64 {
52 let acc: *u8 = sys_mmap(32); var i: i64=0; while i<32 { acc[i]=leaf32[i]; i=i+1 }
53 var pos: i64 = idx; var lvl: i64 = 0
54 while lvl<np {
55 let sib: *u8 = (proof as i64 + lvl*32) as *u8
56 if (pos & 1)==1 { mk_node(sib, acc, acc) } else { mk_node(acc, sib, acc) }
57 pos = pos/2; lvl = lvl+1
58 }
59 return mk_memeq(acc, root32, 32)
60}