Author

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

member
Activity: 144
Merit: 10
May 28, 2020, 02:13:57 PM
I really like this race Cheesy
HardwareCollector or Zielar ?

There is a high probability that if we combine HardwareCollector's and Zielar's working files there will be the required collision.

There is also a way to check it right now without sharing the whole files - only the information with X-coordinates and kangaroo type should be shared (excluding distances), and if we have the same X-coordinate with different types (wild and tame) so we can confirm that the key is found.

HWCollector and Zielar, do you want me to perform such check for you?  Wink
Thanks for the offer, but I’ve not started yet as I am giving time for Zielar to solve the challenge first. He has poured a lot of resources to it already, and out of common courtesy, I will begin late Sunday night assuming that he’s hasn’t solved it yet. But I am working on precomputation for the 115-bit private key challenge.  Grin
full member
Activity: 1162
Merit: 237
Shooters Shoot...
May 28, 2020, 02:08:57 PM
-snip-
we can shift the range to 0
and subtract the beginning of the range from the public key
-snip-

This "shift" was already discussed here. And moreover, Jean_Luc made the shift in his program.
So if we input the range [a..b], the program actually shifts it to 0 and making the search within the range [0... (a-b)]
I also read all read all the DPs from binary file and can confirm this: all the tames distances are within the range [0...(a-b)] and all the wilds are within the range [0...(a-b)/2] - for wilds also the sign is used.

But you are right, Etar, that the "tame" DPs from previous keys could be used for subsequent, however their concentration will be very high on the left side of the range. Tames are distributed within the whole range, however if you use these tames for 1bit more key, they are all be only within the first half of the range, if for 2bit more key, all the tames will be on the first 25% of the range, etc...

But yes, the working files could be used for higher bits keys. However you should use the same DP size.

So if this is possible, then is it also possible to:

Start out with range: 100000:FFFFFF and run a round of kangaroos through it
and then run kangaroos at different ranges within that range, example : 111111:FFFFFF OR 203AB9:FFFFFF, etc. etc.

sr. member
Activity: 443
Merit: 350
May 28, 2020, 01:57:13 PM
I really like this race Cheesy
HardwareCollector or Zielar ?

There is a high probability that if we combine HardwareCollector's and Zielar's working files there will be the required collision.

There is also a way to check it right now without sharing the whole files - only the information with X-coordinates and kangaroo type should be shared (excluding distances), and if we have the same X-coordinate with different types (wild and tame) so we can confirm that the key is found.

HWCollector and Zielar, do you want me to perform such check for you?  Wink
sr. member
Activity: 443
Merit: 350
May 28, 2020, 01:51:30 PM
-snip-
we can shift the range to 0
and subtract the beginning of the range from the public key
-snip-

This "shift" was already discussed here. And moreover, Jean_Luc made the shift in his program.
So if we input the range [a..b], the program actually shifts it to 0 and making the search within the range [0... (a-b)]
I also read all read all the DPs from binary file and can confirm this: all the tames distances are within the range [0...(a-b)] and all the wilds are within the range [0...(a-b)/2] - for wilds also the sign is used.

But you are right, Etar, that the "tame" DPs from previous keys could be used for subsequent, however their concentration will be very high on the left side of the range. Tames are distributed within the whole range, however if you use these tames for 1bit more key, they are all be only within the first half of the range, if for 2bit more key, all the tames will be on the first 25% of the range, etc...

But yes, the working files could be used for higher bits keys. However you should use the same DP size.
sr. member
Activity: 642
Merit: 316
May 28, 2020, 12:57:23 PM
@JeanLuc and other folks who has knowledge in this area..
From what I realized that DP is just the x coordinate with a certain number of leading zeros .. like a brilliant among stones.
Kangaroo algorithm, creates a tribe of tame and a tribe of wild kangaroos.
Tame kangaroos are tied to a range, and wild to the desired public key.
Now the idea itself .. Why can not we use the experience of previous work?
What I mean. For example, we’ll start accumulating experience with a 54-bit key
The range where this private key located is
40000000000000
7fffffffffffff
and seek public key 0385a30d8413af4f8f9e6312400f2d194fe14f02e719b24c3f83bf1fd233a8f963
we can shift the range to 0
and subtract the beginning of the range from the public key
(0x85a30d8413af4f8f9e6312400f2d194fe14f02e719b24c3f83bf1fd233a8f963,0x0eb400323654cec63999b56f4ba44e8b21ab92d9d697fabe4666df3678585669)
-
(374deeae22c93f955cb83ad2071f7e2256f6e109cad7bca6d71dc7b24414bb36,171165b64fcd4f9916032c06f806f7293828d66300e543217875bea98daf734a)
=
(b1f8ba606a61026d1ecaa93d9e9ceb12260c33e92809ed1ecb0850a2856accc1,ac46d892583d7fdd24a25a229b6ea8d17add77b1f410a9d30441e0acbec19c74)
and range
0
3fffffffffffff
as result we will have key 0x2ABE1F9B67E114
if we add range we can regenerate real key
0x2ABE1F9B67E114+0x40000000000000=0x6ABE1F9B67E114
So we have a saved working file, where there are DP both tame and wild kangaroos in range 0-3fffffffffffff
DP of wild kangaroos we do not need more  so they are tied to the public key.
We can cut only tame kangaroos points from the work file and save to a new file.
And this tame will be correct for next puzzle because they are in the same range as next pazzle(after shifting ofcourse)
So we can use this file like initial to next pazzle
Next 59bit Puzzle..
range
800000000000000
fffffffffffffff
and seek public key 0348e843dc5b1bd246e6309b4924b81543d02b16c8083df973a89ce2c7eb89a10d
do the same thing, shift the range to 0 and subtract the beginning of the range from the public key
(0x48e843dc5b1bd246e6309b4924b81543d02b16c8083df973a89ce2c7eb89a10d,0xd094fcabf8995e2a25c73298a9f7419720db622daff89c67fd5535f6ac29720f)
-
(8991225911b9132d28f5c6bc763ceab7d18c37060e8bd1d7ed44db7560788c1e,da8b4d987cc9ac9b27b8763559b136fa36969c84fdef9e11635c42228e8f0ef1)
=
(2b90a8680d08cf81e15e209acadbb16b7bdff19787d6d13ca6a7852fee8d1013,447a29425ea9773471ad9810d21a976cf5bd4bdb46d0c8ae537591dce43252f2)
and range
0
7ffffffffffffff
Don`t forget that we already have some tame DPs on this range(0-3fffffffffffff), so we should find collision faster!
result key is 0x7C07A1825367BBE
add range and real key
0x7C07A1825367BBE+0x800000000000000=0xFC07A1825367BBE
than do the same, cut from work file only tame kangaroos, save and solve next pazzle...
In this case, after each puzzle, we will already have more and more DP points from tame kangaroos.
What you think?
full member
Activity: 1162
Merit: 237
Shooters Shoot...
May 28, 2020, 12:46:52 PM
Published a new release with a faster merger.
Thanks to test it Wink

tested with several files over 1GB; works well!
member
Activity: 873
Merit: 22
$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk
May 28, 2020, 09:45:51 AM
I really like this race Cheesy
HardwareCollector or Zielar ?


Ford VS Ferrari  Wink
sr. member
Activity: 642
Merit: 316
May 28, 2020, 09:31:43 AM
I really like this race Cheesy
HardwareCollector or Zielar ?

friendship)
sr. member
Activity: 462
Merit: 701
May 28, 2020, 08:57:05 AM
I really like this race Cheesy
HardwareCollector or Zielar ?
member
Activity: 144
Merit: 10
May 28, 2020, 08:51:19 AM
There seems to be some kind of mistake in this puzzle#110
A huge number of GPU capacities have already been spent and no one could find the key.
I checked the range borders with bsgs, there is no key there.
This was the only version why we could not find the key for so long.
But she is not true. The key is not near the edge.
Someone has an idea why we can’t find the key .. even with the possibility of 400 GPU?
With my own implementation which is memory optimized (16bytes/point with 22-bit mask), I will consume between ~181GB and ~1.1TB of RAM from best to worst case for a 109-bit interval. If the 110-bit private key challenge hasn’t been solved by @zielar before Sunday night, then I would agree that something is definitely wrong; only assuming that he’s used in excess of 1TB of RAM, otherwise it’s just bad luck.
member
Activity: 348
Merit: 34
May 28, 2020, 08:47:12 AM
-snip-
could you try this for calc time about your 24 2080ti gpu for 100 bit
0314AA23C847D86CE1FCDC4B3E0524F741FDE2AC4B38B522ED2E3B77CF500D5718
and you can use client server or single system with gpuid 0,1,2,3 to 24 command
and just run and you will have estimate time, could update me your estimate time ?

The estimation for 100bit key with 24x2080ti is approximately 24 hours.

24x2080ti has 29500MJump/sec, so 2^(100/2+1.15) / 29500Mjumps/sec --> 24 hours
mean if you run 400 gpu, then how you could found 110 bit in 2 days ? Smiley
sr. member
Activity: 443
Merit: 350
May 28, 2020, 08:27:22 AM
-snip-
could you try this for calc time about your 24 2080ti gpu for 100 bit
0314AA23C847D86CE1FCDC4B3E0524F741FDE2AC4B38B522ED2E3B77CF500D5718
and you can use client server or single system with gpuid 0,1,2,3 to 24 command
and just run and you will have estimate time, could update me your estimate time ?

The estimation for 100bit key with 24x2080ti is approximately 24 hours.

24x2080ti has 29500MJump/sec, so 2^(100/2+1.15) / 29500Mjumps/sec --> 24 hours
sr. member
Activity: 642
Merit: 316
May 28, 2020, 08:21:54 AM
could you try this for calc time about your 24 2080ti gpu for 100 bit
0314AA23C847D86CE1FCDC4B3E0524F741FDE2AC4B38B522ED2E3B77CF500D5718
and you can use client server or single system with gpuid 0,1,2,3 to 24 command
and just run and you will have estimate time, could update me your estimate time ?
it can be calculated, not need to launch GPUs...

Code:
Range 2^ 100.0
Expected OP 2^ 51.054194794629616
SuggestedDP = 24
Total GPU: 24
Total hashrate 2^ 34.860826977961146
Kangaroos per GPU 2^ 21.09
Totalkangaroos 2^ 25.674962500721158
Nkangaroo*2^DPbit = 2^ 49.67496250072116
Average time 2^ 16.19336781666847 s =  0.8673126907677194 days

And i use server client ofcourse.
member
Activity: 348
Merit: 34
May 28, 2020, 08:08:15 AM
-snip-
how much gpu's you have ?
now left 24x2080ti, around half GPU is out of race.

As say Turing, machine working we need only give him what he is undertsand..


could you try this for calc time about your 24 2080ti gpu for 100 bit
0314AA23C847D86CE1FCDC4B3E0524F741FDE2AC4B38B522ED2E3B77CF500D5718
and you can use client server or single system with gpuid 0,1,2,3 to 24 command
and just run and you will have estimate time, could update me your estimate time ?
sr. member
Activity: 462
Merit: 701
May 28, 2020, 08:06:07 AM
Published a new release with a faster merger.
Thanks to test it Wink
jr. member
Activity: 30
Merit: 122
May 28, 2020, 08:01:27 AM
There seems to be some kind of mistake in this puzzle#110
A huge number of GPU capacities have already been spent and no one could find the key.
I checked the range borders with bsgs, there is no key there.
This was the only version why we could not find the key for so long.
But she is not true. The key is not near the edge.
Someone has an idea why we can’t find the key .. even with the possibility of 400 GPU?

I think folks are just being impeded by storage and network issues.
sr. member
Activity: 642
Merit: 316
May 28, 2020, 07:18:50 AM
-snip-
how much gpu's you have ?
now left 24x2080ti, around half GPU is out of race.

As say Turing, machine working we need only give him what he is undertsand..

member
Activity: 348
Merit: 34
May 28, 2020, 07:08:46 AM
There seems to be some kind of mistake in this puzzle#110
A huge number of GPU capacities have already been spent and no one could find the key.
I checked the range borders with bsgs, there is no key there.
This was the only version why we could not find the key for so long.
But she is not true. The key is not near the edge.
Someone has an idea why we can’t find the key .. even with the possibility of 400 GPU?
how much gpu's you have ?
sr. member
Activity: 642
Merit: 316
May 28, 2020, 06:53:13 AM
There seems to be some kind of mistake in this puzzle#110
A huge number of GPU capacities have already been spent and no one could find the key.
I checked the range borders with bsgs, there is no key there.
This was the only version why we could not find the key for so long.
But she is not true. The key is not near the edge.
Someone has an idea why we can’t find the key .. even with the possibility of 400 GPU?
sr. member
Activity: 642
Merit: 316
May 28, 2020, 01:52:28 AM
With the new -wsplit option:

How are you using it?

The way I read, it saves an updated file let's say every -wi 60 seconds. Got it. I've tested it.

So the only way the key can be solved on the server side, is if a collision happens in the current, being worked on, reset/smaller hash table (the one that will be saved next)?

The server doesn't compare the different saved files for a collision, so one must merge the different saved working files to check for a collision.
If you have 10, 20, 30, 100, 1000 saved files over a period of days, weeks, months, are you manually merging the saved work files every so often?
The current merge option only allows the merge of 2 files at a time...manually merging could become an hourly task (depending on how many files you have being saved each minutes/hours.)

So you have a benefit in RAM but increases the amount of work you have to do in merging files?
Grabber and merger merge files in realtime, so i do not have any split files on server. Once file exist merger merge him with masterfile.
all what you need it is set -jobtime to value (wi/2*1000). If -wi set to 60, than you need -jobtime 30000, -jobtime in ms.

Jump to: