Author

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

sr. member
Activity: 462
Merit: 701
June 03, 2020, 08:51:09 AM
The only reward I asked to Zielar is a symbolic satoshi to a symbolic address which is quite important for me. Nothing more. And I will refuse any remuneration for this tool or any other GPL3 tools I did. I already received tons of emails for various development request with fee.

I did this tool for everybody and I will continue, however I can't develop a secure server with a validation mechanism for a pool, it is a very hard task.
I don't know if Zielar solved #62 and #63 with the VanitySearch engine and his own mods or with bitcrack.
sr. member
Activity: 642
Merit: 316
June 03, 2020, 08:35:45 AM
-snip-

Edit: You have no idea who Zielar is actually. He is a very competent person in his domain, I must say that from time to time I pain to follow him !
i will not put here all message, just one left here...
Server autorestart now works fine. You calmed me down, gentlemen. I must admit that I hope to find # 110 in the next few days ... I will remember you if I do it, and of course about the author of this tool, to which I already owe a lot :-)

Greetings !
i did not need any reward from zielar it is just for clarify.
newbie
Activity: 3
Merit: 0
June 03, 2020, 07:18:06 AM
Visual Studio 2015 + Cuda 8 => Take project files in VC_CUDA8
Visual Sutido 2017 + Cuda 10 => Take project files in VC_CUDA10
Visual Studio 2019 + Cuda10.2 => Take project files in VC_CUDA102

Note: I don't have a dev environment Visual Studio 2017 + Cuda 10 at the moment so project files may be out of date and some files may be missing, in that case just add them to the project...

I recommend to use Visual Studio 2019 + Cuda10.2.

I will update the README.

Compiled exe are available from:
https://github.com/JeanLucPons/Kangaroo/releases

How on earth did I miss the 'Releases' tab? The .exe was there all along...  Huh

Thank you for this clarification. I really appreciate taking the time and replying. Have a wonderful day!
sr. member
Activity: 462
Merit: 701
June 03, 2020, 07:02:49 AM
Visual Studio 2015 + Cuda 8 => Take project files in VC_CUDA8
Visual Sutido 2017 + Cuda 10 => Take project files in VC_CUDA10
Visual Studio 2019 + Cuda10.2 => Take project files in VC_CUDA102

Note: I don't have a dev environment Visual Studio 2017 + Cuda 10 at the moment so project files may be out of date and some files may be missing, in that case just add them to the project...

I recommend to use Visual Studio 2019 + Cuda10.2.

I will update the README.

Compiled exe are available from:
https://github.com/JeanLucPons/Kangaroo/releases
newbie
Activity: 3
Merit: 0
June 03, 2020, 06:51:55 AM
-snip-
Code:
error : Designtime build failed for project 'C:\Users\danh\Desktop\kg\Kangaroo-master\VC_CUDA102\Kangaroo.vcxproj' configuration 'Release|x64'. IntelliSense might be unavailable.
Set environment variable TRACEDESIGNTIME = true and restart Visual Studio to investigate.

-snip-

Hi Dan.
I am not using Visual Studio.
I googled the problem and found some solutions that say you should repair the project (I think there is a menu option) or upgrade your visual studio.


Thank you, Tamarindei. The readme file says to use Visual C++ 2017 so upgrading VS won't do any good I suppose.

Jean_Luc , as the creator of this code, would you mind compiling the latest version as .exe on github for those of us having issues building it manually from source code? I am not even trying to solve this Bitcoin puzzle. I need it for a completely different thing at Uni. I am also willing to donate something for your effort. I am not rich but I can appreciate someones time. Feel free to contact me if you want. Thank you.
member
Activity: 330
Merit: 34
June 03, 2020, 05:35:26 AM
I am sure #115, #120 and #125 will go to zielar and no pool can compete. gg.

I disagree.
I spent much time to explain in the readme, in this topics or in the code the way to choose best parameters and trap to avoid.
Zielar has also to win his life and cannot spend full time to solve these puzzles.
It is far from sure that Zielar will win all the races.

Anyway, I'm working on the 1.9 in order to integrate mods from PatataFritas and support of -ws for clients.


Edit: You have no idea who Zielar is actually. He is a very competent person in his domain, I must say that from time to time I pain to follow him !


Pls Correct, about Race
there is no Race, as no one have big gpu pools, and developer saying he have some secret setting and contract with winner, so definatly there is no race, that match was fixed Smiley
next time guys make bets on fixed match and definatlly you all will win,

sr. member
Activity: 462
Merit: 701
June 03, 2020, 03:55:17 AM
Right.
256 for fast access (and check) 1 dummy point is sacrificed.


Code:
// Compute Generator table
  Point N(G);
  for(int i = 0; i < 32; i++) {
    GTable[i * 256] = N;
    N = DoubleDirect(N);
    for (int j = 1; j < 255; j++) {
      GTable[i * 256 + j] = N;
      N = AddDirect(N, GTable[i * 256]);
    }
    GTable[i * 256 + 255] = N; // Dummy point for check function
  }
legendary
Activity: 1932
Merit: 2077
June 03, 2020, 03:50:43 AM
The ComputePublicKey() in kangaroo use 32 blocks of 256 precomputed points and zero are checked so it performs:
31 adds max for a full privkey (nothing when a zero byte is present) and a modular inversion.
There is also a ComputePublicKeys() which group modular inversions.


That means you need only 16 blocks of 255 (why 256?) precomputed points for a 128-bit privkey, only 15 adds, not too much respect to a single addition.

Split a 128-bit in 16 pieces (each piece has 128/16=8 bit -> 255 elements) and  compute only 16-1 = 15 group additions for each key.

Just for example, if you have a 128 bit key:

key = 10101010 10100000 11111111 01000010 ...  11101010

split in 16 pieces of 128/16=8 bits:

(10101010)*2^120 + (10100000)*2^112 + (11111111)*2^104 + (01000010)*2^96 + .... + (11101010)2^0
Code:
00000001   00000010   00000011   ...    11111111      --> 255 possibilities

  2^0        2*2^0     3*2^0     ...     255*2^0      --> one of these is (11101010)*2^0

  ...         ...      ...       ...       ...

2^(12*8)  2*2^(12*8)  3*2^(12*8) ...  255*2^(12*8)    --> one of these is (01000010)*2^96

2^(13*8)  2*2^(13*8)  3*2^(13*8) ...  255*2^(13*8)    --> one of these is (11111111)*2^104

2^(14*8)  2*2^(14*8)  3*2^(14*8) ...  255*2^(14*8)    -->  one of these is (10100000)*2^112
 
2^(15*8)  2*2^(15*8)  3*2^(15*8) ...  255*2^(15*8)    -->  one of these is (10101010)*2^120
sr. member
Activity: 462
Merit: 701
June 03, 2020, 03:38:42 AM
The ComputePublicKey() in kangaroo use 32 blocks of 256 precomputed points and zero are checked so it performs:
31 adds max for a full privkey (nothing when a zero byte is present) and a modular inversion.
There is also a ComputePublicKeys() which group modular inversions.
newbie
Activity: 17
Merit: 25
June 03, 2020, 03:29:54 AM
I am sure #115, #120 and #125 will go to zielar and no pool can compete. gg.

I disagree.
I spent much time to explain in the readme, in this topics or in the code the way to choose best parameters and trap to avoid.
Zielar has also to win his life and cannot spend full time to solve these puzzles.
It is far from sure that Zielar will win all the races.

Anyway, I'm working on the 1.9 in order to integrate mods from PatataFritas and support of -ws for clients.


Edit: You have no idea who Zielar is actually. He is a very competent person in his domain, I must say that from time to time I pain to follow him !



Sorry Jean Luc. I wrote a little offending. I put some resources into the search for #110 so I was little emotional for a moment. I apologize.
legendary
Activity: 1932
Merit: 2077
June 03, 2020, 02:59:40 AM
With a simple python script I can get 2^12 keys/s, but it is not tailored for the public keys with private keys so short (under 128 bit) it could reach at least 2^13 keys/s with keys so short.
What part of code needs tweaked to work with smaller priv keys?


Here there is the explanation on how it works my script:
https://bitcointalksearch.org/topic/m.54213558

