So, the cost for 128 devices will be 128/8 * 620 = 9.9 kUSD per week.. Current prize value of #110 is 1.1x8.8kUSD = 9.7 kUSD, so the prize is more o less the same like the investments need to find it. But there is no 100% guarantee to solve the key, it is only 50%.
To be precise, the current prize is 1.1 BTC + 1.1 BCH + 1.1 BSV = 1.1 * (9300 USD) = 10230 USD
Multiple search is possible but I won't work on it first.
I will work on a distributed client/server version.
The #110 will be likely solved soon.
With the distributed version, I'm almost sure the #115 will also be solved.
In that case it would be a record, 114 bit.
******************************************************************************
I rewrite my idea with more details:
we need 2.sqrt(N) steps to get a collision in a N-space,
we need 2.sqrt(2N) = sqrt(2).2.sqrt(N) steps to get a collision in a 2N-space
if we find a way to generate sqrt(2).2.sqrt(N) points faster than 2.sqrt(N), we get a collision in less time, even if we double our searching space.
If we use the endomorphism, we can double our interval, from
[1,2,3, ..., n-1,n]
to
[1,2,3,....., n-1,n] + [lambda, 2*lambda, 3*lambda, ....., n*lambda]
We have 2 types of jumps (always positive): 16 small steps (in first interval) + 16 big steps (in second interval)
For example:
(1G, 2G, 4G, 8G, 24G, 37G,....., 512G) + (lambda*18G, lambda*72G, ..., lambda*816G)
+ 1 jump from range1 to range2 or from range1 to range2: P -> lambda*P or lambda*P -> lambda^2*(lambda*P)
You have to know at each step in which interval the kangaroo is.
We set the probability to perform a jump between 2 different ranges = 50%, the other 50% is for normal jumps.When a kangaroo is in the point P(x,y):
if x-coordinate > 2^255 then:
change interval
else:
do a normal jumps (x-coordinate % 16, small or big steps depends on the interval in which P is)
If x-coordinate > 2^255 then:
you compute a single multiplication: beta*x (or beta^2*x, it depends on the interval in which P is)
else:
you compute the normal jump P+k*G (or P+s*lambda*G, it depends on the interval in which P is)
(3 multiplications for the inverse + 1M + 1S for the x-coordinate + 1M for the y-coordinate = about 6M + some additions)
You cannot have loops, you have only to avoid 2 consecutive jumps between 2 ranges like: P -> lambda*P -> lambda^2*(lambda*P) = P, in this case you do a normal step P+kG instead of computing lambda*P:
P -> lambda*P ->
lambda^2*(lambda*P) = P instead of doing lambda^2*(lambda*P) you do P+k*G (this jump depends on the x-coordinate of P; note you don't have to compute lambda^2*(lambda*P), you mantain in the memory the last point P)
if another kangaroo falls in the same (lambda*P) from another point you will have a collision:
Q -> Q + lambda*7*G = lambda*P -> lambda^2*(lambda*P) = P ->
lambda*P instead of doing again lambda*P, you do P+k*G as before
If we look at a couple of consecutive jumps, we will have:
probability
normal jump + normal jump = (1/2)^2
normal jump + lambda jump = (1/2)^2
lambda jump + normal jump = (1/2)^2
lambda jump + lambda jump= (1/2)^2 but -> loop, it is forbidden
-> it becomes: lambda jump +
lambda jump + normal jump
On average for each 2 points
we need to perform (1/2)^2*12M + (1/2)^2*2*7M + (1/2)^2*7M = 8.25M,
4,125 M for each point.
If you double the interval:
[1,2,3,....., n-1,n] + [lambda, 2*lambda, 3*lambda, ....., n*lambda]
then
you perform sqrt(2).2.sqrt(N) steps in the same time you are performing now sqrt(2).2.(4,125/6).sqrt(N)= 1.945*sqrt(N)But we have a collision not only when 2 kangaroos (a wild and a tame) meet in a single range (first o second); even when they
fall in 2 points P and lambda*P (with the same y-coordinate),
there is a 75% that they will continue on the same path:
P -> lambda*P -> P there is a collision (same path)
P -> lambda*P -> lambda*P + lambda*7*G there is a collision (same path)
P -> P+12*G and lambda*P -> P there is a collision (same path)
P -> P+12*G and lambda*P -> lambda*P + lambda*7*G there is no collision
there is no a collision, one kangaroo jumps from P to P+12*G and the other one jumps from lambda*P to lambda*P + lambda*7*G
In a N-space, we need 2 lists of sqrt(N) points to form sqrt(N)*sqrt(N) = N couples. N couples over N^2 possible couples, on average we should generate N couples to get one with the same elements (a collision)
In our 2N-space we have 2N couples with the same 2 points + 2N couples with 2 related points (P,lambda*P). On average 3/4 of (P,lambda*P) will produce (if xP > 2^255 or if x(lambda*P)>2^255) a collision,
then we have (2N + 3/4*2N) couples of collisions over (2N*2N) possible couple.
The probability to find a collision for each couple is:
(7/4 * 2N) / (4N^2) = 14/16 * 1/N = 7/8 * 1/N instead of 1/2N, this means 7/4 bigger.
We need than 8N/7 couples to have a collision, 2 lists of sqrt(8N/7) points -> 2,14.sqrt(N) 'cheap' points ->
2,14.(4,125/6).sqrt(N) =
1,47.sqrt(N) normal points
