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.
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:
blockHashes.has(hash(domainInBlockList1) == hash(domainInBlockList2)
blockHashes.has(hash(domainNotInList))
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
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 :).
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 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...