I managed to reproduce the issue with the windows server.
I'll have a look on that
I'll have a look on that
Fixed in 1.5alpha2
Topic: Pollard's kangaroo ECDLP solver - page 136. (Read 58708 times)
Fixed in 1.5alpha2
I managed to reproduce the issue with the windows server.
I'll have a look on that
I'll have a look on that
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 problemNot 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
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..........
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.
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.
Works fine. Tested with 65bits key and 3 clients in same network.
I've a gpu client outside Kangaroo server network. By the moment i'm using SSH tunnel, but the connection isn't perfect.
It would be interesting if the client could operate without a permanent connection to the kangaroo server.
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.
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
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
many thanks
client:
server:
edit:
server:
and server app crash
server:
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
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
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Єюь.
in English it looks like An attempt was made to perform an operation on an object that is not a socket
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? The client and server can be run on both windows or linux.
There is few words on the readme.
Thanks to test it
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
The client and server can be run on both windows or linux.
There is few words on the readme.
Thanks to test it
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...
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...
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.
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.
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.
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
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 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.
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.
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
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 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.
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.
Hello
Expected RAM: 228.1MB
DP size: 23 [0xFFFFFE0000000000]
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.4s]
[511.32 MK/s][GPU 511.32 MK/s][Count 2^33.64][Dead 0][30s (Avg 1.1d)][2.0/4.2MB] ^C
C:\Chromidrol2020>chromatom2020 -t 0 -gpu in.txt
Kangaroo v1.4
Start:0
Stop :FFFFFFFFFFFFFFFFFFFFF
Keys :2
Number of CPU thread: 0
Range width: 2^84
Jump Avg distance: 2^42.03
Number of kangaroos: 2^20.32
Suggested DP: 21
Expected operations: 2^43.43
Expected RAM: 228.1MB
DP size: 21 [0xFFFFF80000000000]
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.5s]
[511.17 MK/s][GPU 511.17 MK/s][Count 2^43.02][Dead 0][05:32:59 (Avg 06:27:23)][132.1/172.6MB] ^C
C:\Chromidrol2020>
Code working fine I think.
p.s. Im not go away from there.
Quote
Expected RAM: 228.1MB
DP size: 23 [0xFFFFFE0000000000]
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.4s]
[511.32 MK/s][GPU 511.32 MK/s][Count 2^33.64][Dead 0][30s (Avg 1.1d)][2.0/4.2MB] ^C
C:\Chromidrol2020>chromatom2020 -t 0 -gpu in.txt
Kangaroo v1.4
Start:0
Stop :FFFFFFFFFFFFFFFFFFFFF
Keys :2
Number of CPU thread: 0
Range width: 2^84
Jump Avg distance: 2^42.03
Number of kangaroos: 2^20.32
Suggested DP: 21
Expected operations: 2^43.43
Expected RAM: 228.1MB
DP size: 21 [0xFFFFF80000000000]
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.5s]
[511.17 MK/s][GPU 511.17 MK/s][Count 2^43.02][Dead 0][05:32:59 (Avg 06:27:23)][132.1/172.6MB] ^C
C:\Chromidrol2020>
Code working fine I think.
p.s. Im not go away from there.
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%.
To be precise, the current prize is 1.1 BTC + 1.1 BCH + 1.1 BSV = 1.1 * (9300 USD) = 10230 USD
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.
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.
In that case it would be a record, 114 bit.
******************************************************************************
I rewrite my idea with more details:
we need 2.sqrt(N) steps to get a collision in a N-space,
we need 2.sqrt(2N) = sqrt(2).2.sqrt(N) steps to get a collision in a 2N-space
if we find a way to generate sqrt(2).2.sqrt(N) points faster than 2.sqrt(N), we get a collision in less time, even if we double our searching space.
If we use the endomorphism, we can double our interval, from
[1,2,3, ..., n-1,n]
to
[1,2,3,....., n-1,n] + [lambda, 2*lambda, 3*lambda, ....., n*lambda]
We have 2 types of jumps (always positive): 16 small steps (in first interval) + 16 big steps (in second interval)
For example:
(1G, 2G, 4G, 8G, 24G, 37G,....., 512G) + (lambda*18G, lambda*72G, ..., lambda*816G)
+ 1 jump from range1 to range2 or from range1 to range2: P -> lambda*P or lambda*P -> lambda^2*(lambda*P)
You have to know at each step in which interval the kangaroo is.
We set the probability to perform a jump between 2 different ranges = 50%, the other 50% is for normal jumps.
When a kangaroo is in the point P(x,y):
if x-coordinate > 2^255 then:
change interval
else:
do a normal jumps (x-coordinate % 16, small or big steps depends on the interval in which P is)
If x-coordinate > 2^255 then:
you compute a single multiplication: beta*x (or beta^2*x, it depends on the interval in which P is)
else:
you compute the normal jump P+k*G (or P+s*lambda*G, it depends on the interval in which P is)
(3 multiplications for the inverse + 1M + 1S for the x-coordinate + 1M for the y-coordinate = about 6M + some additions)
You cannot have loops, you have only to avoid 2 consecutive jumps between 2 ranges like: P -> lambda*P -> lambda^2*(lambda*P) = P, in this case you do a normal step P+kG instead of computing lambda*P:
P -> lambda*P ->
if another kangaroo falls in the same (lambda*P) from another point you will have a collision:
Q -> Q + lambda*7*G = lambda*P -> lambda^2*(lambda*P) = P ->
If we look at a couple of consecutive jumps, we will have:
probability
normal jump + normal jump = (1/2)^2
normal jump + lambda jump = (1/2)^2
lambda jump + normal jump = (1/2)^2
lambda jump + lambda jump= (1/2)^2 but -> loop, it is forbidden
-> it becomes: lambda jump +
On average for each 2 points we need to perform (1/2)^2*12M + (1/2)^2*2*7M + (1/2)^2*7M = 8.25M, 4,125 M for each point.
If you double the interval:
[1,2,3,....., n-1,n] + [lambda, 2*lambda, 3*lambda, ....., n*lambda]
then you perform sqrt(2).2.sqrt(N) steps in the same time you are performing now sqrt(2).2.(4,125/6).sqrt(N)= 1.945*sqrt(N)
But
we have a collision not only when 2 kangaroos (a wild and a tame) meet in a single range (first o second); even when they fall in 2 points P and lambda*P (with the same y-coordinate), there is a 75% that they will continue on the same path:
P -> lambda*P -> P there is a collision (same path)
P -> lambda*P -> lambda*P + lambda*7*G there is a collision (same path)
P -> P+12*G and lambda*P -> P there is a collision (same path)
P -> P+12*G and lambda*P -> lambda*P + lambda*7*G there is no collision
there is no a collision, one kangaroo jumps from P to P+12*G and the other one jumps from lambda*P to lambda*P + lambda*7*G
In a N-space, we need 2 lists of sqrt(N) points to form sqrt(N)*sqrt(N) = N couples. N couples over N^2 possible couples, on average we should generate N couples to get one with the same elements (a collision)
In our 2N-space we have 2N couples with the same 2 points + 2N couples with 2 related points (P,lambda*P). On average 3/4 of (P,lambda*P) will produce (if xP > 2^255 or if x(lambda*P)>2^255) a collision,
then we have (2N + 3/4*2N) couples of collisions over (2N*2N) possible couple.
The probability to find a collision for each couple is:
(7/4 * 2N) / (4N^2) = 14/16 * 1/N = 7/8 * 1/N instead of 1/2N, this means 7/4 bigger.
We need than 8N/7 couples to have a collision, 2 lists of sqrt(8N/7) points -> 2,14.sqrt(N) 'cheap' points ->
2,14.(4,125/6).sqrt(N) = 1,47.sqrt(N) normal points
Yeah the multi pubkey search as for me more interesting and on github there was a first topic about this)
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.
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.
Why don't you focus on the harder 115 and 120 bit problems and give the smaller people a chance? You have 20-30 times the GPUs of most people here.
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 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.
Enjoy your research!!!
Jump to: