sketch_cuckoo.nx

sketch_cuckoo.nx -- Cuckoo Filter (Fan et al. 2014). Approximate-set-membership primitive with DELETION support -- the headline capability Bloom filters lack. Each item gets one of two candidate buckets (the second derived from the fingerprint via XOR), so lookups check both buckets and inserts fall back to relocation when both are full. Versus Bloom (runtime/bloom.nx already shipped): Bloom: k bit-sets per insert, no delete, false-positive rate ~ (1 - e^(-kn/m))^k Cuckoo: fingerprint slots per bucket, supports delete, false- positive rate ~ 2 * bucket_size / (2^fp_bits) At the same memory + FP rate, Cuckoo is typically more space-efficient than Bloom AND supports deletes. Parameters: n_buckets: power of 2 (for XOR-friendly indexing). Total capacity is roughly 95% * n_buckets * 4. bucket_size: we use 4 (canonical; trade-off well-studied). fingerprint: 8 bits (1 byte per slot). False-positive rate ~ 2*4/256 = 3.1% at high load. 16-bit fingerprints (0.024% FP) are queued for v2. LOSSLESS-LANGUAGE DISCIPLINE (doc 20): Membership query returns ApproxI64 with envelope_kind = NX_ENV_ABS, param_a = 0 (false positives but NEVER false negatives for items truly inserted), conf_ppb = 1e9 - expected_fpr_ppb. Substrate's typed envelope precisely declares "absent" is exact and "present" is bounded-uncertain.