Author

Topic: Pollard's kangaroo ECDLP solver - page 138. (Read 59389 times)

sr. member
Activity: 462
Merit: 701
May 11, 2020, 08:13:19 AM
I presume you are using -ws and you have lots of kangaroos, may be multiple GPU ?
jr. member
Activity: 91
Merit: 3
May 11, 2020, 08:11:39 AM
3 times in a row error and then i am at 60 mkeys and then it works 1 time then i go up with the Mkey then error
sr. member
Activity: 462
Merit: 701
May 11, 2020, 08:10:28 AM
Do you have this error always or only from time to time ?
jr. member
Activity: 91
Merit: 3
May 11, 2020, 08:02:03 AM
i tryed with int = 10000 but also get this error
sr. member
Activity: 462
Merit: 701
May 11, 2020, 08:00:59 AM
Try to change the timeout to 3000.

Code:
int timeout = 3000;
jr. member
Activity: 91
Merit: 3
May 11, 2020, 07:49:40 AM
Hello Jean Luc can you please tell me how do edit code for dont get this error anymore ?

Code:
[1996.14 MK/s][GPU 1996.14 MK/s][Count 2^36.30][Dead 0][47s (Avg 03:24:08)][4.5/14.9MB]
SaveWork timweout !

something change in this area of Backup code ?

Code:
// Wait that all threads blocks before saving works
  saveRequest = true;
  int timeout = 1000;
  while(!isWaiting(threads) && timeout>0) {
    Timer::SleepMillis(50);
    timeout -= 50;

sr. member
Activity: 462
Merit: 701
May 11, 2020, 07:20:33 AM
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.
newbie
Activity: 54
Merit: 0
May 11, 2020, 06:14:21 AM
please tell me if you can change the kangaroo so
check not 1 public key but at the same time several?
is this possible?
(let's say 10,000 at the same time)

You are the best! the program is good and if I manage to find something I won’t forget you
sr. member
Activity: 462
Merit: 701
May 10, 2020, 10:54:28 PM
Good luck to solve the puzzle #110, I have the felling that It will be found very soon Wink
Take care of well configuring the 109bit range:

Puzzle #110: 109bit 12JzYkkN76xkwvcPT6AWKZtGX6w2LAgsJg
Code:
2000000000000000000000000000
3FFFFFFFFFFFFFFFFFFFFFFFFFFF
0309976ba5570966bf889196b7fdf5a0f9a1e9ab340556ec29f8bb60599616167d

Ex for puzzle #80 (79bit key) 1BCf6rHUW6m3iH2ptsvnjgLruAiPQQepLe

Code:
80000000000000000000
FFFFFFFFFFFFFFFFFFFF
037E1238F7B1CE757DF94FAA9A2EB261BF0AEB9F84DBF81212104E78931C2A19DC

Code:
:\C++\Kangaroo\VC_CUDA10>x64\Release\Kangaroo.exe -d 17 -t 0 -gpu in79.txt
Kangaroo v1.4
Start:80000000000000000000
Stop :FFFFFFFFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 0
Range width: 2^79
Jump Avg distance: 2^38.96
Number of kangaroos: 2^18.58
Suggested DP: 20
Expected operations: 2^40.60
Expected RAM: 496.9MB
DP size: 17 [0xFFFF800000000000]
GPU: GPU #0 GeForce GTX 1050 Ti (6x128 cores) Grid(12x256) (45.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^18.58 kangaroos [2.0s]
[159.53 MK/s][GPU 159.53 MK/s][Count 2^39.82][Dead 0][01:55:44 (Avg 02:54:02)][228.4/292.0MB]
Key# 0 [1S]Pub:  0x037E1238F7B1CE757DF94FAA9A2EB261BF0AEB9F84DBF81212104E78931C2A19DC
       Priv: 0xEA1A5C66DCC11B5AD180

Done: Total time 01:55:48


I will have a look if i can do something with endomorphism.
sr. member
Activity: 443
Merit: 350
May 10, 2020, 10:07:10 PM
-snip-
Based solely on the tests I’ve done so far with RTX 2080 Tis,  it’s reasonable to expect that a 110-bit interval can be solved in 5 days, 7 hours, and 39 minutes on average with 128 RTX 2080 Tis. While consuming ~640GB(~80bytes/point in the hash table) of distinguished points storage with a 23-bit points mask. Also, one might get very lucky and solve it less than the average time, say a couple of days, or 18-19 days worst case.
-snip-

Anyway this GPU power is not free. Even if you own it, you should have the alternative cots (like to use them for mining with the guaranteed profit).
As for the rent, I made a quick search, and found that 8 x 2080 Ti 384 GB RAM Xeon Gold could be rented for 572 eur per week, i.e 620usd/week (source: https://www.leadergpu.com/#chose-best).

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

Ok, that rent for 8 x2080ti is expensive. I am sure the real cost is 1.5-2 times less (it is possible to find 8x2080ti for 300-400 USD/week. However even you invest 2 times less (5kUSD), you still have 50% probability to solve the key and receive 9.7k. It is like a casino roulette game: put 5k on "red" or "black" and receive 2 times more with 50% probability just for 1 spin (with total duration 1 minute, and not 1 week).

Or someone not ready to invest 5k, can rent just 4x2080ti for 200-300USD/week, divide the total range by (128/4) = 32, select any part of the initial range divided by 32, and search within it for 1 week with rented 4x2080ti. If lucky, he can also win. The prize will be the same, so the pot odds are 9.7k / 0.3k = 32-33 which is more or less like a bet on just one number on the same roulette (with 35:1 pot odds and chances to win), however with 2 times less probability.

So, agree that the method is interesting for intellectual reasons. Money is just an advantage, but not the main goal.
member
Activity: 144
Merit: 10
May 10, 2020, 09:36:50 PM
Who else other than you has that kind of GPU power?
Those of us lucky to have 4 2080 Ti's have no chance of solving anything in time.

A lot of miners do, but we do not have a server with the much RAM available to solve the (110-bit interval) problem as fast as possible. So we need to come up with the best time-memory trade-off parameters. Also, I by far are more interested in the intellectual challenge, although the prize (in BTC) can be a very good motivator for some.
newbie
Activity: 22
Merit: 3
May 10, 2020, 07:11:42 PM
This is the next public key (#110, with a private key in range [ 2^109 , 2^110 - 1], 109 bit) they have been looking for over 7,5 months (about 225 days):
 
0309976ba5570966bf889196b7fdf5a0f9a1e9ab340556ec29f8bb60599616167d

(address: 12JzYkkN76xkwvcPT6AWKZtGX6w2LAgsJg)

The Pollard's kangaroo ECDLP solver needs 2*(2^(109/2)) = 2^55.5 steps to retrieve this private key, a GPU that computes 2^30 steps/sec would take 2^25.5 seconds, about 550 days.

128 RTX 2080 Tis.

Who else other than you has that kind of GPU power?

Those of us lucky to have 4 2080 Ti's have no chance of solving anything in time.
member
Activity: 144
Merit: 10
May 10, 2020, 05:47:13 PM
This is the next public key (#110, with a private key in range [ 2^109 , 2^110 - 1], 109 bit) they have been looking for over 7,5 months (about 225 days):
 
0309976ba5570966bf889196b7fdf5a0f9a1e9ab340556ec29f8bb60599616167d

(address: 12JzYkkN76xkwvcPT6AWKZtGX6w2LAgsJg)

The Pollard's kangaroo ECDLP solver needs 2*(2^(109/2)) = 2^55.5 steps to retrieve this private key, a GPU that computes 2^30 steps/sec would take 2^25.5 seconds, about 550 days.

Based solely on the tests I’ve done so far with RTX 2080 Tis,  it’s reasonable to expect that a 110-bit interval can be solved in 5 days, 7 hours, and 39 minutes on average with 128 RTX 2080 Tis. While consuming ~640GB(~80bytes/point in the hash table) of distinguished points storage with a 23-bit points mask. Also, one might get very lucky and solve it less than the average time, say a couple of days, or 18-19 days worst case. But we definitely can reduce the memory requirements by only using 4-bytes for herd type, 8-bytes for the x-coordinate, and 16-bytes for starting position of the kangaroo. When there’s a collision, we re-walk the kangaroo’s path up to the distinguished point and check for a solution.
legendary
Activity: 1932
Merit: 2077
May 10, 2020, 02:17:15 PM
I've got another idea, but it is not (much) faster:

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,

we need 2.sqrt(3N) = sqrt(3).2.sqrt(N) steps to get a collision in a 3N-space.

If we find a way to generate sqrt(3).2.sqrt(N) points faster than 2.sqrt(N), we get a collision in less time, even if we triple our searching space.

If we use the endomorphism, we can triple our interval, from

[1,2,3, ..., n-1,n]

to

[1,2,3,....., n-1,n] + [lambda, 2*lambda, 3*lambda, ....., n*lambda] + [lambda^2, 2*lambda^2, 3*lambda^2, ....., n*lambda^2]

We have 3 types of jumps (always positive): 10 small steps (in first interval) + 10 big steps (in second interval) + 10 bigbig steps (in third interval)

For example:
(1G, 2G, 4G, 8G, 24G, 37G,....., 512G)  + (lambda*18G, lambda*72G, ..., lambda*816G) + (lambda^2*41G, lambda^2*10G, ..., lambda^2*653G)

+ 1 jump from range1 to range2  or  from range1 to range2:     P -> lambda*P


We set the probability to perform a jump between 2 different ranges = 50%, the other 50% is for normal jupms.

For a single step we compute the normal jump +k*G

(3 multiplications for the inverse + 1M + 1S for the x-coordinate + 1M for the y-coordinate = about 6M + some additions)

or a single multiplication:   beta*x

You cannot have loops, you have only avoid 3 consecutive steps like: P -> lambda*P -> lambda*(lambda*P) -> lambda*(lambda^2*P = P), in this case you do a normal step P+kG instead of lambda*P.

If we look at a triple of consecutive jumps, we will have:

                                                                           probability
normal jump + normal jump + normal jump = (1/2)^3
normal jump + normal jump + lambda jump = (1/2)^3 * 3
normal jump + lambda jump + lambda jump =  (1/2)^3 * 3

lambda jump + lambda jump + lambda jump= (1/2)^3 but -> loop, it is forbidden
-> it becomes: lambda jump + lambda jump + lambda jump + normal jump

On average for each 3 points we need to perform (1/2)^3*18M + (1/2)^3*3*13M + (1/2)^3*3*8M + (1/2)^3*8M = 11.125M,    3.71M for each point.

In this way you perform sqrt(3).2.sqrt(N) steps in the same time you are performing now sqrt(3).2.(3,71/6).sqrt(N)= 2.14*sqrt(N)


If you double the interval:

[1,2,3,....., n-1,n] + [lambda, 2*lambda, 3*lambda, ....., n*lambda]

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)


member
Activity: 144
Merit: 10
May 10, 2020, 01:10:31 PM
Yes the jumps have to be fixed otherwise paths differ and work files become incompatible.
Hope the cafe will be good Smiley

@Jean_Luc

I have some good news, I performed over 250 tests with the client/server approach for [80-85]-bit intervals with randomly generated keys. When memory usage is not an issue for distinguished points storage, we seemed to converge around ~2(SquareRoot(interval size)), the worst cases where around ~7(Square Root(interval size)). Of course, every now and then we get very lucky and solve it in under SquareRoot(interval size).

Now running some random 95-bit interval tests with 96x RTX 2080 Tis and expect the average solution time to be ~60 minutes. I will let in run for a couple of days and see.

Seems to be the worst case: ~7(Square Root(interval size))
Code:
./dlpserver
ECDLP Server Started and Listening on Port 8090...
ECDLP File Merger Process Started...
Loading: savefile_1589084641
MergeWork: [HashTalbe 2.0/4.0MB] [00s]
Appending...
Range width: 2^80
Dead kangaroo: 0
DP[20-bit]: count 2^15.13 [50s]
Loading: savefile_1589084702
MergeWork: [HashTalbe 3.1/9.2MB] [00s]
Appending...
Range width: 2^80
Dead kangaroo: 0
DP[20-bit]: count 2^16.27 [01:50]
Loading: savefile_1589084762
MergeWork: [HashTalbe 4.4/14.7MB] [00s]
Appending...
Range width: 2^80
Dead kangaroo: 0
DP[20-bit]: count 2^16.90 [02:50]
.
.
.
Loading: savefile_1589123004
MergeWork: [HashTalbe 112.3/149.4MB] [00s]
Appending...
Range width: 2^80
Dead kangaroo: 0
DP[20-bit]: count 2^21.80 [02:50]
Loading: savefile_1589123065
MergeWork: [HashTalbe 113.6/150.9MB] [00s]
Appending...
Range width: 2^80
Dead kangaroo: 0
DP[20-bit]: count 2^21.82 [03:51]
Loading: savefile_1589123125
MergeWork: [HashTalbe 115.0/152.5MB] [00s]
Appending...
Range width: 2^80
Dead kangaroo: 0
DP[20-bit]: count 2^21.84 [04:51]
Exiting File Merger Process...
.
.
.
Receiving savefile_1589124355 (8414564 bytes)
Loading: savefile_1589124355
MergeWork: [HashTalbe 186.5/239.7MB] [00s]
Appending...
Range width: 2^80
Dead kangaroo: 1
DP[20-bit]: count 2^22.57 [09:47]
Receiving savefile_1589124361 (3480068 bytes)
Loading: savefile_1589124361
MergeWork: [HashTalbe 192.5/247.2MB] [00s]
Appending...
Range width: 2^80
Dead kangaroo: 1
DP[20-bit]: count 2^22.58 [14:55]
Receiving savefile_1589124416 (8382084 bytes)
Receiving savefile_1589124421 (3489508 bytes)
Loading: savefile_1589124421
MergeWork: [HashTalbe 193.8/248.8MB] [00s]
Appending...
Range width: 2^80
Dead kangaroo: 1
DP[20-bit]: count 2^22.59 [15:55]
Loading: savefile_1589124416
MergeWork: [HashTalbe 195.2/250.5MB] [00s]
Appending...
Range width: 2^80
Dead kangaroo: 1
DP[20-bit]: count 2^22.64 [10:48]
Receiving savefile_1589124476 (8177604 bytes)
Receiving savefile_1589124482 (3483076 bytes)
Loading: savefile_1589124482
MergeWork: [HashTalbe 201.2/258.0MB] [00s]
Appending...
Range width: 2^80
Dead kangaroo: 1
DP[20-bit]: count 2^22.65 [16:56]
Loading: savefile_1589124476
MergeWork: [HashTalbe 202.5/259.6MB] [00s]
Appending...
Range width: 2^80
Dead kangaroo: 1
DP[20-bit]: count 2^22.69 [11:48]
Receiving savefile_1589124537 (7515044 bytes)
Receiving savefile_1589124542 (3492612 bytes)
Loading: savefile_1589124542
MergeWork: [HashTalbe 208.3/266.9MB] [00s]
Appending...
Range width: 2^80
Dead kangaroo: 1
DP[20-bit]: count 2^22.70 [17:56]
Loading: savefile_1589124537
MergeWork: [HashTalbe 209.6/268.5MB] [00s]
Appending...
Range width: 2^80

Key# 0 [1S]Pub:  0x037E1238F7B1CE757DF94FAA9A2EB261BF0AEB9F84DBF81212104E78931C2A19DC
       Priv: 0xEA1A5C66DCC11B5AD180
legendary
Activity: 1932
Merit: 2077
May 10, 2020, 09:30:25 AM
Thanks for the info Wink

I didn't look at all addresses, the #110 is the only one remaining with the pub key exposed ?


#115, #120, #125, #130 ...., #160 are left
newbie
Activity: 5
Merit: 0
May 10, 2020, 08:38:47 AM
Thanks for the info Wink

I didn't look at all addresses, the #110 is the only one remaining with the pub key exposed ?


https://vlmi.io/attachments/privat-txt.24930/

+ # 105

105 | 000000000000000000000000000000000000016F14FC2054CD87EE6396B33DF3 | 1CMjscKB3QW7SDyQ4c3C3DEUHiHRhiZVib | 40564819207303340847894502572031                 | 03bcf7ce887ffca5e62c9cabbdb7ffa71dc183c52c04ff4ee5ee82e0c55c39d77b | 2019-09-23

https://bitcointalksearch.org/topic/m.53649852
copper member
Activity: 205
Merit: 1
May 10, 2020, 07:56:59 AM
Thanks for the info Wink

I didn't look at all addresses, the #110 is the only one remaining with the pub key exposed ?


https://vlmi.io/attachments/privat-txt.24930/
sr. member
Activity: 462
Merit: 701
May 10, 2020, 06:50:21 AM
Thanks for the info Wink

I didn't look at all addresses, the #110 is the only one remaining with the pub key exposed ?
legendary
Activity: 1932
Merit: 2077
May 10, 2020, 04:16:46 AM
The current record for a ECDLP solved on a curve over a prime field is 114-bit:

https://ellipticnews.wordpress.com/2018/04/22/114-bit-ecdlp-solved-on-a-curve-with-automorphisms-over-a-prime-field/

Quote
The curve has j-invariant 0, and so has an automorphism group of size 6. Hence, it is possible to perform the Pollard rho algorithm using equivalence classes of size 6.

They used n = 1024 partitions for the random walk, and the “hash function” was chosen to be the least significant log_2(n) bits of the x-coordinate of the current curve point.

The paper writes that “The parallel implementation of the rho method by adopting a client-server model, using 2000 CPU cores took about 6 months”. They seem to have been lucky to get a collision earlier than expected: “the result of the authors attack is little bit better than the average number of rational points where a simple collision attack stops.”



For the secp256k1, the current record is a ECDLP solved in a interval of 104 bit (key #105 of the "puzzle transaction")

https://www.blockchain.com/btc/tx/08389f34c98c606322740c0be6a7125d9860bb8d5cb182c02f98461e5fa6cd15

that key was found on 2019-09-23.


This is the next public key (#110, with a private key in range [ 2^109 , 2^110 - 1], 109 bit) they have been looking for over 7,5 months (about 225 days):
 
0309976ba5570966bf889196b7fdf5a0f9a1e9ab340556ec29f8bb60599616167d

(address: 12JzYkkN76xkwvcPT6AWKZtGX6w2LAgsJg)

The Pollard's kangaroo ECDLP solver needs 2*(2^(109/2)) = 2^55.5 steps to retrieve this private key, a GPU that computes 2^30 steps/sec would take 2^25.5 seconds, about 550 days.



A good article / recap about ECDLP:

https://ellipticnews.wordpress.com/2016/04/07/ecdlp-in-less-than-square-root-time/

Jump to: