Pollard's kangaroo ECDLP solver

[Etar]

-snip-
You can (see here -> https://bitcointalk.org/index.php?topic=5244940.msg54546770#msg54546770, it is enough to map the new task [1, 2^119 - 1] to the previous one [1, 2^114 - 1]) but it's not worth it.
-snip-

i think all DPs from previous work will be in the left 1/32 part of interval(in the begining).
If you just multiply DPs by 32 then  they will be just points not DPs becouse they will not have leading zeros.
If i wrong can you explaine in very small range how transform DP by 32 times and do not loose leading zeros? Thanks.

[1715554809]

1715554809

[1715554809]

1715554809

[1715554809]

1715554809

[arulbero]

-snip-
You can (see here -> https://bitcointalk.org/index.php?topic=5244940.msg54546770#msg54546770, it is enough to map the new task [1, 2^119 - 1] to the previous one [1, 2^114 - 1]) but it's not worth it.
-snip-

i think all DPs from previous work will be in the left 1/32 part of interval(in the begining).
If you just multiply DPs by 32 then  they will be just points not DPs becouse they will not have leading zeros.
If i wrong can you explaine in very small range how transform DP by 32 times and do not loose leading zeros? Thanks.

No, you don't transform the old DPs, you change only their private keys (changing the generator G). The same for the old jumps. The only point you change is P, the public key for which you are looking the private key.

Instead of multiplying the old points by 32 you divide (= multiply by inv(32)) the new public point P -> P'=inv(32)*P.

If P lies in the [1, 2^119 - 1] interval, then P' lies in the

[1/32, ...., 31/32, 1, 33/32, ....., 2, ......3, .......4, ................., 2^114 -1/32] interval.

Note that the private keys of the old DPs are 'integer'. In this way you spread the old DPs uniformly in a set x32 bigger. This interval contains all the previous points [1,2,3,..., 2^114-1], but not at the beginning!

You can change now the private keys changing the generator, G -> G' = inv(32)*G:

[1, .........,31, 32, 33, .........2*32,..........3*32, .............., 4*32,.................32*2^114 - 1]

the private keys of the old DPs have become all multiplies of 32.

If for example a DP has private key = 78543 respect of G, it has private key = 32*78543 respect of G', the point remains the same (same x-coordinate), you have changed only the point G.

The private key of P' respect of G' is the same private key of P respect of G.  

------------------------------------------------------------------------------------------------------------------

Example:

first interval = [1,2,3,4,5,6,7]  (3 bit)
DPs  = 2*G, 5*G

second interval  = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,....,27,28,29,30,31]  (5 bit)
you want to find P = 11*G, you know only that the P lies in this interval

instead of searching P in the second interval [1*G, 2*G, ...., 31*G]

you search P'=inv(4)*P (a different point) in a

third interval [1*G', 2*G', ......, 31*G']  (that contains the first interval but not at the beginning + P')

The old DPs are now: 8*G' and 20*G' (same points, different private keys). All the points of the first interval are now in the third one too.

The private key of P' = 11, in fact 11*G' = 11*inv(4)*G --> P = 4*P' = 4*11*inv(4)*G = 11*G

[Jean_Luc]

You have computed about 2^58.36 steps. And you know now the private keys of 2^33.36 DPs in the [1, 2^114 - 1] interval (why you said [2^114,2^115-1]? you know only one public key P in [2^114, 2^115 - 1] range, all the public keys/points you have computed lie in [1, 2^114 - 1])

Yes you're right.
I ve forgotten that the start range was shifted to zero. shame on me
It will help to solve #120.

[brainless]

You have computed about 2^58.36 steps. And you know now the private keys of 2^33.36 DPs in the [1, 2^114 - 1] interval (why you said [2^114,2^115-1]? you know only one public key P in [2^114, 2^115 - 1] range, all the public keys/points you have computed lie in [1, 2^114 - 1])

Yes you're right.
I ve forgotten that the start range was shifted to zero. shame on me
It will help to solve #120.

my Question you misunderstand
example i have 2 pubkeys in 115bit range, 1 key found, for 2nd key how i can use that work file for find in less time, ??

[Etar]

second interval[/u]  = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,....,27,28,29,30,31]  (5 bit)
you want to find P = 11*G, you know only that the P lies in this interval

instead of searching P in the second interval [1*G, 2*G, ...., 31*G]

you search P'=inv(4)*P (a different point) in the

third interval [1*G', 2*G', ......, 31*G']  (that contains the first interval but not at the beginning + P')

The old DPs are now: 8*G' and 20*G' (same points, different private keys). All the points of the first interval are now in the third one too.

The private key of P' = 11, in fact 11*G' = 11*inv(4)*G --> P = 4*P' = 4*11*inv(4)*G = 11*G

Perfect explanation. Thanks!

[Jean_Luc]

my Question you misunderstand
example i have 2 pubkeys in 115bit range, 1 key found, for 2nd key how i can use that work file for find in less time, ??

You can simply merge the files, but at the moment the "trapped wild" are not yet handled, you will take benefit only from tame.
This will be done in a future release as we will need it for solving #120.

[arulbero]

You have computed about 2^58.36 steps. And you know now the private keys of 2^33.36 DPs in the [1, 2^114 - 1] interval (why you said [2^114,2^115-1]? you know only one public key P in [2^114, 2^115 - 1] range, all the public keys/points you have computed lie in [1, 2^114 - 1])

Yes you're right.
I ve forgotten that the start range was shifted to zero. shame on me
It will help to solve #120.

Instead of 2^61 steps, you need to compute (2^60 - 2^58.36) steps for tame + 2^60 for wild. If you spread the old DPs like I have suggested you in a previous post.

It would be convenient to start with only wild (for the first 2^58.36 steps) and then continue with wild and tame, but with many machines it should be not simple to do this.

You can save in this way about 15.8% of the work.

An other way it could be: you know that you have already DPs in [1,2^114-1], then you generate tame only in the [2^114, 2^119-1] space --> you have enough DP's (2^33.36) already in the first 1/32.

In the first case you should use 300GB * 2^2.5 = 1700 GB, in the second case I guess you need more RAM and more time.

[Jean_Luc]

Yes thanks for this tip
I'm building a map to compute with accuracy the DP overhead as I didn't yet managed to get the correct analytical expression but only the 2 asymptote (0 and infinity)
Tomorrow I will also investigate how long would it take with the VanitySearch engine optimized for V100 to solve #64.
Then we will make our choice on attacking #64 or #120.

[brainless]

Yes thanks for this tip
I'm building a map to compute with accuracy the DP overhead as I didn't yet managed to get the correct analytical expression but only the 2 asymptote (0 and infinity)
Tomorrow I will also investigate how long would it take with the VanitySearch engine optimized for V100 to solve #64.
Then we will make our choice on attacking #64 or #120.

private key for 115 ?

[JDScreesh]

We (me and zielar) solved #115 after ~2^33.36 DP (DP25) (More than 300GB of DP). I do not know exactly how long the run takes due to unwanted interruption.

Congratulations
did you forget to send some satoshi to
1FoundByJLPKangaroo111Bht3rtyBav8

And there it is!  

The satoshi to 1FoundByJLPKangaroo111Bht3rtyBav8  

Congrats again  

[youssefs0102]

Yes thanks for this tip
I'm building a map to compute with accuracy the DP overhead as I didn't yet managed to get the correct analytical expression but only the 2 asymptote (0 and infinity)
Tomorrow I will also investigate how long would it take with the VanitySearch engine optimized for V100 to solve #64.
Then we will make our choice on attacking #64 or #120.

hello Jean_Luc, how to attaque #64 with kangoroos or the VanitySearch engine without public key ?

[Jean_Luc]

If we attack #64, we will try all priv key one by one, compute the HASH160 until we get a match.
With few mods, the vanitySearch engine can do that. Kangaroo is not usefull here.

[brainless]

If we attack #64, we will try all priv key one by one, compute the HASH160 until we get a match.
With few mods, the vanitySearch engine can do that. Kangaroo is not usefull here.

For one by one bitcrack could work too. Even peoples created group pool for find 64. Like client server sharing

[arulbero]

If we attack #64, we will try all priv key one by one, compute the HASH160 until we get a match.
With few mods, the vanitySearch engine can do that. Kangaroo is not usefull here.

I suppose that computing HASH160 is more expensive than computing P+Q, then searching for #120 (2^61 steps) should be faster than computing #63 (2^61 steps on average)  

[zielar]

Yes thanks for this tip
I'm building a map to compute with accuracy the DP overhead as I didn't yet managed to get the correct analytical expression but only the 2 asymptote (0 and infinity)
Tomorrow I will also investigate how long would it take with the VanitySearch engine optimized for V100 to solve #64.
Then we will make our choice on attacking #64 or #120.

private key for 115 ?

The private key will be announced immediately after the last transaction on 1FoundByJLPKangaroo111Bht3rtyBav8 receives the first confirmation.

[Etar]

-snip-
For one by one bitcrack could work too. Even peoples created group pool for find 64. Like client server sharing

A couple of days ago, I decided to leave the kangaroo alone, because it is impossible to compete with Zielar.
 I think, well, I’ll try to solve the 64 puzzle with the help of a BitCrack.
Wrote a server, wrote a client so that more than one could decide .. 
And here it turns out that Zielar also decided to let the dogs down on him..

Of course, no one can forbid him to do anything, but can leave alone at least 64 and 66 for weak players?

[Konstanting2]

Code:
Kangaroo.exe -t 4 -d 14 -w 65save -wi 30 65.txt

pause
Code:
Kangaroo.exe -t 0 -d 14 -gpu -gpuId 0 -w 65save -wi 30 65.txt

Code:
10000000000000000
1FFFFFFFFFFFFFFFF
0230210c23b1a047bc9bdbb13448e67deddc108946de6de639bcc75d47c0216b1b

In three minutes I received just such an answer, and then please help.

65save.txt
20D0900 | 78 C9 C8 0A 68 33 DF 16 81 56 23 A6 92 E5 95 B3 13 C0 67 7C 00 00 00 00 00 00 00 40 00 00 00 00
20D0920 | 00 00 00 00

help.

[Konstanting2]

Windows 7, Win64.
C \ windows \ system32 \ cmd.exe
C: \ USERS \ GAM> "D: BTC \ Kangaroo.exe" Nothing happens.
If I immediately start Kangaroo.exe, the Windows 7 Command Prompt (CMD) appears and closes immediately. How to make the program work?javascript:void(0);

Do this so you know it works on your machine/rig:

copy the below text, paste in notepad, and save it as a .bat file.  Save it as kangarootest.bat

if you only have CPU

Code:

Kangaroo.exe -t 4 -d 14 -w 65save -wi 30 65.txt

pause

if you have GPU:

Code:

Kangaroo.exe -t 0 -d 14 -gpu -gpuId 0 -w 65save -wi 30 65.txt

Again, copy and paste that into a text document and save as kangarootest.bat

Now, copy the below text and save it as 65.txt  

Code:

10000000000000000
1FFFFFFFFFFFFFFFF
0230210c23b1a047bc9bdbb13448e67deddc108946de6de639bcc75d47c0216b1b

make sure each line is it's own line...a total of 3 lines.  Save it as 65.txt

Now, place the kangarootest.bat file, the 65.txt file, and the Kangaroo.exe file all in the same folder.
Double click or select the kangarootest.bat file and the program will start.
It may tell you that you do not have a certain file called, "vcruntime140_1" . If that's the case, Google that file, download it and place it in the same folder as the other files. Now, double click, select the kangarootest.bat file and it should work.

Let us know.

Cпacибo oгpoмнoe зa пoмoщь. Пocлe пoлyчил oтвeт в фaйлe 65save.txt
In three minutes I received just such an answer, and then please help.

65save.txt
20D0900 | 78 C9 C8 0A 68 33 DF 16 81 56 23 A6 92 E5 95 B3 13 C0 67 7C 00 00 00 00 00 00 00 40 00 00 00 00
20D0920 | 00 00 00 00

help.

[MrFreeDragon]

Congratulations to Jean_Luc and zielar!
Very nice job!

Is it possible you share your combined DPs database for #115? (300Gb file as you said)

[zielar]

-snip-
For one by one bitcrack could work too. Even peoples created group pool for find 64. Like client server sharing

A couple of days ago, I decided to leave the kangaroo alone, because it is impossible to compete with Zielar.
 I think, well, I’ll try to solve the 64 puzzle with the help of a BitCrack.
Wrote a server, wrote a client so that more than one could decide ..  
And here it turns out that Zielar also decided to let the dogs down on him..

Of course, no one can forbid him to do anything, but can leave alone at least 64 and 66 for weak players?

I took up # 64 over half a year ago when I found the key to 63 and 62. I have scanned 5% of the range and with this state I stopped working on it towards VanityPool, which I abandoned against Kangaroo. I transferred my work results to cooperation with the pool working on # 64 (http://ttdsales.com/64bit).
Due to the fact that Jean_Luc proposed optimization # 64 - we plan to check the progress by continuing to search # 64 due to the fact that he will optimize VanitySearch to work on this challenge. Of course, due to the fact that I decided to join the pool before - work will be done to support the pool.