sketch_robust_hll.nx
buildroot/runtime/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 · 2 importers
imports: syscalls.nxsketch_hll.nxsketch_types.nx
imported by: sketch_robust_hll_test.nxsketch_robust_hll_vs_hll_adv_bench.nx
structs
| 47 | struct RobustHll { |
consts
| 34 | const NX_ROBUST_K_MIN: i64 = 3 |
| 35 | const NX_ROBUST_K_MAX: i64 = 31 |
| 40 | const NX_ROBUST_SEED_DERIVE: i64 = 0x9E3779B9 |
functions
| 61 | func nx_robust_hll_alloc(lg_k: i64, k: i64, seed_base: i64) -> *RobustHll { |
| 92 | func nx_robust_hll_add(r: *RobustHll, key: *u8, len: i64) -> i64 { |
| 109 | func nx_median_i64(arr: *i64, n: i64) -> i64 {
called by 1: nx_robust_hll_estimate |
| 144 | func nx_robust_hll_estimate(r: *RobustHll) -> i64 { |
| 167 | func nx_robust_hll_query(r: *RobustHll) -> *ApproxI64 { |
| 178 | func nx_robust_hll_inner_estimate(r: *RobustHll, i: i64) -> i64 { |
| 193 | func nx_robust_hll_poison_inner(r: *RobustHll, i: i64, rho: i64) -> i64 { |