Hacker News Reader

Comment by muti | Hacker News Reader

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.

View on HN

AI wrote the readme so it's unsurprising

For all we know an AI bot wrote the above comment as well.

This is a worrying trend on HN. Nearly for all submissions, there is one unquantified, unproven comment at the top saying it's AI, with just emotion and no proof. This is the new witch hunt, or karma farming without having to contribute anything positive to the discussion.

> Nearly for all submissions, there is one unquantified, unproven comment at the top saying it's AI, with just emotion and no proof

nearly all of the commits in the repo are co-authored by claude

you could just go straight to the source instead of speculating. read the readme. it's obviously AI.

It is proven because Claude is listed as a contributor. Its not proof-less and completely emotion based

It is quite literally written by claude

https://github.com/M-Abozaid/esp32-c3-adblock/commits/main/R...

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).

Edit: Skip to 4gotunameagain's reply, this probably doesn't contain anything helpful to read.

The math is correct, but it's the math for the question:

  blockHashes.has(hash(domainInBlockList1) == hash(domainInBlockList2)

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.

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

Ah, I get what you're saying to do with the collision probability and that should definitely make sense but whatever they actually did in the readme ended up a factor of ~4 off the result that approach should give. E.g. the much simpler direct path of 2^40/537000 for that "next domain" question is giving me 1 in ~2.05 million rather than 1 in ~537k.

Edit: Or maybe they formulated that path to derivation and how to map it back but couldn't quickly find a tool able to approximate the birthday problem to that scale so they tried direct testing instead? If, e.g., they were slowly upping the values to see when a collision occurred it would make sense they ran into a collision earlier than would be expected as they (effectively) gave more than 1 trial. Or just random chance too if that's really the path they took I suppose :).

Edit2: After looking at the readme for far too long, I saw the original readme was in Japanese. Running that through a good translator actually clarifies or corrects a lot of the wording like saying "In the latter case, one other unlucky domain also gets blocked" rather than focusing on the number of domains over-blocked out of the 537000 only. With this version of the text I think you're definitely right, the math approach used should have given them the right number as the original text is already flipping things back to what happens with the one new query but they (apparently) just didn't do the actual calculation with it.

Sharp catch :).

You don't need to simulate, it is a well studied problem [1]

It seems that the average number of expected collisions for 537k would be 0.13 and not 1:

the average value of pairs of individuals with the same birthday (or hash collisions) is E[X] = k*(k-1)/(2*n). Plugging in k=2^40 for 40 bits and n=537e3 I get their result of 0.1311

Thanks for the nerdsnipe, I ran out of my daily LLM mistake fixing quota !

[1] https://en.wikipedia.org/wiki/Birthday_problem#Average_numbe...

I don't think this framing in this thread lines up with what the readme says. Also note that the python script to build the blocklist [1] reports the number of collisions found when generating the hashes.

I read their statement as "there were 0 collisions when building a blocklist for 141k domains, and 1 collision for a blocklist of 537k domains", and the script points at that number coming directly from collisions within the blocklist.

1: https://github.com/M-Abozaid/esp32-c3-adblock/blob/238ef7b27...

Makes sense why their numbers were wrong then, thanks ! Nice dive nevertheless x)

> 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.

Sorry was a bit unclear, by two blocked domains I meant two domains in the original blocklist having the same hash, i.e. hn and adserver are both in our desired blocklist in your example

In this case only the one risk flagged in the article and other comments matters: that the hash of a domain you blocked coincides with the hash of a domain you want to access, so they are both blocked. There is no difference between false positive and false negative, it's all one collision leading to one unintended block.

Reply on news.ycombinator.com