Pollard's kangaroo ECDLP solver - page 109.

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote from: Etar on June 04, 2020, 04:23:59 AM

Quote from: WanderingPhilospher on June 04, 2020, 01:13:39 AM

Quote from: WanderingPhilospher on June 03, 2020, 10:14:48 AM

What does program compare to result in a solved key/solution?

(Tame,Wild) = Collision
k = k1 + Tame.dist - Wild.dist

Tame File:

Code:

000000000000054e3f71000000000a250208a 0000000024a2b6bb0000000026dd90e3

Wild File:

Code:

00003000000007666967d0000000093b5394a 000000008dc1e960000000002be62262

Those are from Tame and Wild files. What exactly does the program look for in those 2 lines above to result in solved key? Can anyone break it down by line and what the line/characters represent? Thanks.

Anyone?

i do not know what wild and tame file you have, but work file has Dp points like tame and wild.
Each dp have 2 128bit word distance and x-coordinate.
There will be collision if x-coordinate of tame and wild Dp the same.
to chech what type of Dp need test 126 bit of distance if it zero then it is tame dp, if it is one then dp is wild.

Thank you.
The above tame and wild files, were from some random search I did. These tame and wild were exported from a workfile using this program.
So for the above tame and wild, the first part of each line needs to match; the x coord? The second part is the distance and it just tells us what kind of kangaroo it is?

Etar

sr. member

Activity: 617

Merit: 312

Quote from: WanderingPhilospher on June 04, 2020, 01:13:39 AM

Quote from: WanderingPhilospher on June 03, 2020, 10:14:48 AM

What does program compare to result in a solved key/solution?

(Tame,Wild) = Collision
k = k1 + Tame.dist - Wild.dist

Tame File:

Code:

000000000000054e3f71000000000a250208a 0000000024a2b6bb0000000026dd90e3

Wild File:

Code:

00003000000007666967d0000000093b5394a 000000008dc1e960000000002be62262

Those are from Tame and Wild files. What exactly does the program look for in those 2 lines above to result in solved key? Can anyone break it down by line and what the line/characters represent? Thanks.

Anyone?

i do not know what wild and tame file you have, but work file has Dp points like tame and wild.
Each dp have 2 128bit word distance and x-coordinate.
There will be collision if x-coordinate of tame and wild Dp the same.
to chech what type of Dp need test 126 bit of distance if it zero then it is tame dp, if it is one then dp is wild.

Kpot87

jr. member

Activity: 43

Merit: 1

Quote from: WanderingPhilospher on June 04, 2020, 01:13:39 AM

Quote from: WanderingPhilospher on June 03, 2020, 10:14:48 AM

What does program compare to result in a solved key/solution?

(Tame,Wild) = Collision
k = k1 + Tame.dist - Wild.dist

Tame File:

Code:

000000000000054e3f71000000000a250208a 0000000024a2b6bb0000000026dd90e3

Wild File:

Code:

00003000000007666967d0000000093b5394a 000000008dc1e960000000002be62262

Those are from Tame and Wild files. What exactly does the program look for in those 2 lines above to result in solved key? Can anyone break it down by line and what the line/characters represent? Thanks.

Anyone?

Ask Etar he know

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote from: WanderingPhilospher on June 03, 2020, 10:14:48 AM

What does program compare to result in a solved key/solution?

(Tame,Wild) = Collision
k = k1 + Tame.dist - Wild.dist

Tame File:

Code:

000000000000054e3f71000000000a250208a 0000000024a2b6bb0000000026dd90e3

Wild File:

Code:

00003000000007666967d0000000093b5394a 000000008dc1e960000000002be62262

Those are from Tame and Wild files. What exactly does the program look for in those 2 lines above to result in solved key? Can anyone break it down by line and what the line/characters represent? Thanks.

Anyone?

Jean_Luc

sr. member

Activity: 462

Merit: 696

6*sqrt(N) => 99.752% chance that you found the key so ~0.25% chance that the key is well in the range.
This value assume that your setup is well tuned with a negligible DP overhead.

math09183

member

Activity: 170

Merit: 58

What is the earliest moment to be sure that range is wrong and result is outside? 6N?

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

What does program compare to result in a solved key/solution?

(Tame,Wild) = Collision
k = k1 + Tame.dist - Wild.dist

Tame File:

Code:

000000000000054e3f71000000000a250208a 0000000024a2b6bb0000000026dd90e3

Wild File:

Code:

00003000000007666967d0000000093b5394a 000000008dc1e960000000002be62262

Those are from Tame and Wild files. What exactly does the program look for in those 2 lines above to result in solved key? Can anyone break it down by line and what the line/characters represent? Thanks.

Jean_Luc

sr. member

Activity: 462

Merit: 696

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.

Etar

sr. member

Activity: 617

Merit: 312

Quote from: Jean_Luc on June 03, 2020, 02:18:52 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...

Quote from: zielar on May 23, 2020, 08:36:32 AM

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.

Interested2020

newbie

Activity: 3

Merit: 0

Quote from: Jean_Luc on 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

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!

Jean_Luc

sr. member

Activity: 462

Merit: 696

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

Interested2020

newbie

Activity: 3

Merit: 0

Quote from: Tamarindei on June 02, 2020, 09:30:35 PM

Quote from: Interested2020 on June 02, 2020, 09:03:26 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.

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.

brainless

member

Activity: 330

Merit: 34

Quote from: Jean_Luc on June 03, 2020, 02:18:52 AM

Quote from: Tamarindei on June 03, 2020, 02:08:57 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

next time guys make bets on fixed match and definatlly you all will win,

Jean_Luc

sr. member

Activity: 462

Merit: 696

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
  }

arulbero

legendary

Activity: 1932

Merit: 2077

Quote from: Jean_Luc on 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.

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

Jean_Luc

sr. member

Activity: 462

Merit: 696

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.

Tamarindei

newbie

Activity: 17

Merit: 25

Quote from: Jean_Luc on June 03, 2020, 02:18:52 AM

Quote from: Tamarindei on June 03, 2020, 02:08:57 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.

arulbero

legendary

Activity: 1932

Merit: 2077

Quote from: WanderingPhilospher on June 02, 2020, 08:30:10 PM

Quote from: arulbero on June 02, 2020, 04:54:05 PM

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.

arulbero

legendary

Activity: 1932

Merit: 2077

Quote from: BitCrack on June 02, 2020, 06:13:27 PM

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.

Quote from: Tamarindei on June 02, 2020, 09:23:28 PM

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.

Jean_Luc

sr. member

Activity: 462

Merit: 696

Quote from: Tamarindei on June 03, 2020, 02:08:57 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 !

Topic: Pollard's kangaroo ECDLP solver - page 109. (Read 58667 times)