The
birthday problem can be applied to estimate the probability of a collision given the size of a hash function.
The Taylor series expansion of the exponential function can be used to estimate the probability of a collision as follows:
p(n, d) = 1 - e
-n(n - 1)/(2d)where n is the number of hashes and d is the total number of possible hashes.
Given a hash function size of h in bits and a number of Bitcoin addresses generated 2
x this can be simplified as follows:
p(n, d) = 1 - e
-2x(2x - 1)/(2(2h)) = 1 - e
-(22x - 2x)/(2h + 1) = 1 - e
-[22x/(2h + 1) - 2x/(2h + 1)] = 1 - e
-(22x - h - 1 - 2x - h - 1)Within the limits of my Excel spreadsheet for h = 160 the probability of a collision for various values of x is:
x p(2x, 2160)
83 1
82 0.999664537
81 0.864664717
80 0.39346934
79 0.117503097
78 0.030766766
77 0.007782062
76 0.001951219
75 0.000488162
74 0.000122063
73 3.05171E-05
72 7.62937E-06
71 1.90735E-06
70 4.76837E-07
69 1.19209E-07
68 2.98023E-08
67 7.45058E-09
66 1.86265E-09
65 4.65661E-10
64 1.16415E-10
63 2.91038E-11
62 7.27596E-12
61 1.81899E-12
60 4.54747E-13
59 1.13687E-13
58 2.84217E-14
57 7.10543E-15
56 1.77636E-15
55 0
This yields the interesting result that
after "using up" only 283 out of our 2160 Bitcoins addresses we will almost certainly have one or more address collisions. In fact we really only want to "use up" about 2
55 Bitcoin addresses in order to keep the probability of a collision very near to zero (within the limits of the estimation function, my simplification, and the resolution abilities of the Excel spreadsheet).
How fast can we use up or generate 255 addresses? Well as of this posting the
large bitcoin collider project has already sequentially searched the first 2
52.19 Bitcoin addresses and is on track to search the first 2
54.46 addresses within a year. Given some serious resources to attack the problem, orders of magnitude more addresses could be generated and checked per year.
This thread is not about the merits or failing of the LBC so posts related to the LBC will be deleted. I only use the maximum key generation rate of the LBC as an example of how fast keys can be created.
So far the LBC has had a peak key generation rate of about 2.5 x 10
9 key pairs per second. That is about
(3.154 x 10
7)(2.5 x 10
9) = 7.885 x 10
16 or approximately
256 key pairs per year.
If we were to move from the current 160 bit Bitcoin address to a new system that would fully utilize all 256 bit available for Bitcoin addresses the situation is much better:
x p(2x, 2256)
131 1
130 0.999664537
129 0.864664717
128 0.39346934
127 0.117503097
126 0.030766766
125 0.007782062
124 0.001951219
123 0.000488162
122 0.000122063
121 3.05171E-05
120 7.62937E-06
119 1.90735E-06
118 4.76837E-07
117 1.19209E-07
116 2.98023E-08
115 7.45058E-09
114 1.86265E-09
113 4.65661E-10
112 1.16415E-10
111 2.91038E-11
110 7.27596E-12
109 1.81899E-12
108 4.54747E-13
107 1.13687E-13
106 2.84217E-14
105 7.10543E-15
104 1.77636E-15
103 0
In this case we should be able to safely use up to 2
103 Bitcoin addresses before collisions would be a problem.
I think we should discuss phasing out the old 160 bit Bitcoin address version and replacing it with a new 256 bit address version.