Pollard's kangaroo ECDLP solver

[MrFreeDragon]

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.

110 solve depend on multiple pubkeys search at once, in others , you all will spend time in jumping here and there, mean you need lot of gpu powers, you need lot of ram, etc, and you can not manage all things togather, and no one have these all option available, only my last word, if you design multiple pubkeys search ver, that will be solution for just within 3 days
Enjoy your research!!!

I am not sure the multiple pubkey search will really help to solve #110 within 3 days.
As I see your idea is to "decrease" the pow of the key and solve the lower bits key, however decreasing the power you will also receive the incorrect public keys which will be the dust for you and will "burn" the resources.

This is the example what you want to do (correct me if I am not right):
1) The key #110 (with kno public key P110) has range with width 2^109 (start range is 2^109, end range is 2^110-1). To solve it, the current GPU solver needs approx. 2.22*sqrt(2^109) = 2^55.65
2) You want to divide this key by some number and receive the "lower bit" public key and solve that new one. Let's imagine you want to receive the key with range 2^90 instead of 2^109, so you need to divide by 2^(109-90) = 2^19 = 524 288. However as you do not know the remainder from that division you should check all the keys.
3) You  make 2^19 (524 288) additions (or divisions, it does not matter) of P110 with points 0*G, 1*G, 2*G, 3*G, ... 2^19-1*G (total 2^19 points) and receive 2^19 new points. All these new points are subsequent points, and the scalar of one of that points could be divided by 2^19 with 0 remainder.
4) Now you divide (i.e multiply by inverse scalar) every of these new points by 2^19, and receive another set of 2^19 points, where one of them will be in range 2^90
5) New range for that divided points is now from 2^90 to 2^91-1 (with width exactly 2^90).

However, you do not know which point from generated 2^19 is that one with the private key in the new range. So you should check all of them, all 524 288 points (2^19). Yes, the solver could find 90 bit range for some hours, but only for one key to search. If you put 2^19 public keys, (a) the speed will not be the same as for one, (b) you will have "wrong" DPs in the hashtable generated by wild kangaroos started from "wrong" points. Only 1 point from 2^19 is correct, others are wrong and will never solved (because of the incorrect range for them).

Now, let's calculate the number of operations required to solve these 2^19 new public keys with new ranges (with one key in range 2^90). For one key, the total number of operations is 2.22*sqrt(2^90) = 2^46.15; However we have not one, but 2^19 key to check. So, the total number of operations for all new generated public keys is 2^19 * 2^46.15 = 2^65.15

So, with the whole range you could solve the key for 2^55.65 operations, but now need 2^65.15 operations. This is 725 times more (2^9.5)

Moreover, this approximation does not count the new overheads due to incorrect DPs in hashtable.
Even you have several independent public keys in the same range, running their solving altogether at the same time will proportionally decrease the speed to find the collision.

[brainless]

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.

110 solve depend on multiple pubkeys search at once, in others , you all will spend time in jumping here and there, mean you need lot of gpu powers, you need lot of ram, etc, and you can not manage all things togather, and no one have these all option available, only my last word, if you design multiple pubkeys search ver, that will be solution for just within 3 days
Enjoy your research!!!

I am not sure the multiple pubkey search will really help to solve #110 within 3 days.
As I see your idea is to "decrease" the pow of the key and solve the lower bits key, however decreasing the power you will also receive the incorrect public keys which will be the dust for you and will "burn" the resources.

This is the example what you want to do (correct me if I am not right):
1) The key #110 (with kno public key P110) has range with width 2^109 (start range is 2^109, end range is 2^110-1). To solve it, the current GPU solver needs approx. 2.22*sqrt(2^109) = 2^55.65
2) You want to divide this key by some number and receive the "lower bit" public key and solve that new one. Let's imagine you want to receive the key with range 2^90 instead of 2^109, so you need to divide by 2^(109-90) = 2^19 = 524 288. However as you do not know the remainder from that division you should check all the keys.
3) You  make 2^19 (524 288) additions (or divisions, it does not matter) of P110 with points 0*G, 1*G, 2*G, 3*G, ... 2^19-1*G (total 2^19 points) and receive 2^19 new points. All these new points are subsequent points, and the scalar of one of that points could be divided by 2^19 with 0 remainder.
4) Now you divide (i.e multiply by inverse scalar) every of these new points by 2^19, and receive another set of 2^19 points, where one of them will be in range 2^90
5) New range for that divided points is now from 2^90 to 2^91-1 (with width exactly 2^90).

However, you do not know which point from generated 2^19 is that one with the private key in the new range. So you should check all of them, all 524 288 points (2^19). Yes, the solver could find 90 bit range for some hours, but only for one key to search. If you put 2^19 public keys, (a) the speed will not be the same as for one, (b) you will have "wrong" DPs in the hashtable generated by wild kangaroos started from "wrong" points. Only 1 point from 2^19 is correct, others are wrong and will never solved (because of the incorrect range for them).

Now, let's calculate the number of operations required to solve these 2^19 new public keys with new ranges (with one key in range 2^90). For one key, the total number of operations is 2.22*sqrt(2^90) = 2^46.15; However we have not one, but 2^19 key to check. So, the total number of operations for all new generated public keys is 2^19 * 2^46.15 = 2^65.15

So, with the whole range you could solve the key for 2^55.65 operations, but now need 2^65.15 operations. This is 725 times more (2^9.5)

Moreover, this approximation does not count the new overheads due to incorrect DPs in hashtable.
Even you have several independent public keys in the same range, running their solving altogether at the same time will proportionally decrease the speed to find the collision.

Dear Friends
your mention method of division pubkeys point, are an other way, and maybe not workable as you said, my Proof of Exact 1 key inside low pow you tested,
you stated " total number of operations for all new generated public keys is 2^19 * 2^46.15 = 2^65.15 "
its also not multi pubkeys search method, its look like each key create its own dp points, and start, and think 2**19 point how much ram you need, ? here for 1 key in big range peoples facing ram problem.
its already i mention in above my message
multi pubkey search will be multi pubkeys support ver
example
bitcrack load 1 key my gpu 45mkeys, 100k keys load 40mkeys, gradually last 25 million keys load 33mkeys, and 925mb/1gb ram used for 25m keys,
similar when  kangaroo ver support multiple pubkeys checking, it show decress speed some how 10% 20% etc, not like " total number of operations for all new generated public keys is 2^19 * 2^46.15 = 2^65.15"
Jean Luc understand how multikey search could work,
hope you all will have ability to understand what method could be applied for multi support

[HardwareCollector]

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.

N = Interval size, number of group elements.
Then, with current implementation, most instances will be solved between ~(1/2)(sqrt(N)) and ~(7)(sqrt(N)) number of group operations, with the average case being ~(2)(sqrt(N)).

If we set the distinguished points (DP) mask to 23-bit, then the number of DPs needed to solve the #110 challenge will fall within ~1.519G (very lucky) to 21.259G (very unlucky). Obviously, for each additional bit that we add to the DP mask, we reduce the storage requirements by a factor of two, but may also increase the solution time.

We need ~16-bytes for each DP: 8-btyes for x-coordinate, 1-byte for herd type, 5-bytes for slow storage lookup index, and 2-bytes for hash table overhead. So we only need ~22.64GiB (very lucky) to ~333.68GiB (very unlucky) of RAM with DP=23.

If increasing DP mask doesn’t adversely affect the solution time by much, then I can see the following challenges falling before the end of this year: #110, #115, and #120.


I've solved several instances of the DLP where the solution's number of expected operations were on the very lucky side. The frequency increased as DP mask was lowered:

Code:

./dlpserver in80.txt
ECDLP Server Started and Listening on Port 8090...
ECDLP File Merger Process Started...
Exiting File Merger Process...
Receiving savefile_1589254133 (11458340 bytes)
Loading: savefile_1589254133
MergeWork: [HashTalbe 2.0/4.0MB] [00s]
Appending...
Range width: 2^80
Dead kangaroo: 0
DP[16-bit]: count 2^18.16 [12s] Calculated Operations:[2^34.16]
Receiving savefile_1589254163 (19464260 bytes)
Loading: savefile_1589254163
MergeWork: [HashTalbe 10.9/34.4MB] [00s]
Appending...
Range width: 2^80
Dead kangaroo: 0
DP[16-bit]: count 2^19.67 [42s] Calculated Operations:[2^35.67]
.
.
.
Receiving savefile_1589254864 (19403588 bytes)
Loading: savefile_1589254864
MergeWork: [HashTalbe 389.8/493.7MB] [00s]
Appending...
Range width: 2^80
Dead kangaroo: 0
DP[16-bit]: count 2^23.66 [12:22] Calculated Operations:[2^39.66]
Receiving savefile_1589254894 (19371428 bytes)
Loading: savefile_1589254894
MergeWork: [HashTalbe 406.3/514.4MB] [00s]
Appending...
Range width: 2^80

Start:80000000000000000000
Stop :17FFFFFFFFFFFFFFFFFFF
Key# 0 [1S]Pub:  0x037E1238F7B1CE757DF94FAA9A2EB261BF0AEB9F84DBF81212104E78931C2A19DC
       Priv: 0xEA1A5C66DCC11B5AD180

Done: Total time 12:22

Code:

./dlpserver in79.txt
ECDLP Server Started and Listening on Port 8090...
ECDLP File Merger Process Started...
Exiting File Merger Process...
Receiving savefile_1589205241 (39837508 bytes)
Loading: savefile_1589205241
MergeWork: [HashTalbe 2.0/4.0MB] [00s]
Appending...
Range width: 2^79
Dead kangaroo: 0
DP[14-bit]: count 2^20.17 [12s] Calculated Operations:[2^34.17]
.
.
.
Receiving savefile_1589205739 (71532132 bytes)
Loading: savefile_1589205739
MergeWork: [HashTalbe 1033.3/1298.1MB] [00s]
Appending...
Range width: 2^79
Dead kangaroo: 0
DP[14-bit]: count 2^25.10 [08:30] Calculated Operations:[2^39.10]
Receiving savefile_1589205770 (71452420 bytes)
Loading: savefile_1589205770
MergeWork: [HashTalbe 1099.5/1380.9MB] [00s]
Appending...
Range width: 2^79

Start:80000000000000000000
Stop :FFFFFFFFFFFFFFFFFFFF
Key# 0 [1S]Pub:  0x037E1238F7B1CE757DF94FAA9A2EB261BF0AEB9F84DBF81212104E78931C2A19DC
       Priv: 0xEA1A5C66DCC11B5AD180

Done: Total time 08:30

Code:

./Kangaroos -t 0 -d 14 -gpu -gpuId 0,1 in80.txt
Kangaroo v1.5alpha
Start:100000000000000000000
Stop :1FFFFFFFFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 0
Range width: 2^80
Jump Avg distance: 2^40.03
Number of kangaroos: 2^21.52
Suggested DP: 18
Expected operations: 2^41.09
Expected RAM: 5443.0MB
DP size: 14 [0xfffc000000000000]
GPU: GPU #0 GeForce RTX 2070 (36x64 cores) Grid(72x128) (117.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
GPU: GPU #1 GeForce GTX 1080 Ti (28x128 cores) Grid(56x256) (177.0 MB used)
SolveKeyGPU Thread GPU#1: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.17 kangaroos [10.3s]
SolveKeyGPU Thread GPU#1: 2^20.81 kangaroos [16.1s]
[1346.70 MK/s][GPU 1346.70 MK/s][Count 2^40.55][Dead 0][22:42 (Avg 28:52)][2995.6/3751.0MB]
Key# 0 [1S]Pub:  0x035E9F3C5AA41562E796041B0AA65EAE3E1ECD6E9000C246E617F9E8580634DBE1
       Priv: 0x1FFFFFFFFFFFFFFFFFFFE

Done: Total time 23:32

[MrFreeDragon]

Can you please describe what does these stats mean in workfile info (showed with -winfo):

HT Max    : 9 [@ 01598C]
HT Min    : 0 [@ 000003]
HT Avg    : 0.88
HT SDev   : 0.94

All other stats are clear.

PS. Some small misprint also in usage section README.md: -gpuId gpuId1,gpuId2,...: List of GPU(s) to use, default is 0 (Id missed)
Also in all headers of all your files there a first line:  * This file is part of the BSGS distribution (https://github.com/JeanLucPons/Kangaroo)
However BSGS remained from baby step giant step as I understand.

[Jean_Luc]

Hi,

I'm working on the client/server solution.
Almost ready, commit probably tomorrow.
Difficulty to find an efficient protocol for handling dead kangaroo and server backup.

@MrFreeDragon

HT Max    : 9 [@ 01598C]
HT Min    : 0 [@ 000003]
HT Avg    : 0.88
HT SDev   : 0.94

This is the distribution of DP in the HashTable:
9 DP at hash 01598C (largest entry)
0 DP at hash 000003 (smallest)
0.88 DP per hash in average
0.94 standard deviation of DP distribution in the HashTable

@Hardware collector:
I'm sure you will solve the #110
With the client/server version, only the server (without GPU) will need a large amount of memory.

@arulbero
I didn't worked yet on endomorphism optimization and studied your proposal.
I will be on holidays (in mountains, far from computer) the next week, I would like to try to publish the client/server release first...

[Jean_Luc]

A first draft of the client/server is ready on github (source only).
The client and server can be run on both windows or linux.
There is few words on the readme.
Thanks to test it

[Etar]

A first draft of the client/server is ready on github (source only).
The client and server can be run on both windows or linux.
There is few words on the readme.
Thanks to test it

Can you make release?

[Jean_Luc]

Done
Release 1.5alpha
https://github.com/JeanLucPons/Kangaroo/releases

[Etar]

Done
Release 1.5alpha
https://github.com/JeanLucPons/Kangaroo/releases

many thanks

client:

Code:

RecvFromServer(Status): The operation timed out

server:

Code:

WriteError(Status): ╤фxыpэp яюя√Єъp т√яюыэшЄ№ юяxЁpЎш■ эp юc·xъЄx, эx  ты ■∙xьё  ёюъxЄюь.

edit:
server:

Code:

Closing connection with

and server app crash

server:

Code:

ReadError(nbDP): ╤фxыpэp яюя√Єъp т√яюыэшЄ№ юяxЁpЎш■ эp юc·xъЄx, эx  ты ■∙xьё  ёюъxЄюь.
WriteError(Status): ╤фxыpэp яюя√Єъp т√яюыэшЄ№ юяxЁpЎш■ эp юc·xъЄx, эx  ты ■∙xьё  ёюъxЄюь.
WriteError(Status): ╤фxыpэp яюя√Єъp т√яюыэшЄ№ юяxЁpЎш■ эp юc·xъЄx, эx  ты ■∙xьё  ёюъxЄюь.

and server app crash

in English it looks like An attempt was made to perform an operation on an object that is not a socket

[Jean_Luc]

lol
Not very good !
The error messages with windows are the hell with FormatMessage() and MAKELANGID
Could you starts the server and post the full ouput ?
Same for one client
Thanks

[patatasfritas]

Works fine. Tested with 65bits key and 3 clients in same network.

Code:

[Client 3][DP Count 2^14.39/2^13.05][Dead 0][01:50][2.7/7.2MB]
Key# 0 [1S]Pub:  0x0230210C23B1A047BC9BDBB13448E67DEDDC108946DE6DE639BCC75D47C0216B1B
       Priv: 0x1A838B13505B26867

Closing connection with

Closing connection with X.X.X.X:47611

Closing connection with

I've a gpu client outside Kangaroo server network. By the moment i'm using SSH tunnel, but the connection isn't perfect.

Code:

ssh user@kangarooServer -L 17403:127.0.0.1:17403

Code:

kangaroo -c 127.0.0.1

It would be interesting if the client could operate without a permanent connection to the kangaroo server.

[Jean_Luc]

Thanks for the test
A http like connection is very unefficient. I tried this first but it slows down the client.
I will see what I can do.
I didn't try through a ssh tunnel.

[Etar]

lol
Not very good !
The error messages with windows are the hell with FormatMessage() and MAKELANGID
Could you starts the server and post the full ouput ?
Same for one client
Thanks

With 1 client there no problem
Once added new client got this

Code:

Kangaroo v1.5alpha
Start:80000000000000000000
Stop :FFFFFFFFFFFFFFFFFFFF
Keys :1
Range width: 2^79
Expected operations: 2^40.55
Expected RAM: 481.9MB
DP size: 17 [0xFFFF800000000000]
Kangaroo server is ready and listening to TCP port 17403 ...
[Client 0][DP Count 2^-inf/2^23.55][Dead 0][32s][2.0/4.0MB]
New connection from X.X.X.X:62788
[Client 1][DP Count 2^21.74/2^23.55][Dead 0][07:40][109.1/145.8MB]
New connection from X.X.X.X:61719
[Client 2][DP Count 2^21.84/2^23.55][Dead 0][08:06][116.3/154.0MB]
WriteError(Status): ╤фxыpэp яюя√Єъp т√яюыэшЄ№ юяxЁpЎш■ эp юc·xъЄx, эx  ты ■∙xьё  ёюъxЄюь.

[Client 3][DP Count 2^22.06/2^23.55][Dead 0][08:34][135.9/177.1MB]
WriteError(Status): ╤фxыpэp яюя√Єъp т√яюыэшЄ№ юяxЁpЎш■ эp юc·xъЄx, эx  ты ■∙xьё  ёюъxЄюь.

[Client 4][DP Count 2^22.08/2^23.55][Dead 0][08:40][137.5/179.0MB]
SaveWork: test1..........

and crash in save

[Jean_Luc]

I managed to reproduce the issue with the windows server.
I'll have a look on that

[Jean_Luc]

I managed to reproduce the issue with the windows server.
I'll have a look on that

Fixed in 1.5alpha2

[Etar]

I managed to reproduce the issue with the windows server.
I'll have a look on that

Fixed in 1.5alpha2

Work like sharm! Excellent! (little bit dropped speed from 1450Mkey/s to 1340Mkey/s, but this is not so important compared to what can be done distributed now)
I think you made a very important and big step!

[Jean_Luc]

Yes the problem is the server. if it gets too much points it will slow down all clients.
You have to carefully deal with the distinguished bit number in order to avoid to flood the server and get a reasonable TMTO.
The server needs RAM and a powerful CPU.
At the server side the insertion and collision check is not parallelized (difficult to do).
Still possible to have several servers and to merge work files coming from servers.

[Etar]

-snip-
Still possible to have several servers and to merge work files coming from servers.

about this.. i do programm that ckeck saved work and send this work to server. All work saved with flag -ws.
server merged each this works and looks at the message in the console when merging.
readme.md say that during merge can be solved key.
But i do not understand how it can be solved if client finished job when found key and do not save last job which can be send to server and solved by server...
So client found the key and the program ended and the last job was not sent even not saved..

[Etar]

I managed to reproduce the issue with the windows server.
I'll have a look on that

Fixed in 1.5alpha2

Client:

Code:

Kangaroo v1.5alpha2
Number of CPU thread: 0
Succesfully connected to server: X.X (Version 1)
Range width: 2^109
Jump Avg distance: 2^54.00
Number of kangaroos: 2^21.09
DP size: 31 [0xFFFFFFFE00000000]
GPU: GPU #0 GeForce RTX 2080 Ti (68x64 cores) Grid(136x128) (213.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^21.09 kangaroos [14.9s]
[1322.96 MK/s][GPU 1322.96 MK/s][Count 2^40.08][16:37][Server     OK]
SendToServer(Status): ╙фpыxээ√щ їюёЄ яЁшэєфшЄxы№эю ЁpчюЁтpы ёє∙xёЄтє■∙xx яюфъы■ўxэшx.

[1302.97 MK/s][GPU 1302.97 MK/s][Count 2^40.91][35:12][Server     OK]
ReadError(Status): ╙фpыxээ√щ їюёЄ яЁшэєфшЄxы№эю ЁpчюЁтpы ёє∙xёЄтє■∙xx яюфъы■ўxэшx.

[0.00 MK/s][GPU 0.00 MK/s][Count 2^40.91][36:32][Server  Fault]

server:

Code:

Kangaroo v1.5alpha2
Loading: workfin2
Start:2000000000000000000000000000
Stop :3FFFFFFFFFFFFFFFFFFFFFFFFFFF
Keys :1
LoadWork: [HashTable 23.3/55.1MB] [00s]
Range width: 2^109
Expected operations: 2^55.55
Expected RAM: 951.7MB
DP size: 31 [0xFFFFFFFE00000000]
Kangaroo server is ready and listening to TCP port 17403 ...
[Client 5][DP Count 2^19.42/2^24.55][Dead 0][02:32][23.3/55.1MB]
Closing connection with X.X.X.X:32766
[Client 4][DP Count 2^19.42/2^24.55][Dead 0][10:00][23.4/55.2MB]
SaveWork: workfin2...............done [23.4 MB] [00s] Wed May 13 17:37:47 2020
[Client 4][DP Count 2^19.42/2^24.55][Dead 0][12:56][23.4/55.2MB]
E:\kangaroo>pause

server quit without any error.

[Jean_Luc]

I made an other fix 1.5alpha3, hope it solve the issue.
I will also get rid of from the Windows error message system which is quite inconvenient !
A client cannot solve a key as it does not perform collision check, it just calculate path and send DP to the server.