Weird how the readme talks about hash collisions, but not in the way I would expect. Two blocked domains with the same hash isn't a problem, they both need to be blocked.
Where hash collisions matter is false positives, e.g. if hash(google.com) = hash(adserver.com). There does appear to be a web dashboard and /unblock api so should be straightforward to resolve.
Yeah, I think they have it backwards. As you say, regardless of how many entries you have locally, the collision risk comes from false positive hash matches not from worrying if the positive hashes collide.
While the thing they probably want to check the collision math for is:
blockHashes.has(hash(domainNotInList))
As that's the risk you do the wrong action due to a hash collision. Importantly, the 2nd calculation is not going to be bounded by the size of your block list, it's going to be bounded by the number of domains overall.
The former question isn't really useful - you can have a 100 entry blocklist with 100 collisions and it still works the same as if it had 0 collision since the action on all 100 is the same. That's more a problem for generating unique IDs per hash whereas this is flipped around because it's about classification.
If we assume uniform sampling for both the blocklist (size N) and the domain to be visited (not in the block list), the collision probability we care about is Pcol(N+1).
The number of existing domains does not matter, only the size of the block list.
Of course when we consider all 401 million domains there will be many more collisions, but in each case we only care about a collision in N+1
> Two blocked domains with the same hash isn't a problem, they both need to be blocked.
This is a problem if the second one is actually a major useful domain. If HN and adserver have the same hash, you have a problem. This could be described as a false positive for HN.
> Where hash collisions matter is false positives, e.g. if hash(google.com) = hash(adserver.com)
This sounds like the same issue I describe above where you need to use Google but block adserver. Otherwise it's only a problem if you implemented allow lists, right? This is when you explicitly allow Google and implicitly allow adserver along with it because of the hash collision.
If you're ever thinking about getting an ESP32-C3, do yourself a favor and get the variant that you can connect an external antenna to. The normal C3 has a built-in antenna that is extremely weak, making it useless for most things I was planning using it for.
And make sure to read the reviews as there are apparently fraudulent versions out there that don't include the 4MB flash chip. That said I took a gamble on a bunch of $2 C3 super minis, and they've had surprisingly adequate signal strength for indoor applications, even in the basement. (-60's dBm)
yes and its such a important detail to have in later ESP projects. Having the ability to add antennas onto ESP-32 is a blessing-in-disguise that helps with more complex projects at a range later on
I think it could fit even more domains using a Bloom Filter or similar probabilistic data structure. With a chance of false-positives of course. But that's a trade-off the project already makes.
I'm a bit of a paranoid freak that likes lists, so I've got a PiHole that has a total list of 14-16M blocked domains.
Great idea, and good for casual blocking, but I'm almost moving to an "allow list" mindset. This solution would probably work better for that, I wonder if the good parts of the internet would fit into an 140k list.
I've aggregated the lists into four tiers: Base, Recommended, Aggressive, and Paranoid. And I've got two sets of these, one that includes Newly Registered Domains (Full directory), and one that doesn't include NRDs (NoNRD directory, because NRDs are ... heavy: Paranoid list with NRDs: 9.1 million records, without NRDs: 3.7 million records).
Aggregation of lists under the topic that matches the file name. Fake News list needs to be updated as it contains a _way_ overbroad list that I need to remove from the aggregation.
Depends on the user but not everyone is visiting new websites everyday
Even for those that are, the number of domain-IP mappings needed will be relatively small
Definitely under 140,000
Most DNS data I use is "static", it rarely changes. As such most times I don't have to make DNS queries. I store the domain-IP mappings in proxy memory; this is faster than DNS
Just make a captive portal that shows up on your screen for new domains where you can just click "add to allow" or "allow this once" or "add to deny". That way you build the dataset, like most of these tools its annoying in the beginning while you generate the dataset, but after a while its only a few pages a week.
This is all a guesstimate, but my gut feel is that a considerable part of the HN population doesn't even read the linked content, only the comment section here.
With github being the exception, I use comments to see if the article is AI. If it is, I prefer the condensed opinions in the comments. Not to say it can't be interesting I just don't want to waste time reading overly verbose generated text.
I really like this conceptually. However, multiple elements feel like slop and that’s throwing warning signs to me. The Claude readme file and the tiktok-ish fast cut youtube video felt like Vince the Sham-wow guy put them together. Ironically it feels like the product of the problem we’re trying to avoid.
>"The trick everyone misses: you don't need to keep the blocklist in RAM.
Store the domains as sorted 40-bit hashes in flash and binary-search them.
140,000+ domains fit in ~0.7 MB of flash..."
Brilliant! (Although, what about potential hash collisions with domain names that shouldn't be blocked? Those are probably few and far between, so the utility of the block overall far outweighs any few false positives that might arise -- so I reiterate my claim of "brilliant"!)
Also (if you're a compression nerd like I am), it may be possible to analyze this table of 40-bit hashes further to find the longest binary substring that repeats the most across all of them (or binary substrings that just repeat a whole lot), and design a Huffman-like (or other tree or tree-like) data structure around those, and possibly compress the data further...
Of course, then the simplicity and elegance of the Binary Search might be lost, but it might be an interesting optimization exercise to know just how far that data could be compressed... "Hey Claude, try to optimize the compression of this data using alternative compression data structures, and report back to me!" (Or something like that! You know, get the AI coding agents to try different things -- or attempt to code it on your own (always better for understanding!), etc., etc.!)
The biggest benefit of my local dns server is latency.
On wired internet, my dns is <1ms from my PC.
Upstream dns for me is pretty quick. Google and cloudflare dns are ~5ms from me.
But WiFi latency alone is ~8ms most of the time in my experience. On my fiber internet, pinging a dns server in some random upstream server miles away is lower latency than WiFi 10 feet away. But the real issue on WiFi is any packet loss at all adding 50-100ms to that at random depending on interference.
With DNS you are paying this latency cost all the time on nearly every request.
But a remote resolver, such as the ones on the list, is not used to determine whether an item is contained in a set (0.0.0.0) but rather to retrieve the current IP of that domain.
The way Pi-Hole is used is to first determine whether a DNS should be blocked and only if it's not in that set, forward it to a remote resolver.
I'd think the local resolver should be at least an order of magnitude less than the remote to justify it.
pinhole is great but if the device fails your network is down. I swapped to nextdns because of that. maybe support of multiple devices would fix it - now that is this cheap it would not matter
.
The simple answer is have 2. If the cost per unit is low enough than deploying 2 PiHoles is trivial.
The developers could make users' lives easier by implementing a clustering option that syncs the 2 out of the box. For static deployments, where you don't change the config too often, it's still decent as it is.
I did the same (until my RPi zero stopped working). Both the devices share same vertical IP address and if one ever went down, the other would take over without any delay.
I have a weird opinion: I believe adblocking must become a basic human right. Conversely Google trying to deny ublock origin and other extensions, should be fined many billions of euros as punishment. Then be disbanded if unable to pay. That money also should directly go back to The People, since they suffered from this evil malpractice of Google and others. You can see that currently the opposite is happening e. g. AI slop companies pushing ads down to people. That's why we must make adblocking a basic human right - free access to information at all times.
It may sound strange right now, but people in the future will ask why we did not push back against these evil leeching companies before. Those fines are no longer enough nor sufficient - CEOs that break human rights need to go to jail for mandatory 5 years minimum, without any way to weasel out their way via money. Right now money is a way to get out - that system is broken. Anyone wondered how Epstein got so much money in the first place? Hint: he did not build it up by himself only.
Weird how the readme talks about hash collisions, but not in the way I would expect. Two blocked domains with the same hash isn't a problem, they both need to be blocked.
Where hash collisions matter is false positives, e.g. if hash(google.com) = hash(adserver.com). There does appear to be a web dashboard and /unblock api so should be straightforward to resolve.
AI wrote the readme so it's unsurprising
Yeah, I think they have it backwards. As you say, regardless of how many entries you have locally, the collision risk comes from false positive hash matches not from worrying if the positive hashes collide.
I think they have it right.
If you have N entries where N >> 1, the probability of an arbitrary value colliding with the existing ones is Pcol(N+1) which is approx Pcol(N).
The math is correct, but it's the math for the question:
While the thing they probably want to check the collision math for is: As that's the risk you do the wrong action due to a hash collision. Importantly, the 2nd calculation is not going to be bounded by the size of your block list, it's going to be bounded by the number of domains overall.The former question isn't really useful - you can have a 100 entry blocklist with 100 collisions and it still works the same as if it had 0 collision since the action on all 100 is the same. That's more a problem for generating unique IDs per hash whereas this is flipped around because it's about classification.
No, it is for the right (second) question.
If we assume uniform sampling for both the blocklist (size N) and the domain to be visited (not in the block list), the collision probability we care about is Pcol(N+1).
The number of existing domains does not matter, only the size of the block list.
Of course when we consider all 401 million domains there will be many more collisions, but in each case we only care about a collision in N+1
> Two blocked domains with the same hash isn't a problem, they both need to be blocked.
This is a problem if the second one is actually a major useful domain. If HN and adserver have the same hash, you have a problem. This could be described as a false positive for HN.
> Where hash collisions matter is false positives, e.g. if hash(google.com) = hash(adserver.com)
This sounds like the same issue I describe above where you need to use Google but block adserver. Otherwise it's only a problem if you implemented allow lists, right? This is when you explicitly allow Google and implicitly allow adserver along with it because of the hash collision.
If you're ever thinking about getting an ESP32-C3, do yourself a favor and get the variant that you can connect an external antenna to. The normal C3 has a built-in antenna that is extremely weak, making it useless for most things I was planning using it for.
And make sure to read the reviews as there are apparently fraudulent versions out there that don't include the 4MB flash chip. That said I took a gamble on a bunch of $2 C3 super minis, and they've had surprisingly adequate signal strength for indoor applications, even in the basement. (-60's dBm)
You can find instructions for making and soldering on a small antenna to the common "mini" dev board that reportedly helps quite a bit
yes and its such a important detail to have in later ESP projects. Having the ability to add antennas onto ESP-32 is a blessing-in-disguise that helps with more complex projects at a range later on
You mean chip antenna (one that looks like a big SMD resistor)? Yes, they're garbage. But this is orthogonal to the chip itself.
Also, PCB antennas are reasonably good for most indoor situations.
I think it could fit even more domains using a Bloom Filter or similar probabilistic data structure. With a chance of false-positives of course. But that's a trade-off the project already makes.
I'm a bit of a paranoid freak that likes lists, so I've got a PiHole that has a total list of 14-16M blocked domains.
Great idea, and good for casual blocking, but I'm almost moving to an "allow list" mindset. This solution would probably work better for that, I wonder if the good parts of the internet would fit into an 140k list.
Do you host your lists somewhere you can share?
I'm currently (very slowly, in the small gaps between 'life') setting up a site the host the lists and also explains them and their usage.
Since it's not ready, it'll be best if I point you to the sources I've aggregated from:
https://firebog.net/
https://github.com/hagezi/dns-blocklists
https://github.com/StevenBlack/hosts
https://github.com/jerryn70/GoodbyeAds
Link to my in-progress list file hosting: https://lists.uninvitedactivity.com/DNS/
00_Tiers directory:
I've aggregated the lists into four tiers: Base, Recommended, Aggressive, and Paranoid. And I've got two sets of these, one that includes Newly Registered Domains (Full directory), and one that doesn't include NRDs (NoNRD directory, because NRDs are ... heavy: Paranoid list with NRDs: 9.1 million records, without NRDs: 3.7 million records).
11_Allow directory:
A bunch of allow lists sourced from: https://discourse.pi-hole.net/t/commonly-whitelisted-domains.... I also use this list for an Allow list: https://github.com/anudeepND/whitelist
21_SpecificTopics directory:
Aggregation of lists under the topic that matches the file name. Fake News list needs to be updated as it contains a _way_ overbroad list that I need to remove from the aggregation.
Tbh, for the ESP32-C3’s perf, an allow list would likely save RAM and CPU time.
Whitelist/allowlist is easier, e.g., it's smaller
Depends on the user but not everyone is visiting new websites everyday
Even for those that are, the number of domain-IP mappings needed will be relatively small
Definitely under 140,000
Most DNS data I use is "static", it rarely changes. As such most times I don't have to make DNS queries. I store the domain-IP mappings in proxy memory; this is faster than DNS
No "blocklist" needed
Just make a captive portal that shows up on your screen for new domains where you can just click "add to allow" or "allow this once" or "add to deny". That way you build the dataset, like most of these tools its annoying in the beginning while you generate the dataset, but after a while its only a few pages a week.
I would think that a regular user of Hacker News would be visiting new websites every day (though it'd definitely still be below 140k)
This is all a guesstimate, but my gut feel is that a considerable part of the HN population doesn't even read the linked content, only the comment section here.
I sure hope that's not true. Maybe hit the comments section first?
With github being the exception, I use comments to see if the article is AI. If it is, I prefer the condensed opinions in the comments. Not to say it can't be interesting I just don't want to waste time reading overly verbose generated text.
Depends on the content, for all of these model release marketing sites, I for example only read the comments.
If i would estimate it, I only take a look at 1/4 of the links where i read the comments.
> The trick everyone misses:
Please just write the first sentence of your README yourself
The trick everyone misses: binary search of hashes can be done in log(log(n))
Apparently solving blocking extra domains due to hash collisions (reducing from 1 to 0) would be extra space "to solve a problem I don't have".
I dislike when LLMs talk to me like that. I hate it when humans do it, confidently spewing their overconfident llm assumptions to others
I actually thought this was one of the more communicative parts of the readme and quite liked their explanation.
Nice project and poc maybe, but I'm not seeing the practical application of this in a real world env, surely the latency is a deal breaker ?
I really like this conceptually. However, multiple elements feel like slop and that’s throwing warning signs to me. The Claude readme file and the tiktok-ish fast cut youtube video felt like Vince the Sham-wow guy put them together. Ironically it feels like the product of the problem we’re trying to avoid.
There's no point in using PlatformIO for ESP32 MCUs. The native ESP-IDF extension works much better.
I would only recommend using it instead of the standard Arduino Processing IDE.
I use arduino-cli exclusively, lighter than ESP-IDF and works completely standalone from the IDE.
>"The trick everyone misses: you don't need to keep the blocklist in RAM.
Store the domains as sorted 40-bit hashes in flash and binary-search them.
140,000+ domains fit in ~0.7 MB of flash..."
Brilliant! (Although, what about potential hash collisions with domain names that shouldn't be blocked? Those are probably few and far between, so the utility of the block overall far outweighs any few false positives that might arise -- so I reiterate my claim of "brilliant"!)
Also (if you're a compression nerd like I am), it may be possible to analyze this table of 40-bit hashes further to find the longest binary substring that repeats the most across all of them (or binary substrings that just repeat a whole lot), and design a Huffman-like (or other tree or tree-like) data structure around those, and possibly compress the data further...
Of course, then the simplicity and elegance of the Binary Search might be lost, but it might be an interesting optimization exercise to know just how far that data could be compressed... "Hey Claude, try to optimize the compression of this data using alternative compression data structures, and report back to me!" (Or something like that! You know, get the AI coding agents to try different things -- or attempt to code it on your own (always better for understanding!), etc., etc.!)
Anyway, brilliant!
Cool idea, latency might be too high, wish the docs weren't all AI vomit.
The biggest benefit of my local dns server is latency. On wired internet, my dns is <1ms from my PC.
Upstream dns for me is pretty quick. Google and cloudflare dns are ~5ms from me. But WiFi latency alone is ~8ms most of the time in my experience. On my fiber internet, pinging a dns server in some random upstream server miles away is lower latency than WiFi 10 feet away. But the real issue on WiFi is any packet loss at all adding 50-100ms to that at random depending on interference.
With DNS you are paying this latency cost all the time on nearly every request.
> With DNS you are paying this latency cost all the time on nearly every request.
Surely not? macOS, Windows, and I think most of the big Linux distros, all cache DNS responses. Probably the web browser itself does too.
This will be slow for one user, let alone more than one
“The trick everyone misses”
10ms? Good grief that’s slow.
Still faster than using a remote resolver: https://www.dnsperf.com/
But a remote resolver, such as the ones on the list, is not used to determine whether an item is contained in a set (0.0.0.0) but rather to retrieve the current IP of that domain.
The way Pi-Hole is used is to first determine whether a DNS should be blocked and only if it's not in that set, forward it to a remote resolver. I'd think the local resolver should be at least an order of magnitude less than the remote to justify it.
pinhole is great but if the device fails your network is down. I swapped to nextdns because of that. maybe support of multiple devices would fix it - now that is this cheap it would not matter .
You can have a 2 adguard home + adguard-sync. Works smoothly.
But what if both fail? :)
The simple answer is have 2. If the cost per unit is low enough than deploying 2 PiHoles is trivial.
The developers could make users' lives easier by implementing a clustering option that syncs the 2 out of the box. For static deployments, where you don't change the config too often, it's still decent as it is.
I did the same (until my RPi zero stopped working). Both the devices share same vertical IP address and if one ever went down, the other would take over without any delay.
"They were too preoccupied with whether they could, they never stopped to think whether they should"
Jokes aside, very impressive that it works!
i dont get pihole. just use a proper dns? if you want local, just use unbound?
Pihole and unbound can work together. Pihole isn't a good DNS server, it's a good adblocking DNS server.
people like ease of use, UI, docs, and community.
after all, why use opnSense; just use suricata and $PROPER_X! why use TrueNAS; just use $DISTRO and ZFS!
it is easier to add adguard dns if you want ease of use
I have a weird opinion: I believe adblocking must become a basic human right. Conversely Google trying to deny ublock origin and other extensions, should be fined many billions of euros as punishment. Then be disbanded if unable to pay. That money also should directly go back to The People, since they suffered from this evil malpractice of Google and others. You can see that currently the opposite is happening e. g. AI slop companies pushing ads down to people. That's why we must make adblocking a basic human right - free access to information at all times.
It may sound strange right now, but people in the future will ask why we did not push back against these evil leeching companies before. Those fines are no longer enough nor sufficient - CEOs that break human rights need to go to jail for mandatory 5 years minimum, without any way to weasel out their way via money. Right now money is a way to get out - that system is broken. Anyone wondered how Epstein got so much money in the first place? Hint: he did not build it up by himself only.
Let’s not trivialize “human rights”, those are much more fundamental issues and this kind of discourse does not help achieve anything.
Wow, this is an atrocious name for a project haha. Cool though.