Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Overview

In DNS TAPIR Edge, measures are taken to avoid the transmission of sensitive data from Edge to Core. We specifically want to avoid transmitting two things: i) IP addresses of end-users and ii) sets of queries that are known to stem from a small number of end-users. This document describes how we achieve this.

The Privacy-unfriendly Way

To understand how the DNS TAPIR does this, let's first study a privacy-unfriendly implementation. In such an implementation the data sent from Edge to Core could look something like the following:

{
    "measurement_interval": {
        "start": 2026-07-27 12:50:00+02:00,
        "end": 2026-07-27 12:55:00+02:00
    },
    "domains": [
        "example.com": {
            "a_count": 1000,
            "mx_count": 100,
            "other_rtype_count": 200,
            "nx_count": 0,
            "ok_count": 1300,
            "other_rcode_count": 0,
            "clients": [
                "192.0.2.1",
                "192.0.2.10",
                "192.0.2.100"
            ]
        },
        "example.org": {
            "a_count": 200,
            "mx_count": 20,
            "other_rtype_count": 40,
            "nx_count": 0,
            "ok_count": 260,
            "other_rcode_count": 0,
            "clients": [
                "192.0.2.10",
                "198.51.100.100"
            ]
        }
    ]
}

The data sent was collected during a 5-minute interval. Most of it is just counters, which do not harm the privacy of the end-users, and they can be aggregated over, say, the course of a day or a week if more long-term trends are being studied. Unfortunately, relying solely on counters for analysing DNS data is a bit meager. Therefore, this privacy-unfriendly example also transmits the IP-addresses of the end-users that asked the questions. While this allows for a detailed study of how individual end-users are behaving over time, it also violates their privacy and as such, it is NOT how DNS TAPIR does things.

A Naive "Solution"

A naive approach of mitigating the privacy violation might be to simply hash the IP addresses of the clients. That avoids transmitting the IP addresses, but it might still harm end-user privacy. Consider the following chunk of data:

{
    "measurement_interval": {
        "start": 2026-07-27 12:50:00+02:00,
        "end": 2026-07-27 12:55:00+02:00
    },
    "domains": [
        "gnesta.se": {
            # counters omitted for brevity
            "clients": [
                "123abc",
                "8d3e01"
            ]
        },
        "ssa.se": {
            # counters omitted for brevity
            "clients": [
                "123abc",
                "fa3957",
                "492041",
                "859a38"
            ]
        },
        "smogon.com": {
            # counters omitted for brevity
            "clients": [
                "123abc",
                "1930d8",
                "9c958a"
            ]
        },
        "aa.org": {
            # counters omitted for brevity
            "clients": [
                "123abc"
            ]
        }
    ]
}

No IP addresses are being transmitted, but we can still study end-user behavior with the same amount of detail. Unfortunately, being able to do so might still reveal sensitive information about individual end-users. From the data in the example above, one might infer that the end-user whose IP address hashes to 123abc is someone who lives in the small city of Gnesta, Sweden, is engaged in the Swedish amateur radio community via ssa.se and the Pokemon community via smogon.com and has problems with alcohol, as suggested by aa.org. Arguably, not a lot of people fit a description like that and in the DNS TAPIR project, we consider this a privacy violation as well.

A "Solution" that is Too Lossy

A data model that respects privacy might look like this:

{
    "measurement_interval": {
        "start": 2026-07-27 12:50:00+02:00,
        "end": 2026-07-27 12:55:00+02:00
    },
    "domains": [
        "example.com": {
            "a_count": 1000,
            "mx_count": 100,
            "other_rtype_count": 200,
            "nx_count": 0,
            "ok_count": 1300,
            "other_rcode_count": 0,
            "client_count": 3
        },
        "example.org": {
            "a_count": 200,
            "mx_count": 20,
            "other_rtype_count": 40,
            "nx_count": 0,
            "ok_count": 260,
            "other_rcode_count": 0,
            "client_count": 2
        }
    ]
}

In this model, the "clients" field was replaced with a simple counter that keeps track of the number of unique end-users seen querying for a particular domain name during a particular interval. This approach comes with a major limitation: it does not allow the aggregation of data over multiple domain names or time intervals. For example, it not allow us to answer fundamental questions like "how many unique end-users were asking for example.com in the last week?" or "how many unique end-users that asked for example.com were also asking for example.org?". Moreover, if implemented naively, this model will still require the same amount of memory on an Edge node as the previous two examples. And if the number of end-users is high, that might be a lot.

A Compromise: HyperLogLog

To be able to aggregate end-user counts over time or across domains, DNS TAPIR employs a so-called HyperLogLog data structure. HyperLogLog is mainly used for its memory-efficiency but it also allows us to store less information about the end-users. Specifically, all we to store about an end-users IP is a few bits of its hash (typically, a MurmurHash) and a count of the starting number of zeroes from a given offset for a subset of all end-users hashed IPs.

The act of storing the IP addresses 192.0.2.1, 192.0.2.10, and 192.0.2.100 in a HyperLogLog structure is as follows:

We start by hashing 192.0.2.1 and let's say it hashes to 00011 for the purpose of this tutorial. From the hash value we extract two properties: the first p bits (p=2 in this case) and the number of leading zeroes of the remaining bits (plus one). The first p bits selects a "bucket" in which we store the value 2 since there is one leading zero, which we increment by one.

graph LR
    ip(192.0.2.1)
    hasher
    extract
    subgraph bucket00 [Bucket 00]
        contents00[2]
    end
    subgraph bucket01 [Bucket 01]
        contents01[0]
    end
    subgraph bucket10 [Bucket 10]
        contents10[0]
    end
    subgraph bucket11 [Bucket 11]
        contents11[0]
    end

    ip-->hasher
    hasher-->|00011|extract
    extract -.00.-bucket00
    extract --1+1-->contents00

Next, we hash 192.0.2.10 and get the result 10111. This selects bucket 10 and since there were no leading zeroes we store the value 1 in this bucket.

---
title: 
---
graph LR
    ip(192.0.2.10)
    hasher
    extract
    subgraph bucket00 [Bucket 00]
        contents00[2]
    end
    subgraph bucket01 [Bucket 01]
        contents01[0]
    end
    subgraph bucket10 [Bucket 10]
        contents10[1]
    end
    subgraph bucket11 [Bucket 11]
        contents11[0]
    end

    ip-->hasher
    hasher-->|10111|extract
    extract -.10.-bucket10
    extract --0+1-->contents10

Lastly, we hash 192.0.2.100 and get 00100. Again, this selects bucket 00 but this time we DO NOT update the value of the bucket. We only do that when the value we are trying to add is greater than what is already in the bucket.

---
title: 
---
graph LR
    ip(192.0.2.100)
    hasher
    extract
    subgraph bucket00 [Bucket 00]
        contents00[2]
    end
    subgraph bucket01 [Bucket 01]
        contents01[0]
    end
    subgraph bucket10 [Bucket 10]
        contents10[1]
    end
    subgraph bucket11 [Bucket 11]
        contents11[0]
    end

    ip-->hasher
    hasher-->|00100|extract
    extract -.00.-bucket00
    extract --0+1--xcontents00

After adding 192.0.2.1, 192.0.2.10 and 192.0.2.100 to the buckets we have the following structure, called a "sketch" of the set {192.0.2.1, 192.0.2.10, 192.0.2.100}:

---
title: 
---
graph LR
    subgraph bucket00 [Bucket 00]
        contents00[2]
    end
    subgraph bucket01 [Bucket 01]
        contents01[0]
    end
    subgraph bucket10 [Bucket 10]
        contents10[1]
    end
    subgraph bucket11 [Bucket 11]
        contents11[0]
    end

This is then typically encoded with some compact binary representation. For instance, we could encode the buckets as a single 32-bit integer. This is more compact than representing the set {192.0.2.1, 192.0.2.10, 192.0.2.100} as an array of 32-bit integers, where each integer represents an IP-address. Sketches can be merged and have elements added to them, just like the set they are representing, even though the sketch doesn't actually contain the set elements.

When we want to count the number of distinct elements in our sketch, we do this by taking the Harmonic Mean of the bucket values and multiplying that with a constant.

An example using HyperLogLog

Using the 32-bit integer encoding mentioned above, a model with HyperLogLog could look something like the following:

{
    "measurement_interval": {
        "start": 2026-07-27 12:50:00+02:00,
        "end": 2026-07-27 12:55:00+02:00
    },
    "domains": [
        "example.com": {
            "a_count": 1000,
            "mx_count": 100,
            "other_rtype_count": 200,
            "nx_count": 0,
            "ok_count": 1300,
            "other_rcode_count": 0,
            "clients_hll": 65538
        },
        "example.org": {
            "a_count": 200,
            "mx_count": 20,
            "other_rtype_count": 40,
            "nx_count": 0,
            "ok_count": 260,
            "other_rcode_count": 0,
            "clients_hll": 66560
            ]
        }
    ]
}

Although in reality, the binary encoding of the HyperLogLog is more complicated to make it even more space-efficient. But its data contents are no different. Also, in DNS TAPIR we use separate sketches for IPv4 and IPv6.

What Information Can a HyperLogLog Sketch Leak?

Consider the following state of the buckets: {"bucket 00": 0, "bucket 01": 4, "bucket 10": 1, "bucket 11": 0}. We can ask ourselves, is 192.0.2.1 in this sketch? If we know what hashing function the sketch uses (which we typically do), we might be able to answer the question. As in the previous example, 192.0.2.1 hashes to 00011. We calculate this hash, which tells us that we should inspect Bucket 00. Since Bucket 00 contains the value zero, we know for sure that 192.0.2.1 is not in this sketch. Otherwise, the bucket couldn't possibly hold a value of 0. That is, that end-user did not visit "example.org" within the time interval that the sketch represents.

We can also ask ourselves, is 192.0.2.10 in the sketch? Again, we hash it to 10111 and see that Bucket 10 holds a value that doesn't exclude the possibility that 192.0.2.10 is in the sketch (i.e. that it visited "example.org" in the given time interval). But we cannot say for sure, perhaps it was an end-user whose IP adress hashed to 10100? Or 10101? We cannot say for sure.

Lastly, we can ask ourselves, is 198.51.100.100 in the sketch? Let's imagine that that IP adress hashes to 01000. We check Bucket 10 and see that it value does not exclude this possibility. In fact, there is only one hash that could've caused Bucket 10 to hold the value 4, and that is the hash of 198.51.100.100. Therefore, in this specific case we can say for certain that the end-user whose IP address hashes to 01000 visited "example.org" within the given time frame.