nx_sketch_robust_hll.nx
buildroot/runtime/nx_sketch_robust_hll.nx
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
imports: nx_syscalls.nxnx_sketch_hll.nxnx_sketch_types.nx
imported by: nobody (leaf or entry point)
structs
| 53 | struct RobustHll |
consts
| 40 | const NX_ROBUST_K_MIN: i64 = 3 |
| 41 | const NX_ROBUST_K_MAX: i64 = 31 |
| 46 | const NX_ROBUST_SEED_DERIVE: i64 = 0x9E3779B9 |
functions
| 65 | func nx_robust_hll_alloc(lg_k: i64, k: i64, seed_base: i64) -> *RobustHll |
| 95 | func nx_robust_hll_add(r: *RobustHll, key: *u8, len: i64) -> i64 calls 1: nx_hll_add |
| 112 | func nx_median_i64(arr: *i64, n: i64) -> i64 called by 1: nx_robust_hll_estimate |
| 147 | func nx_robust_hll_estimate(r: *RobustHll) -> i64 |
| 171 | func nx_robust_hll_query(r: *RobustHll) -> *ApproxI64 |
| 182 | func nx_robust_hll_inner_estimate(r: *RobustHll, i: i64) -> i64 calls 1: nx_hll_estimate |
| 197 | func nx_robust_hll_poison_inner(r: *RobustHll, i: i64, rho: i64) -> i64 |