Topic: Pollard's kangaroo ECDLP solver - page 64. (Read 58537 times)

If you are searching with GPU and searching in a decent sized bit range, say 64 bit range and up, you may get a few same herd collisions, but it's not a bad thing. The program just resets those kangaroos to start a different path from a different random point.

Smaller DP and smaller ranges will create more same herd collisions; especially if using GPU.

Does your program solve keys, or just keep running?

Are kangaroo collisions in the same herd a bad thing? My program (https://github.com/ZenulAbidin/Kangaroo-256) was doing that until I changed the hash table index calculation to use & HASHMASK instead of % HASHMASK.

To my understanding, they don't slow down the search - that happens when your DP size is too small for your search range and initial points are lost - but it just keeps going on forever without colliding the private key in the hash table.

code complex more than I can understand
I run pollard-kangaroo-multi.py with config flag_verbose = 2   

look like start from  random tame wild by random with distance tame wild
and get xpoint (how to calculate)
then compare both
and jump to next tame wild (and jump)
if not yet collision do again new random

I am not programmer not yet clear to read complex code

Can I do easy by using python library bit
https://ofek.dev/bit/guide/keys.html

import bit
pvk = random.randrange(2**119,2**120)
key = Key.from_int(pvk)
X,Y = key.public_point

this is same value or not

Thank you for help answer

kangaroo save file is binary format right
I try to open in text editor it is not work

this one random on range right
00CF048E0B6645018CE925D30B01F1  = 304597017357365078784491997823473

this long how can I calculate
D141E70913A6F67CD00DB847B31C28  = 1086526704572680266696100020277681192

I think kangaroo.exe calculate better

may be difference work with kangaroo.exe and kangaroo python version

example pubkey 03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4

command

results.txt

tame.txt

wild.txt


match/collision

tame.txt
ec9d5049bd4509aa41e1f5c312de1900d3eac4adba0692a41286b2497e520000 1110317004752
wild.txt
ec9d5049bd4509aa41e1f5c312de1900d3eac4adba0692a41286b2497e520000 106665591802


number = 1110317004752
and
number = 106665591802

it is random from command = random.randint

and this value
ec9d5049bd4509aa41e1f5c312de1900d3eac4adba0692a41286b2497e520000

Are they come from?
How to calculate?

Can you give example of what you mean by "two number one is hash on hex format and two is random value in range
What is first number on hex" ?

If you mean the columns from the saved file, for tame and wild both, column/tab 1 is the point, a.k.a pubkey, for tame in column/tab 2 is the distance, a.k.a. privkey and column/tab 2 for the wild is the distance a.k.a. the offset of pubkey you are searching for. If column 1 matches up, then for JLPs kangaroo program, you would subtract column/tab 2 "distances" from each other and then add back the start range you entered in command line.

Example:
Tame
Wild

Both column 1s line up (points) so that is a collision. Now subtract column 2s from each other and add back start range and that is the private key to the pubkey you are searching for.

EDIT: I forgot to mention that the column 1/pubkeys are the least significant bits, the last x amount of characters in the pubkey; so in the example above, if you look at privkey CF048E0B6645018CE925D30B01F1 you will see that D141E70913A6F67CD00DB847B31C28 are the last bits of its pubkey's x coord.

Kangaroo calculate  Tame,Wild

Can anybody tell me what number Tame,Wild calculate and How I calculate with what formula?

two number one is hash on hex format and two is random value in range
What is first number on hex

I would like to testing some experiment by  random Tame,Wild (in range) and see can possible to collision or not

Is this output from my fork? (I did not bump the version number, maybe it would be wise for me to do so)?

I have not changed the code related to speed reporting, and I also haven't made any of the planned optimizations yet.

For a kangaroo pool, you would not split the keyspace up. You would wind up doing way more group operations versus everyone (all gpus) working on the full keyspace.

The pool would have to have powerful hardware.  Huge SSD harddrives (to hold distinguished points + kangaroo positions of all gpus), lots of RAM, and lots of CPU cores.  Merging the files is the issue/biggest challenge.

That's why I tried with the Baby Step Giant Step. But everyone thinks they can come up with new creative way to solve #120 and do it on their own. Some people probably have the hardware to do so, but not most.

EDIT: Just to add about breaking #120 down into bite size chunks of 64 bits. That would be 72,057,594,037,927,936 ranges to be searched. So that would also be 72,057,594,037,927,936 minutes to search and cover entire range.  But the biggest problem is, you still wouldn't be 100% to find the key unless everyone has high -m option set.   But you are right, It would be faster than brute forcing #64. 50% of brute forcing #64 = 2^63 . Kangaroo only requires 2^60 +-1 .

Why no body create Kangaroo 120 bit pool?
if can do it make pool fast to found key
I think may be fast before found 64 bit bitcrack pool


compare now bitcrack scan pool already 1 quadrillion from all 9 quadrillion on 64 bit
1,000,000,000,000,000,000 =  1 Quintillion

calculate kangaroo
2**199 = 664613997892457936451903530140172288

split kangaroo for each 2**64 for small keyspace search
2**199/2**64
664613997892457936451903530140172288/18446744073709551616 = 36028797018963968 time(slot)
36,028,797,018,963,968 = 30 Quadrillion scan
1,000,000,000,000,000 = 1 Quadrillion
1,000,000,000,000,000,000 = 1 Quintillion = 1000 Quadrillion

kangaroo is power full can scan 64 bit on 1 minute

What is this: "Kangaroo v2.1 : Added Start End Options"

Did you compile yourself? Tweak code?

these is the data of that kind speed......

Kangaroo v2.1 : Added Start End Options
Start:4956C9891727D63DA8F9B49FE524C02206504109B416CC454C3E20EB14441F56
Stop :4956C9891727D63DA8F9B49FE524C02206504109B416CC454D3E20EB14441F55
Keys :3
Number of CPU thread: 2
Range width: 2^56
Jump Avg distance: 2^28.01
Number of kangaroos: 2^18.18
Suggested DP: 7
Expected operations: 2^29.12
Expected RAM: 185.6MB
DP size: 7 [0xFE00000000000000]
SolveKeyCPU Thread 1: 1024 kangaroos
SolveKeyCPU Thread 0: 1024 kangaroos
GPU: GPU #0 Quadro K2100M (3x192 cores) Grid(6x384) (29.5 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^18.17 kangaroos [1.3s]
[1948901416.30 MK/s][GPU 1193969262.41 MK/s][Count 2^29.27][Dead 2][16s (Avg 13s)][155.9/201.6MB]

Yeah something is wrong with the code in your program or your hardware.

Hate to tell you, if you got that kind of speed with 1 rtx 2060 you could solve every key in the 2^256 range pretty quickly.

Something is wrong in your setup, software or hardware.

I show a speed of 140168155140.13 MK/S in kangaroo with one rtx 2060..........with 8 x rt 3090, will be more around 10^21 or 22 digits. May be more who knows

Yeah that seems way too fast regardless of what you have seen elsewhere. Especially for a CPU to be getting 40,000 MKey/s.

5,000 per 3090 card seems maybe right?  I'm not sure. a V100 gets around 1,600 MKey/s

How many MKey/s are you expecting from one 3090 card?

No, its 40 000Mk/S cpu and 40 000 MK/S gpu speed..........but these is too slow as I seen a here : https://github.com/JeanLucPons/VanitySearch/issues/97

Strange. What are your input file range and public keys, and any command line options you used?

EDIT: please also confirm what your reported speed is (total and GPU) because 80,000MKeys/s sounds way too high. Did you mean 80 MKeys/s or something in that ballpark?

Does the segmentation fault happen ONLY when you change the compute cap 8.6 threads constant to 128 [I left it on 64 by default]?

I tries running new kangaroo-256 with { 0x86, 128 }, changes to GPUEngine.cu with 8 x RTX 3090 cards and its showing segmentation fault (core dumped error). I also tries running { 0x86, 64 }, with these codes but its slow like 80 000 MK/S.
Sill some changes need to build its capacity.

thanks

I already completed that change  

Now that that's done I'm working on trying to speed up Int arithmetic (there's a couple of add carry statements which I can replace with SSE2 add instructions if I reserve the upper half of 64-bit bits for carry bits.

Maybe while I'm at it I'll put it on Github as well.

How can I testing, it works with 256 function upgade?

Try use with 256 bits full keys?

What mean of 256?
Can using wide of keyspace 256bits
or Can using with full 256 keys?

What feature of kangaroo256 upgrade?


I don't know mush about deep technical and deep programing (just user)
Can possible to develop to 512 bits or 1024 bits? Just ask to known
I think over like bitcoin use at 256 bits or sha256, if creator bitcoin think first time 64bit is high enough now is crack already.
512 bits or 1024 bits is thank like buy power supply for PC buy 1100 Watt PSU and using  600W for performance and long time using with no high heat. something like that
may be possible create 512 bits or 1024 bits for high performance and may be no need to update much in future
may be puzzle up to 120 bit and 160 bits with using 256 bit support may be difficult to scan

and or think reversal 64 bit is short right 256 bit is long right  over 4 time (256/64=4) (and 256/128=2)
It scan possible code for double calculate same time like calculate 64bit 4 calculate parallel in 1 one time
or may be flip method combine 64+64+64+64= 256 bit calculate and split
may be GPU system calculate something like that already no need to think about it
sorry just think about number may be can not possible on technic, I don't know computer knowledge mush

I am confused. I thought you were trying to get the program so it would store 256 bits in the hashtable? Are you also working on different things inside the program?