code wiki / (root) / sketch_robust_hll.nx

sketch_robust_hll.nx

buildroot/runtime/sketch_robust_hll.nx

7264 B203 linesdepth 6pulls 11 transitivereach 2 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 · 2 importers

syscalls.nx sketch_hll.nx sketch_types.nx sketch_robust_hll.nx sketch_robust_hll_test.nx sketch_robust_hll_vs_hll_adv_bench

imports: syscalls.nxsketch_hll.nxsketch_types.nx

imported by: sketch_robust_hll_test.nxsketch_robust_hll_vs_hll_adv_bench.nx

structs

47struct RobustHll {

consts

34const NX_ROBUST_K_MIN: i64 = 3
35const NX_ROBUST_K_MAX: i64 = 31
40const NX_ROBUST_SEED_DERIVE: i64 = 0x9E3779B9

functions

61func nx_robust_hll_alloc(lg_k: i64, k: i64, seed_base: i64) -> *RobustHll {
called by 2: mainmain calls 1: nx_hll_alloc
92func nx_robust_hll_add(r: *RobustHll, key: *u8, len: i64) -> i64 {
called by 2: mainmain calls 1: nx_hll_add
109func nx_median_i64(arr: *i64, n: i64) -> i64 {
144func nx_robust_hll_estimate(r: *RobustHll) -> i64 {
167func nx_robust_hll_query(r: *RobustHll) -> *ApproxI64 {
178func nx_robust_hll_inner_estimate(r: *RobustHll, i: i64) -> i64 {
called by 2: mainmain calls 1: nx_hll_estimate
193func nx_robust_hll_poison_inner(r: *RobustHll, i: i64, rho: i64) -> i64 {
called by 2: mainmain