Binary Fuse Filter JavaScript Specification

Version: 1.0 Date: 2025-12-04

Needs verification

This spec describes a bincode wire format and xorf 0.11. The server now emits a MessagePack array and uses xorf 0.13. Research is tracked in #47.

Overview
Data Structures
Serialization Format
Hash Functions
Lookup Algorithm
Implementation Requirements
Test Vectors
Performance Characteristics
References

Overview

This specification describes a JavaScript implementation of the binary fuse filter (16-bit variant) that is byte-for-byte compatible with the Rust xorf crate (v0.11) and uses the same serialization format (bincode).

Purpose

Binary fuse filters provide fast, space-efficient probabilistic set membership testing with:

No false negatives: If filter says "not present", item is definitely absent
Low false positive rate: ~0.0015% (1 in 65,536) for 16-bit fingerprints
Deterministic: Same query always returns same result
Immutable: Filter cannot be modified after construction

Use Cases

Privacy-preserving blob discovery in BLOSSOM servers
Client-side validation without server roundtrips
Offline filter caching and querying
Verification of server-provided filter results

Data Structures

BinaryFuse16 Filter

A BinaryFuse16 filter consists of two main components:

javascript

{
  // Descriptor: Configuration parameters
  seed: BigInt,                 // u64: Random seed for hash functions
  segmentLength: Number,        // u32: Length of each segment
  segmentLengthMask: Number,    // u32: Mask for segment operations
  segmentCountLength: Number,   // u32: Number of segments

  // Fingerprints: Array of 16-bit values
  fingerprints: Array<Number>   // [u16]: Array of 16-bit fingerprints
}

Field Descriptions

Field	Type	Description
`seed`	u64 (BigInt)	Random seed used in hash mixing
`segmentLength`	u32	Length of each segment in the filter
`segmentLengthMask`	u32	Bitmask for segment length operations
`segmentCountLength`	u32	Total number of segments
`fingerprints`	[u16]	Array of 16-bit fingerprint values

Input Hash Format

SHA-256 hashes are converted to 64-bit unsigned integers:

javascript

// Input: "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855"
// Take first 16 hex chars: "e3b0c44298fc1c14"
// Parse as big-endian u64: 0xe3b0c44298fc1c14

Serialization Format

The filter is serialized using the bincode format (matching Rust's bincode v1.3) and then base64-encoded for transport.

Binary Layout

Offset  | Size | Type | Field
--------|------|------|----------------------
0x00    | 8    | u64  | seed (little-endian)
0x08    | 4    | u32  | segment_length (LE)
0x0C    | 4    | u32  | segment_length_mask (LE)
0x10    | 4    | u32  | segment_count_length (LE)
0x14    | 8    | u64  | fingerprints.length (LE)
0x1C    | N*2  | [u16]| fingerprints data (LE)

Total Size: 28 + (fingerprints.length × 2) bytes

Example

For a filter with 2 input hashes:

Hex dump:
c1 5c 02 89 ec 2d 0a 91  04 00 00 00 03 00 00 00
04 00 00 00 0c 00 00 00  00 00 00 00 10 7d 87 c4
39 a2 ab a1 20 8a bc a4  8a 5b 67 fb 97 8d b4 2b
85 f8 96 e1

Parsing:
- seed: 0x910a2dec89025cc1
- segment_length: 4
- segment_length_mask: 3
- segment_count_length: 4
- fingerprints.length: 12
- fingerprints: [0x7d10, 0xc487, 0xa239, ...]

Deserialization Code

javascript

function deserializeBinaryFuse16(base64Data) {
  // Step 1: Decode base64 to binary
  const binaryString = atob(base64Data);
  const bytes = new Uint8Array(binaryString.length);
  for (let i = 0; i < binaryString.length; i++) {
    bytes[i] = binaryString.charCodeAt(i);
  }

  // Step 2: Parse binary structure
  const view = new DataView(bytes.buffer);

  // Descriptor fields (20 bytes)
  const seed = view.getBigUint64(0, true);                // LE u64
  const segmentLength = view.getUint32(8, true);          // LE u32
  const segmentLengthMask = view.getUint32(12, true);     // LE u32
  const segmentCountLength = view.getUint32(16, true);    // LE u32

  // Fingerprints length prefix (8 bytes)
  const fingerprintsLength = Number(view.getBigUint64(20, true)); // LE u64

  // Fingerprints data (N * 2 bytes)
  const fingerprints = [];
  for (let i = 0; i < fingerprintsLength; i++) {
    const offset = 28 + i * 2;
    fingerprints.push(view.getUint16(offset, true));      // LE u16
  }

  return {
    seed,
    segmentLength,
    segmentLengthMask,
    segmentCountLength,
    fingerprints
  };
}

Hash Functions

1. MurmurHash3 Mix64 Finalization

Applies MurmurHash3's finalization mixing to create an avalanched hash.

javascript

function murmur3Mix64(k) {
  k = BigInt.asUintN(64, k);

  // Round 1
  k ^= k >> 33n;
  k = BigInt.asUintN(64, k * 0xff51afd7ed558ccdn);

  // Round 2
  k ^= k >> 33n;
  k = BigInt.asUintN(64, k * 0xc4ceb9fe1a85ec53n);

  // Round 3
  k ^= k >> 33n;

  return k;
}

Constants:

0xff51afd7ed558ccd: MurmurHash3 multiplier 1
0xc4ceb9fe1a85ec53: MurmurHash3 multiplier 2

Properties:

Input: u64
Output: u64
Avalanche effect: Single bit change affects ~32 output bits

2. Mix Function

Combines input key with seed and applies MurmurHash3 mixing.

javascript

function mix(key, seed) {
  // Add key and seed with 64-bit wrapping
  const sum = BigInt.asUintN(64, BigInt(key) + BigInt(seed));

  // Apply MurmurHash3 finalization
  return murmur3Mix64(sum);
}

Parameters:

key: u64 (BigInt) - Input key to hash
seed: u64 (BigInt) - Random seed from filter

Returns: u64 (BigInt) - Mixed hash value

3. Fingerprint Function

Extracts a fingerprint by XORing upper and lower 32-bit halves.

javascript

function fingerprint(hash) {
  return hash ^ (hash >> 32n);
}

Parameters:

hash: u64 (BigInt) - Input hash value

Returns: u64 (BigInt) - Fingerprint value (only lower 16 bits used)

Example:

javascript

hash = 0xe3b0c44298fc1c14n
upper32 = 0xe3b0c442n (shifted right 32)
lower32 = 0x98fc1c14n
result = 0x7b4cd856n (XOR of upper and lower)

4. Hash of Hash Function

Computes three positions in the fingerprint array.

javascript

function hashOfHash(hash, segmentLength, segmentLengthMask, segmentCountLength) {
  // Step 1: Compute base position using multiplication shift
  const product = hash * BigInt(segmentCountLength);
  const hi = product >> 64n;
  const h0 = Number(BigInt.asUintN(32, hi));

  // Step 2: Compute positions in segments 1 and 2
  let h1 = h0 + segmentLength;
  let h2 = h1 + segmentLength;

  // Step 3: Apply XOR perturbations
  h1 ^= Number((hash >> 18n) & BigInt(segmentLengthMask));
  h2 ^= Number(hash & BigInt(segmentLengthMask));

  return [h0, h1, h2];
}

Parameters:

hash: u64 (BigInt) - Mixed hash value
segmentLength: u32 - Length of each segment
segmentLengthMask: u32 - Mask for segment operations
segmentCountLength: u32 - Number of segments

Returns: [u32, u32, u32] - Three positions in fingerprint array

Algorithm Details:

h0: Base position in first segment (uses multiplication shift)
h1: Position in second segment (base + segment_length + XOR perturbation)
h2: Position in third segment (h1 + segment_length + XOR perturbation)

Lookup Algorithm

Overview

The binary fuse filter lookup uses XOR logic across three fingerprint positions.

Algorithm

javascript

function testBinaryFuse16(filter, hashU64) {
  const { seed, segmentLength, segmentLengthMask,
          segmentCountLength, fingerprints } = filter;

  // Step 1: Mix the input key with seed
  const hash = mix(hashU64, seed);

  // Step 2: Compute query fingerprint (16-bit)
  let f = Number(BigInt.asUintN(16, fingerprint(hash)));

  // Step 3: Compute three hash positions
  const [h0, h1, h2] = hashOfHash(
    hash,
    segmentLength,
    segmentLengthMask,
    segmentCountLength
  );

  // Step 4: XOR fingerprints at all three positions
  f ^= fingerprints[h0];
  f ^= fingerprints[h1];
  f ^= fingerprints[h2];

  // Step 5: Check if result is zero (match)
  return (f & 0xFFFF) === 0;
}

Why XOR Logic?

Binary fuse filters are constructed such that for each key in the set:

fingerprint(key) = FP[h0] ⊕ FP[h1] ⊕ FP[h2]

During lookup, we compute:

f = fingerprint(query) ⊕ FP[h0] ⊕ FP[h1] ⊕ FP[h2]

If query == key, then:

f = fingerprint(key) ⊕ FP[h0] ⊕ FP[h1] ⊕ FP[h2]
f = fingerprint(key) ⊕ fingerprint(key)  [by construction]
f = 0

SHA-256 to u64 Conversion

Before testing, SHA-256 hex strings must be converted to u64:

javascript

function sha256ToU64(hex) {
  const bytes = [];

  // Parse first 16 hex characters (8 bytes)
  for (let i = 0; i < 16; i += 2) {
    bytes.push(parseInt(hex.substr(i, 2), 16));
  }

  // Convert to big-endian u64
  let result = 0n;
  for (let i = 0; i < 8; i++) {
    result = (result << 8n) | BigInt(bytes[i]);
  }

  return result;
}

Example:

javascript

sha256ToU64("e3b0c44298fc1c14...")
// Returns: 0xe3b0c44298fc1c14n

Implementation Requirements

JavaScript Environment

BigInt support: Required for 64-bit integer operations
DataView: Required for binary parsing
Base64 decoding: atob() or equivalent
Browser compatibility: Chrome 67+, Firefox 68+, Safari 14+, Node.js 10.4+

Numeric Precision

All hash operations must use BigInt to avoid precision loss:

javascript

// ✅ CORRECT: Using BigInt
const hash = mix(0xe3b0c44298fc1c14n, seed);

// ❌ WRONG: Using Number (loses precision above 2^53)
const hash = mix(0xe3b0c44298fc1c14, seed);

Bit Masking

Use BigInt.asUintN(64, value) to ensure 64-bit wrapping:

javascript

// ✅ CORRECT: Wraps to 64 bits
k = BigInt.asUintN(64, k * 0xff51afd7ed558ccdn);

// ❌ WRONG: May overflow BigInt range
k = k * 0xff51afd7ed558ccdn;

Endianness

All multi-byte values are little-endian:

javascript

// ✅ CORRECT: Specifying little-endian
const seed = view.getBigUint64(0, true);  // true = LE

// ❌ WRONG: Using big-endian (default)
const seed = view.getBigUint64(0);

Test Vectors

Test Case 1: Two-Element Filter

Input Hashes:

e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855
5891b5b522d5df086d0ff0b110fbd9d21bb4fc7163af34d08286a2e846f6be03

Input as u64:

0xe3b0c44298fc1c14
0x5891b5b522d5df08

Serialized Filter (Base64):

wVwCiewtCpEEAAAAAwAAAAQAAAAMAAAAAAAAABB9h8Q5oquhIIq8pIpbZ/uXjbQrhfiW4Q==

Deserialized Structure:

javascript

{
  seed: 0x910a2dec89025cc1n,
  segmentLength: 4,
  segmentLengthMask: 3,
  segmentCountLength: 4,
  fingerprints: [
    0x7d10, 0xc487, 0xa239, 0xa1ab, 0x8a20, 0xa4bc,
    0x5b8a, 0xfb67, 0x8d97, 0x2bb4, 0xf885, 0xe196
  ]
}

Test Queries:

Hash (first 16 chars)	u64 Value	Expected Result
`e3b0c44298fc1c14`	`0xe3b0c44298fc1c14`	✅ true (in set)
`5891b5b522d5df08`	`0x5891b5b522d5df08`	✅ true (in set)
`0000000000000000`	`0x0000000000000000`	❌ false (not in set)
`ffffffffffffffff`	`0xffffffffffffffff`	❌ false (not in set)

Test Case 2: Hash Function Verification

Input:

javascript

key = 0xe3b0c44298fc1c14n
seed = 0x910a2dec89025cc1n

Expected Intermediate Values:

javascript

sum = BigInt.asUintN(64, key + seed)
    = 0x74bbd8ef229ad8d5n

hash = murmur3Mix64(sum)
     = 0xd84a6fb68c8a3526n

fp = fingerprint(hash)
   = 0x544d2d1cn (64-bit result)
   = 0x2d1c (16-bit truncation)

Performance Characteristics

Time Complexity

Operation	Complexity	Typical Time
Deserialization	O(n)	1-5ms for 10K items
Single lookup	O(1)	100-500ns
Batch lookup	O(k)	k × 100-500ns

where:

n = number of fingerprints
k = number of lookups

Space Complexity

Component	Size
Descriptor	20 bytes (fixed)
Length prefix	8 bytes (fixed)
Fingerprints	n × 2 bytes
Total	28 + 2n bytes

Example: Filter for 1 million items:

Fingerprints: ~1,500,000 (1.5× input size)
Total size: 28 + 3,000,000 = ~2.86 MB
Bits per element: ~23 bits (vs. ~9 bits theoretical minimum)

False Positive Rate

Binary-fuse-16: ~0.0015% (1 in 65,536)
Calculation: 1 / 2^16 = 0.0000152587890625

References

Source Code

xorf Rust Crate: https://github.com/ayazhafiz/xorf
- src/bfuse16.rs: BinaryFuse16 struct definition
- src/murmur3.rs: MurmurHash3 mix64 implementation
- src/prelude/mod.rs: mix() and fingerprint() functions
- src/prelude/bfuse.rs: hash_of_hash() and lookup algorithm
Almond Implementation:
- src/handlers/filter.rs: Server-side filter endpoint
- src/filter-test.html: JavaScript client implementation
- src/bin/inspect_filter.rs: Serialization inspection tool

Academic Papers

Binary Fuse Filters: Thomas Mueller Graf and Daniel Lemire
- Paper: "Binary Fuse Filters: Fast and Smaller Than Xor Filters" (2021)
- arXiv: https://arxiv.org/abs/2201.01174
Xor Filters: Thomas Mueller Graf and Daniel Lemire
- Paper: "Xor Filters: Faster and Smaller Than Bloom Filters" (2019)
- arXiv: https://arxiv.org/abs/1912.08258

Standards

BUD-11: Blossom Filter List (BLOSSOM specification)
Bincode: Rust binary serialization format (v1.3)
MurmurHash3: https://github.com/aappleby/smhasher

Appendix A: Complete Implementation

See src/filter-test.html (lines 183-291) for the complete, production-ready JavaScript implementation.

Appendix B: Testing

Open test-filter.html in a browser or run cargo run --bin inspect_filter to verify implementation correctness.

Document Version: 1.0 Last Updated: 2025-12-04 Maintainer: Almond Project License: MIT

Binary Fuse Filter JavaScript Specification ​

Table of Contents ​

Overview ​

Purpose ​

Use Cases ​

Data Structures ​

BinaryFuse16 Filter ​

Field Descriptions ​

Input Hash Format ​

Serialization Format ​

Binary Layout ​

Example ​

Deserialization Code ​

Hash Functions ​

1. MurmurHash3 Mix64 Finalization ​

2. Mix Function ​

3. Fingerprint Function ​

4. Hash of Hash Function ​

Lookup Algorithm ​

Overview ​

Algorithm ​

Why XOR Logic? ​

SHA-256 to u64 Conversion ​

Implementation Requirements ​

JavaScript Environment ​

Numeric Precision ​

Bit Masking ​

Endianness ​

Test Vectors ​

Test Case 1: Two-Element Filter ​

Test Case 2: Hash Function Verification ​

Performance Characteristics ​

Time Complexity ​

Space Complexity ​

False Positive Rate ​

References ​

Source Code ​

Academic Papers ​

Standards ​

Appendix A: Complete Implementation ​

Appendix B: Testing ​

Binary Fuse Filter JavaScript Specification

Table of Contents

Overview

Purpose

Use Cases

Data Structures

BinaryFuse16 Filter

Field Descriptions

Input Hash Format

Serialization Format

Binary Layout

Example

Deserialization Code

Hash Functions

1. MurmurHash3 Mix64 Finalization

2. Mix Function

3. Fingerprint Function

4. Hash of Hash Function

Lookup Algorithm

Overview

Algorithm

Why XOR Logic?

SHA-256 to u64 Conversion

Implementation Requirements

JavaScript Environment

Numeric Precision

Bit Masking

Endianness

Test Vectors

Test Case 1: Two-Element Filter

Test Case 2: Hash Function Verification

Performance Characteristics

Time Complexity

Space Complexity

False Positive Rate

References

Source Code

Academic Papers

Standards

Appendix A: Complete Implementation

Appendix B: Testing