Case Study 2.2: How does Google Chrome protect 3 billion users using Bloom Filters?

How does Google Chrome protect 3 billion users from malicious sites?

This is the Bloom filter from the previous page, deployed to 3 billion devices. Google's Safe Browsing service flags over 100 million malicious URLs, ranging from phishing to malware. The mission: shield every Chrome user from these threats. But two hurdles stand in the way: Scale and Privacy.

The Challenges: Scale and Privacy

1. Scale: Storing 100 million URLs, each averaging 80 characters, demands roughly 8 GB of storage. Expecting every device to download this blacklist is impractical.

2. Privacy: Constantly pinging Google's servers with every URL you visit raises privacy red flags. Nobody wants a tech giant tracking their every click.

3. Infrastructure: With 3 billion users online, querying Google's servers for each URL would flood the system with trillions of requests daily, straining bandwidth and risking server overload. A single point of failure isn't an option.

The Solution: The 125 MB Local Filter

Chrome opts for a probabilistic method. Instead of the full list, it downloads a compressed Bloom filter of URL hashes.

The compression advantage

• Raw list: 100M URLs × 80 bytes = 8,000 MB (8 GB)

• Bloom filter: 100M items × 10 bits/item = 1,000M bits = 125 MB (~1% false-positive rate)

• Efficiency: the Bloom filter is about 64x smaller than the raw list

Technical Workflow: The Privacy-Preserving Check

The Bloom filter enables Chrome to assess "is this site bad?" directly on your device.

1. Local Check: Chrome hashes the URL and checks against its local 125 MB Bloom filter.

2. Confidential Path: If the filter returns "Not in set," the URL is safe. Chrome doesn't inform Google, keeping your browsing history private.

3. "K-Anonymity" Trick: If the filter indicates "Maybe in set" (potential threat), Chrome sends only a prefix (e.g., first 32 bits) of the hash. Google responds with all malicious hashes sharing that prefix, and Chrome completes the check locally.

Python Implementation: Malicious URL Filter

import math
import mmh3 # MurmurHash3
from bitarray import bitarray

class SafeBrowsingFilter:
    def __init__(self, expected_items, fpr):
        # bits_per_item = -1.44 * log2(fpr); ~10 bits at 1% FPR
        self.size = int(expected_items * -1.44 * math.log2(fpr))
        self.bit_array = bitarray(self.size)
        self.bit_array.setall(0)
        self.hash_count = 7  # ~optimal for 1%

    def add_malicious_url(self, url):
        for seed in range(self.hash_count):
            index = mmh3.hash(url, seed) % self.size
            self.bit_array[index] = 1

    def check_url(self, url):
        for seed in range(self.hash_count):
            index = mmh3.hash(url, seed) % self.size
            if self.bit_array[index] == 0:
                return "SAFE" # 100% Guaranteed 
        return "MAYBE_THREAT" # Perform prefix-check validation

# Setup filter for 1M malicious URLs
sbf = SafeBrowsingFilter(1_000_000, 0.01)
sbf.add_malicious_url("phish-bank.ru/login.html")

# Instant local lookup
print(f"'google.com': {sbf.check_url('google.com')}")  # SAFE
print(f"'phish-bank.ru/login.html': {sbf.check_url('phish-bank.ru/login.html')}")  # MAYBE_THREAT

Comparison: Why not just use a Database?

Takeaway: A ~125 MB Bloom filter on every device answers "safe" locally for almost all browsing; only the rare "maybe" sends a hash prefix to Google, so 100M URLs and 3B users cost little bandwidth and leak almost nothing.