Bitcointalk Mobile Browser presented by IRLBTC™

<< >> (p.6)

Author

Topic: Pollard's kangaroo ECDLP solver (Read 62387 times)

Jean_Luc (OP)

Sr. Member

Offline

Activity: 462
Merit: 737

Re: Pollard's kangaroo ECDLP solver

May 07, 2020, 02:50:17 PM

#101

I committed the mods. Linux user can try them. (Edit: or Windows user who compile,
I updated project files)

./kangaroo -w save.work -wi 10 in.txt (Save work file every 10 sec)
./kangaroo -w save2.work -wi 10 in.txt (Save work file every 10 sec)

Merge 2 files:

Code:

pons@linpons:~/Kangaroo$ ./kangaroo -wm save.work save2.work save3.work
Kangaroo v1.4notready
Loading: save.work
MergeWork: [HashTalbe1 2.3/5.7MB] [00s]
Loading: save2.work
MergeWork: [HashTalbe2 2.3/5.7MB] [00s]
Merging...
Range width: 2^56

SaveWork: save3.work...............done [2.5 MB] [00s] Thu May 7 16:38:03 2020
Dead kangaroo: 0
Total f1+f2: count 2^29.03 [30s]

During the merge the key can also be solved, you can share your work files !

Code:

pons@linpons:~/Kangaroo$ ./kangaroo -wm save.work save2.work save3.work
Kangaroo v1.4notready
Loading: save.work
MergeWork: [HashTalbe1 2.5/6.5MB] [00s]
Loading: save2.work
MergeWork: [HashTalbe2 2.5/6.5MB] [00s]
Merging...
Range width: 2^56

Key# 0 [1S]Pub: 0x02E9F43F810784FF1E91D8BC7C4FF06BFEE935DA71D7350734C3472FE305FEF82A
Priv: 0x378ABDEC51BC5D
Dead kangaroo: 1
Total f1+f2: count 2^29.78 [50s]

Restart a work file:
pons@linpons:~/Kangaroo$ ./kangaroo -i save.work

If you use the -ws option, it saves all the kangaroo state, so you restart exactly where you are and you avoid kangaroo creation.

Hope that I have no added too much bugs

Thanks to test

arulbero

Legendary

Offline

Activity: 2023
Merit: 2267

Re: Pollard's kangaroo ECDLP solver

May 07, 2020, 03:04:08 PM
Last edit: May 07, 2020, 06:36:16 PM by arulbero

#102

Quote from: MrFreeDragon on May 07, 2020, 12:55:36 PM

For the range [a,b] if we have pre-calculated (b-a)^(1/3) distinguished points, we would need only (b-a)^(1/3) group operations in order to find the collision. But precomputation requires (b-a)^(2/3) group operations (performed once as a preliminary stage).

If you can store (b-a)^2/3 distinguished points,
the best things to do is to generate 1*G, 2*G, 3*G, ...., (b-a)^2/3 * G.
In this way you can use the BSGS algorithm, that is faster than kangaroo (less steps - on average 2^(N/2) - and each step is faster because the points are consecutive)

For each public key P, if you try with these (b-a)^1/3 giant steps:

P-1*(b-a)^2/3*G, P-2*(b-a)^2/3*G, P-3*(b-a)^2/3*G, ..., P -(b-a)^1/3*(b-a)^2/3*G = P - (b-a)*G you will recover for sure the private key (on average in 0.5*(b-a)^(1/3) steps).

You have divided the interval into (b-a)^1/3 sub-intervals each with length = (b-a)^2/3

In case you have to find a key in a 45-bit space, you can shift the interval in [-(b-a)/2, (b-a)/2] and use only half baby steps (1*G, ..., 2^29*G) instead of 2^30 steps. And you need on average 2^14 steps to recover the key. Then in a space of 2^n points you need only 2^((n/3)-1) steps (if you have precomputed 2^((2*n/3)-1) points)

In case you have to find a key in a 90-bit space and you have only 2^29 precomputed points, you need no more than 2^60 giant steps (2^60 sub-intervals to search through) to find a key, on average 2^59 giant steps. Then much better kangaroo.

In any case for large space (like 90 bits), (b-a)^(2/3) means 2^60, too much.

If you want to find many public keys in 69 bits, you need to store 2^46 points, too much.

If you want to find many public keys in 2^45 bits, you need to store 2^30 points, ok, you have enough space to store them. But finding public keys in 2^23 steps or in 2^15 is similar, it takes less than 1 sec for each key. Unless you need to find millions of public keys, there is no difference.

arulbero

Legendary

Offline

Activity: 2023
Merit: 2267

Re: Pollard's kangaroo ECDLP solver

May 07, 2020, 03:07:49 PM

#103

Quote from: Jean_Luc on May 07, 2020, 02:50:17 PM

Code:

During the merge the key can also be solved, you can share your work files !

You save the jumps too or only the DP? I mean the array of NB_JUMPS jumps.

Jean_Luc (OP)

Sr. Member

Offline

Activity: 462
Merit: 737

Re: Pollard's kangaroo ECDLP solver

May 07, 2020, 03:15:49 PM

#104

No the jump are now with a fixed seed in order to avoid incompatibility with work files.

Btckeypuzzle

Newbie

Offline

Activity: 5
Merit: 0

Re: Pollard's kangaroo ECDLP solver

May 07, 2020, 04:55:18 PM

#105

To: Jean_Luc

CPU "as-is" test results:

Code:

-w save.work -wi 10 in.txt

Kangaroo v1.4notready
Start:0
Stop :FFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 4
Range width: 2^56
Jump Avg distance: 2^28.01
Number of kangaroos: 2^12.00
Suggested DP: 16
Expected operations: 2^29.62
Expected RAM: 12.5MB
DP size: 16 [0xFFFF000000000000]
SolveKeyCPU Thread 3: 1024 kangaroos
SolveKeyCPU Thread 2: 1024 kangaroos
SolveKeyCPU Thread 1: 1024 kangaroos
SolveKeyCPU Thread 0: 1024 kangaroos
[7.26 MK/s][GPU 0.00 MK/s][Count 2^25.68][Dead 0][11s (Avg 01:53)][2.0/4.1MB]
SaveWork: save.work...............done [2.0 MB] [00s] Thu May 07 18:58:36 2020
[5.81 MK/s][GPU 0.00 MK/s][Count 2^26.78][Dead 0][23s (Avg 02:22)][2.1/4.3MB]
SaveWork: save.work...............done [2.1 MB] [00s] Thu May 07 18:58:50 2020
[5.47 MK/s][GPU 0.00 MK/s][Count 2^27.46][Dead 0][38s (Avg 02:31)][2.1/4.4MB]
SaveWork: save.work...............done [2.1 MB] [00s] Thu May 07 18:59:04 2020
[5.45 MK/s][GPU 0.00 MK/s][Count 2^27.80][Dead 0][49s (Avg 02:31)][2.1/4.5MB]
SaveWork: save.work...............done [2.1 MB] [00s] Thu May 07 18:59:14 2020

