Assume the xor of your test hash with their desired hash is just 160 random bits. Furthermore, choose a certain number N, and assert: they must be white!! What is the probability that this is true:
(0.5 for each bit)^(number of bits you chose).
So given 160 random bits, what are the chances of there being atleast N bits set to zero?
(0.5^N)*(ways to choose N from 160).
(0.5^N)*(160!/(N!*(160-N)!)).
define d = 160 - N
0.5^(160-d)*(160!/((160-d)!*d!))
So I think that you are miscalculating by a bit, that is why & how.
He was computing the probability of a Hamming distance of exactly D instead of at most D. To get the "at most" version, you could just add up the exact ones, but it's better to just use the central limit theorem instead.
As for your math, I think you are over counting a little :). The problem is, 100...0 is counted by both ??0...0 and ?0?00...0, where ? marks a digit that you've allowed to be free, and 0 marks a "chosen" 0.
Assume the xor of your test hash with their desired hash is just 160 random bits. Furthermore, choose a certain number N, and assert: they must be white!! What is the probability that this is true:
So given 160 random bits, what are the chances of there being atleast N bits set to zero? define d = 160 - N So I think that you are miscalculating by a bit, that is why & how.NOTE: difference is in the 0.5^(here)