code wiki / (root) / nx_sketch_robust_hll.nx

nx_sketch_robust_hll.nx

buildroot/runtime/nx_sketch_robust_hll.nx

7117 B207 linesdepth 6pulls 11 transitivereach 0 importersview sourcekind sketch/demotopic sketch
docsdependenciesstructsconstsfunctions

about

sketch_robust_hll.nx -- adversarial-safe HLL via median-of-k. Wraps k independent HyperLogLog sketches with derived seeds and reports the median cardinality estimate. Defeats simple adaptive adversaries that game a single HLL by crafting inputs to inflate one register: poisoning a single inner sketch can't move the median when k >= 3. Maturity: ReferenceImpl. Full Cohen-Kaplan-Mansour-Matias-Stemmer scheme ("Breaking the Quadratic Barrier", arXiv:2502.05723) uses cryptographic sketch-switching with a secret key; this median- of-k is the simpler partial defense that catches replay attacks and single-target adaptive queries without that machinery. AdversarialSafety = NX_ADV_ADVERSARIAL. Substrate refuses to allow an Honest-tagged Hll to substitute for this in compositions requiring adversarial robustness. CAPABILITY-STOMP POSITION (per doc 19): Apache DataSketches: NO adversarial variant. Redis / RedisBloom: NO adversarial variant. ClickHouse uniqHLL: NO adversarial variant. Druid: uses DS internally; NO adversarial variant. stream-lib (Java): NO adversarial variant. python-datasketch: NO adversarial variant. This is greenfield -- a primitive NO INCUMBENT SHIPS.

dependencies 3 imports · 0 importers

nx_syscalls.nx nx_sketch_hll.nx nx_sketch_types.nx nx_sketch_robust_hll.nx

imports: nx_syscalls.nxnx_sketch_hll.nxnx_sketch_types.nx

imported by: nobody (leaf or entry point)

structs

53struct RobustHll

consts

40const NX_ROBUST_K_MIN: i64 = 3
41const NX_ROBUST_K_MAX: i64 = 31
46const NX_ROBUST_SEED_DERIVE: i64 = 0x9E3779B9

functions

65func nx_robust_hll_alloc(lg_k: i64, k: i64, seed_base: i64) -> *RobustHll
95func nx_robust_hll_add(r: *RobustHll, key: *u8, len: i64) -> i64
calls 1: nx_hll_add
112func nx_median_i64(arr: *i64, n: i64) -> i64
147func nx_robust_hll_estimate(r: *RobustHll) -> i64
171func nx_robust_hll_query(r: *RobustHll) -> *ApproxI64
182func nx_robust_hll_inner_estimate(r: *RobustHll, i: i64) -> i64
calls 1: nx_hll_estimate
197func nx_robust_hll_poison_inner(r: *RobustHll, i: i64, rho: i64) -> i64