Key# 0 [1S]Pub: 0x02E9F43F810784FF1E91D8BC7C4FF06BFEE935DA71D7350734C3472FE305F
EF82A
Priv: 0x378ABDEC51BC5D

[ 0] 2^27.923 Dead:0 Avg:2^27.923 DeadAvg:0.0 (2^29.621)

Done: Total time 53s

Code:

-w save2.work -wi 10 in.txt

Kangaroo v1.4notready
Start:0
Stop :FFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 4
Range width: 2^56
Jump Avg distance: 2^28.01
Number of kangaroos: 2^12.00
Suggested DP: 16
Expected operations: 2^29.62
Expected RAM: 12.5MB
DP size: 16 [0xFFFF000000000000]
SolveKeyCPU Thread 1: 1024 kangaroos
SolveKeyCPU Thread 2: 1024 kangaroos
SolveKeyCPU Thread 3: 1024 kangaroos
SolveKeyCPU Thread 0: 1024 kangaroos
[7.27 MK/s][GPU 0.00 MK/s][Count 2^25.97][Dead 0][13s (Avg 01:53)][2.0/4.1MB]
SaveWork: save2.work...............done [2.0 MB] [00s] Thu May 07 19:08:13 2020
[5.84 MK/s][GPU 0.00 MK/s][Count 2^26.97][Dead 0][27s (Avg 02:21)][2.1/4.3MB]
SaveWork: save2.work...............done [2.1 MB] [00s] Thu May 07 19:08:27 2020
[5.48 MK/s][GPU 0.00 MK/s][Count 2^27.56][Dead 0][41s (Avg 02:30)][2.1/4.5MB]
SaveWork: save2.work...............done [2.1 MB] [00s] Thu May 07 19:08:42 2020
[5.45 MK/s][GPU 0.00 MK/s][Count 2^27.87][Dead 0][51s (Avg 02:31)][2.1/4.6MB]
SaveWork: save2.work...............done [2.1 MB] [00s] Thu May 07 19:08:51 2020
[5.45 MK/s][GPU 0.00 MK/s][Count 2^28.10][Dead 0][01:00 (Avg 02:31)][2.1/4.7MB]
[5.45 MK/s][GPU 0.00 MK/s][Count 2^28.22][Dead 0][01:05 (Avg 02:31)][2.1/4.7MB]

SaveWork: save2.work...............done [2.1 MB] [00s] Thu May 07 19:09:05 2020
[5.45 MK/s][GPU 0.00 MK/s][Count 2^28.33][Dead 0][01:10 (Avg 02:31)][2.2/4.8MB]
[5.45 MK/s][GPU 0.00 MK/s][Count 2^28.41][Dead 0][01:14 (Avg 02:31)][2.2/4.8MB]
[5.45 MK/s][GPU 0.00 MK/s][Count 2^28.48][Dead 0][01:18 (Avg 02:31)][2.2/4.9MB]

SaveWork: save2.work...............done [2.2 MB] [00s] Thu May 07 19:09:18 2020
[5.45 MK/s][GPU 0.00 MK/s][Count 2^28.58][Dead 0][01:24 (Avg 02:31)][2.2/4.9MB]
[5.45 MK/s][GPU 0.00 MK/s][Count 2^28.66][Dead 0][01:28 (Avg 02:31)][2.2/5.0MB]

SaveWork: save2.work...............done [2.2 MB] [00s] Thu May 07 19:09:29 2020
[5.44 MK/s][GPU 0.00 MK/s][Count 2^28.74][Dead 0][01:33 (Avg 02:31)][2.2/5.0MB]
[5.45 MK/s][GPU 0.00 MK/s][Count 2^28.80][Dead 0][01:37 (Avg 02:31)][2.2/5.1MB]
[5.44 MK/s][GPU 0.00 MK/s][Count 2^28.87][Dead 0][01:42 (Avg 02:31)][2.2/5.1MB]

SaveWork: save2.work...............done [2.2 MB] [00s] Thu May 07 19:09:43 2020
[5.45 MK/s][GPU 0.00 MK/s][Count 2^28.96][Dead 0][01:49 (Avg 02:31)][2.2/5.2MB]
[5.45 MK/s][GPU 0.00 MK/s][Count 2^29.02][Dead 0][01:53 (Avg 02:31)][2.3/5.2MB]

SaveWork: save2.work...............done [2.3 MB] [00s] Thu May 07 19:09:54 2020
[5.44 MK/s][GPU 0.00 MK/s][Count 2^29.08][Dead 0][01:58 (Avg 02:31)][2.3/5.3MB]
[5.45 MK/s][GPU 0.00 MK/s][Count 2^29.12][Dead 0][02:02 (Avg 02:31)][2.3/5.3MB]
[5.46 MK/s][GPU 0.00 MK/s][Count 2^29.19][Dead 0][02:08 (Avg 02:31)][2.3/5.4MB]

SaveWork: save2.work...............done [2.3 MB] [00s] Thu May 07 19:10:08 2020
[5.46 MK/s][GPU 0.00 MK/s][Count 2^29.24][Dead 0][02:12 (Avg 02:31)][2.3/5.5MB]
[5.46 MK/s][GPU 0.00 MK/s][Count 2^29.28][Dead 0][02:16 (Avg 02:31)][2.3/5.5MB]
[5.45 MK/s][GPU 0.00 MK/s][Count 2^29.34][Dead 0][02:22 (Avg 02:31)][2.3/5.6MB]

SaveWork: save2.work...............done [2.3 MB] [00s] Thu May 07 19:10:23 2020
[5.44 MK/s][GPU 0.00 MK/s][Count 2^29.39][Dead 0][02:27 (Avg 02:31)][2.3/5.6MB]
[5.44 MK/s][GPU 0.00 MK/s][Count 2^29.43][Dead 0][02:31 (Avg 02:31)][2.3/5.7MB]
[5.45 MK/s][GPU 0.00 MK/s][Count 2^29.48][Dead 0][02:36 (Avg 02:31)][2.3/5.7MB]

SaveWork: save2.work...............done [2.4 MB] [00s] Thu May 07 19:10:37 2020
[5.44 MK/s][GPU 0.00 MK/s][Count 2^29.53][Dead 0][02:42 (Avg 02:31)][2.4/5.8MB]
[5.44 MK/s][GPU 0.00 MK/s][Count 2^29.56][Dead 0][02:45 (Avg 02:31)][2.4/5.8MB]
[5.44 MK/s][GPU 0.00 MK/s][Count 2^29.58][Dead 0][02:48 (Avg 02:31)][2.4/5.8MB]

