Pollard's kangaroo ECDLP solver - page 135.

Jean_Luc

sr. member

Activity: 462

Merit: 696

I'm not really surpirsed.
The key you search is the worst case.
When searching a key near to the border, you have only one half of tame and wild that overlap.
In that case you need ~22 times more DP than expected, this can happen Sad

If you count the total number of jumps:
Each time you restart from scratch a program (or a client), you have the overhead of nbKangaroo*2^dpbit, this is the average time that each kangqroo produce a DP.
This is why you need an nbKangaroo*2^dpbit the lowest possible compare to sqrt(N).

Code:

Tame:   [0.......................N]
Wild:               [-N/2+k..............N/2+k]
k is the key to search

To improve the search on the border it is possible to have a non uniform sampling and increasing kangaroo density near the border, it compensates a bit.

HardwareCollector

member

Activity: 144

Merit: 10

@Jean_Luc

I performed a small test late last night and the results were quite surprising. So in theory this can happen, unless I’m overlooking something obvious. Please see the output from Run 4, ~43.4(sqrt(N)). I am going to code a very simple version of Pollard’s Kangaroo algorithm to see if this behavior holds.

Run: 1

Code:

./Kangaroos -w MasterSavefile -wi 300 -s -d 24 in85.txt

Run: 2

Code:

./Kangaroos -i MasterSavefile -w MasterSavefile -wi 300 -s -d 24 in85.txt

Run: 3

Code:

./Kangaroos -i MasterSavefile -w MasterSavefile -wi 300 -s -d 24 in85.txt

Run: 4

Code:

./Kangaroos -i MasterSavefile -w MasterSavefile -wi 300 -s -d 24 in85.txt
Kangaroo v1.5
Loading: MasterSavefile
Start:2000000000000000000000
Stop :3FFFFFFFFFFFFFFFFFFFFF
Keys :1
LoadWork: [HashTable 458.6/579.8MB] [01s]
Range width: 2^85
Expected operations: 2^43.55
Expected RAM: 41.4MB
DP size: 24 [0xffffff0000000000]
Kangaroo server is ready and listening to TCP port 9123 ...
[Client 0][DP Count 2^23.83/2^19.55][Dead 0][04s][458.6/579.8MB]
New connection from 172.20.1.10:36914
[Client 1][DP Count 2^23.83/2^19.55][Dead 0][08s][458.6/579.8MB]
New connection from 172.20.1.11:40098
[Client 2][DP Count 2^23.84/2^19.55][Dead 0][04:58][459.8/581.3MB]
SaveWork: MasterSavefile...............done [459.8 MB] [13s] Fri May 15 00:35:46 2020
.
.
.
[Client 2][DP Count 2^23.94/2^19.55][Dead 0][02:15:24][491.6/620.9MB]
SaveWork: MasterSavefile...............done [491.6 MB] [13s] Fri May 15 02:46:12 2020
[Client 2][DP Count 2^23.94/2^19.55][Dead 0][02:20:24][492.8/622.4MB]
SaveWork: MasterSavefile...............done [492.8 MB] [13s] Fri May 15 02:51:13 2020
[Client 2][DP Count 2^23.94/2^19.55][Dead 1][02:25:21][493.9/623.9MB]
Key# 0 [1S]Pub:  0x0276229F0C29917272A22FBB7DE39DF2606B4B0CAA03669C8CAA8D16CEAC512F47
       Priv: 0x3FFFFFFFFFFFFFFFEFFFFF

Closing connection with 172.20.1.10:36914

Closing connection with 172.20.1.11:40098

PietCoin97

jr. member

Activity: 91

Merit: 3

A question for understanding.

Workfiles can be merge with same Keyspace and same dp numbers and same key for search.

When it's not the same we have to use the - ws Funktion.

And it only make sense merge safe work file from maybe running one day with safe.work1 and secound day with safe.work2

But when we restart the kangaroo process it everytime take new random points but are these random points all saved in one work file or only the last random points what was created?

Jean_Luc

sr. member

Activity: 462

Merit: 696

No there is no feedback yet from the server to kill kangaroos which collide in same herd.
This is tricky to implement but possible.
On the other hand, this kind of collision is rather rare (up to 2sqrt(N) total jumps) and if you start to have too much collisions, it is better to restart all clients in order to re-randomize all starting points.

MrFreeDragon

sr. member

Activity: 443

Merit: 350

Does the server perform synchronization with all its clients and kill "looped" kangaroos? Or the server only listens to clients, collect works files and search for collision without feedback to clients?

j2002ba2

full member

Activity: 206

Merit: 447

In order for a collision to happen, one needs at least 1 DP per kangaroo. This is the absolute minimum. In my software (June 26 - July 5, 2019) I was targeting 8 DP/kangaroo at 100% expected jumps. Then my very simple hash table was with max 2³² entries, but DPs were limited to 2²⁹ entries (IIRC 2²⁸ for #95). The whole program was using 48GB for the data - 32GB for DP, 16GB for hash table. For #95 2^27.79 points were used at 86.55%, for #100 2^26.97 at 69.1%. All the DPs were written to file, there was no performance difference on the AWS instance (p3.8xlarge). The file was write-only, since I never needed to read from it, software just found the keys.

In my experiments collision was happening between 3 and 12 DP/kangaroo. There was never tame/tame or wild/wild collision, since I used the original Pollard Kangaroo, no wrapping around 0 or other funky stuff - IMO it would make it faster in half of the cases, and way slower in the other half, when it's negative.

I was using 72*512*256 = 3²2²⁰ kangaroos per GPU. So for #110 if one is using the same number of kangaroos on 128 GPUs, at 8 DP/kangaroo it would be 2^33.17 DPs, or 576GB for DPs, and maybe 128GB for (a not-so-simple) hash table minimum.

The other thing that would affect performance is the bandwidth in server-GPU communication. With 8 DP/kgr at 100% of expected time, one can calculate the DP/second of each client. For #110, 128 GPUs, and 9 million kangaroos/GPU, 42.18 million jumps/kgr for 100% exp. time, 1600 MJ/s per GPU, 172.6 Jumps/second/kangaroo, about 618 DP/GPU/second are needed, which is 39 KB/s without overhead. For 128 GPUs the total bandwidth without overhead would be 5 MB/s, or 40 Mbit/s.

HardwareCollector

member

Activity: 144

Merit: 10

Quote from: Jean_Luc on May 14, 2020, 11:43:13 AM

Interesting, a key very near to the border
0x3FFFFFFFFFFFFFFFEFFFFF
has taken more than 4 times more DP than expected: 2^21.75/2^19.55

Yes, I set dp=24 because I did not want the solver to complete too fast, dp=18 would be more appropriate.

Jean_Luc

sr. member

Activity: 462

Merit: 696

@PietCoin97
You need a server with a powerful CPU and the needed RAM according to the number of DP bits you choose.
It is good to have more RAM however than the computed Expected RAM.
The server does not receive kangaroos from clients so no -ws.

@HardwareCollector
Thanks for the test Wink

Interesting, a key very near to the border
0x3FFFFFFFFFFFFFFFEFFFFF
has taken more than 4 times more DP than expected: 2^21.75/2^19.55

HardwareCollector

member

Activity: 144

Merit: 10

Quote from: Jean_Luc on May 14, 2020, 07:08:32 AM

I released the 1.5.
I tested the windows server as much as I can with several clients, connection, re-connection, backup, linux clients...
It seems to work rather well.
Thanks for testing it Wink

Seem to work well in client/server mode, will test next with a Hierarchical topology.

Code:

./Kangaroos -w MasterSavefile -wi 900 -s -d 24 in85.txt
Kangaroo v1.5
Start:2000000000000000000000
Stop :3FFFFFFFFFFFFFFFFFFFFF
Keys :1
Range width: 2^85
Expected operations: 2^43.55
Expected RAM: 41.4MB
DP size: 24 [0xffffff0000000000]
Kangaroo server is ready and listening to TCP port 9123 ...
.
.
.
[Client 13][DP Count 2^21.75/2^19.55][Dead 1][00:05:11][109.4/146.1MB]
[Client 13][DP Count 2^21.77/2^19.55][Dead 1][00:06:21][111.3/148.3MB]
Key# 0 [1S]Pub:  0x0276229F0C29917272A22FBB7DE39DF2606B4B0CAA03669C8CAA8D16CEAC512F47
       Priv: 0x3FFFFFFFFFFFFFFFEFFFFF

Closing connection with 172.16.0.20:35798

Closing connection with 172.16.0.17:55468

Closing connection with 172.16.0.16:54442

Closing connection with 172.16.0.11:40074

Closing connection with 172.16.0.22:37912

Closing connection with 172.16.0.18:48178

Closing connection with 172.16.0.12:49640

Closing connection with 172.16.0.23:51990

Closing connection with 172.16.0.21:51264

Closing connection with 172.16.0.19:33716

Closing connection with 172.16.1.10:36514

Closing connection with 172.16.0.14:46046

Closing connection with 172.16.0.13:47500

PietCoin97

jr. member

Activity: 91

Merit: 3

what kind of server requirements do we need when we want to make a server for 110 bit puzzel or 115 bit ?

and why is -ws option not suported on server ?

Code:

Kangaroo.exe -t 0 -gpu -gpuId 0,1,2,3,4,5 -w safe.work1 -ws -wi 300 -s -d 20 -i safe.work1
Kangaroo v1.5
Loading: safe.work1
Start:2000000000000000000000000000
Stop :3FFFFFFFFFFFFFFFFFFFFFFFFFFF
Keys :1
LoadWork: [HashTable 98.8/134.3MB] [00s]
Range width: 2^109
Expected operations: 2^55.55
Expected RAM: 1924606.2MB
DP size: 20 [0xFFFFF00000000000]
Waring: Server does not support -ws, ignoring

COBRAS

member

Activity: 873

Merit: 22

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk

Quote from: Jean_Luc on May 14, 2020, 07:08:32 AM

I released the 1.5.
I tested the windows server as much as I can with several clients, connection, re-connection, backup, linux clients...
It seems to work rather well.
Thanks for testing it Wink

You're a very tough guy !;)

Jean_Luc

sr. member

Activity: 462

Merit: 696

I released the 1.5.
I tested the windows server as much as I can with several clients, connection, re-connection, backup, linux clients...
It seems to work rather well.
Thanks for testing it Wink

COBRAS

member

Activity: 873

Merit: 22

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk

Quote from: Etar on May 13, 2020, 03:18:58 PM

Quote from: Jean_Luc on May 13, 2020, 01:39:57 PM

A client cannot solve a key as it does not perform collision check, it just calculate path and send DP to the server.

i mean that i do analog of your client/server app.
Client app simply launch kangaroo.exe
Than it check work file(with kangaroos), if the file has been modified app send file to server.
At the same time app monitors what is being done in the solver console, if solver solve key, it send key to server and stopped solver (kangaroo.exe)

Server app collect work files from clients and merge each to solve key.
Once key solved, app send command to all clients to stop working.

The problem is that files with work and kangaroos take up a lot of space and a lot of time to send.
But any way it is working)

Do not foget send to Jean_Luc some part of your praises Wink

Etar

sr. member

Activity: 617

Merit: 312

Quote from: Jean_Luc on May 13, 2020, 01:39:57 PM

A client cannot solve a key as it does not perform collision check, it just calculate path and send DP to the server.

i mean that i do analog of your client/server app.
Client app simply launch kangaroo.exe
Than it check work file(with kangaroos), if the file has been modified app send file to server.
At the same time app monitors what is being done in the solver console, if solver solve key, it send key to server and stopped solver (kangaroo.exe)

Server app collect work files from clients and merge each to solve key.
Once key solved, app send command to all clients to stop working.

The problem is that files with work and kangaroos take up a lot of space and a lot of time to send.
But any way it is working)

Etar

sr. member

Activity: 617

Merit: 312

Quote from: Jean_Luc on May 13, 2020, 01:39:57 PM

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.

many thanks for release.

Jean_Luc

sr. member

Activity: 462

Merit: 696

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.

Etar

sr. member

Activity: 617

Merit: 312

Quote from: Jean_Luc on May 13, 2020, 08:49:27 AM

Quote from: Jean_Luc on May 13, 2020, 08:28:12 AM

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.

Etar

sr. member

Activity: 617

Merit: 312

Quote from: Jean_Luc on May 13, 2020, 09:22:44 AM

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

Jean_Luc

sr. member

Activity: 462

Merit: 696

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

sr. member

Activity: 617

Merit: 312

Quote from: Jean_Luc on May 13, 2020, 08:49:27 AM

Quote from: Jean_Luc on May 13, 2020, 08:28:12 AM

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!

Topic: Pollard's kangaroo ECDLP solver - page 135. (Read 58708 times)