Hi albertajuelo and kTimesG
thank you both for your replies, especially albertajuelo's detailed explanation was very helpful!
While being here to solve the puzzle, the process itself has become more interesting than the price itself. The parallel computing power of GPUs it will become my next learning endeavour.
albertajuelo and kTimesG if not bothering you, please DM me as I cannot send you as a newbie (bitcointalk by default has deactivated the option to receive from newbies DMs)
Thanks
Topic: Solving ECDLP with Kangaroos: Part 1 + 2 + RCKangaroo - page 3. (Read 7214 times)
3) i rent an RTX 4090 but no matter the options I use, it doesn't utilize the full RAM of the GPU...why is that? is it from my side or a bug in your updated version?
As the above post explained it in too many words, using the GPU memory is not beneficial at all. The highest performance occurs when 0 (zero) bytes of memory are being used. The highest throughput is a fine balance between the GPU clock (cycles/s), the kernel implementation, the launched grid size, and the size of the on-chip registers, L1 cache, and L2 cache. This balance greatly differs from one GPU to another, but in all cases, filling up the GPU memory with a gazillion kangaroos is a very bad idea, as it slows down the computations and also greatly increases the DP overhead, for no good reason.
In essence, the less kangaroos, the better.
Updated Part #1, v1.4:
- added option to make K better at the range edges (for SOTA and SOTA+) - define BETTER_EDGE_K.
- added option to see interval stats - define INTERVAL_STATS.
- fixed some bugs.
- added option to make K better at the range edges (for SOTA and SOTA+) - define BETTER_EDGE_K.
- added option to see interval stats - define INTERVAL_STATS.
- fixed some bugs.
First, Happy New Year to everybody!
RetiredCoder thank you for sharing your work!
I had commented on your repo with a pdf that may be useful to speedup the code. Also, I asked you kindly to contact me to my email but you didn't, which is a bit sad, but it's up to you.
Regarding the RCKangaroo version I have three questions:
1) does it use any CPU for DPs?
I ask because I use a rented GPU and I am not sure if I can get a powerful CPU from this provider
2) can you explain a bit the ideal -dp value for small and high puzzles and the impact on each case?
3) i rent an RTX 4090 but no matter the options I use, it doesn't utilize the full RAM of the GPU...why is that? is it from my side or a bug in your updated version?
Thanks
Hi tmar777,
You should learn a bit about how programming works with CUDA (Compute Unified Device Architecture) and how RetiredCoder has implemented it in his code.
In CUDA, you work with the following:
* Kernel: name of a function run by CUDA on the GPU.
* Thread: CUDA will run many threads in parallel on the GPU. Each thread executes the kernel.
* Blocks: Threads are grouped into blocks, a programming abstraction. Currently a thread block can contain up to 1024 threads.
* Grid: contains thread blocks.
If we focus on the software that RetiredCoder has shared on GitHub (https://github.com/RetiredC/RCKangaroo):
There are currently 4 Kernels:
* KernelGen: Runs once at the beginning this kernel calculates start points of kangs
* KernelA: this kernel performs main jumps
* KernelB: this kernel counts distances and detects loops Size>2
* KernelC: this kernel performs single jump3 for looped kangs
Then KernelA, KernelB and KernelC are run in a loop where if we ignore KernelGen (since it is only run once at the start) in percentages of time it would be something like this:
* KernelA: 90%
* KernelB: 4%
* KernelC: 1%
So, you have to understand that the executable that is run will run on the CPU and then in CUDA the Kernels will run on the GPU.
Answering your questions:
1) This problem does NOT require much CPU. This problem is computationally intensive on the GPU. Imagine that it needed 400x RTX 4090 to be able to complete the 129-bit puzzle.
2) To understand DPs and how they affect. First you need to know what a DP is: Distinguished points: a point is a distinguished point if its representation exhibits a certain bit pattern, e.g., has the top 20 bits equal to zero.
You have to know that you have a number of X kangaroos that make Y jumps every second.
Now if we use a DP of Z bits, that means that depending on the Z, that will be the average chance that a kangaroo will find a point that has that DP.
The higher the Z, the harder it will be to find that DP.
Now I recommend that for you to learn better in a practical way, you play with if I use a very low DP, what happens to the memory? How many points do I store?
Same if I use a very high DP.
3) When running any software, these are the metrics (there are more, but these could be the main ones) that one should look at:
* CPU usage
* Disk usage (disk I/O: input/output operations).
* RAM usage
With this you have a view of what is happening with the application you are running. In this case, and as I already told you, it is an application that uses CUDA, that is, it makes use of the GPU, therefore, you should analyze:
* GPU index (starts from 0)
* GPU name
* GPU temperature
* GPU memory usage (Used / Total). Here you can see how different memories are used
* Using CUDA Cores and SMs
You can use `nvidia-smi` or other tools like:
* https://github.com/XuehaiPan/nvitop
* https://github.com/Syllo/nvtop
* NVIDIA Nsight Compute (https://developer.nvidia.com/nsight-compute)
To sum up: the important thing is not the RAM or memory usage that the GPU uses, but the amount of work that it is processing in the kernels.
I hope it has helped you and if you have any questions, I am here to help you.
Updated Part #1, v1.4:
- added option to make K better at the range edges (for SOTA and SOTA+) - define BETTER_EDGE_K.
- added option to see interval stats - define INTERVAL_STATS.
- fixed some bugs.
- added option to make K better at the range edges (for SOTA and SOTA+) - define BETTER_EDGE_K.
- added option to see interval stats - define INTERVAL_STATS.
- fixed some bugs.
First, Happy New Year to everybody!
RetiredCoder thank you for sharing your work!
I had commented on your repo with a pdf that may be useful to speedup the code. Also, I asked you kindly to contact me to my email but you didn't, which is a bit sad, but it's up to you.
Regarding the RCKangaroo version I have three questions:
1) does it use any CPU for DPs?
I ask because I use a rented GPU and I am not sure if I can get a powerful CPU from this provider
2) can you explain a bit the ideal -dp value for small and high puzzles and the impact on each case?
3) i rent an RTX 4090 but no matter the options I use, it doesn't utilize the full RAM of the GPU...why is that? is it from my side or a bug in your updated version?
Thanks
Updated Part #1, v1.4:
- added option to make K better at the range edges (for SOTA and SOTA+) - define BETTER_EDGE_K.
- added option to see interval stats - define INTERVAL_STATS.
- fixed some bugs.
- added option to make K better at the range edges (for SOTA and SOTA+) - define BETTER_EDGE_K.
- added option to see interval stats - define INTERVAL_STATS.
- fixed some bugs.
Thank you a lot for the work you are doing, I do wonder if you had implemented or found a way to implement this new method? https://arxiv.org/html/2409.08784v1
Why would anyone get past the title of that paper? Its title is "How to cook potatoes better", while what we are interested in here is "how to make the perfect cheesecake". Elliptic curves DLP is not a DLP over a finite prime field, it's over curve points defined over a finite prime field. Notice the difference.
Hi all,
Here is my research about using kangaroo methods to solve ECDLP, Part 1.
Open source: https://github.com/RetiredC/Kang-1
This software demonstrates various ways to solve the ECDLP using Kangaroos.
The required number of operations is approximately K * sqrt(range), where K is a coefficient that depends on the method used.
This software demonstrates five methods:
1 - Classic. The simplest method. There are two groups of kangaroos: tame and wild.
As soon as a collision between any tame and wild kangaroos happens, the ECDLP is solved.
In practice, K is approximately 2.10 for this method.
2 - 3-way. A more advanced method. There are three groups of kangaroos: tame, wild1, and wild2.
As soon as a collision happens between any two types of kangaroos, the ECDLP is solved.
In practice, K is approximately 1.60 for this method.
3 - Mirror. This method uses two groups of kangaroos and the symmetry of the elliptic curve to improve K.
Another trick is to reduce the range for wild kangaroos.
In practice, K is approximately 1.30 for this method.
The main issue with this method is that the kangaroos loop continuously.
4 - SOTA. This method uses three groups of kangaroos and the symmetry of the elliptic curve.
In practice, K is approximately 1.15 for this method. The main issue is the same as in the Mirror method.
I couldn’t find any papers about this method, so let's assume that I invented it
5 - SOTA+. This method is the same as SOTA, but also uses cheap second point.
When we calculate "NextPoint = PreviousPoint + JumpPoint" we can also quickly calculate "PreviousPoint - JumpPoint" because inversion is the same.
If inversion calculation takes a lot of time, this second point is cheap for us and we can use it to improve K.
Using cheap point costs only (1MUL+1SQR)/2. K is approximately 1.02 for this method (assuming cheap point is free and not counted as 1op).
Again, I couldn’t find any papers about this method applied to Kangaroo, so let's assume that I invented it.
Important note: this software handles kangaroo looping in a very simple way.
This method is bad for large ranges higher than 100 bits.
Next part will demonstrate a good way to handle loops.
PS. Please don't post any stupid messages here, I will remove them; also don't post AI-generated messages and other spam.
Here is my research about using kangaroo methods to solve ECDLP, Part 1.
Open source: https://github.com/RetiredC/Kang-1
This software demonstrates various ways to solve the ECDLP using Kangaroos.
The required number of operations is approximately K * sqrt(range), where K is a coefficient that depends on the method used.
This software demonstrates five methods:
1 - Classic. The simplest method. There are two groups of kangaroos: tame and wild.
As soon as a collision between any tame and wild kangaroos happens, the ECDLP is solved.
In practice, K is approximately 2.10 for this method.
2 - 3-way. A more advanced method. There are three groups of kangaroos: tame, wild1, and wild2.
As soon as a collision happens between any two types of kangaroos, the ECDLP is solved.
In practice, K is approximately 1.60 for this method.
3 - Mirror. This method uses two groups of kangaroos and the symmetry of the elliptic curve to improve K.
Another trick is to reduce the range for wild kangaroos.
In practice, K is approximately 1.30 for this method.
The main issue with this method is that the kangaroos loop continuously.
4 - SOTA. This method uses three groups of kangaroos and the symmetry of the elliptic curve.
In practice, K is approximately 1.15 for this method. The main issue is the same as in the Mirror method.
I couldn’t find any papers about this method, so let's assume that I invented it
5 - SOTA+. This method is the same as SOTA, but also uses cheap second point.
When we calculate "NextPoint = PreviousPoint + JumpPoint" we can also quickly calculate "PreviousPoint - JumpPoint" because inversion is the same.
If inversion calculation takes a lot of time, this second point is cheap for us and we can use it to improve K.
Using cheap point costs only (1MUL+1SQR)/2. K is approximately 1.02 for this method (assuming cheap point is free and not counted as 1op).
Again, I couldn’t find any papers about this method applied to Kangaroo, so let's assume that I invented it.
Important note: this software handles kangaroo looping in a very simple way.
This method is bad for large ranges higher than 100 bits.
Next part will demonstrate a good way to handle loops.
PS. Please don't post any stupid messages here, I will remove them; also don't post AI-generated messages and other spam.
Been interested about this puzzle for more than a week now; unfortunately I don't have the gear required (I do own two desktops, one i9 14900k with an RTX 2060 and an RTX 2080 and another with i9 10900k with an RTX 3050) and the speeds I got are very good, but won't do much.
Thank you a lot for the work you are doing, I do wonder if you had implemented or found a way to implement this new method? https://arxiv.org/html/2409.08784v1
If after a jump I get second (cheap) point for almost free, I can calc K without this point.
Yes it's not 100% correct, but it's definitely better than counting it as 1op, showing almost twice speed at almost twice worse K.
But of course this assumption must be mentioned in the method description and I do it.
Also, it depends on a point of view: for example, if cheap point is used for vanity addresses generation, this point should be counted because it's used as a normal point. But for kangaroo jumps - this point should not be counted because only one point is used for next jump and only one point is calculated completely (both X and Y).
Yes it's not 100% correct, but it's definitely better than counting it as 1op, showing almost twice speed at almost twice worse K.
But of course this assumption must be mentioned in the method description and I do it.
Also, it depends on a point of view: for example, if cheap point is used for vanity addresses generation, this point should be counted because it's used as a normal point. But for kangaroo jumps - this point should not be counted because only one point is used for next jump and only one point is calculated completely (both X and Y).
I have a different question, how you transfer the BTC and protect it for the bots? Use you MARA or have you a different way?
Many thanks
Hey atom13,
You need to learn a bit of how a Bitcoin Address is generated and in which ranges are we talking.
Generate private key:
1. Private key is 256 random bits.
2. Prepend version number.
3. Append compression flag.
4. Append checksum. Checksum is the first 4 bytes of double sha256 hash of whatever is being checkedsum'ed.
5. Base58 encoded data is easier to read and manage.
Generate public key:
6. Multiply the private key by the elliptic curve generator point to get the public key. The public key is a point on the elliptic curve and has x and y coordinates.
7. Use parity of y coordinate and full x coordinate to represent the public key.
8. Hash public key twice. This obfuscates the public key and shortens it.
9. Prepend version (version number is different than in step 2)
10. Append checksum (same method as step 4)
11. After another base58 encoding, we have our public address
This page will help you a bit to understand the process behind it: https://royalforkblog.github.io/2014/08/11/graphical-address-generator/
The problem with bots is in the ranges where it is fast to calculate the private key given a public key (not the same as a public address).
Moreover, puzzles 135, 140, 145, 150, 155 and 160 have the public key known, but nobody has taken the private key. That is due to the range they are in (and the high cost to extract it).
The problem is in puzzles 67, 68, ... where the public key is not yet available (but the public address is). The moment you send the transaction to send Bitcoin from that puzzle to a wallet of yours is when you can get the public key (it is in Mempool).
Public keys can be found inside the ScriptPubKey or ScriptSig of raw transactions.
I hope this helps you a bit to understand the process behind it. If you have any questions, feel free to ask. I will be glad to help you.
If after a jump I get second (cheap) point for almost free, I can calc K without this point.
Yes it's not 100% correct, but it's definitely better than counting it as 1op, showing almost twice speed at almost twice worse K.
But of course this assumption must be mentioned in the method description and I do it.
Also, it depends on a point of view: for example, if cheap point is used for vanity addresses generation, this point should be counted because it's used as a normal point. But for kangaroo jumps - this point should not be counted because only one point is used for next jump and only one point is calculated completely (both X and Y).
Yes it's not 100% correct, but it's definitely better than counting it as 1op, showing almost twice speed at almost twice worse K.
But of course this assumption must be mentioned in the method description and I do it.
Also, it depends on a point of view: for example, if cheap point is used for vanity addresses generation, this point should be counted because it's used as a normal point. But for kangaroo jumps - this point should not be counted because only one point is used for next jump and only one point is calculated completely (both X and Y).
I have a different question, how you transfer the BTC and protect it for the bots? Use you MARA or have you a different way?
Many thanks
Public keys were already known.
Also, best of luck to bots cracking >100-bit ranges before the block is confirmed
Okay you think they can´t cracking over 100 bit ranges? I read that someone stole bit 66 from the finder, thats only possible because is < 100 bit?
If after a jump I get second (cheap) point for almost free, I can calc K without this point.
Yes it's not 100% correct, but it's definitely better than counting it as 1op, showing almost twice speed at almost twice worse K.
But of course this assumption must be mentioned in the method description and I do it.
Also, it depends on a point of view: for example, if cheap point is used for vanity addresses generation, this point should be counted because it's used as a normal point. But for kangaroo jumps - this point should not be counted because only one point is used for next jump and only one point is calculated completely (both X and Y).
Yes it's not 100% correct, but it's definitely better than counting it as 1op, showing almost twice speed at almost twice worse K.
But of course this assumption must be mentioned in the method description and I do it.
Also, it depends on a point of view: for example, if cheap point is used for vanity addresses generation, this point should be counted because it's used as a normal point. But for kangaroo jumps - this point should not be counted because only one point is used for next jump and only one point is calculated completely (both X and Y).
I have a different question, how you transfer the BTC and protect it for the bots? Use you MARA or have you a different way?
Many thanks
Public keys were already known.
Also, best of luck to bots cracking >100-bit ranges before the block is confirmed
If after a jump I get second (cheap) point for almost free, I can calc K without this point.
Yes it's not 100% correct, but it's definitely better than counting it as 1op, showing almost twice speed at almost twice worse K.
But of course this assumption must be mentioned in the method description and I do it.
Also, it depends on a point of view: for example, if cheap point is used for vanity addresses generation, this point should be counted because it's used as a normal point. But for kangaroo jumps - this point should not be counted because only one point is used for next jump and only one point is calculated completely (both X and Y).
Yes it's not 100% correct, but it's definitely better than counting it as 1op, showing almost twice speed at almost twice worse K.
But of course this assumption must be mentioned in the method description and I do it.
Also, it depends on a point of view: for example, if cheap point is used for vanity addresses generation, this point should be counted because it's used as a normal point. But for kangaroo jumps - this point should not be counted because only one point is used for next jump and only one point is calculated completely (both X and Y).
I have a different question, how you transfer the BTC and protect it for the bots? Use you MARA or have you a different way?
Many thanks
about bots, yes bots can f y.... and blockchain.com wallet too
https://github.com/phrutis/Bitcoin_Hack
One more piece of science! 
Everybody knows that when we calculate "NextPoint = PreviousPoint + JumpPoint", we can also quickly calculate "PreviousPoint - JumpPoint" because the inversion is the same.
Therefore, if the inversion calculation takes a lot of time, this second point is cheap for us, and we can use it to improve K.
I updated Part #1: Added "SOTA+" method with K = 1.02.
Everybody knows that when we calculate "NextPoint = PreviousPoint + JumpPoint", we can also quickly calculate "PreviousPoint - JumpPoint" because the inversion is the same.
Therefore, if the inversion calculation takes a lot of time, this second point is cheap for us, and we can use it to improve K.
I updated Part #1: Added "SOTA+" method with K = 1.02.
I still study your code, especially the gpu part, which gives me a lot to learn.
I think JLP applied this trick in his BSGS/kangaroo.
https://github.com/JeanLucPons/BSGS/blob/master/BSGS.cpp#L347
Yes, he did it for BSGS, and now I’ve figured out how to apply it to Kangaroo.
I took a closer look at JLP's code, and kangaroo's code does not have this.
This PreviousPoint - JumpPoint jump is equivalent to PreviousPoint jumping JumpPoint backwards.
If after a jump I get second (cheap) point for almost free, I can calc K without this point.
Yes it's not 100% correct, but it's definitely better than counting it as 1op, showing almost twice speed at almost twice worse K.
But of course this assumption must be mentioned in the method description and I do it.
Also, it depends on a point of view: for example, if cheap point is used for vanity addresses generation, this point should be counted because it's used as a normal point. But for kangaroo jumps - this point should not be counted because only one point is used for next jump and only one point is calculated completely (both X and Y).
Yes it's not 100% correct, but it's definitely better than counting it as 1op, showing almost twice speed at almost twice worse K.
But of course this assumption must be mentioned in the method description and I do it.
Also, it depends on a point of view: for example, if cheap point is used for vanity addresses generation, this point should be counted because it's used as a normal point. But for kangaroo jumps - this point should not be counted because only one point is used for next jump and only one point is calculated completely (both X and Y).
Cheap point does not cost 0.5 op, practically it costs max 15-20% of op (it's just additional 1 MUL + 1 SQR and these additional calculations happen only in 50% of jumps), but if you don't use groups in inversions (or group size is small), it costs much less, so it's not a good idea to count cheap point as 1 op. That's why in some cases using cheap point makes the whole algorithm faster. For example, you can compile my "Kang1" project and press "SOTA" button and then "SOTA+" button to see about 8% speedup.
I can't follow up on your logic. A key is still a key, no matter what optimizations are used to compute it or whether it was 90% easier to compute it or not. By your logic, in order to compare efficiency, we should also reduce (divide by
But it's your software so do as you wish, but please try to not be misleading at the abstract level. The number of iterations where you do whatever you want is not at all the same thing as the number of computed X & Y.
If I were you I would:
- count the number of ops (so complexity increases correctly, yes I know you would hate this)
- use the cheap point to increase throughput (keys/s)
which would result in a worse complexity (more keys), but a faster speed (more keys / s) due to implementation-specific optimizations.
But again, do as you wish.
One more piece of science!
Everybody knows that when we calculate "NextPoint = PreviousPoint + JumpPoint", we can also quickly calculate "PreviousPoint - JumpPoint" because the inversion is the same.
Therefore, if the inversion calculation takes a lot of time, this second point is cheap for us, and we can use it to improve K.
I updated Part #1: Added "SOTA+" method with K = 1.02.
Everybody knows that when we calculate "NextPoint = PreviousPoint + JumpPoint", we can also quickly calculate "PreviousPoint - JumpPoint" because the inversion is the same.
Therefore, if the inversion calculation takes a lot of time, this second point is cheap for us, and we can use it to improve K.
I updated Part #1: Added "SOTA+" method with K = 1.02.
I still study your code, especially the gpu part, which gives me a lot to learn.
I think JLP applied this trick in his BSGS/kangaroo.
https://github.com/JeanLucPons/BSGS/blob/master/BSGS.cpp#L347
Yes, he did it for BSGS, and now I’ve figured out how to apply it to Kangaroo.
One more piece of science!
Everybody knows that when we calculate "NextPoint = PreviousPoint + JumpPoint", we can also quickly calculate "PreviousPoint - JumpPoint" because the inversion is the same.
Therefore, if the inversion calculation takes a lot of time, this second point is cheap for us, and we can use it to improve K.
I updated Part #1: Added "SOTA+" method with K = 1.02.
Everybody knows that when we calculate "NextPoint = PreviousPoint + JumpPoint", we can also quickly calculate "PreviousPoint - JumpPoint" because the inversion is the same.
Therefore, if the inversion calculation takes a lot of time, this second point is cheap for us, and we can use it to improve K.
I updated Part #1: Added "SOTA+" method with K = 1.02.
I still study your code, especially the gpu part, which gives me a lot to learn.
I think JLP applied this trick in his BSGS/kangaroo.
https://github.com/JeanLucPons/BSGS/blob/master/BSGS.cpp#L347
Code:
...
// We use the fact that P + i*G and P - i*G has the same deltax, so the same inverse
// We compute key in the positive and negative way from the center of the group
// center point
pts[CPU_GRP_SIZE / 2] = startP;
for(i = 0; i
pp = startP;
pn = startP;
// P = startP + i*G
dy.ModSub(&GSn[i].y,&pp.y);
_s.ModMulK1(&dy,&dx[i]); // s = (p2.y-p1.y)*inverse(p2.x-p1.x);
_p.ModSquareK1(&_s); // _p = pow2(s)
pp.x.ModNeg();
pp.x.ModAdd(&_p);
pp.x.ModSub(&GSn[i].x); // rx = pow2(s) - p1.x - p2.x;
#if 0
pp.y.ModSub(&GSn[i].x,&pp.x);
pp.y.ModMulK1(&_s);
pp.y.ModSub(&GSn[i].y); // ry = - p2.y - s*(ret.x-p2.x);
#endif
// P = startP - i*G , if (x,y) = i*G then (x,-y) = -i*G
dyn.Set(&GSn[i].y);
dyn.ModNeg();
dyn.ModSub(&pn.y);
_s.ModMulK1(&dyn,&dx[i]); // s = (p2.y-p1.y)*inverse(p2.x-p1.x);
_p.ModSquareK1(&_s); // _p = pow2(s)
pn.x.ModNeg();
pn.x.ModAdd(&_p);
pn.x.ModSub(&GSn[i].x); // rx = pow2(s) - p1.x - p2.x;
#if 0
pn.y.ModSub(&GSn[i].x,&pn.x);
pn.y.ModMulK1(&_s);
pn.y.ModAdd(&GSn[i].y); // ry = - p2.y - s*(ret.x-p2.x);
#endif
pts[CPU_GRP_SIZE / 2 + (i + 1)] = pp;
pts[CPU_GRP_SIZE / 2 - (i + 1)] = pn;
}
// First point (startP - (GRP_SZIE/2)*G)
pn = startP;
dyn.Set(&GSn[i].y);
dyn.ModNeg();
dyn.ModSub(&pn.y);
_s.ModMulK1(&dyn,&dx[i]);
_p.ModSquareK1(&_s);
pn.x.ModNeg();
pn.x.ModAdd(&_p);
pn.x.ModSub(&GSn[i].x);
#if 0
pn.y.ModSub(&GSn[i].x,&pn.x);
pn.y.ModMulK1(&_s);
pn.y.ModAdd(&GSn[i].y);
#endif
pts[0] = pn;
...
// We use the fact that P + i*G and P - i*G has the same deltax, so the same inverse
// We compute key in the positive and negative way from the center of the group
// center point
pts[CPU_GRP_SIZE / 2] = startP;
for(i = 0; i
pp = startP;
pn = startP;
// P = startP + i*G
dy.ModSub(&GSn[i].y,&pp.y);
_s.ModMulK1(&dy,&dx[i]); // s = (p2.y-p1.y)*inverse(p2.x-p1.x);
_p.ModSquareK1(&_s); // _p = pow2(s)
pp.x.ModNeg();
pp.x.ModAdd(&_p);
pp.x.ModSub(&GSn[i].x); // rx = pow2(s) - p1.x - p2.x;
#if 0
pp.y.ModSub(&GSn[i].x,&pp.x);
pp.y.ModMulK1(&_s);
pp.y.ModSub(&GSn[i].y); // ry = - p2.y - s*(ret.x-p2.x);
#endif
// P = startP - i*G , if (x,y) = i*G then (x,-y) = -i*G
dyn.Set(&GSn[i].y);
dyn.ModNeg();
dyn.ModSub(&pn.y);
_s.ModMulK1(&dyn,&dx[i]); // s = (p2.y-p1.y)*inverse(p2.x-p1.x);
_p.ModSquareK1(&_s); // _p = pow2(s)
pn.x.ModNeg();
pn.x.ModAdd(&_p);
pn.x.ModSub(&GSn[i].x); // rx = pow2(s) - p1.x - p2.x;
#if 0
pn.y.ModSub(&GSn[i].x,&pn.x);
pn.y.ModMulK1(&_s);
pn.y.ModAdd(&GSn[i].y); // ry = - p2.y - s*(ret.x-p2.x);
#endif
pts[CPU_GRP_SIZE / 2 + (i + 1)] = pp;
pts[CPU_GRP_SIZE / 2 - (i + 1)] = pn;
}
// First point (startP - (GRP_SZIE/2)*G)
pn = startP;
dyn.Set(&GSn[i].y);
dyn.ModNeg();
dyn.ModSub(&pn.y);
_s.ModMulK1(&dyn,&dx[i]);
_p.ModSquareK1(&_s);
pn.x.ModNeg();
pn.x.ModAdd(&_p);
pn.x.ModSub(&GSn[i].x);
#if 0
pn.y.ModSub(&GSn[i].x,&pn.x);
pn.y.ModMulK1(&_s);
pn.y.ModAdd(&GSn[i].y);
#endif
pts[0] = pn;
...
But then again, it depends what you are counting.
I don't check cheap points for DP, it's senseless. Instead, I choose cheap point as next point if it has even X. So I use it for kang walking and prefer even X when possible, it helps kangs to collide faster.
Code:
// rec->iters++; point (PreviousPoint - JumpPoint) is cheap so we don't count it
Can you explain what you are referring to as "K"? Because any algorithmician can tell you that once you do 1.5 times more operations / loop (such as your "cheap point" even X preference with a 50% increase in ops count) and you ignore the extra .5 steps, then this "K" of yours is not really useful for anything, no one should care about how many iterations your algorithm does, but the number of group (or field) operations.
Cheap point does not cost 0.5 op, practically it costs max 15-20% of op (it's just additional 1 MUL + 1 SQR and these additional calculations happen only in 50% of jumps), but if you don't use groups in inversions (or group size is small), it costs much less, so it's not a good idea to count cheap point as 1 op. That's why in some cases using cheap point makes the whole algorithm faster. For example, you can compile my "Kang1" project and press "SOTA" button and then "SOTA+" button to see about 8% speedup.
But then again, it depends what you are counting.
I don't check cheap points for DP, it's senseless. Instead, I choose cheap point as next point if it has even X. So I use it for kang walking and prefer even X when possible, it helps kangs to collide faster.
Code:
// rec->iters++; point (PreviousPoint - JumpPoint) is cheap so we don't count it
Can you explain what you are referring to as "K"? Because any algorithmician can tell you that once you do 1.5 times more operations / loop (such as your "cheap point" even X preference with a 50% increase in ops count) and you ignore the extra .5 steps, then this "K" of yours is not really useful for anything, no one should care about how many iterations your algorithm does, but the number of group (or field) operations.
I had time again and was able to continue taking tests.
I think there is a bug in the tool when solving large bit areas.
I was able to solve bits 70, 75, and 80 without any problems, but from 85 onwards none of the puzzles that had already been solved. For example, I changed values at Bit 85 start, etc. but it was never found. An example, after that i stop -> Err: 0, DPs: 98481K/77175K, Time: 0d:00h:13m/0d:00h:10m
Don't think I'm making a mistake because it solved bit 70, 75, 80. If I had time again I would look at it more intensively, I'm not sure but maybe there is an overflow, .....
Can someone else please test this too??
Please, it is better to send the command line you are / were using. That way someone can take a better look at everything. Maybe you forgot to use the correct subtract amount, wrong key, etc. Could be anything, could be nothing, but it's the first thing to look at.I think there is a bug in the tool when solving large bit areas.
I was able to solve bits 70, 75, and 80 without any problems, but from 85 onwards none of the puzzles that had already been solved. For example, I changed values at Bit 85 start, etc. but it was never found. An example, after that i stop -> Err: 0, DPs: 98481K/77175K, Time: 0d:00h:13m/0d:00h:10m
Don't think I'm making a mistake because it solved bit 70, 75, 80. If I had time again I would look at it more intensively, I'm not sure but maybe there is an overflow, .....
Can someone else please test this too??
Here is for Bit 85, i can´t find the key:
./rckangaroo -dp 16 -range 84 -start 1000000000000000000000 -pubkey 0329c4574a4fd8c810b7e42a4b398882b381bcd85e40c6883712912d167c83e73a
./rckangaroo -dp 16 -range 84 -start 11720c4f018d51b8000000 -pubkey 0329c4574a4fd8c810b7e42a4b398882b381bcd85e40c6883712912d167c83e73a
For Bit 70 i always find the key, doesn´t matter which -start i use (only two see below):
./rckangaroo -dp 16 -range 69 -start 200000000000000000 -pubkey 0290e6900a58d33393bc1097b5aed31f2e4e7cbd3e5466af958665bc0121248483
./rckangaroo -dp 16 -range 69 -start 100000000000000000 -pubkey 0290e6900a58d33393bc1097b5aed31f2e4e7cbd3e5466af958665bc0121248483
./rckangaroo -dp 16 -range 69 -start 300000000000000000 -pubkey 0290e6900a58d33393bc1097b5aed31f2e4e7cbd3e5466af958665bc0121248483
./rckangaroo -dp 16 -range 69 -start 340000000000000000 -pubkey 0290e6900a58d33393bc1097b5aed31f2e4e7cbd3e5466af958665bc0121248483
./rckangaroo -dp 16 -range 69 -start 349000000000000000 -pubkey 0290e6900a58d33393bc1097b5aed31f2e4e7cbd3e5466af958665bc0121248483
./rckangaroo -dp 16 -range 69 -start 349B84B6431A6C4EF0 -pubkey 0290e6900a58d33393bc1097b5aed31f2e4e7cbd3e5466af958665bc0121248483
with this -start offset can´t find the key:
./rckangaroo -dp 16 -range 69 -start 0 -pubkey 0290e6900a58d33393bc1097b5aed31f2e4e7cbd3e5466af958665bc0121248483
./rckangaroo -dp 16 -range 69 -start 349B84B6431A6C4EF1 -pubkey 0290e6900a58d33393bc1097b5aed31f2e4e7cbd3e5466af958665bc0121248483
./rckangaroo -dp 16 -range 85 -start 1000000000000000000000 -pubkey 0329c4574a4fd8c810b7e42a4b398882b381bcd85e40c6883712912d167c83e73a
I am running it with -range 84 to see if it solves. Will update.
Edit:
Spoke to soon lol. Here is my result using your command line:
Code:
Solving public key
X: 29C4574A4FD8C810B7E42A4B398882B381BCD85E40C6883712912D167C83E73A
Y: 0E02C3AFD79913AB0961C95F12498F36A72FFA35C93AF27CEE30010FA6B51C53
Offset: 0000000000000000000000000000000000000000001000000000000000000000
Solving point: Range 84 bits, DP 16, start...
SOTA method, estimated ops: 2^42.202, RAM for DPs: 3.062 GB. DP and GPU overheads not included!
Estimated DPs per kangaroo: 98.133.
GPU 0: allocated 4437 MB, 786432 kangaroos.
GPUs started...
MAIN: Speed: 7904 MKeys/s, Err: 0, DPs: 1181K/77175K, Time: 0d:00h:00m, Est: 0d:00h:10m
MAIN: Speed: 7828 MKeys/s, Err: 0, DPs: 2387K/77175K, Time: 0d:00h:00m, Est: 0d:00h:10m
MAIN: Speed: 7868 MKeys/s, Err: 0, DPs: 3591K/77175K, Time: 0d:00h:00m, Est: 0d:00h:10m
MAIN: Speed: 7822 MKeys/s, Err: 0, DPs: 4795K/77175K, Time: 0d:00h:00m, Est: 0d:00h:10m
MAIN: Speed: 7859 MKeys/s, Err: 0, DPs: 5976K/77175K, Time: 0d:00h:00m, Est: 0d:00h:10m
MAIN: Speed: 7822 MKeys/s, Err: 0, DPs: 7179K/77175K, Time: 0d:00h:01m, Est: 0d:00h:10m
MAIN: Speed: 7862 MKeys/s, Err: 0, DPs: 8382K/77175K, Time: 0d:00h:01m, Est: 0d:00h:10m
MAIN: Speed: 7834 MKeys/s, Err: 0, DPs: 9563K/77175K, Time: 0d:00h:01m, Est: 0d:00h:10m
MAIN: Speed: 7831 MKeys/s, Err: 0, DPs: 10766K/77175K, Time: 0d:00h:01m, Est: 0d:00h:10m
MAIN: Speed: 7845 MKeys/s, Err: 0, DPs: 11970K/77175K, Time: 0d:00h:01m, Est: 0d:00h:10m
MAIN: Speed: 7834 MKeys/s, Err: 0, DPs: 13152K/77175K, Time: 0d:00h:01m, Est: 0d:00h:10m
MAIN: Speed: 7822 MKeys/s, Err: 0, DPs: 14356K/77175K, Time: 0d:00h:02m, Est: 0d:00h:10m
MAIN: Speed: 7842 MKeys/s, Err: 0, DPs: 15536K/77175K, Time: 0d:00h:02m, Est: 0d:00h:10m
MAIN: Speed: 7834 MKeys/s, Err: 0, DPs: 16740K/77175K, Time: 0d:00h:02m, Est: 0d:00h:10m
MAIN: Speed: 7828 MKeys/s, Err: 0, DPs: 17942K/77175K, Time: 0d:00h:02m, Est: 0d:00h:10m
MAIN: Speed: 7830 MKeys/s, Err: 0, DPs: 19121K/77175K, Time: 0d:00h:02m, Est: 0d:00h:10m
MAIN: Speed: 7788 MKeys/s, Err: 0, DPs: 20324K/77175K, Time: 0d:00h:02m, Est: 0d:00h:10m
MAIN: Speed: 7792 MKeys/s, Err: 0, DPs: 21502K/77175K, Time: 0d:00h:03m, Est: 0d:00h:10m
MAIN: Speed: 7799 MKeys/s, Err: 0, DPs: 22707K/77175K, Time: 0d:00h:03m, Est: 0d:00h:10m
MAIN: Speed: 7862 MKeys/s, Err: 0, DPs: 23884K/77175K, Time: 0d:00h:03m, Est: 0d:00h:10m
MAIN: Speed: 7834 MKeys/s, Err: 0, DPs: 25089K/77175K, Time: 0d:00h:03m, Est: 0d:00h:10m
MAIN: Speed: 7792 MKeys/s, Err: 0, DPs: 26269K/77175K, Time: 0d:00h:03m, Est: 0d:00h:10m
MAIN: Speed: 7822 MKeys/s, Err: 0, DPs: 27473K/77175K, Time: 0d:00h:03m, Est: 0d:00h:10m
MAIN: Speed: 7822 MKeys/s, Err: 0, DPs: 28652K/77175K, Time: 0d:00h:04m, Est: 0d:00h:10m
MAIN: Speed: 7828 MKeys/s, Err: 0, DPs: 29856K/77175K, Time: 0d:00h:04m, Est: 0d:00h:10m
MAIN: Speed: 7834 MKeys/s, Err: 0, DPs: 31059K/77175K, Time: 0d:00h:04m, Est: 0d:00h:10m
MAIN: Speed: 7828 MKeys/s, Err: 0, DPs: 32238K/77175K, Time: 0d:00h:04m, Est: 0d:00h:10m
MAIN: Speed: 7828 MKeys/s, Err: 0, DPs: 33441K/77175K, Time: 0d:00h:04m, Est: 0d:00h:10m
MAIN: Speed: 7831 MKeys/s, Err: 0, DPs: 34619K/77175K, Time: 0d:00h:04m, Est: 0d:00h:10m
MAIN: Speed: 7837 MKeys/s, Err: 0, DPs: 35824K/77175K, Time: 0d:00h:05m, Est: 0d:00h:10m
MAIN: Speed: 7791 MKeys/s, Err: 0, DPs: 37003K/77175K, Time: 0d:00h:05m, Est: 0d:00h:10m
Stopping work ...
Point solved, K: 0.552 (with DP and GPU overheads)
PRIVATE KEY: 00000000000000000000000000000000000000000011720C4F018D51B8CEBBA8
X: 29C4574A4FD8C810B7E42A4B398882B381BCD85E40C6883712912D167C83E73A
Y: 0E02C3AFD79913AB0961C95F12498F36A72FFA35C93AF27CEE30010FA6B51C53
Offset: 0000000000000000000000000000000000000000001000000000000000000000
Solving point: Range 84 bits, DP 16, start...
SOTA method, estimated ops: 2^42.202, RAM for DPs: 3.062 GB. DP and GPU overheads not included!
Estimated DPs per kangaroo: 98.133.
GPU 0: allocated 4437 MB, 786432 kangaroos.
GPUs started...
MAIN: Speed: 7904 MKeys/s, Err: 0, DPs: 1181K/77175K, Time: 0d:00h:00m, Est: 0d:00h:10m
MAIN: Speed: 7828 MKeys/s, Err: 0, DPs: 2387K/77175K, Time: 0d:00h:00m, Est: 0d:00h:10m
MAIN: Speed: 7868 MKeys/s, Err: 0, DPs: 3591K/77175K, Time: 0d:00h:00m, Est: 0d:00h:10m
MAIN: Speed: 7822 MKeys/s, Err: 0, DPs: 4795K/77175K, Time: 0d:00h:00m, Est: 0d:00h:10m
MAIN: Speed: 7859 MKeys/s, Err: 0, DPs: 5976K/77175K, Time: 0d:00h:00m, Est: 0d:00h:10m
MAIN: Speed: 7822 MKeys/s, Err: 0, DPs: 7179K/77175K, Time: 0d:00h:01m, Est: 0d:00h:10m
MAIN: Speed: 7862 MKeys/s, Err: 0, DPs: 8382K/77175K, Time: 0d:00h:01m, Est: 0d:00h:10m
MAIN: Speed: 7834 MKeys/s, Err: 0, DPs: 9563K/77175K, Time: 0d:00h:01m, Est: 0d:00h:10m
MAIN: Speed: 7831 MKeys/s, Err: 0, DPs: 10766K/77175K, Time: 0d:00h:01m, Est: 0d:00h:10m
MAIN: Speed: 7845 MKeys/s, Err: 0, DPs: 11970K/77175K, Time: 0d:00h:01m, Est: 0d:00h:10m
MAIN: Speed: 7834 MKeys/s, Err: 0, DPs: 13152K/77175K, Time: 0d:00h:01m, Est: 0d:00h:10m
MAIN: Speed: 7822 MKeys/s, Err: 0, DPs: 14356K/77175K, Time: 0d:00h:02m, Est: 0d:00h:10m
MAIN: Speed: 7842 MKeys/s, Err: 0, DPs: 15536K/77175K, Time: 0d:00h:02m, Est: 0d:00h:10m
MAIN: Speed: 7834 MKeys/s, Err: 0, DPs: 16740K/77175K, Time: 0d:00h:02m, Est: 0d:00h:10m
MAIN: Speed: 7828 MKeys/s, Err: 0, DPs: 17942K/77175K, Time: 0d:00h:02m, Est: 0d:00h:10m
MAIN: Speed: 7830 MKeys/s, Err: 0, DPs: 19121K/77175K, Time: 0d:00h:02m, Est: 0d:00h:10m
MAIN: Speed: 7788 MKeys/s, Err: 0, DPs: 20324K/77175K, Time: 0d:00h:02m, Est: 0d:00h:10m
MAIN: Speed: 7792 MKeys/s, Err: 0, DPs: 21502K/77175K, Time: 0d:00h:03m, Est: 0d:00h:10m
MAIN: Speed: 7799 MKeys/s, Err: 0, DPs: 22707K/77175K, Time: 0d:00h:03m, Est: 0d:00h:10m
MAIN: Speed: 7862 MKeys/s, Err: 0, DPs: 23884K/77175K, Time: 0d:00h:03m, Est: 0d:00h:10m
MAIN: Speed: 7834 MKeys/s, Err: 0, DPs: 25089K/77175K, Time: 0d:00h:03m, Est: 0d:00h:10m
MAIN: Speed: 7792 MKeys/s, Err: 0, DPs: 26269K/77175K, Time: 0d:00h:03m, Est: 0d:00h:10m
MAIN: Speed: 7822 MKeys/s, Err: 0, DPs: 27473K/77175K, Time: 0d:00h:03m, Est: 0d:00h:10m
MAIN: Speed: 7822 MKeys/s, Err: 0, DPs: 28652K/77175K, Time: 0d:00h:04m, Est: 0d:00h:10m
MAIN: Speed: 7828 MKeys/s, Err: 0, DPs: 29856K/77175K, Time: 0d:00h:04m, Est: 0d:00h:10m
MAIN: Speed: 7834 MKeys/s, Err: 0, DPs: 31059K/77175K, Time: 0d:00h:04m, Est: 0d:00h:10m
MAIN: Speed: 7828 MKeys/s, Err: 0, DPs: 32238K/77175K, Time: 0d:00h:04m, Est: 0d:00h:10m
MAIN: Speed: 7828 MKeys/s, Err: 0, DPs: 33441K/77175K, Time: 0d:00h:04m, Est: 0d:00h:10m
MAIN: Speed: 7831 MKeys/s, Err: 0, DPs: 34619K/77175K, Time: 0d:00h:04m, Est: 0d:00h:10m
MAIN: Speed: 7837 MKeys/s, Err: 0, DPs: 35824K/77175K, Time: 0d:00h:05m, Est: 0d:00h:10m
MAIN: Speed: 7791 MKeys/s, Err: 0, DPs: 37003K/77175K, Time: 0d:00h:05m, Est: 0d:00h:10m
Stopping work ...
Point solved, K: 0.552 (with DP and GPU overheads)
PRIVATE KEY: 00000000000000000000000000000000000000000011720C4F018D51B8CEBBA8
So since I solved at both 85 and 84 range, I am not sure what the problem is/was on your end. Your command line args are fine.
I had time again and was able to continue taking tests.
I think there is a bug in the tool when solving large bit areas.
I was able to solve bits 70, 75, and 80 without any problems, but from 85 onwards none of the puzzles that had already been solved. For example, I changed values at Bit 85 start, etc. but it was never found. An example, after that i stop -> Err: 0, DPs: 98481K/77175K, Time: 0d:00h:13m/0d:00h:10m
Don't think I'm making a mistake because it solved bit 70, 75, 80. If I had time again I would look at it more intensively, I'm not sure but maybe there is an overflow, .....
Can someone else please test this too??
Please, it is better to send the command line you are / were using. That way someone can take a better look at everything. Maybe you forgot to use the correct subtract amount, wrong key, etc. Could be anything, could be nothing, but it's the first thing to look at.I think there is a bug in the tool when solving large bit areas.
I was able to solve bits 70, 75, and 80 without any problems, but from 85 onwards none of the puzzles that had already been solved. For example, I changed values at Bit 85 start, etc. but it was never found. An example, after that i stop -> Err: 0, DPs: 98481K/77175K, Time: 0d:00h:13m/0d:00h:10m
Don't think I'm making a mistake because it solved bit 70, 75, 80. If I had time again I would look at it more intensively, I'm not sure but maybe there is an overflow, .....
Can someone else please test this too??
Here is for Bit 85, i can´t find the key:
./rckangaroo -dp 16 -range 84 -start 1000000000000000000000 -pubkey 0329c4574a4fd8c810b7e42a4b398882b381bcd85e40c6883712912d167c83e73a
./rckangaroo -dp 16 -range 84 -start 11720c4f018d51b8000000 -pubkey 0329c4574a4fd8c810b7e42a4b398882b381bcd85e40c6883712912d167c83e73a
For Bit 70 i always find the key, doesn´t matter which -start i use (only two see below):
./rckangaroo -dp 16 -range 69 -start 200000000000000000 -pubkey 0290e6900a58d33393bc1097b5aed31f2e4e7cbd3e5466af958665bc0121248483
./rckangaroo -dp 16 -range 69 -start 100000000000000000 -pubkey 0290e6900a58d33393bc1097b5aed31f2e4e7cbd3e5466af958665bc0121248483
./rckangaroo -dp 16 -range 69 -start 300000000000000000 -pubkey 0290e6900a58d33393bc1097b5aed31f2e4e7cbd3e5466af958665bc0121248483
./rckangaroo -dp 16 -range 69 -start 340000000000000000 -pubkey 0290e6900a58d33393bc1097b5aed31f2e4e7cbd3e5466af958665bc0121248483
./rckangaroo -dp 16 -range 69 -start 349000000000000000 -pubkey 0290e6900a58d33393bc1097b5aed31f2e4e7cbd3e5466af958665bc0121248483
./rckangaroo -dp 16 -range 69 -start 349B84B6431A6C4EF0 -pubkey 0290e6900a58d33393bc1097b5aed31f2e4e7cbd3e5466af958665bc0121248483
with this -start offset can´t find the key:
./rckangaroo -dp 16 -range 69 -start 0 -pubkey 0290e6900a58d33393bc1097b5aed31f2e4e7cbd3e5466af958665bc0121248483
./rckangaroo -dp 16 -range 69 -start 349B84B6431A6C4EF1 -pubkey 0290e6900a58d33393bc1097b5aed31f2e4e7cbd3e5466af958665bc0121248483
Jump to: