Solving ECDLP with Kangaroos: Part 1 + 2 + RCKangaroo

[minobia]

The actual DPs (1176754K) far exceed the expected DPs (109142K), meaning the solver is generating significantly more DPs than anticipated.
The more i lower the DP bits from 16 the worse it gets, it does not generate a single Solved Point.

For solving points with saved tames you must use same "-range" and "-dp" values that you used for tames generation.

Thanks, i must had it messed up!

[kTimesG]

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.

This was something already known and smart guys here already used this knowledge for example in faster vanity searches and even for BSGS. arulbero posted this trick many years ago and it is also in the literature. I used the P + Q and P - Q same inverse speedup even for Python scripts, however there is one big problem here: if P - Q is a DP then this only marginally improves the collision probability lower and lower as DP value grows, because the walk does not continue from P - Q, it continues from P + Q. It is what I call a "weak DP". For low DPs it indeed brings what you call "K" down a lot, or more precisely, you get an increase in DP throughput with the same "K" if not a larger "K".

Do you remember a few months ago when you said you don't believe I reached a K of ~1.0 and it was most likely a bug in my code? Well, do you still believe this today?

[RetiredCoder]

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.

This was something already known and smart guys here already used this knowledge for example in faster vanity searches and even for BSGS. arulbero posted this trick many years ago and it is also in the literature. I used the P + Q and P - Q same inverse speedup even for Python scripts, however there is one big problem here: if P - Q is a DP then this only marginally improves the collision probability lower and lower as DP value grows, because the walk does not continue from P - Q, it continues from P + Q. It is what I call a "weak DP". For low DPs it indeed brings what you call "K" down a lot, or more precisely, you get an increase in DP throughput with the same "K" if not a larger "K".

I'm not talking about the trick with cheap second point, I mentioned that everybody knows about it. But noone could use this trick to improve K at DP>0 and you explained why. But I can and I demonstrated it. If you have any links to sources or papers that do it (improve K at any DP>0) - let me know!

Do you remember a few months ago when you said you don't believe I reached a K of ~1.0 and it was most likely a bug in my code? Well, do you still believe this today?

Yes I'm still sure that your non-looping method with K=1.0 (at DP>0) does not exist  

[kTimesG]

I'm not talking about the trick with cheap second point, I mentioned that everybody knows about it. But noone could use this trick to improve K at DP>0 and you explained why. But I can and I demonstrated it. If you have any links to sources or papers that do it (improve K at any DP>0) - let me know!

Can you explain how that is, without having to be a C++ expert? Once you have P - Q you are at a point that is basically the end of a line, how does that help you further (unless maybe you save it and walk further, but this grows your herd size by 2x of course at each step). The cheap point is still one extra semi-addition (sort of), are you sure you're counting it correctly? In my tests, as DP grows, K grows as well, but less than double, so overall it's an improvement. But then again, it depends what you are counting.

Yes I'm still sure that your non-looping method with K=1.0 (at DP>0) does not exist  

Remains to be seen It's debatable what K means anymore once the inner guts of adding points start to become intertwined and you only need parts of the final result. We'd need the hyperelliptic equations style of notation to get the complexity (how many field ops we need grouped by op type).

[RetiredCoder]

Can you explain how that is, without having to be a C++ expert? Once you have P - Q you are at a point that is basically the end of a line, how does that help you further (unless maybe you save it and walk further, but this grows your herd size by 2x of course at each step). The cheap point is still one extra semi-addition (sort of), are you sure you're counting it correctly? In my tests, as DP grows, K grows as well, but less than double, so overall it's an improvement. 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.
Here is the related code, since it's open-source you can easily compile and check everything by yourself:

Code:

if ((kangs[i].p.x.data[0] & 1) != 0)
{
AddP.y.NegModP();
EcPoint p2 = ec.AddPointsHaveInv(Saved, AddP, inversion);
if ((p2.x.data[0] & 1) == 0)
{
kangs[i].p = p2;
kangs[i].dist = SavedD;
if (!inv)
kangs[i].dist.Sub(EcJumps[jmp_ind].dist);
else
kangs[i].dist.Add(EcJumps[jmp_ind].dist);
}
}

You can use this trick only for methods that use symmetry.
It works, I know why it works, and I never saw this trick before.

[atom13]

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.

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

[WanderingPhilospher]

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.

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

I have solved #85, using -range 85. Try it and see if you find the key.

./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

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.

[kTimesG]

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.

[RetiredCoder]

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.

[hskun]

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.

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<hLength; 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;
...

[RetiredCoder]

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.

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.

[kTimesG]

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 1.5 2.0) the reported complexity of any other implementations that use this "trick", but count the number of computed keys (not the number of iterations). For example BSGS where this trick does wonders. Or maybe a kangaroo with weak DPs. Is it fair?

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.

[RetiredCoder]

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).

[hskun]

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.

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.

[COBRAS]

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).

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

[RetiredCoder]

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).

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  

[atom13]

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).

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?

[albertajuelo]

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).

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.

[fairmuffin]

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.

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

[kTimesG]

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.