nx_sketch_robust_hll.nx source
↩ module page · 207 lines · 7117 B
1// sketch_robust_hll.nx -- adversarial-safe HLL via median-of-k.
2//
3// Wraps k independent HyperLogLog sketches with derived seeds and
4// reports the median cardinality estimate. Defeats simple adaptive
5// adversaries that game a single HLL by crafting inputs to inflate
6// one register: poisoning a single inner sketch can't move the
7// median when k >= 3.
8//
9// Maturity: ReferenceImpl. Full Cohen-Kaplan-Mansour-Matias-Stemmer
10// scheme ("Breaking the Quadratic Barrier", arXiv:2502.05723) uses
11// cryptographic sketch-switching with a secret key; this median-
12// of-k is the simpler partial defense that catches replay attacks
13// and single-target adaptive queries without that machinery.
14//
15// AdversarialSafety = NX_ADV_ADVERSARIAL. Substrate refuses to
16// allow an Honest-tagged Hll to substitute for this in compositions
17// requiring adversarial robustness.
18//
19// CAPABILITY-STOMP POSITION (per doc 19):
20// Apache DataSketches: NO adversarial variant.
21// Redis / RedisBloom: NO adversarial variant.
22// ClickHouse uniqHLL: NO adversarial variant.
23// Druid: uses DS internally; NO adversarial variant.
24// stream-lib (Java): NO adversarial variant.
25// python-datasketch: NO adversarial variant.
26// This is greenfield -- a primitive NO INCUMBENT SHIPS.
27
28// nx_safety_envelope:
29// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
30// sil_target: SIL1
31// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
32// verdict: NOT_YET_EVALUATED
33
34import "nx_syscalls.nx"
35import "nx_sketch_hll.nx"
36import "nx_sketch_types.nx"
37
38// k in [3, 31]. k=3 is the minimum for non-trivial median; k=31
39// caps at 31 inner sketches (~8KB at lgK=8) for a generous budget.
40const NX_ROBUST_K_MIN: i64 = 3
41const NX_ROBUST_K_MAX: i64 = 31
42
43// Golden-ratio derivation constant for per-inner-sketch seed
44// diversification. Mirrors the TS reference (core-sketch/
45// robust_hll.ts).
46const NX_ROBUST_SEED_DERIVE: i64 = 0x9E3779B9
47
48// Handle stores k inner-HLL pointers as an array. Total handle
49// size: 32 + k*8 bytes (header + inner pointer array). We
50// over-allocate to NX_ROBUST_K_MAX so the size is fixed and the
51// caller doesn't need to track k for memory layout.
52
53struct RobustHll {
54 lg_k: i64,
55 k: i64,
56 seed_base: i64,
57 inner_count: i64,
58 // 32 bytes header above; inner pointers stored externally via
59 // a sys_mmap'd i64 array (avoids needing flexible struct fields).
60 inner_ptrs: *i64,
61}
62
63// === construction =================================================
64
65func nx_robust_hll_alloc(lg_k: i64, k: i64, seed_base: i64) -> *RobustHll {
66 if k < NX_ROBUST_K_MIN { return 0 as *RobustHll }
67 if k > NX_ROBUST_K_MAX { return 0 as *RobustHll }
68 let raw: *u8 = sys_mmap(40)
69 let r: *RobustHll = raw as *RobustHll
70 r.lg_k = lg_k
71 r.k = k
72 r.seed_base = seed_base
73 r.inner_count = k
74 let inner_bytes: i64 = k * 8
75 let inner_raw: *u8 = sys_mmap(inner_bytes)
76 r.inner_ptrs = inner_raw as *i64
77 var i: i64 = 0
78 while i < k {
79 // Derive per-inner seed via XOR with golden-ratio multiple.
80 // Each inner HLL gets a distinct seed so register-clobber on
81 // one doesn't propagate to the others.
82 let mix: i64 = (i + 1) * NX_ROBUST_SEED_DERIVE
83 let seed_i: i64 = seed_base ^ mix
84 let h: *Hll = nx_hll_alloc(lg_k, seed_i)
85 if h == (0 as *Hll) { return 0 as *RobustHll }
86 r.inner_ptrs[i] = h as i64
87 i = i + 1
88 }
89 return r
90}
91
92// === add ===========================================================
93// Fan out to every inner sketch.
94
95func nx_robust_hll_add(r: *RobustHll, key: *u8, len: i64) -> i64 {
96 var i: i64 = 0
97 while i < r.k {
98 let h: *Hll = r.inner_ptrs[i] as *Hll
99 nx_hll_add(h, key, len)
100 i = i + 1
101 }
102 return 0
103}
104
105// === median helper ================================================
106//
107// Insertion sort over k i64 estimates (k <= 31, so n^2 is fine);
108// return the middle element. For even k, average the two middles
109// (loses a bit of integer precision but matches the standard
110// definition).
111
112func nx_median_i64(arr: *i64, n: i64) -> i64 {
113 // Simple in-place insertion sort.
114 var i: i64 = 1
115 while i < n {
116 let cur: i64 = arr[i]
117 var j: i64 = i - 1
118 var done: i64 = 0
119 while done == 0 {
120 if j < 0 { done = 1 }
121 if done == 0 {
122 let prev: i64 = arr[j]
123 if prev <= cur {
124 done = 1
125 }
126 if done == 0 {
127 arr[j + 1] = prev
128 j = j - 1
129 }
130 }
131 }
132 arr[j + 1] = cur
133 i = i + 1
134 }
135 let mid: i64 = n / 2
136 if (n & 1) == 1 {
137 return arr[mid]
138 }
139 return (arr[mid - 1] + arr[mid]) / 2
140}
141
142// === estimate =====================================================
143//
144// Collect every inner sketch's cardinality estimate, sort, return
145// the median.
146
147func nx_robust_hll_estimate(r: *RobustHll) -> i64 {
148 let buf_bytes: i64 = r.k * 8
149 let buf: *u8 = sys_mmap(buf_bytes)
150 let ests: *i64 = buf as *i64
151 var i: i64 = 0
152 while i < r.k {
153 let h: *Hll = r.inner_ptrs[i] as *Hll
154 ests[i] = nx_hll_estimate(h)
155 i = i + 1
156 }
157 return nx_median_i64(ests, r.k)
158}
159
160// === typed query =================================================
161//
162// Returns ApproxI64 with stddev_rel envelope SAME as inner HLL.
163// We don't tighten the bound (median of k normal samples has
164// asymptotic stderr ~ sigma * sqrt(pi/(2k)) -- ~0.94x for k=5)
165// because under ADVERSARIAL input the samples are non-normal and
166// the bound doesn't hold. Honest > optimistic.
167//
168// Critical difference from nx_hll_query: adv_safety field is
169// NX_ADV_ADVERSARIAL. Substrate refuses cross-domain substitution.
170
171func nx_robust_hll_query(r: *RobustHll) -> *ApproxI64 {
172 let est: i64 = nx_robust_hll_estimate(r)
173 let stddev_ppb: i64 = nx_hll_stddev_rel_ppb(r.lg_k)
174 return nx_approx_new(est, NX_ENV_REL_STDDEV, stddev_ppb,
175 682700000,
176 NX_MATURITY_REFERENCE_IMPL,
177 NX_ADV_ADVERSARIAL)
178}
179
180// === inner-estimate inspection (debug / per-sketch divergence) ====
181
182func nx_robust_hll_inner_estimate(r: *RobustHll, i: i64) -> i64 {
183 if i < 0 { return 0 }
184 if i >= r.k { return 0 }
185 let h: *Hll = r.inner_ptrs[i] as *Hll
186 return nx_hll_estimate(h)
187}
188
189// === manual register-poison (for adversarial-test setup) ==========
190//
191// Sets all registers of inner sketch `i` to a chosen rho value.
192// Simulates an attacker who has found a hash collision targeting
193// one specific seed. Used by the smoke gate's poison-injection
194// case to verify the median holds when one inner sketch is
195// destroyed.
196
197func nx_robust_hll_poison_inner(r: *RobustHll, i: i64, rho: i64) -> i64 {
198 if i < 0 { return 0 }
199 if i >= r.k { return 0 }
200 let h: *Hll = r.inner_ptrs[i] as *Hll
201 var j: i64 = 0
202 while j < h.m {
203 h.regs[j] = rho
204 j = j + 1
205 }
206 return 0
207}