Pollard's kangaroo ECDLP solver

[Etar]

First of all, guys i am just having posted that what i posted outside the two or three of you guys
keep me out of it, and for the rest this next one is for Etar,


Total f1+f2: count 2^51.98 in the server app, and in the client  [Count 2^44.27]

Etar was wondering is this the way it should be? or am i going somewhere wrong, and was
wondering do you have you'r server app with kangaroo 1.9, currently is 1.5

and dont need wsplit, thanks

hi, answer you in PM. if you don`t want recompile app just copy kangaroo.exe 1.9v to work folder.
And server/client app is little bit old idea(it was need when kangaroo server always crashed)
Now with -wsplit you can use mergerServer/mergerClient app (do not need to send BIG file with kangaroos)
and yes, counter during merge reflect incorrect counter, because it increased every time when merge.(what the kangaroo.exe writes to console  that’s what the client / server writes in the console, app is do not do any calculation only grab lines from kangaroo.exe console  and display it on client / server app)

[Etar]

@JeanLuc can you explain structure DP that send client to server
Each DP has 40 bytes length.

Edit: solved int128_t X;      int128_t D;      uint64_t h;
It is not easy))

dp.h - it is 18bit hash(hope i think correct)
dp.x and dp.d - it is understand for what
but for what need dp.kIdx when sending DP?

[PietCoin97]

what does all these values mean ?

what is important here the Dp counter all other counters show 2^-inf


btw is someone open to share some workfiles for merge together ?

[WanderingPhilospher]

what does all these values mean ?

what is important here the Dp counter all other counters show 2^-inf


btw is someone open to share some workfiles for merge together ?

DP count is most important. You are running at DP 25, so it will take 2^57 (whatever expected group ops is for 115) - 2^25 (your DP setting) so roughly you want your DP count up to 2^32 to be getting close to solving.

I have files for DP 30.  So I need to get close to 2^27 to be getting close to solving. 2^57(expected ops) - 2^30(my DP setting) = 2^27 DP count .

[PietCoin97]

OK and what is better for now?
And what happens when I want to merge dp30 files and dp 25 file it takes only the lower dp or not?

[WhyMe]

Some "unusable sticky thing" by me
https://github.com/Telariust/VanitySearch-appspot/releases
https://github.com/Telariust/VanitySearch-bitcrack/releases

Doing some tests with your job :
~780MKs on 2060 ( core +120, PL60 )
~950MKs on 2070 ( core +120, PL60 )

Only needed few changes in my tool to run your version, thanks !

[BitCrack]

what does all these values mean ?

what is important here the Dp counter all other counters show 2^-inf


btw is someone open to share some workfiles for merge together ?

DP count is most important. You are running at DP 25, so it will take 2^57 (whatever expected group ops is for 115) - 2^25 (your DP setting) so roughly you want your DP count up to 2^32 to be getting close to solving.

I have files for DP 30.  So I need to get close to 2^27 to be getting close to solving. 2^57(expected ops) - 2^30(my DP setting) = 2^27 DP count .

The number of points represented by the DPs is most important. If you are using a 30-bit distinguisher on GPUs, it is going to take way more than 2^27 DP's to solve #115.

[WanderingPhilospher]

what does all these values mean ?

what is important here the Dp counter all other counters show 2^-inf


btw is someone open to share some workfiles for merge together ?

DP count is most important. You are running at DP 25, so it will take 2^57 (whatever expected group ops is for 115) - 2^25 (your DP setting) so roughly you want your DP count up to 2^32 to be getting close to solving.

I have files for DP 30.  So I need to get close to 2^27 to be getting close to solving. 2^57(expected ops) - 2^30(my DP setting) = 2^27 DP count .

The number of points represented by the DPs is most important. If you are using a 30-bit distinguisher on GPUs, it is going to take way more than 2^27 DP's to solve #115.

You think so? I was using the math that was explained to me...I'm not an expert like some here, but I've seen it been said that way several times.
How long say you, or better yet, how many DPs do I need? 2^what?

[WanderingPhilospher]

Some "unusable sticky thing" by me
https://github.com/Telariust/VanitySearch-appspot/releases
https://github.com/Telariust/VanitySearch-bitcrack/releases

Doing some tests with your job :
~780MKs on 2060 ( core +120, PL60 )
~950MKs on 2070 ( core +120, PL60 )

Only needed few changes in my tool to run your version, thanks !

Concur...been flying through some ranges. Solid version. Just testing. I am trying to figure out the continue option...I want to use it every 30-60 seconds without the +100000 rekey option; without losing power. Asked Tela, hopefully he understands and knows how to. I manually changed the +100000 and went from 3400ish MK/s to 1200 MK/s.

[PietCoin97]

@WanderingPhilospher

what happens when I want to merge dp30 files and dp 25 file it takes only the lower dp or not?

[WanderingPhilospher]

@WanderingPhilospher

what happens when I want to merge dp30 files and dp 25 file it takes only the lower dp or not?

Etar can explain it a lot better than me because I'm not really sure...Jean Luc's README states:

However, work files are compatible (same key and range) and can be merged, if 2 work files have a different number of distinguished bits, the lowest will be recorded in the destination file.

So yes, it can be done, but I'm not sure if it helps much. Etar studied this in depth and combined his DP 31 and DP 28, I think.

[Etar]

@WanderingPhilospher

what happens when I want to merge dp30 files and dp 25 file it takes only the lower dp or not?

if you have 5 DPs=31 and 4 DPs=25 when merge you will get 9 DPs=25.(ofcourse if points different)
in this case droping from 31 to 25 you will need again find 64 times more new points (2^(31-25))

[math09183]

Some "unusable sticky thing" by me
https://github.com/Telariust/VanitySearch-appspot/releases
https://github.com/Telariust/VanitySearch-bitcrack/releases

I receive "Segmentation fault (core dumped)" each time I want to use --keyspace

[Jean_Luc]

Can you explain yourself better? What is 'Ygrid' ?

Ygrid is the second coordinate of the GPU thread array.
It affects performance. This is very useful for linear algebra because you can use thread coordinates to make fast matrix calculus.
In our case, this is just used to tune performance.

I was in weekend, Yesterday was also a day off in France, I restart the work today. I also have professional work to perform but I will continue to make update on github when I can for everybody. I will try to integrate ASAP the mods from  PatatasFritas and the support of -ws for the client mode. News from AndrewBrz who is progressing well with the OpenCL kernel.

Zielar solved #110 with official 1.8 and 1.9alpha for merging.

[WanderingPhilospher]

Can you explain yourself better? What is 'Ygrid' ?

Ygrid is the second coordinate of the GPU thread array.
It affects performance. This is very useful for linear algebra because you can use thread coordinates to make fast matrix calculus.
In our case, this is just used to tune performance.

I was in weekend, Yesterday was also a day off in France, I restart the work today. I also have professional work to perform but I will continue to make update on github when I can for everybody. I will try to integrate ASAP the mods from  PatatasFritas and the support of -ws for the client mode. News from AndrewBrz who is progressing well with the OpenCL kernel.

Zielar solved #110 with official 1.8 and 1.9alpha for merging.

It'll be interesting to see what my Vega VIIs can do. They murder all the RTX cards when mining ethash (90 to 100 Mh/s compared to 40-55 Mh/s). I know mining is different but we shall see how they perform when it comes to this program. Hopefully Andrew has success, at least for himself.

[arulbero]

Can you explain yourself better? What is 'Ygrid' ?

Ygrid is the second coordinate of the GPU thread array.
It affects performance. This is very useful for linear algebra because you can use thread coordinates to make fast matrix calculus.
In our case, this is just used to tune performance.

Thanks.

About using an experience of previous work.
----
So as you can see an experience didn`t help to solve next pazzle faster.
Most likely because the range is increased by 32 times in the next puzzle, and all DPs are concentrated at the very beginning of the range. Perhaps experience can help in solving the next range, but not after 5 bits.

And here is result of 3 test randomly generated keys in range 64bit and with experience from the puzzle 79:
...
In all three cases, experience helped me find the key faster.

The result is that experience helps you find the key in the current range or in the previous one, but it is absolutely useless to search in the following range that is multiple large to the current one.
In other words, in order to solve the puzzle faster you need to move from end to beginning .. first 125, then 120, then 115 and then 110))

There is a way to reuse the same DP's set in a different range.

If you have DPs in range [1,...,2^109] and you need DPs in [1,...,2^114], it is enough to

transform [1, ..., 2^114] into [1/32, 2*1/32, 3*1/32, ....,  2^114 *1 / 32 = 2^109] (a 'contraction')

where 1/32 means 32^-1 mod N. There are always 2^114 elements,  and the public key P becomes P'= 1/32 * P and lies in the same interval.

You can see [1/32, 2*1/32, 3*1/32, ....,  2^114 *1 / 32 = 2^109] as the set of the private keys respect of G,
or the same points set can be represented as [1,...,2^114]', the set of the private keys respect of G' = 1/32 * G

In this way the DPs are spread uniformly in the interval [1, ..., 2^114]'. The private key of each DP respect of G' is the previous private key * 32.

You have to modify the jumps too, instead of +r*G you have to perform +r*G', where G' = (1/32) * G.

Then you will find the private key k' of P' respect of G', that is the same private key k of P respect of G.

Basically so far we have used only the 'translation' of the interval, but we can use a 'expansion/contraction' too.

[WhyMe]

Can you explain yourself better? What is 'Ygrid' ?

Ygrid is the second coordinate of the GPU thread array.
It affects performance. This is very useful for linear algebra because you can use thread coordinates to make fast matrix calculus.
In our case, this is just used to tune performance.

I was in weekend, Yesterday was also a day off in France, I restart the work today. I also have professional work to perform but I will continue to make update on github when I can for everybody. I will try to integrate ASAP the mods from  PatatasFritas and the support of -ws for the client mode. News from AndrewBrz who is progressing well with the OpenCL kernel.

Zielar solved #110 with official 1.8 and 1.9alpha for merging.

It'll be interesting to see what my Vega VIIs can do. They murder all the RTX cards when mining ethash (90 to 100 Mh/s compared to 40-55 Mh/s). I know mining is different but we shall see how they perform when it comes to this program. Hopefully Andrew has success, at least for himself.

Someone is working on opencl support ?

[BitCrack]

what does all these values mean ?

what is important here the Dp counter all other counters show 2^-inf


btw is someone open to share some workfiles for merge together ?

DP count is most important. You are running at DP 25, so it will take 2^57 (whatever expected group ops is for 115) - 2^25 (your DP setting) so roughly you want your DP count up to 2^32 to be getting close to solving.

I have files for DP 30.  So I need to get close to 2^27 to be getting close to solving. 2^57(expected ops) - 2^30(my DP setting) = 2^27 DP count .

The number of points represented by the DPs is most important. If you are using a 30-bit distinguisher on GPUs, it is going to take way more than 2^27 DP's to solve #115.

You think so? I was using the math that was explained to me...I'm not an expert like some here, but I've seen it been said that way several times.
How long say you, or better yet, how many DPs do I need? 2^what?

That 2^27 figure assumes the average walk length is 2^30. The GPU works by doing many slow walks in parallel e.g. 60 million walks that do 20 iterations per second. At that rate, it will take 2^30 / 20 seconds = 1.7 years before any of the walks are 2^30. Your DP count is going to be a few powers of 2 higher than 27.

[COBRAS]

Can you explain yourself better? What is 'Ygrid' ?

Ygrid is the second coordinate of the GPU thread array.
It affects performance. This is very useful for linear algebra because you can use thread coordinates to make fast matrix calculus.
In our case, this is just used to tune performance.

I was in weekend, Yesterday was also a day off in France, I restart the work today. I also have professional work to perform but I will continue to make update on github when I can for everybody. I will try to integrate ASAP the mods from  PatatasFritas and the support of -ws for the client mode. News from AndrewBrz who is progressing well with the OpenCL kernel.

Zielar solved #110 with official 1.8 and 1.9alpha for merging.

Good day Jean_Luc.

Because you will restart work, Can you start make a version for ASIC I think because KANGAROO need very many power, ASIC version is more perspective and adequate task for solving KANGAROO.




If you don't have an ASIC I think the discussion participants will support the idea of chipping in money and buying you one !





What you think about this ?

BR. 

[MrFreeDragon]

-snip-
Because you will restart work, Can you start make a version for ASIC I think because KANGAROO need very many power, ASIC version is more perspective and adequate task for solving KANGAROO.


-snip-

This is impossible. Kangaroo works with elliptic curve operations (ECDSA) and no need to hash anything.
ASIC was designed for hash calculations. ASIC works only with algorithms designed by the producer: SHA-256, Scrypt, Cryptonight, Ethash, Blake, X11. Different models have different set of algorithms.

For Kangaroo algorithm only the elliptic curve operations are required (i.e. transformation of the private key to the public key, operations with the points such as additions, subtractions and multiplications). ASICS does not support it.