Author

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

full member
Activity: 1162
Merit: 237
Shooters Shoot...
May 20, 2020, 11:57:41 AM
Who know what is problem can be with 1080ti and Kangaroo.exe
Code:
GPUEngine: Launch: an illegal instruction was encountered
OS: Windows 10, i was tryed different drivers.. allways the same error.  Huh

That usually means the GPU code was compiled to target a compute capability higher than what your card supports. The GTX 1080 Ti supports up to 6.1, so it would need to be compiled with sm_61,compute_61 or lower.
but this error apear not from start. Program can be launched sometimes without any error. but any way after fiew minutes got this error.
I do not compile programm by self. I use release from github.

Maybe this error associated with pinned memory.
I look at code and didn’t see any unusual instructions there. Only using pinned memory...

maybe somebody want exchange mastersavefile (pazzle #110 (109 bit))  with the same DP size =31 and around the same DP counter and range 2000000000000000000000000000:3FFFFFFFFFFFFFFFFFFFFFFFFFFF? . I have mastersavefile(DP=31, DP Count  : 2755716 2^21.394)
Exchange available only for Sr. Member and higher



Sr. Member or higher? Interesting... DP 31, seems too high.
sr. member
Activity: 642
Merit: 316
May 17, 2020, 01:11:50 PM
Who know what is problem can be with 1080ti and Kangaroo.exe
Code:
GPUEngine: Launch: an illegal instruction was encountered
OS: Windows 10, i was tryed different drivers.. allways the same error.  Huh

That usually means the GPU code was compiled to target a compute capability higher than what your card supports. The GTX 1080 Ti supports up to 6.1, so it would need to be compiled with sm_61,compute_61 or lower.
but this error apear not from start. Program can be launched sometimes without any error. but any way after fiew minutes got this error.
I do not compile programm by self. I use release from github.

Maybe this error associated with pinned memory.
I look at code and didn’t see any unusual instructions there. Only using pinned memory...

maybe somebody want exchange mastersavefile (pazzle #110 (109 bit))  with the same DP size =31 and around the same DP counter and range 2000000000000000000000000000:3FFFFFFFFFFFFFFFFFFFFFFFFFFF? . I have mastersavefile(DP=31, DP Count  : 2755716 2^21.394)
Exchange available only for Sr. Member and higher

jr. member
Activity: 30
Merit: 122
May 17, 2020, 01:07:43 PM
Who know what is problem can be with 1080ti and Kangaroo.exe
Code:
GPUEngine: Launch: an illegal instruction was encountered
OS: Windows 10, i was tryed different drivers.. allways the same error.  Huh

That usually means the GPU code was compiled to target a compute capability higher than what your card supports. The GTX 1080 Ti supports up to 6.1, so it would need to be compiled with sm_61,compute_61 or lower.
sr. member
Activity: 642
Merit: 316
May 17, 2020, 12:57:26 PM
Who know what is problem can be with 1080ti and Kangaroo.exe
Code:
GPUEngine: Launch: an illegal instruction was encountered
OS: Windows 10, i was tryed different drivers.. allways the same error.  Huh
sr. member
Activity: 642
Merit: 316
May 16, 2020, 01:03:10 PM
Hello, everybody.

Does it make sense to continue the test, or is it better to end with ctrl^c and run with other parameters such as-d 22 ? The range is not known, I am looking for approximately up to ^91 inclusive.

1. Is there a chance that a collision will be found in the remaining range (Expected operations: 2^46.56 - [Count 2^45.01 ) ?


2. I have to wait a very long time, please help me-please tell me what settings are better to use ?



Please.




Thanks

Code:



c:\******.exe -d 18 -t 0 -gpu *******.txt
Kangaroo v1.5
Start:7FFFFFFFFFFEEE928C00
Stop :8000000000023E137430000
Keys :4
Number of CPU thread: 0
Range width: 2^91
Jump Avg distance: 2^45.04
Number of kangaroos: 2^20.32
Suggested DP: 25
Expected operations: 2^46.56
Expected RAM: 15097.9MB
DP size: 18 [0xFFFFC00000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(80x128) (129.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.32 kangaroos [6.0s]
[510.43 MK/s][GPU 510.43 MK/s][Count 2^44.99][Dead 0][21:43:51 (Avg 2.4d)][4072.4/5097.0MB]

There should be balance between DP size and GPU perfomance.
Small DP size = more GPU memory = less GPU perfomance, big DP size = more time to find expected amount of DP
And i agree that if you don`t know exist key in this range or not you should not use Kangaroo algorithm.
Kangaroo algorithm used only in case that  you know that key exist in range!
jr. member
Activity: 43
Merit: 1
May 16, 2020, 10:48:46 AM
You check 4 keys but if you didn’t find first the other 3 will not start to search now just one by one . If you don’t know range of search it’s impossible to find keys
member
Activity: 873
Merit: 22
$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk
May 16, 2020, 01:37:27 AM
Hello, everybody.

Does it make sense to continue the test, or is it better to end with ctrl^c and run with other parameters such as-d 22 ? The range is not known, I am looking for approximately up to ^91 inclusive.

1. Is there a chance that a collision will be found in the remaining range (Expected operations: 2^46.56 - [Count 2^45.01 ) ?


2. I have to wait a very long time, please help me-please tell me what settings are better to use ?



Please.




Thanks

Code:



c:\******.exe -d 18 -t 0 -gpu *******.txt
Kangaroo v1.5
Start:7FFFFFFFFFFEEE928C00
Stop :8000000000023E137430000
Keys :4
Number of CPU thread: 0
Range width: 2^91
Jump Avg distance: 2^45.04
Number of kangaroos: 2^20.32
Suggested DP: 25
Expected operations: 2^46.56
Expected RAM: 15097.9MB
DP size: 18 [0xFFFFC00000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(80x128) (129.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.32 kangaroos [6.0s]
[510.43 MK/s][GPU 510.43 MK/s][Count 2^44.99][Dead 0][21:43:51 (Avg 2.4d)][4072.4/5097.0MB]

member
Activity: 873
Merit: 22
$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk
May 15, 2020, 02:21:21 PM
I will be off up to the end of the next week.
I'll add the support for the -ws for client backup, this should avoid this overhead due to path breaking.
Good luck for solving #110 Wink



Have a nice trip. Wink
sr. member
Activity: 642
Merit: 316
May 15, 2020, 01:56:27 PM
I will be off up to the end of the next week.
I'll add the support for the -ws for client backup, this should avoid this overhead due to path breaking.
Good luck for solving #110 Wink
Happy holidays!
sr. member
Activity: 462
Merit: 701
May 15, 2020, 01:45:42 PM
I will be off up to the end of the next week.
I'll add the support for the -ws for client backup, this should avoid this overhead due to path breaking.
Good luck for solving #110 Wink

sr. member
Activity: 462
Merit: 701
May 15, 2020, 12:46:05 PM
I need more tests.
I think path breaking (when you are not using -ws) can also impact but I'm not sure.
sr. member
Activity: 642
Merit: 316
May 15, 2020, 11:58:55 AM
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.

Maybe i am wrong but it may be better to increase the range by N beginrange-n/2 and endrange +n/2.
This will require twice as much time to search, but it will exclude the option that the key will be at the border and need ~22 times more DP than expected.. no?
sr. member
Activity: 462
Merit: 701
May 15, 2020, 11:01:01 AM
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.
member
Activity: 144
Merit: 10
May 15, 2020, 07:37:18 AM
@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
jr. member
Activity: 91
Merit: 3
May 15, 2020, 06:06:06 AM
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?
sr. member
Activity: 462
Merit: 701
May 15, 2020, 01:04:52 AM
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.
sr. member
Activity: 443
Merit: 350
May 14, 2020, 07:15:40 PM
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?
full member
Activity: 206
Merit: 447
May 14, 2020, 03:04:50 PM
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 232 entries, but DPs were limited to 229 entries (IIRC 228 for #95). The whole program was using 48GB for the data - 32GB for DP, 16GB for hash table. For #95 227.79 points were used at 86.55%, for #100 226.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 = 32220 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 233.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.
member
Activity: 144
Merit: 10
May 14, 2020, 11:47:22 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.
sr. member
Activity: 462
Merit: 701
May 14, 2020, 11:43:13 AM
@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
Jump to: