Pollard's kangaroo ECDLP solver - page 138.

PietCoin97

jr. member

Activity: 91

Merit: 3

Here is loaded file with new code

Code:

Keys :1
LoadWork: [HashTalbe 8.5/28.1MB] [00s]
Number of CPU thread: 0
Range width: 2^86
Jump Avg distance: 2^42.96
Number of kangaroos: 2^22.49
Expected operations: 2^44.47
Expected RAM: 901.5MB
DP size: 20 [0xFFFFF00000000000]
Fetch kangaroos: 983040
Fetch kangaroos: 983040
Fetch kangaroos: 983040
Fetch kangaroos: 983040
Fetch kangaroos: 983040
Fetch kangaroos: 983040
LoadWork: [2^22.49 kangaroos loaded] [0 created] [01s]
GPU: GPU #2 P104-100 (15x128 cores) Grid(30x256) (99.0 MB used)
GPU: GPU #0 P104-100 (15x128 cores) Grid(30x256) (99.0 MB used)
GPU: GPU #1 P104-100 (15x128 cores) Grid(30x256) (99.0 MB used)
SolveKeyGPU Thread GPU#2: 2^19.91 kangaroos [0.8s]
SolveKeyGPU Thread GPU#0: 2^19.91 kangaroos [0.8s]
GPU: GPU #4 GeForce GTX 1070 (15x128 cores) Grid(30x256) (99.0 MB used)
GPU: GPU #5 GeForce GTX 1070 (15x128 cores) Grid(30x256) (99.0 MB used)
GPU: GPU #3 GeForce GTX 1070 (15x128 cores) Grid(30x256) (99.0 MB used)
SolveKeyGPU Thread GPU#1: 2^19.91 kangaroos [1.6s]
SolveKeyGPU Thread GPU#3: 2^19.91 kangaroos [1.0s]
SolveKeyGPU Thread GPU#5: 2^19.91 kangaroos [1.0s]
SolveKeyGPU Thread GPU#4: 2^19.91 kangaroos [1.1s]
[1999.63 MK/s][GPU 1999.63 MK/s][Count 2^38.23][Dead 0][13:26 (Avg 03:23:47)][11.4/35.5MB]
SaveWork timweout !
[62.04 MK/s][GPU 62.04 MK/s][Count 2^38.25][Dead 0][14:27 (Avg 4.6d)][11.5/35.7MB]  6MB]
SaveWork timweout !
[59.46 MK/s][GPU 59.46 MK/s][Count 2^38.26][Dead 0][15:28 (Avg 4.8d)][11.6/35.9MB]
SaveWork: safe.work1..............................done [551.6 MB] [25s] Mon May 11 18:03:44 2020
[1949.67 MK/s][GPU 1949.67 MK/s][Count 2^38.51][Dead 0][16:30 (Avg 03:29:00)][13.4/39.7MB]
SaveWork timweout !
[59.95 MK/s][GPU 59.95 MK/s][Count 2^38.52][Dead 0][17:32 (Avg 4.7d)][13.5/39.9MB]  7MB]
SaveWork timweout !
[59.30 MK/s][GPU 59.30 MK/s][Count 2^38.53][Dead 0][18:33 (Avg 4.8d)][13.6/40.1MB]
SaveWork: safe.work1..............................done [553.6 MB] [28s] Mon May 11 18:06:52 2020
[1966.21 MK/s][GPU 1966.21 MK/s][Count 2^38.72][Dead 0][19:33 (Avg 03:27:15)][15.2/43.0MB]
SaveWork timweout !
[60.46 MK/s][GPU 60.46 MK/s][Count 2^38.73][Dead 0][20:36 (Avg 4.7d)][15.3/43.2MB]  1MB]
SaveWork timweout !
[61.23 MK/s][GPU 61.23 MK/s][Count 2^38.74][Dead 0][21:38 (Avg 4.6d)][15.4/43.3MB]
SaveWork: safe.work1..............................done [555.4 MB] [26s] Mon May 11 18:09:56 2020
[2002.32 MK/s][GPU 2002.32 MK/s][Count 2^38.92][Dead 0][22:39 (Avg 03:23:31)][17.1/46.3MB]
SaveWork timweout !
[62.15 MK/s][GPU 62.15 MK/s][Count 2^38.93][Dead 0][23:41 (Avg 4.6d)][17.2/46.4MB]  3MB]
SaveWork timweout !
[60.69 MK/s][GPU 60.69 MK/s][Count 2^38.93][Dead 0][24:41 (Avg 4.7d)][17.3/46.6MB]
SaveWork timweout !
[62.82 MK/s][GPU 62.82 MK/s][Count 2^38.94][Dead 0][25:41 (Avg 4.5d)][17.4/46.7MB]
SaveWork timweout !
[58.73 MK/s][GPU 58.73 MK/s][Count 2^38.95][Dead 0][26:44 (Avg 4.8d)][17.5/46.9MB]
SaveWork timweout !
[59.46 MK/s][GPU 59.46 MK/s][Count 2^38.96][Dead 0][27:46 (Avg 4.8d)][17.6/47.0MB]
SaveWork: safe.work1..............................done [557.6 MB] [28s] Mon May 11 18:16:05 2020
[282.34 MK/s][GPU 282.34 MK/s][Count 2^38.98][Dead 0][28:19 (Avg 1.0d)][17.8/47.4MB]

and this is -winfo from Workfile

Code:

Version   : 0
DP bits   : 20
Start     : 2000000000000000000000000000
Stop      : 3FFFFFFFFFFFFFFFFFFFFFFFFFFF
Key       : 0309976BA5570966BF889196B7FDF5A0F9A1E9AB340556EC29F8BB60599616167D
Count     : 534868131840 2^38.960
Time      : 27:46
DP Size   : 17.6/47.0MB
DP Count  : 510335 2^18.961
HT Max    : 11 [@ 0090E4]
HT Min    : 0 [@ 000008]
HT Avg    : 1.95
HT SDev   : 1.40
Kangaroos : 5898240 2^22.492

patatasfritas

newbie

Activity: 17

Merit: 0

Quote from: Jean_Luc on May 11, 2020, 09:39:05 AM

I did a small patch to try to speed up kangaroo transfer and also changed the timeout to 3 sec. Could you try it and tell me if it improves something ?

I had same problem. Also, when the save fails, the GPU downs from ~500M to ~20M.

The 3sec patch fixed it. Thanks

PietCoin97

jr. member

Activity: 91

Merit: 3

Yeah I will test when I am back on PC

Jean_Luc

sr. member

Activity: 462

Merit: 701

I did a small patch to try to speed up kangaroo transfer and also changed the timeout to 3 sec. Could you try it and tell me if it improves something ?

Jean_Luc

sr. member

Activity: 462

Merit: 701

When you save kangaroo, the CPU has to get back all kangaroos from GPUs memory this might be long.
Could you reload a work and post the output ?

PietCoin97

jr. member

Activity: 91

Merit: 3

Code:

Number of kangaroos: 2^22.49
Suggested DP: 20
Expected operations: 2^44.47
Expected RAM: 901.5MB
DP size: 20 [0xFFFFF00000000000]
GPU: GPU #1 P104-100 (15x128 cores) Grid(30x256) (99.0 MB used)
SolveKeyGPU Thread GPU#1: creating kangaroos...
GPU: GPU #2 P104-100 (15x128 cores) Grid(30x256) (99.0 MB used)
SolveKeyGPU Thread GPU#2: creating kangaroos...
GPU: GPU #0 P104-100 (15x128 cores) Grid(30x256) (99.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
GPU: GPU #3 GeForce GTX 1070 (15x128 cores) Grid(30x256) (99.0 MB used)
SolveKeyGPU Thread GPU#3: creating kangaroos...
GPU: GPU #4 GeForce GTX 1070 (15x128 cores) Grid(30x256) (99.0 MB used)
SolveKeyGPU Thread GPU#4: creating kangaroos...
GPU: GPU #5 GeForce GTX 1070 (15x128 cores) Grid(30x256) (99.0 MB used)
SolveKeyGPU Thread GPU#5: creating kangaroos...
SolveKeyGPU Thread GPU#2: 2^19.91 kangaroos [11.5s]
SolveKeyGPU Thread GPU#1: 2^19.91 kangaroos [11.7s]
SolveKeyGPU Thread GPU#0: 2^19.91 kangaroos [13.9s]
SolveKeyGPU Thread GPU#3: 2^19.91 kangaroos [11.7s]
SolveKeyGPU Thread GPU#5: 2^19.91 kangaroos [11.2s]
SolveKeyGPU Thread GPU#4: 2^19.91 kangaroos [11.5s]
[1984.76 MK/s][GPU 1984.76 MK/s][Count 2^36.22][Dead 0][45s (Avg 03:25:19)][4.3/14.4MB]
SaveWork timweout !
[62.13 MK/s][GPU 62.13 MK/s][Count 2^36.28][Dead 0][01:47 (Avg 4.6d)][4.4/14.8MB]  5MB]
SaveWork timweout !
[59.95 MK/s][GPU 59.95 MK/s][Count 2^36.33][Dead 0][02:49 (Avg 4.7d)][4.5/15.2MB]
SaveWork: safe.work1..............................done [544.5 MB] [26s] Mon May 11 15:17:09 2020
[523.14 MK/s][GPU 523.14 MK/s][Count 2^36.54][Dead 0][03:22 (Avg 12:58:57)][4.9/16.6MB]

Code:

[1984.76 MK/s][GPU 1984.76 MK/s][Count 2^36.22][Dead 0][45s (Avg 03:25:19)][4.3/14.4MB]
SaveWork timweout !
[62.13 MK/s][GPU 62.13 MK/s][Count 2^36.28][Dead 0][01:47 (Avg 4.6d)][4.4/14.8MB]  5MB]
SaveWork timweout !
[59.95 MK/s][GPU 59.95 MK/s][Count 2^36.33][Dead 0][02:49 (Avg 4.7d)][4.5/15.2MB]
SaveWork: safe.work1..............................done [544.5 MB] [26s] Mon May 11 15:17:09 2020
[2034.60 MK/s][GPU 2034.60 MK/s][Count 2^37.12][Dead 0][03:50 (Avg 03:20:17)][6.3/21.7MB]
SaveWork timweout !
[61.08 MK/s][GPU 61.08 MK/s][Count 2^37.15][Dead 0][04:52 (Avg 4.6d)][6.4/22.0MB]  8MB]
SaveWork timweout !
[57.19 MK/s][GPU 57.19 MK/s][Count 2^37.18][Dead 0][05:55 (Avg 4.9d)][6.5/22.3MB]
SaveWork timweout !
[63.30 MK/s][GPU 63.30 MK/s][Count 2^37.21][Dead 0][06:55 (Avg 4.5d)][6.6/22.6MB]
SaveWork timweout !
[62.27 MK/s][GPU 62.27 MK/s][Count 2^37.24][Dead 0][07:58 (Avg 4.5d)][6.7/22.9MB]
SaveWork timweout !
[60.29 MK/s][GPU 60.29 MK/s][Count 2^37.26][Dead 0][08:58 (Avg 4.7d)][6.8/23.2MB]
SaveWork: safe.work1..............................done [546.8 MB] [26s] Mon May 11 15:23:19 2020
[1999.43 MK/s][GPU 1999.43 MK/s][Count 2^37.71][Dead 0][09:59 (Avg 03:23:48)][8.5/28.4MB]
SaveWork timweout !
[1306.40 MK/s][GPU 1306.40 MK/s][Count 2^37.72][Dead 0][10:09 (Avg 05:11:55)][8.6/28.4MB]

PietCoin97

jr. member

Activity: 91

Merit: 3

yes 6 GPUs and i use -ws

Jean_Luc

sr. member

Activity: 462

Merit: 701

I presume you are using -ws and you have lots of kangaroos, may be multiple GPU ?

PietCoin97

jr. member

Activity: 91

Merit: 3

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

Jean_Luc

sr. member

Activity: 462

Merit: 701

Do you have this error always or only from time to time ?

PietCoin97

jr. member

Activity: 91

Merit: 3

i tryed with int = 10000 but also get this error

Jean_Luc

sr. member

Activity: 462

Merit: 701

Try to change the timeout to 3000.

Code:

int timeout = 3000;

PietCoin97

jr. member

Activity: 91

Merit: 3

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;

Jean_Luc

sr. member

Activity: 462

Merit: 701

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.

stalker00075

newbie

Activity: 54

Merit: 0

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

Jean_Luc

sr. member

Activity: 462

Merit: 701

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.

MrFreeDragon

sr. member

Activity: 443

Merit: 350

Quote from: HardwareCollector on May 10, 2020, 05:47:13 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.

HardwareCollector

member

Activity: 144

Merit: 10

Quote from: Elliptic23 on May 10, 2020, 07:11:42 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.

Elliptic23

newbie

Activity: 22

Merit: 3

Quote from: HardwareCollector on May 10, 2020, 05:47:13 PM

Quote from: arulbero on May 10, 2020, 04:16:46 AM

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.

HardwareCollector

member

Activity: 144

Merit: 10

Quote from: arulbero on May 10, 2020, 04:16:46 AM

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.

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