sketch_robust_hll.nx source
↩ module page · 203 lines · 7264 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
28import "syscalls.nx"
29import "sketch_hll.nx"
30import "sketch_types.nx"
31
32// k in [3, 31]. k=3 is the minimum for non-trivial median; k=31
33// caps at 31 inner sketches (~8KB at lgK=8) for a generous budget.
34const NX_ROBUST_K_MIN: i64 = 3
35const NX_ROBUST_K_MAX: i64 = 31
36
37// Golden-ratio derivation constant for per-inner-sketch seed
38// diversification. Mirrors the TS reference (core-sketch/
39// robust_hll.ts).
40const NX_ROBUST_SEED_DERIVE: i64 = 0x9E3779B9
41
42// Handle stores k inner-HLL pointers as an array. Total handle
43// size: 32 + k*8 bytes (header + inner pointer array). We
44// over-allocate to NX_ROBUST_K_MAX so the size is fixed and the
45// caller doesn't need to track k for memory layout.
46
47struct RobustHll {
48 lg_k: i64,
49 k: i64,
50 seed_base: i64,
51 inner_count: i64,
52 // 32 bytes header above; inner pointers stored externally via
53 // a sys_mmap'd i64 array (avoids needing flexible struct fields).
54 inner_ptrs: *i64,
55 est_scratch: *i64, // bits-up: hoisted from nx_robust_hll_estimate
56 // sized NX_ROBUST_K_MAX once at alloc.
57}
58
59// === construction =================================================
60
61func nx_robust_hll_alloc(lg_k: i64, k: i64, seed_base: i64) -> *RobustHll {
62 if k < NX_ROBUST_K_MIN { return 0 as *RobustHll }
63 if k > NX_ROBUST_K_MAX { return 0 as *RobustHll }
64 let raw: *u8 = sys_mmap(48)
65 let r: *RobustHll = raw as *RobustHll
66 r.lg_k = lg_k
67 r.k = k
68 r.seed_base = seed_base
69 r.inner_count = k
70 let inner_bytes: i64 = k * 8
71 let inner_raw: *u8 = sys_mmap(inner_bytes)
72 r.inner_ptrs = inner_raw as *i64
73 r.est_scratch = sys_mmap(NX_ROBUST_K_MAX * 8) as *i64
74 var i: i64 = 0
75 while i < k {
76 // Derive per-inner seed via XOR with golden-ratio multiple.
77 // Each inner HLL gets a distinct seed so register-clobber on
78 // one doesn't propagate to the others.
79 let mix: i64 = (i + 1) * NX_ROBUST_SEED_DERIVE
80 let seed_i: i64 = seed_base ^ mix
81 let h: *Hll = nx_hll_alloc(lg_k, seed_i)
82 if h == (0 as *Hll) { return 0 as *RobustHll }
83 r.inner_ptrs[i] = h as i64
84 i = i + 1
85 }
86 return r
87}
88
89// === add ===========================================================
90// Fan out to every inner sketch.
91
92func nx_robust_hll_add(r: *RobustHll, key: *u8, len: i64) -> i64 {
93 var i: i64 = 0
94 while i < r.k {
95 let h: *Hll = r.inner_ptrs[i] as *Hll
96 nx_hll_add(h, key, len)
97 i = i + 1
98 }
99 return 0
100}
101
102// === median helper ================================================
103//
104// Insertion sort over k i64 estimates (k <= 31, so n^2 is fine);
105// return the middle element. For even k, average the two middles
106// (loses a bit of integer precision but matches the standard
107// definition).
108
109func nx_median_i64(arr: *i64, n: i64) -> i64 {
110 // Simple in-place insertion sort.
111 var i: i64 = 1
112 while i < n {
113 let cur: i64 = arr[i]
114 var j: i64 = i - 1
115 var done: i64 = 0
116 while done == 0 {
117 if j < 0 { done = 1 }
118 if done == 0 {
119 let prev: i64 = arr[j]
120 if prev <= cur {
121 done = 1
122 }
123 if done == 0 {
124 arr[j + 1] = prev
125 j = j - 1
126 }
127 }
128 }
129 arr[j + 1] = cur
130 i = i + 1
131 }
132 let mid: i64 = n / 2
133 if (n & 1) == 1 {
134 return arr[mid]
135 }
136 return (arr[mid - 1] + arr[mid]) / 2
137}
138
139// === estimate =====================================================
140//
141// Collect every inner sketch's cardinality estimate, sort, return
142// the median.
143
144func nx_robust_hll_estimate(r: *RobustHll) -> i64 {
145 // Bits-up: scratch hoisted to struct (was per-query sys_mmap).
146 let ests: *i64 = r.est_scratch
147 var i: i64 = 0
148 while i < r.k {
149 let h: *Hll = r.inner_ptrs[i] as *Hll
150 ests[i] = nx_hll_estimate(h)
151 i = i + 1
152 }
153 return nx_median_i64(ests, r.k)
154}
155
156// === typed query =================================================
157//
158// Returns ApproxI64 with stddev_rel envelope SAME as inner HLL.
159// We don't tighten the bound (median of k normal samples has
160// asymptotic stderr ~ sigma * sqrt(pi/(2k)) -- ~0.94x for k=5)
161// because under ADVERSARIAL input the samples are non-normal and
162// the bound doesn't hold. Honest > optimistic.
163//
164// Critical difference from nx_hll_query: adv_safety field is
165// NX_ADV_ADVERSARIAL. Substrate refuses cross-domain substitution.
166
167func nx_robust_hll_query(r: *RobustHll) -> *ApproxI64 {
168 let est: i64 = nx_robust_hll_estimate(r)
169 let stddev_ppb: i64 = nx_hll_stddev_rel_ppb(r.lg_k)
170 return nx_approx_new(est, NX_ENV_REL_STDDEV, stddev_ppb,
171 682700000,
172 NX_MATURITY_REFERENCE_IMPL,
173 NX_ADV_ADVERSARIAL)
174}
175
176// === inner-estimate inspection (debug / per-sketch divergence) ====
177
178func nx_robust_hll_inner_estimate(r: *RobustHll, i: i64) -> i64 {
179 if i < 0 { return 0 }
180 if i >= r.k { return 0 }
181 let h: *Hll = r.inner_ptrs[i] as *Hll
182 return nx_hll_estimate(h)
183}
184
185// === manual register-poison (for adversarial-test setup) ==========
186//
187// Sets all registers of inner sketch `i` to a chosen rho value.
188// Simulates an attacker who has found a hash collision targeting
189// one specific seed. Used by the smoke gate's poison-injection
190// case to verify the median holds when one inner sketch is
191// destroyed.
192
193func nx_robust_hll_poison_inner(r: *RobustHll, i: i64, rho: i64) -> i64 {
194 if i < 0 { return 0 }
195 if i >= r.k { return 0 }
196 let h: *Hll = r.inner_ptrs[i] as *Hll
197 var j: i64 = 0
198 while j < h.m {
199 h.regs[j] = rho
200 j = j + 1
201 }
202 return 0
203}