Basically you have to split the private key as a sum of precomputed private keys.

In these sentences:
Quote
I use 64 groups of 15 points = 960 precomputed points
...
I split a 256 bit key in 64 pieces of 4 bit and I compute 63 additions.


you can half the groups (32 pieces of 4 bit instead of 64 for a total of 480 precomputed points) and the additions needed (31 instead of 63) if you use 128bit-private keys.

You can have a estimation too on how long it takes to perform k*G against P+Q,  about 31 times (or 63 times) more than a simple addition P+Q (that we use in the kangaroo algorithm).

I refer only to the cpu speed, because on gpus things are different, we can't exploit a fast access on a huge memory for the precomputed points.
legendary
Activity: 1932
Merit: 2077
June 03, 2020, 02:25:20 AM
You would need to check that the DP is actually valid though. That involves performing the entire walk. If you did this for every DP you would be re-doing the entire computation.

As far as I understand it is important that the DP is from a real kangaroo walk.

The difference:
As soon as a kangaroo hits a point (a point that is not qualified to be a DP by bitmask) that has been visited by a kangaroo of the other type, their walks are synchronized and the next DP they find will definately result in a collision and PK is found.
This is not the case with randomly selected points in the range that fullfill the DP bitmask criteria.

It is possible that there will be a collision with these kind of "not real walk" points though.

I agree with you, but I remember you that a proof of work is always a probabilistic task, we cannot redo the entire work to be sure that the entire work is correct.

My proposal:

let's say DP=25, we perform a check on 2 levels, a result and a process check:

level 1) result check

we check that each DP fulfils:
                   - has at least 25 zeros bits
                   - its private key is correct and lies in the correct interval

level 2) process check, proof that the points were generated with a correct path

- we check that there are at least 1/2000 of the points with x-coordinate with at least 25 + 10 zeros
- we redo only the complete path of each kangaroo that ends with a DP with at least 35 zeros

The second check is a valid proof of work, because to generate (in the correct way, with the correct jumps) a single DP with 35 zeros you need to generate correctly on average 2^10 = 1024 kangaroos with a end point with 25 zeroes, you can't fake it.

Obviously you can choose to modify + 10 zeros in +12 or +8, as you prefer.
In this way you need to redo only a small fraction on the entire work, but it is a very significative fraction, not a simple random sample.

There are no shortcuts to generate this correct fraction (DP = 35) of the entire work without doing the entire work, but the checker needs only to do a check on the fraction.
sr. member
Activity: 462
Merit: 701
June 03, 2020, 02:18:52 AM
I am sure #115, #120 and #125 will go to zielar and no pool can compete. gg.

I disagree.
I spent much time to explain in the readme, in this topics or in the code the way to choose best parameters and trap to avoid.
Zielar has also to win his life and cannot spend full time to solve these puzzles.
It is far from sure that Zielar will win all the races.

Anyway, I'm working on the 1.9 in order to integrate mods from PatataFritas and support of -ws for clients.


Edit: You have no idea who Zielar is actually. He is a very competent person in his domain, I must say that from time to time I pain to follow him !

newbie
Activity: 17
Merit: 25
June 03, 2020, 02:08:57 AM
In the end Jean Luc took the chance from all with the knowledge of creating a working Pollard Kangaroo for GPU and gave it to those with the power but no knowledge.
I am sure #115, #120 and #125 will go to zielar and no pool can compete. gg.
sr. member
Activity: 462
Merit: 701
June 02, 2020, 11:58:43 PM
As said in the README the server is simple and doesn't have an authentication mechanism.
It is quite easy for a hacker to make it crash or make it generate wrong collision to make the server unusable.
So, do not export this server to the world or hide the ip and port and give server address to trusted person only.
sr. member
Activity: 642
Merit: 316
June 02, 2020, 11:41:55 PM
-snip-
If you need it I can put together a C program, I think at least 100k key/s are possible, then 2^30 points in less than 3 hours; what speed do you think you need? How much DPs you want to check per hour?
At picture 1 2080ti produce 2200DPs every 2seconds. the same 2^30.5(Nop) / 20^20(Dpsize)=2^10.5 DP/s = 1176
If there will be for example 100 GPU 2080ti it is 110K DP/s need to be verified.
To prevent crash kangaroo server we need only check hash mask. But it is not enouch to prevent addiding job to bad actor.
Everyone can easy make forge DP where mask correct(0<=mask<1<<18), but distance and x-coordinate is fake.
Without verification this DP, actor will get +1DP to his account.
The same like in mining where each share from miner verified we need verify each DP.
newbie
Activity: 17
Merit: 25
June 02, 2020, 09:30:35 PM
-snip-
Code:
error : Designtime build failed for project 'C:\Users\danh\Desktop\kg\Kangaroo-master\VC_CUDA102\Kangaroo.vcxproj' configuration 'Release|x64'. IntelliSense might be unavailable.
Set environment variable TRACEDESIGNTIME = true and restart Visual Studio to investigate.

-snip-

Hi Dan.
I am not using Visual Studio.
I googled the problem and found some solutions that say you should repair the project (I think there is a menu option) or upgrade your visual studio.
newbie
Activity: 17
Merit: 25
June 02, 2020, 09:23:28 PM
-snip-
Checking the DPs only for validity does not mean performing the entire work again. Kangaroos are jumping from one point to another based on visited x-coordinate, and as soon as kangaroo lands the x-coordinate with the determined pattern (i.e. coordinate with 25 leading zeros -----snip-

As far as I understand it is important that the DP is from a real kangaroo walk.

The difference:
As soon as a kangaroo hits a point (a point that is not qualified to be a DP by bitmask) that has been visited by a kangaroo of the other type, their walks are synchronized and the next DP they find will definately result in a collision and PK is found.
This is not the case with randomly selected points in the range that fullfill the DP bitmask criteria.


It is possible that there will be a collision with these kind of "not real walk" points though.



newbie
Activity: 3
Merit: 0
June 02, 2020, 09:03:26 PM
Hello,

Thank you for allowing public testing of your code.

I am using CUDA 10.2 and VS 2017 (15.9), Windows Server 2019 on Google Console with a GPU Tesla V100.

I am trying to compile in VS but I can't seem to get rid of this error:

Code:
error : Designtime build failed for project 'C:\Users\danh\Desktop\kg\Kangaroo-master\VC_CUDA102\Kangaroo.vcxproj' configuration 'Release|x64'. IntelliSense might be unavailable.
Set environment variable TRACEDESIGNTIME = true and restart Visual Studio to investigate.

Any suggestions appreciated.

Thanks for your time.

Dan


sr. member
Activity: 443
Merit: 350
June 02, 2020, 09:02:14 PM
-snip-
You would need to check that the DP is actually valid though. That involves performing the entire walk. If you did this for every DP you would be re-doing the entire computation.

One way to do this would to include a checksum with the DP whete the checksum is the count of each jump point that makes up the DP. To verify it the server multiplies and adds the counts and the jump points together. This would involve more work for the client since it would need to keep count for every walk.

Checking the DPs only for validity does not mean performing the entire work again. Kangaroos are jumping from one point to another based on visited x-coordinate, and as soon as kangaroo lands the x-coordinate with the determined pattern (i.e. coordinate with 25 leading zeros from total 256 bits for DP 25) this coordinate is saved to hashtable together with the distance. So we have saved distance and x-coordinate (only 2nd half of it with length 128 bit).

To check one tame point from hashtable we just need perform one elliptic curve multiplication - converting distance (i.e. private key) to public key and compare last 128 bits of x-coordinate with saved in hashtable. For wild points we should perform one elliptic curve multiplication and addition/subtraction - compute public key from the distance and add/subtract the received point with the target public key, and compare the resulted x-coordinate with hashtable. {ok, actually it is not one addition and multiplication it consists from 32 additions, but it depends on the used algorithm and pre-computed points}

Also no need to save the whole path of the kangaroos. Only the final distinguished point (DP) with the total distance is important.

But we should not make the whole job again to check the DP. Client should perform approximately 2^25 jumps (operations) in order to find one DP. On server side we need to perform just one operation.

Agree with arulbero
Jump to: