Topic: Science Fair Project to trap Bitcoin private keys using Kangaroos! - page 2. (Read 7850 times)

In this case, remains the question whether the program stops running immediately or not when one of the threads finds the solution. We need to ask the developper

Naturally I did a few measurements. Python scripts behaved the same way. The single-core and multi-core scripts showed approximately the same search time, although the multi-core speed was much higher.

Thank's Telariust!
It will take time but i could try to implement the kangaroo method myself in c#,
to learn if it would be possible to detect a parallelism for the average usage of sqr(2^(bit-2)) operations, when halfing x values of the searchspace,
unless you can confirm from your experience that there is no such behaviour detectable?

Currently it's just like you would guess in a keyspace of 1024 that the privatekey is greater than 512...
BUT...
If it is possible to find a privatekey less than 512 in less than 150% of sqr(2^(bit-1)) it should be an average overall speedgain.

My current idea to achieve that would be with the cost of an extra wild, when pushing the searchspace to point Infinity.
This wild point could just be the negation point of the orginal point without or with offset.
Cause i don't see ECPoint subtraction implemented in your script, you can use addition:
therefore the ECPoint offset calculation to wrap the space arround Infinity should be G.Multiply(ORDER-SpaceL-(SpaceL/2)).

Thank's

Can you explain why don't you keep the points on disk, and keep them only in memory? And also please tell which point you keep - every point, or just some multipliers of predefined number (let's say 10^10)?

No problem.  We enjoy your informative posts and have used several of your ideas in our program.

Right now I am very busy with work and my daughter is very busy in school so we have not had time to work on the program.

We will get back to our version when things slow down a bit.

BTW we keep all our points in memory in a hash table also.  Disk access is a no no, especially when we are targeting a GPU (eventually).

Even with higher speeds, runtime may fluctuate a lot.  In order to compare performances, you need  several trials.

This is Ryzen 7 2700 (8 cores 16 threads)
I understand that -t is the number of threads.
The question is why the speed increases, but time does not decrease, more often it even increases.

why are you  ?

scaling depends on CPU, ie # of cores (typically 2,4,8 ... or 56 if you have a Intel® Xeon® Platinum 9282 Processor )
 and # of threads per core (which is one or two)

 -t is generally equal to core number ... on some cpu's you might get better performance for -t equal to  2 x core number.
 

Thanks for your answer and all your answers.
The Hash table is only 1024 entries, is it enough for cases like #110 ?

-t 4 -bits 55 1.0M j/s [runtime]  00:04:01

-t 16 -bits 55 3.2M j/s [runtime]  00:04:33 

Telariust, there is nothing in Source Code, only README.md

1) Algo of Pollard is probablistic nature (Birthday Paradox, Kruskal's card trick, etc)
The solution time is not stable; several attempts (timeit loop in python script) are needed to obtain the avg runtime and jumps.
heuristic time rather than deterministic

2) threads should run at equal speed.
If input -t N over than really N cores, so threads will compete, some will be faster and some will be left behind.

3) maybe my code have bug, need more tests

#################
post dedicated cuda/opencl implementations

we have some ways for just ready GPU implement
good candidates to rewrite:

1) cuda, c++, VanitySearch,  by Jean_Luc
https://github.com/JeanLucPons/VanitySearch

2) cuda/opencl, c++, BitCrack, by brichard19
https://github.com/brichard19/BitCrack

2) cuda, python, pollard-rho, by brichard19
https://github.com/brichard19/ecdl

3) cuda, ?, pollard-rho
github.com/beranm14/pollard_rho/

4) opencl, C#, pollard-rho
github.com/twjvdhorst/Parallel-Pollard-Rho/

I intend to evaluate their performance, as well as rewrite one or more to kangaroo.

#################

multicore, CPU only, c++, based on engine VanitySearch1.15
https://github.com/Telariust/vs-kangaroo/releases

bignum lib by Jean_Luc is good, only %15 slower than bitcoin-core/secp256k1 lib (with raw asm mult)


#################

not

BitCrack use batch packet inversion (x8 speed-up).
We cant(OR CAN?..) use its in kangaroo method, so 1430/8 = 175M j/s

but on screen
see 4xV100=6515M j/s, each 1600M j/s

now unclear..

#################

https://bitcointalksearch.org/topic/m.48224432
November 25, 2018 this man speaks as if he already has a finished implementation.


O great master, j2002ba2, I urge you!   Plz, come and explain to the miserable mortals, which means s2,s1,m3,m4 in your program!

#################
https://docs.nvidia.com/cuda/volta-tuning-guide/index.html
he high-priority recommendations from those guides are as follows:
 - Find ways to parallelize sequential code;
 - Minimize data transfers between the host and the device;
 - Adjust kernel launch configuration to maximize device utilization;
 - Ensure global memory accesses are coalesced;
 - Minimize redundant accesses to global memory whenever possible;
 - Avoid long sequences of diverged execution by threads within the same warp;


about last, " - Avoid long sequences of diverged execution by threads within the same warp;"
parallelism algo by Pollard (U+V) escape problem of collisions between kangaroos of the same herd;
this allows you to completely abandon the correction block because adding IF () inevitably breaks the parallelism of the GPU;

#################

to be continued..

Yes, this was my point.
I first thought that there is a parallel behaviour, cause the script was finding the publickey when changing y value only, and we could use it to only make sqr(2^(bit-2)) operations,
unitil i found a completely different pubkey from another space.
You don't have to set from 8:... bitspace it also works with orginal keyspace

It's not a bug i guess...i am cleary not an expert in this matter , but that's what i think:
It seems logical, it will just take longer on average to find the key.
The average jumpsize should be calculated from the searchspace.
When you search for exampe puplic key from 37 bit within 40 bit the average jumpsize should be bigger and the opposite when searching 43bit pubkey within  40 bit.

It's strange, that when you change only the y value of the key, you will find the orginal publickey with privatekey, but not the one you changed.

hi
in script, there is bug, or maybe he unable to catch point, as
if you have 37 bit pubkey
and you command is
./script 40 02xxxxxxpublickey
40 bit mean search in bit range
but script will find key in 37 bit
if you have 42 bit key, and same command for search in 40 bit by apply 40 or 8:fffff.... bit range, script will find 42 key

its not restrict only for define bit range
mean always find start from 8 to onword, so its take time consume, Smiley
test it

seems like you need to change your settings too

i sent you PM, 2 time in last 2 days, have some time for reply
Looking Farword

I deleted my posts to avoid any confusions.

Now i better understand how kangaroo jumping works, i didn't even know that it is possible to find a publickey which is not in the space we are searching for.
That's why it finds the publickey when you just change Y.
I thought that when a tame kangaroo jumps out of space, a new tame and wild kangaroo would be set within the space to start jumping again.

As my suggestion, it would be the same if you just set the searchspace for from 2^(bit-1) > (2^(bit)-1) to (2^(bit-1) + 2^(bit-2)) > (2(bit)-1).
You would have a 50% chance to find the key in sqr(2^(bit-2)).
In my tests it must have been luck to find the keys not in that 50%chance in less time than average.
The only benefit i see by pushing the space with the middle to Infinity point, would be if a X value match could be detected when a wildkangaroo starts in negative mirrored space. That would possible be a rarely case by the time it catches up to the positive space where all tame kangaroos would start.

Exactly that was the plan > wraping the space W with the middle of the space to point infinity.
So that actually all x values get halfed.
I thought possibly that when a wild kangaroo jumps, a jump from the tame kangaroo in the negative space in the different direction could also lead to the same result in less time(cause it would be the same distance).
The key is definitely to find in the space(bit-2), however if you say regarding the kangaroo method, that there is no speed gain, the method is useless.
i have to test #35. i would not understand if the key is not findable. like #50 if the key is on the negative side it will find the privatekey and publickey on the positiv side,there will be just no publickey match> Watch it in the console im not sure if gets to the result.txt
Thanks for testing!  

Absolutely!


In general terms, it could be explaind like this: for bit key the range is from 2^(bit-1) up to 2^(bit)-1, where the total number of combinations (range length) is 2^(bit-1).
2^(bit-2) is a half of 2^(bit-1), so 2^(bit-1) + 2^(bit-2) is 1.5 * 2^(bit-1) --> the absolute middle of the total range for the (bit) key.

824633720832 is just 0xC000000000
179017692118  is 0x29AE4933D6
1003651412950  is  0xE9AE4933D6

So 0xC000000000 is just the mid point of the normal #40 range 8000000000:FFFFFFFFFF
in other words the #40 sqr(2^(bit-2)) range you are mentioning is just the position of the private key from the mid-point.
You are not doing less work, you've just changed the origin.
Instead of working with the tame kangaroo matching the private key solution, you are working with the corresponding wild kangaroo.