SaveWork: save2.work...............done [2.4 MB] [00s] Thu May 07 19:10:47 2020
[5.41 MK/s][GPU 0.00 MK/s][Count 2^29.60][Dead 0][02:50 (Avg 02:32)][2.4/5.9MB]
[5.40 MK/s][GPU 0.00 MK/s][Count 2^29.62][Dead 0][02:53 (Avg 02:32)][2.4/5.9MB]
[5.41 MK/s][GPU 0.00 MK/s][Count 2^29.64][Dead 0][02:56 (Avg 02:32)][2.4/5.9MB]
[5.43 MK/s][GPU 0.00 MK/s][Count 2^29.66][Dead 0][02:58 (Avg 02:32)][2.4/5.9MB]

SaveWork: save2.work...............done [2.4 MB] [00s] Thu May 07 19:10:57 2020
[5.40 MK/s][GPU 0.00 MK/s][Count 2^29.68][Dead 0][03:00 (Avg 02:32)][2.4/6.0MB]
[5.42 MK/s][GPU 0.00 MK/s][Count 2^29.70][Dead 0][03:02 (Avg 02:32)][2.4/6.0MB]

Key# 0 [1S]Pub: 0x02E9F43F810784FF1E91D8BC7C4FF06BFEE935DA71D7350734C3472FE305F
EF82A
Priv: 0x378ABDEC51BC5D

[ 0] 2^29.711 Dead:0 Avg:2^29.711 DeadAvg:0.0 (2^29.621)

Done: Total time 03:04

Code:

-wm save.work save2.work save3.work

Kangaroo v1.4notready
Loading: save.work
MergeWork: [HashTalbe1 2.1/4.6MB] [00s]
Loading: save2.work
MergeWork: [HashTalbe2 2.1/4.6MB] [00s]
Merging...
Range width: 2^56

SaveWork: save3.work...............done [2.5 MB] [00s] Thu May 07 19:19:00 2020
Dead kangaroo: 2
Total f1+f2: count 2^30.01 [03:47]

Code:

-i save.work

Kangaroo v1.4notready
Loading: save.work
Start:0
Stop :FFFFFFFFFFFFFF
Keys :1
LoadWork: [HashTalbe 2.1/4.6MB] [00s]
Number of CPU thread: 4
Range width: 2^56
Jump Avg distance: 2^28.01
Number of kangaroos: 2^12.00
Suggested DP: 16
Expected operations: 2^29.62
Expected RAM: 12.5MB
DP size: 16 [0xFFFF000000000000]
SolveKeyCPU Thread 0: 1024 kangaroos
SolveKeyCPU Thread 3: 1024 kangaroos
SolveKeyCPU Thread 1: 1024 kangaroos
SolveKeyCPU Thread 2: 1024 kangaroos
[7.25 MK/s][GPU 0.00 MK/s][Count 2^28.10][Dead 0][01:00 (Avg 01:53)][2.1/4.7MB]
[6.64 MK/s][GPU 0.00 MK/s][Count 2^28.19][Dead 0][01:03 (Avg 02:04)][2.1/4.7MB]
[6.15 MK/s][GPU 0.00 MK/s][Count 2^28.27][Dead 0][01:07 (Avg 02:14)][2.2/4.8MB]
[5.86 MK/s][GPU 0.00 MK/s][Count 2^28.37][Dead 0][01:12 (Avg 02:20)][2.2/4.8MB]
[5.66 MK/s][GPU 0.00 MK/s][Count 2^28.44][Dead 0][01:16 (Avg 02:25)][2.2/4.9MB]
[5.54 MK/s][GPU 0.00 MK/s][Count 2^28.52][Dead 0][01:19 (Avg 02:29)][2.2/4.9MB]
[5.52 MK/s][GPU 0.00 MK/s][Count 2^28.61][Dead 0][01:25 (Avg 02:29)][2.2/5.0MB]
[5.53 MK/s][GPU 0.00 MK/s][Count 2^28.71][Dead 0][01:31 (Avg 02:29)][2.2/5.0MB]
[5.53 MK/s][GPU 0.00 MK/s][Count 2^28.77][Dead 0][01:34 (Avg 02:29)][2.2/5.1MB]
[5.54 MK/s][GPU 0.00 MK/s][Count 2^28.82][Dead 0][01:38 (Avg 02:29)][2.2/5.1MB]
[5.54 MK/s][GPU 0.00 MK/s][Count 2^28.89][Dead 0][01:43 (Avg 02:29)][2.2/5.2MB]
[5.54 MK/s][GPU 0.00 MK/s][Count 2^28.96][Dead 0][01:48 (Avg 02:29)][2.2/5.2MB]
[5.54 MK/s][GPU 0.00 MK/s][Count 2^29.03][Dead 0][01:53 (Avg 02:29)][2.3/5.3MB]
[5.54 MK/s][GPU 0.00 MK/s][Count 2^29.08][Dead 0][01:57 (Avg 02:29)][2.3/5.3MB]
[5.54 MK/s][GPU 0.00 MK/s][Count 2^29.13][Dead 0][02:01 (Avg 02:29)][2.3/5.4MB]
[5.53 MK/s][GPU 0.00 MK/s][Count 2^29.19][Dead 0][02:07 (Avg 02:29)][2.3/5.4MB]
[5.54 MK/s][GPU 0.00 MK/s][Count 2^29.25][Dead 0][02:12 (Avg 02:29)][2.3/5.5MB]
[5.53 MK/s][GPU 0.00 MK/s][Count 2^29.29][Dead 0][02:16 (Avg 02:29)][2.3/5.5MB]
[5.53 MK/s][GPU 0.00 MK/s][Count 2^29.33][Dead 0][02:20 (Avg 02:29)][2.3/5.6MB]
[5.53 MK/s][GPU 0.00 MK/s][Count 2^29.38][Dead 0][02:25 (Avg 02:29)][2.3/5.6MB]
[5.53 MK/s][GPU 0.00 MK/s][Count 2^29.43][Dead 0][02:30 (Avg 02:29)][2.3/5.7MB]
[5.53 MK/s][GPU 0.00 MK/s][Count 2^29.47][Dead 0][02:34 (Avg 02:29)][2.3/5.7MB]
[5.53 MK/s][GPU 0.00 MK/s][Count 2^29.51][Dead 0][02:38 (Avg 02:29)][2.4/5.8MB]
[5.53 MK/s][GPU 0.00 MK/s][Count 2^29.54][Dead 0][02:42 (Avg 02:29)][2.4/5.8MB]
[5.53 MK/s][GPU 0.00 MK/s][Count 2^29.59][Dead 0][02:47 (Avg 02:29)][2.4/5.9MB]
[5.54 MK/s][GPU 0.00 MK/s][Count 2^29.63][Dead 0][02:52 (Avg 02:29)][2.4/5.9MB]
[5.53 MK/s][GPU 0.00 MK/s][Count 2^29.66][Dead 0][02:56 (Avg 02:29)][2.4/6.0MB]
[5.54 MK/s][GPU 0.00 MK/s][Count 2^29.70][Dead 0][03:00 (Avg 02:29)][2.4/6.0MB]
[5.54 MK/s][GPU 0.00 MK/s][Count 2^29.74][Dead 0][03:05 (Avg 02:29)][2.4/6.1MB]

Key# 0 [1S]Pub: 0x02E9F43F810784FF1E91D8BC7C4FF06BFEE935DA71D7350734C3472FE305F
EF82A
Priv: 0x378ABDEC51BC5D

[ 0] 2^29.325 Dead:0 Avg:2^29.325 DeadAvg:0.0 (2^29.621)

Done: Total time 03:08

HardwareCollector

Member

Offline

Activity: 144
Merit: 10

Re: Pollard's kangaroo ECDLP solver

May 07, 2020, 05:50:17 PM

#106

@Jean_Luc

Saving and merging the work across multiple machines seem to work well, tested with 80 and 85 bit intervals. Next test is to compare the run times against a single powerful machine for 90-bit intervals.

MrFreeDragon

Sr. Member

Offline

Activity: 443
Merit: 350

Re: Pollard's kangaroo ECDLP solver

May 07, 2020, 06:31:17 PM

#107

Quote from: arulbero on May 07, 2020, 03:04:08 PM

Quote from: MrFreeDragon on May 07, 2020, 12:55:36 PM

If you can store (b-a)^2/3 distinguished points,
the best things to do is to generate 1*G, 2*G, 3*G, ...., (b-a)^2/3 * G.
-snip-

That method requires (b-a)^2/3 group operations to find (b-a)^1/3 distinguished points. So, only cube root from the length should be stored, but not square root compared to baby step giant step.

Visual Private Key Generator - https://btckeygen.com

arulbero

Legendary

Offline

Activity: 2023
Merit: 2267

Re: Pollard's kangaroo ECDLP solver

May 07, 2020, 06:44:03 PM
Last edit: May 07, 2020, 07:57:34 PM by arulbero

#108

Quote from: MrFreeDragon on May 07, 2020, 06:31:17 PM

Quote from: arulbero on May 07, 2020, 03:04:08 PM

Quote from: MrFreeDragon on May 07, 2020, 12:55:36 PM

If you can store (b-a)^2/3 distinguished points,
the best things to do is to generate 1*G, 2*G, 3*G, ...., (b-a)^2/3 * G.
-snip-

That method requires (b-a)^2/3 group operations to find (b-a)^1/3 distinguished points. So, only cube root from the length should be stored, but not square root compared to baby step giant step.

Then it is much better.

With 90-bit space, you need to perform 2^60 operations to get 2^30 DP and then only 2^30 operations to retrieve each key.

But if you need to find only 2^10 private keys, it is faster to run 2^10 times the program -> 2^10*2^46 = 2^56 operations.

MrFreeDragon

Sr. Member

Offline

Activity: 443
Merit: 350

Re: Pollard's kangaroo ECDLP solver

May 07, 2020, 07:56:24 PM

#109

Jean_Luc, does this command $ ./kangaroo -wm save.work save2.work save3.work mean that two work files (save.work and save2.work) merged to the 3d file save3.work, and later all the further work is saved to save3.work file? I understood it like this.

I expected to see normal txt tables in work files

Distinguished points with distance, X, and kangaroo type. So my intention was to perform the search for the known public key (in the same range), then stop the work and manually change all the "wild" values in DP to "tame" values. After that re-start the program for the "unknown" public key. So, i wanted to test the idea about RangeWidth^(1/3) group operations (cube root instead of square root) if we have RangeWidth^(1/3) distinguished points at start.

Quote from: arulbero on May 07, 2020, 06:44:03 PM

-snip-
With 90-bit space, you need to perform 2^60 operations to get 2^30 DP and then only 2^30 operations to retrieve each key.
But if you need to find only 2^10 private keys, it is faster to run 2^10 times the program -> 2^10*2^46 = 2^56 operations.

Make sense if all the job is performed by one machine... However if the precomputation work is delegated to "free" machines/servers/users, we could benefit from these operations Wink

Visual Private Key Generator - https://btckeygen.com

MrFreeDragon

Sr. Member

Offline

Activity: 443
Merit: 350

Re: Pollard's kangaroo ECDLP solver

May 07, 2020, 11:05:29 PM

#110

Quote from: Jean_Luc on May 07, 2020, 02:50:17 PM

I made the test with separate works on GPU, merge, continue on CPU, transfer to another machine with another GPU and return back. I did not save kangaroos, only the work (so kangaroos were created again).

The test was made with 2^80 range (for info: to solve it on 4xRTX2080ti i need only 6-8 minutes).

1) I started the job with 1xRTX2080ti and had expected operations 2^41.38 and about 38min time --> made work1 for 22 min (2^40.37 operations)
2) Started the same job from the beginning on the same 1xRTX2080ti and made work2 for 2min (2^36.5 operations)
3) Merged work1 and work2 to work3, and started work3 for 1 minute
4) Continued the job on CPU (4 threads) - started and stop 3 times.
5) Transferred the job to another machine with Tesla T4 (expected time there to finish was 1:16hour with expected operations 2^41.26). I started on Tesla (continued) with 2^40.84 operations saving the work to the same file, after 7 minutes stops and start again.
6) Tesla T4 did not finish the work for expected time and operations. Actually it finished the work with total time 2:22 hour (1 hour more as expected) and with total operations 2^42.26 - actually 2 times more.

While Tesla T4 was trying to finish the job, I copied the current work file from Tesla T4 machine back to 2080ti and continued the job on the same machine there I start (continued from 2^41. Cool

I tried to continue the job 7 times - for the 1st time 2080ti solved the key for the extra 1 minute (with total operations 2^41.9), but all other 6 attempts I stopped while they reach 2^42.3 group operations (actually 2 times more than the expected).

Suggested DP on 2080ti was 18, but on Tesla T4 it was 19, however DP size was also 18 (as was started). So I do not think that different machines use different distinguish points pattern.

The feature to save work, merge work and continue work is a very good. Does this option takes care about hardware configuration change? The idea was to implement "a pause" button, and continue the "movie" later, or later on another screen.

As you developed these, probably you could understand what was the reason for such 2 times longer delay?
- Just no luck
- Creation of new kangaroos many times (instead of saving them and continue the full job)
- Configuration change (2080ti, then CPU, and then Tesla T4)

Visual Private Key Generator - https://btckeygen.com

Jean_Luc (OP)

Sr. Member

Offline

Activity: 462
Merit: 737

Re: Pollard's kangaroo ECDLP solver

May 08, 2020, 04:12:28 AM
Last edit: May 08, 2020, 05:04:16 AM by Jean_Luc

#111

Many thanks for this test @HardwareCollector and @MrFreeDragon Wink

Yes this is a bit tricky and this extra delay delay can be due to the overload of the dp. I will add note on the README about that.

First the suggested dp is a bad approximation, it needs improvement, you have to tune it manually according to available RAM and expected operation, the goal is to be as close as possible to 2sqrt(N).

When you continue a job on a different configuration, depending on how much kangaroo you have, the overload will be different, each kangaroo need 2^dp (in average) to reach a distinguished point. So if you continue on a configuration with much more kangaroo, the overload will be much higher and during the merge, it will add a count but only count/(nbKangaroo*2^dp) distinguished points to the hashtable.

Each time you do a merge, the count recorded in the merge will get an error of ~nbKangaroo*2^dp which is the counting granularity of actual distinguished point which will impact the estimation...

Another things is that when you merge 2 work files with a different dp bits, the lowest will be saved.

If you overload the dp bits by hand using -d and you choose a larger one (let's say +2), you will benefit only of 1 distinguished point on 4 in the hashtable.

Quote from: MrFreeDragon on May 07, 2020, 11:05:29 PM

However I'm also a bit surprised here, i would need more info to try to understand, especially number of kangaroo of each configuration and evolution of the number of distinguished point bits in the work files...

sssergy2705

Copper Member
Jr. Member

Offline

Activity: 205
Merit: 1

Re: Pollard's kangaroo ECDLP solver

May 08, 2020, 07:04:44 AM

#112

Quote from: Jean_Luc on May 07, 2020, 02:50:17 PM

I committed the mods. Linux user can try them. (Edit: or Windows user who compile,
I updated project files)

Good afternoon.
You can make statistics at the end of the work cycle.
It is very inconvenient to leaf through all the console output if there are several keys in the input file.

Jean_Luc (OP)

Sr. Member

Offline

Activity: 462
Merit: 737

Re: Pollard's kangaroo ECDLP solver

May 08, 2020, 07:30:50 AM

#113

The statistics will not be present in the final release.
It is more for developers.
You can remove it by removing the #define STATS in Kangaroo.cpp:796

Jean_Luc (OP)

Sr. Member

Offline

Activity: 462
Merit: 737

Re: Pollard's kangaroo ECDLP solver

May 08, 2020, 09:03:13 AM
Last edit: May 08, 2020, 09:20:02 AM by Jean_Luc

#114

I did a test:

Starting from scratch on 64bit range, save the work file every 10sec. It has solved the key in 2^33.8, a bit more than the average and the last work file at 2^33.27.

Code:

C:\C++\Kangaroo\VC_CUDA10>x64\Release\Kangaroo.exe -d 11 -t 0 -w work1.wrk -wi 10 -gpu ..\VC_CUDA8\in64.txt
Kangaroo v1.4notready
Start:5B3F38AF935A3640D158E871CE6E9666DB862636383386EE0000000000000000
Stop :5B3F38AF935A3640D158E871CE6E9666DB862636383386EEFFFFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 0
Range width: 2^64
Jump Avg distance: 2^31.99
Number of kangaroos: 2^18.58
Suggested DP: 13
Expected operations: 2^33.18
Expected RAM: 193.1MB
DP size: 11 [0xFFE0000000000000]
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 [1.9s]
[183.89 MK/s][GPU 183.89 MK/s][Count 2^29.99][Dead 0][08s (Avg 52s)][17.9/47.6MB]
SaveWork: work1.wrk...............done [18.0 MB] [00s] Fri May 8 09:37:01 2020
[151.40 MK/s][GPU 151.40 MK/s][Count 2^31.17][Dead 0][18s (Avg 01:04)][37.9/71.6MB]
SaveWork: work1.wrk...............done [38.0 MB] [00s] Fri May 8 09:37:12 2020
[149.85 MK/s][GPU 149.85 MK/s][Count 2^31.80][Dead 0][28s (Avg 01:04)][57.8/91.8MB]
SaveWork: work1.wrk...............done [57.9 MB] [00s] Fri May 8 09:37:22 2020
[148.78 MK/s][GPU 148.78 MK/s][Count 2^32.24][Dead 0][39s (Avg 01:05)][77.7/111.9MB]
SaveWork: work1.wrk...............done [77.7 MB] [00s] Fri May 8 09:37:33 2020
[147.04 MK/s][GPU 147.04 MK/s][Count 2^32.58][Dead 0][49s (Avg 01:06)][97.5/132.9MB]
SaveWork: work1.wrk...............done [97.6 MB] [00s] Fri May 8 09:37:44 2020
[145.74 MK/s][GPU 145.74 MK/s][Count 2^32.85][Dead 0][01:00 (Avg 01:06)][117.2/155.0MB]
SaveWork: work1.wrk...............done [117.2 MB] [00s] Fri May 8 09:37:55 2020
[144.31 MK/s][GPU 144.31 MK/s][Count 2^33.07][Dead 1][01:11 (Avg 01:07)][136.8/178.2MB]
SaveWork: work1.wrk...............done [136.9 MB] [01s] Fri May 8 09:38:06 2020
[143.51 MK/s][GPU 143.51 MK/s][Count 2^33.27][Dead 2][01:22 (Avg 01:07)][156.4/202.3MB]
SaveWork: work1.wrk...............done [156.5 MB] [01s] Fri May 8 09:38:17 2020
[136.98 MK/s][GPU 136.98 MK/s][Count 2^33.31][Dead 2][01:26 (Avg 01:10)][160.3/207.0MB]
Key# 0 [1S]Pub: 0x03BB113592002132E6EF387C3AEBC04667670D4CD40B2103C7D0EE4969E9FF56E4
Priv: 0x5B3F38AF935A3640D158E871CE6E9666DB862636383386EE510F18CCC3BD72EB

[ 0] 2^33.338 Dead:2 Avg:2^33.338 DeadAvg:2.0 (2^33.179)

work file info:

Code:

Loading: work1.wrk
Version: 0
DP bits: 11
Start :5B3F38AF935A3640D158E871CE6E9666DB862636383386EE0000000000000000
Stop :5B3F38AF935A3640D158E871CE6E9666DB862636383386EEFFFFFFFFFFFFFFFF
Key :03BB113592002132E6EF387C3AEBC04667670D4CD40B2103C7D0EE4969E9FF56E4
Count : 10355736576 2^33.270
Time :01:22
DP Size: 156.5/202.4MB
DP Cnt : 5063157 2^22.272
DP Max : 41 [@ 006CDC]
DP Min : 4 [@ 003037]
DP Avg : 19.31

I get this work file and restarted 10 times the search:

Code:

[ 0] 2^31.073 Dead:0 Avg:2^31.073 DeadAvg:0.0 (2^33.179)
[ 0] 2^32.051 Dead:2 Avg:2^32.051 DeadAvg:2.0 (2^33.179)
[ 0] 2^30.842 Dead:0 Avg:2^30.842 DeadAvg:0.0 (2^33.179)
[ 0] 2^31.480 Dead:1 Avg:2^31.480 DeadAvg:1.0 (2^33.179)
[ 0] 2^31.268 Dead:0 Avg:2^31.268 DeadAvg:0.0 (2^33.179)
[ 0] 2^30.116 Dead:0 Avg:2^30.116 DeadAvg:0.0 (2^33.179)
[ 0] 2^30.999 Dead:0 Avg:2^30.999 DeadAvg:0.0 (2^33.179)
[ 0] 2^32.083 Dead:1 Avg:2^32.083 DeadAvg:1.0 (2^33.179)
[ 0] 2^30.306 Dead:0 Avg:2^30.306 DeadAvg:0.0 (2^33.179)
[ 0] 2^33.031 Dead:4 Avg:2^33.031 DeadAvg:4.0 (2^33.179)

So an average of 2^31.583 (~3 times less than the average)

The dp overhead is about 2^29.58 = 2^31.583 4.
I would expect 2^31.583/3, one dp overhead when starting the first tine, one when writing the file and one when restarting the search....

If you save the kangaroo, you get rid off this extra overhead, only one when starting the first time, but you need to continue on the same hardware or on an hardware that handle all kangaroos.

Need more average and test to fully understand this...

Jean_Luc (OP)

Sr. Member

Offline

Activity: 462
Merit: 737

Re: Pollard's kangaroo ECDLP solver

May 08, 2020, 12:34:29 PM

#115

The release 1.4 is ready.
Available on github

https://github.com/JeanLucPons/Kangaroo/releases

Quote

- Added load/save/merge work file
- Memory usage improvements
- Added max step option

Thanks to test it Wink

HardwareCollector

Member

Offline

Activity: 144
Merit: 10

Re: Pollard's kangaroo ECDLP solver

May 08, 2020, 02:44:17 PM

#116

@Jean_Luc

I did some (90-bit) tests from yesterdays commit and an instance running on a single power server always seemed to solve the DL much faster, up to 2x faster in most cases than with a distributed model with distinguished point persistence. I will need to run more tests in the 100-bit range to see if this observation holds.

I do agree that its very difficult to come up with a formula for calculating the optimal distinguished point mask and memory requirements for solving large intervals 95+ bits in size with diverse hardware configurations. The issue in my case seems to be the lack of a centralized server for saving distinguished points and checking for collisions. So I came up with an idea, modify the code not to use the internal hash table, but periodically (every 5 minutes) send accumulated distinguished points to a centralized server for storage and verification. I will be testing this idea sometime this weekend for comparison against an instance running on single powerful server.

I ran some small tests with your latest commit, version 1.4; and so far it's looking good.

80-bit Default:

Code:

./Kangaroos -t 0 -gpu -gpuId 0,1,2,3,4,5,6,7 -w server_1 -wi 300 input_80_bit_interval.txt
Kangaroo v1.4
Start:7FFFFFFFFFFFFFFFFFFF
Stop :FFFFFFFFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 0
Range width: 2^80
Jump Avg distance: 2^40.03
Number of kangaroos: 2^24.09
Suggested DP: 15
Number of kangaroos: 2^24.09
Suggested DP: 15
Expected operations: 2^41.38
Expected RAM: 3350.0MB
DP size: 15 [0xfffe000000000000]
GPU: GPU #0 GeForce RTX 2080 Ti (68x64 cores) Grid(136x128) (213.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
GPU: GPU #4 GeForce RTX 2080 Ti (68x64 cores) Grid(136x128) (213.0 MB used)
SolveKeyGPU Thread GPU#4: creating kangaroos...
GPU: GPU #1 GeForce RTX 2080 Ti (68x64 cores) Grid(136x128) (213.0 MB used)
SolveKeyGPU Thread GPU#1: creating kangaroos...
GPU: GPU #5 GeForce RTX 2080 Ti (68x64 cores) Grid(136x128) (213.0 MB used)
SolveKeyGPU Thread GPU#5: creating kangaroos...
GPU: GPU #7 GeForce RTX 2080 Ti (68x64 cores) Grid(136x128) (213.0 MB used)
SolveKeyGPU Thread GPU#7: creating kangaroos...
GPU: GPU #2 GeForce RTX 2080 Ti (68x64 cores) Grid(136x128) (213.0 MB used)
SolveKeyGPU Thread GPU#2: creating kangaroos...
GPU: GPU #3 GeForce RTX 2080 Ti (68x64 cores) Grid(136x128) (213.0 MB used)
SolveKeyGPU Thread GPU#3: creating kangaroos...
GPU: GPU #6 GeForce RTX 2080 Ti (68x64 cores) Grid(136x128) (213.0 MB used)
SolveKeyGPU Thread GPU#6: creating kangaroos...
SolveKeyGPU Thread GPU#7: 2^21.09 kangaroos [21.4s]
SolveKeyGPU Thread GPU#0: 2^21.09 kangaroos [21.9s]
SolveKeyGPU Thread GPU#5: 2^21.09 kangaroos [21.5s]
SolveKeyGPU Thread GPU#3: 2^21.09 kangaroos [21.8s]
SolveKeyGPU Thread GPU#4: 2^21.09 kangaroos [22.0s]
SolveKeyGPU Thread GPU#2: 2^21.09 kangaroos [21.9s]
SolveKeyGPU Thread GPU#1: 2^21.09 kangaroos [22.0s]
SolveKeyGPU Thread GPU#6: 2^21.09 kangaroos [22.1s]
[8893.11 MK/s][GPU 8893.11 MK/s][Count 2^40.97][Dead 0][04:36 (Avg 05:22)][2009.8/2518.7MB]
SaveWork: savefile...............done [2010.0 MB] [14s] Fri May 8 13:23:32 2020
[8197.71 MK/s][GPU 8197.71 MK/s][Count 2^41.96][Dead 2][09:37 (Avg 05:49)][3980.3/4981.8MB]
SaveWork: savefile...............done [3980.5 MB] [32s] Fri May 8 13:28:51 2020
[6947.03 MK/s][GPU 6947.03 MK/s][Count 2^42.31][Dead 2][13:12 (Avg 06:52)][5077.2/6353.1MB]
Key# 0 [1S]Pub: 0x037E1238F7B1CE757DF94FAA9A2EB261BF0AEB9F84DBF81212104E78931C2A19DC
Priv: 0xEA1A5C66DCC11B5AD180

Done: Total time 14:53

80-bit d=18:

Code:

./Kangaroos -t 0 -d 18 -gpu -gpuId 0,1,2,3,4,5,6,7 -w server_2 -wi 300 input_80_bit_interval.txt
Kangaroo v1.4
Start:7FFFFFFFFFFFFFFFFFFF
Stop :FFFFFFFFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 0
Range width: 2^80
Jump Avg distance: 2^40.03
Number of kangaroos: 2^24.09
Suggested DP: 15
Expected operations: 2^42.66
Expected RAM: 1024.2MB
DP size: 18 [0xffffc00000000000]
GPU: GPU #7 GeForce RTX 2080 Ti (68x64 cores) Grid(136x128) (213.0 MB used)
SolveKeyGPU Thread GPU#7: creating kangaroos...
GPU: GPU #0 GeForce RTX 2080 Ti (68x64 cores) Grid(136x128) (213.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
GPU: GPU #5 GeForce RTX 2080 Ti (68x64 cores) Grid(136x128) (213.0 MB used)
SolveKeyGPU Thread GPU#5: creating kangaroos...
GPU: GPU #4 GeForce RTX 2080 Ti (68x64 cores) Grid(136x128) (213.0 MB used)
SolveKeyGPU Thread GPU#4: creating kangaroos...
GPU: GPU #6 GeForce RTX 2080 Ti (68x64 cores) Grid(136x128) (213.0 MB used)
SolveKeyGPU Thread GPU#6: creating kangaroos...
GPU: GPU #3 GeForce RTX 2080 Ti (68x64 cores) Grid(136x128) (213.0 MB used)
SolveKeyGPU Thread GPU#3: creating kangaroos...
GPU: GPU #2 GeForce RTX 2080 Ti (68x64 cores) Grid(136x128) (213.0 MB used)
SolveKeyGPU Thread GPU#2: creating kangaroos...
GPU: GPU #1 GeForce RTX 2080 Ti (68x64 cores) Grid(136x128) (213.0 MB used)
SolveKeyGPU Thread GPU#1: creating kangaroos...
SolveKeyGPU Thread GPU#1: 2^21.09 kangaroos [21.6s]
SolveKeyGPU Thread GPU#0: 2^21.09 kangaroos [21.8s]
SolveKeyGPU Thread GPU#5: 2^21.09 kangaroos [21.8s]
SolveKeyGPU Thread GPU#4: 2^21.09 kangaroos [21.9s]
SolveKeyGPU Thread GPU#7: 2^21.09 kangaroos [22.3s]
SolveKeyGPU Thread GPU#2: 2^21.09 kangaroos [21.9s]
SolveKeyGPU Thread GPU#6: 2^21.09 kangaroos [22.4s]
SolveKeyGPU Thread GPU#3: 2^21.09 kangaroos [24.2s]
[8860.95 MK/s][GPU 8860.95 MK/s][Count 2^40.97][Dead 0][04:34 (Avg 13:05)][252.2/321.7MB]
SaveWork: savefile...............done [252.2 MB] [02s] Fri May 8 13:41:21 2020
[8871.56 MK/s][GPU 8871.56 MK/s][Count 2^41.21][Dead 1][05:26 (Avg 13:04)][297.6/378.5MB]
Key# 0 [1S]Pub: 0x037E1238F7B1CE757DF94FAA9A2EB261BF0AEB9F84DBF81212104E78931C2A19DC
Priv: 0xEA1A5C66DCC11B5AD180

Done: Total time 05:55

Jean_Luc (OP)

Sr. Member

Offline

Activity: 462
Merit: 737

Re: Pollard's kangaroo ECDLP solver

May 08, 2020, 03:09:42 PM

#117

Thanks again for the tests Wink

What you can try is to store the work file on a NFS mount and write a script on an other host that check for collision using -wm option.
That should be more or less equivalent to what you suggest.
Of course, using a centralized server is much more convenient.
Interesting, i know rather well socket and I have good experience with server coding, so that should not be too hard to write an efficient distributed solution.

Edit: Don't forget to update you repository Wink

MrFreeDragon

Sr. Member

Offline

Activity: 443
Merit: 350

Re: Pollard's kangaroo ECDLP solver

May 08, 2020, 04:21:10 PM

#118

Quote from: HardwareCollector on May 08, 2020, 02:44:17 PM

-snip-
Start:7FFFFFFFFFFFFFFFFFFF
Stop :FFFFFFFFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 0
Range width: 2^80
.....
Done: Total time 14:53

In you test you used 8xRTX2080ti. It strange for me why you spent 15 minutes to solve one key. Some earlier I made the test for 80bit range with 4xRTX2080ti and in all cases the key was solved for 6-7 minutes. I guess that your result 15 minutes some wrong one.

For test I used the key from the repository VC_CUDA8/in80.txt
This key is "in open space", not shifted to 0 value.

Code:

TEST1:

$ ./kangaroo -gpu -gpuId 0,1,2,3 -t 0 VC_CUDA8/in80.txt
Kangaroo v1.4beta
Start:B60E83280258A40F9CDF1649744D730D6E939DE92A2B00000000000000000000
Stop :B60E83280258A40F9CDF1649744D730D6E939DE92A2BE19BFFFFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 0
Range width: 2^80
Jump Avg distance: 2^39.97
Number of kangaroos: 2^23.09
Suggested DP: 15
Expected operations: 2^41.15
Expected RAM: 5672.9MB
DP size: 15 [0xfffe000000000000]
GPU: GPU #0 GeForce RTX 2080 Ti (68x64 cores) Grid(136x128) (213.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
GPU: GPU #1 GeForce RTX 2080 Ti (68x64 cores) Grid(136x128) (213.0 MB used)
SolveKeyGPU Thread GPU#1: creating kangaroos...
GPU: GPU #3 GeForce RTX 2080 Ti (68x64 cores) Grid(136x128) (213.0 MB used)
SolveKeyGPU Thread GPU#3: creating kangaroos...
GPU: GPU #2 GeForce RTX 2080 Ti (68x64 cores) Grid(136x128) (213.0 MB used)
SolveKeyGPU Thread GPU#2: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^21.09 kangaroos in 12460.6ms
SolveKeyGPU Thread GPU#1: 2^21.09 kangaroos in 13354.0ms
SolveKeyGPU Thread GPU#2: 2^21.09 kangaroos in 14831.5ms
SolveKeyGPU Thread GPU#3: 2^21.09 kangaroos in 15159.3ms
[4917.62 MK/s][GPU 4917.62 MK/s][Count 2^40.26][Dead 0][05:04 (Avg 08:15)][3066.1MB]
Key# 0 Pub: 0x0284A930C243C0C2F67FDE3E0A98CE6DB0DB9AB5570DAD9338CADE6D181A431246
Priv: 0xB60E83280258A40F9CDF1649744D730D6E939DE92A2BE19B0D19A3D64A1DE032

Done: Total time 05:49

------------------------------------------------------------------

TEST2:

$ ./kangaroo -gpu -gpuId 0,1,2,3 -t 0 VC_CUDA8/in80.txt
Kangaroo v1.4beta
Start:B60E83280258A40F9CDF1649744D730D6E939DE92A2B00000000000000000000
Stop :B60E83280258A40F9CDF1649744D730D6E939DE92A2BE19BFFFFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 0
Range width: 2^80
Jump Avg distance: 2^40.04
Number of kangaroos: 2^23.09
Suggested DP: 15
Expected operations: 2^41.15
Expected RAM: 5672.9MB
DP size: 15 [0xfffe000000000000]
GPU: GPU #0 GeForce RTX 2080 Ti (68x64 cores) Grid(136x128) (213.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
GPU: GPU #1 GeForce RTX 2080 Ti (68x64 cores) Grid(136x128) (213.0 MB used)
SolveKeyGPU Thread GPU#1: creating kangaroos...
GPU: GPU #2 GeForce RTX 2080 Ti (68x64 cores) Grid(136x128) (213.0 MB used)
SolveKeyGPU Thread GPU#2: creating kangaroos...
GPU: GPU #3 GeForce RTX 2080 Ti (68x64 cores) Grid(136x128) (213.0 MB used)
SolveKeyGPU Thread GPU#3: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^21.09 kangaroos in 12070.3ms
SolveKeyGPU Thread GPU#3: 2^21.09 kangaroos in 12887.1ms
SolveKeyGPU Thread GPU#1: 2^21.09 kangaroos in 13696.3ms
SolveKeyGPU Thread GPU#2: 2^21.09 kangaroos in 14832.6ms
[4925.05 MK/s][GPU 4925.05 MK/s][Count 2^40.61][Dead 0][06:28 (Avg 08:14)][3907.7MB]
Key# 0 Pub: 0x0284A930C243C0C2F67FDE3E0A98CE6DB0DB9AB5570DAD9338CADE6D181A431246
Priv: 0xB60E83280258A40F9CDF1649744D730D6E939DE92A2BE19B0D19A3D64A1DE032

Done: Total time 07:19

------------------------------------------------------------------

TEST3 (the same key repeated 3 times, and shift range to the end (close to order)):

$ ./kangaroo -gpu -gpuId 0,1,2,3 -t 0 in80order.txt
Kangaroo v1.4beta
Start:FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF47BE9FBFD25E8CD0364141
Stop :FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140
Keys :3
Number of CPU thread: 0
Range width: 2^80
Jump Avg distance: 2^40.01
Number of kangaroos: 2^23.09
Suggested DP: 15
Expected operations: 2^41.15
Expected RAM: 5672.9MB
DP size: 15 [0xfffe000000000000]
GPU: GPU #1 GeForce RTX 2080 Ti (68x64 cores) Grid(136x128) (213.0 MB used)
SolveKeyGPU Thread GPU#1: creating kangaroos...
GPU: GPU #0 GeForce RTX 2080 Ti (68x64 cores) Grid(136x128) (213.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
GPU: GPU #3 GeForce RTX 2080 Ti (68x64 cores) Grid(136x128) (213.0 MB used)
SolveKeyGPU Thread GPU#3: creating kangaroos...
GPU: GPU #2 GeForce RTX 2080 Ti (68x64 cores) Grid(136x128) (213.0 MB used)
SolveKeyGPU Thread GPU#2: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^21.09 kangaroos in 12114.8ms
SolveKeyGPU Thread GPU#3: 2^21.09 kangaroos in 12728.4ms
SolveKeyGPU Thread GPU#2: 2^21.09 kangaroos in 13667.7ms
SolveKeyGPU Thread GPU#1: 2^21.09 kangaroos in 14680.0ms
[4907.53 MK/s][GPU 4907.53 MK/s][Count 2^38.75][Dead 0][01:46 (Avg 08:16)][1080.8MB]
Key# 0 Pub: 0x033F93598445D64434F6D8F92621EBA31346864990095A13D142E8E83D5CC701EB
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03ACCEC02631A542173
[4905.64 MK/s][GPU 4905.64 MK/s][Count 2^41.11][Dead 0][09:24 (Avg 08:16)][5515.9MB]
Key# 1 Pub: 0x033F93598445D64434F6D8F92621EBA31346864990095A13D142E8E83D5CC701EB
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03ACCEC02631A542173
[4904.92 MK/s][GPU 4904.92 MK/s][Count 2^40.40][Dead 0][05:52 (Avg 08:16)][3391.6MB]
Key# 2 Pub: 0x033F93598445D64434F6D8F92621EBA31346864990095A13D142E8E83D5CC701EB
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03ACCEC02631A542173

Done: Total time 18:50

So, in all cases the average time to solve 80bit range with 4x2080ti was 6-7 minutes

Visual Private Key Generator - https://btckeygen.com

HardwareCollector

Member

Offline

Activity: 144
Merit: 10

Re: Pollard's kangaroo ECDLP solver

May 08, 2020, 05:42:15 PM

#119

Quote from: MrFreeDragon on May 08, 2020, 04:21:10 PM

I am not that surprised because hardware configurations do matter, which seems to be an issue on my end. The optimal number of kangaroos launched and distinguished point mask is based on your hardware configuration. Ideally, with a centralized server implementation, it should be solely based on the interval size and TMTO that you are satisfied with.

Jean_Luc (OP)

Sr. Member

Offline

Activity: 462
Merit: 737

Re: Pollard's kangaroo ECDLP solver

May 08, 2020, 05:53:00 PM

#120

@MrFreeDragon
You have to take in consideration that on this first test it has written a ~2GB file and ~4GB one and created 2^24 kangaroos.
On the second with DP18 and 2^24, this gives an overhead of ~2^42 so more than the average, however it was solved solved in only 2^41, more than 2 time less than expected, he was lucky

This is the problem of multiple powerful GPU, with 2^24 kangaroos, 80bit range is a too small range.
The client/server mode is a good idea as it will avoid memory consumption on the client side, but the server should be well tuned., the overhead due to DP still apply.

@HardwareCollector

I agree

Pages: « 1 2 3 4 5 [6] 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 ... 146 »

Page 5

Viewing Page: 6