Solving ECDLP with Kangaroos: Part 1 + 2 + RCKangaroo

[nomachine]

Everyone else seems to be hiding how it works. 

Another conspiracy theory in the series? 

[Akito S. M. Hosana]

Everyone else seems to be hiding how it works. 

Another conspiracy theory in the series? 

I'm not sure. I know that Google search often brings me back to this forum. I also know that you have code you don't want to release publicly, or you release code as bait. Nothing specific which is the fastest. 

[kTimesG]

I'm not able to find an implementation for batch inversion on your code, do you use batch inversion to speed up the computation of the inverses?

The only place I've been able to find anyone publicly using Inverse Wild Herd is in this Python script here:

https://github.com/mikorist/Kangaroo-256-bit-python/blob/main/kangaroo.py

 Everyone else seems to be hiding how it works. 

Maybe you are not watching carefully, I posted a Kangaroo python script that used the inverse herd since last July or August, and explained all the equations of why it's working, and why it brings down Kangaroo to 1.0 * sqrt(N) when DP = 0

But TBH this is already known for many years, just maybe not many people bothered to apply it, since it's at most something like a 20% speed-up over the usual 2 kang method.

[nomachine]

I also know that you have code you don't want to release publicly, or you release code as bait. Nothing specific which is the fastest. 

What would you do with the fastest Kangaroo program I have? To be fair, you still need 1,200 GPUs, even if kTimesG or RetiredCoder publicly release the fastest version.

Besides puzzles it has no practical application whatsoever.

Exactly. 

[Akito S. M. Hosana]

What would you do with the fastest Kangaroo program I have?

To experiment and learn. I mean, it's impossible that you don't have a faster solution at least for the CPU. 

[kTimesG]

What would you do with the fastest Kangaroo program I have?

To experiment and learn. I mean, it's impossible that you don't have a faster solution at least for the CPU. 

And what is to be learned? Definitely nothing about the 3-kang algorithm itself, all of that is public already. Like nomachine said, one would still need many, many GPUs to find high-bit solutions, no matter how well an implementation is optimized.

The only curiosity one might have would be "why is it faster" or "how did RetiredCoder manage to pull off 12.8 Gk/s on a RTX 4090", which might end up just as a terrible headache reading low-level code, or an "oh", not a revolutionary breakthrough.

[mcdouglasx]

Yeah. Definitely. No one cares what is the fastest kangaroo solution.
Besides puzzles it has no practical application whatsoever.
Because no one will ever be so stupid as to generate key pair with  the private key that is in the range for those  seeking treasures.

It's not about that. If you think that research without a 'real' (for you) use is impractical, you're wrong. Many of the technological advances we consider fundamental today started as theoretical ideas without an apparent practical application. We never know when something might be useful or if it will pave the way for something bigger. Perhaps in the context of current puzzles, it might not be enough without thousands of GPUs, but that doesn't detract from its merit, like the study of radio waves, someone studying rainbows and light, and another person who wanted to organize the elements in a table to make it more practical. If we all thought that way, we would still be sending carrier pigeons instead of using mobile phones.

[Veliquant]

I have been studying the puzzles for a year now.  I was able to comunicate with professor Teske and professor Galbraith, they both worked with professor Pollard, and pointed me in the right direction. I have some questions and some original ideas about the pollard methods.

I understand that you use a base magnitude for the jumps and add a random portion to make the jumps, in a different way for each of the 3 heards, I will study this in detail.

It seems you don't know how it works even after a year. The jump table is the same for all herds, otherwise it won't work.

I'm not able to find an implementation for batch inversion on your code, do you use batch inversion to speed up the computation of the inverses? I understand that in the Classic Pollard method, you can use this approach, computing the next point for a group kangaroo paths. This will make the cost for one inversion only 3 - 4 multiplications? Is that correct?

For CPU code I don't use batch inversion because I tried to make the code as simple as possible. That code demonstrates various methods for ECDLP and loop handling, not optimizations.
For RCKangaroo I use batch inversion, check its CUDA sources.

Yes you are absolutely right, after one year of dreaming with babies, gigants and kangaroos, I understand that the jump table has to be the same for all herds  .

For me is very interesting the way you see the kangaroo methods conceptually. There is one part that is the method itself were we try to make as little as possible point additions, the other part is "optimizations" were we try to make those point additions as fast as possible, and use parallel computing to increase the point output.

I understand why is so important the concept of "K", I have an intuition about this that i would like to ask if it is correct. The kangaroo method by itself as in only 2 kangaroos (Tame and Wild) would solve the discrete logarithm in only sqrt(range) steps (k = 1) if both kangaroos started at the same point. This is sqrt(range)/2 for each kangaroo. This is related with the birthday paradox. Wen you use the first method in your program, and the kangaroos are separated, there is an overhead, because the path before both kangaroos meet is wasted. This accounts for an additional K points, so this method will solve in 2K jumps on average. What I have not been able to understand is how the 3 kangaroo method works. You start with one tamed an 2 wilds, and place them in a different position. This makes the kangaroos meet faster on average.

There is also the concept that if you start the path in the origin, and jump to the right, is the same as jumping to the left, so you are actually making, 2 paths at once.
 
For the 3 kangaroo methods this are my questions:

1) Where the 3 kangaroos should be placed at the beginning?
2) The wild kangaroos travel 1/4 of the jumps each and the tamed 1/2 of the jumps?

Thanks

[kTimesG]

For the 3 kangaroo methods this are my questions:

1) Where the 3 kangaroos should be placed at the beginning?
2) The wild kangaroos travel 1/4 of the jumps each and the tamed 1/2 of the jumps?

You know, this thread is a POC about something called SOTA+ method, not 3-kang. Usually in literature this is actually a Gaudry-Schost variant, because there cannot be a Kangaroo algorithm that actually goes side-ways, since cycles cannot be part of a Kangaroo algorithm, by definition.

You can read up on the actual 3 and 4 kangaroo algorithm in the original paper from 2012 by Pollard et. co, it's called "Computing discrete logarithms in an interval", maybe you will then notice some of your statements or questions don't make much sense. Also don't forget that 3-kang works on any generic group, and has a lower complexity for groups with fast inversion, like secp256k1. I'm not aware of any papers that take this into account. The rabbit hole is deep.

[Veliquant]

You know, this thread is a POC about something called SOTA+ method, not 3-kang.

Thanks for your answer. Yes, I am trying to understand SOTA+, but I believe I have to learn all the methods in order to understand SOTA+.  This means in order to understand SOTA+, I should understand 2 kangaroos, then 3-4 kangaroos, then Mirror, and then SOTA, and SOTA+. Is this correct?

Usually in literature this is actually a Gaudry-Schost variant, because there cannot be a Kangaroo algorithm that actually goes side-ways, since cycles cannot be part of a Kangaroo algorithm, by definition.

This means the 2-3-4 kangaroo algorithm makes 2-3-4 long paths, while Gaudry-Schost variant makes many smaller paths until a distinguished point is found. I see your point, a normal kangaroo method can't go sideways, as the "maximum excursion" would not allow for the kangaroo to travel very far before going in to a loop?

But in general terms:

Mirror is faster than 3 kangaroos because it calculates 2 "cheap" points in every jump instead of 1, and SOTA is faster than mirror because it computes 4 "cheap" points instead of 1?

The trick in SOTA+ is how to detect and then get out of the cycles in a way that the overhead is not to big?

Thanks

[kTimesG]

You know, this thread is a POC about something called SOTA+ method, not 3-kang.

Thanks for your answer. Yes, I am trying to understand SOTA+, but I believe I have to learn all the methods in order to understand SOTA+.  This means in order to understand SOTA+, I should understand 2 kangaroos, then 3-4 kangaroos, then Mirror, and then SOTA, and SOTA+. Is this correct?

Usually in literature this is actually a Gaudry-Schost variant, because there cannot be a Kangaroo algorithm that actually goes side-ways, since cycles cannot be part of a Kangaroo algorithm, by definition.

This means the 2-3-4 kangaroo algorithm makes 2-3-4 long paths, while Gaudry-Schost variant makes many smaller paths until a distinguished point is found. I see your point, a normal kangaroo method can't go sideways, as the "maximum excursion" would not allow for the kangaroo to travel very far before going in to a loop?

But in general terms:

Mirror is faster than 3 kangaroos because it calculates 2 "cheap" points in every jump instead of 1, and SOTA is faster than mirror because it computes 4 "cheap" points instead of 1?

The trick in SOTA+ is how to detect and then get out of the cycles in a way that the overhead is not to big?

Mirror = takes advantage of group symmetry - you have both P and -P with the same X. If DP is on X and a DP is found, then you basically have two DPs found instead of one. Also this helps with more collisions.

What I'm trying to say, this is just something that's part of the group, it has nothing to do with any 2-kang or 3-kang algorithm itself, it works the same even for a brute-force algorithm (to halve the key space).

The cheap points have nothing to do with mirroring, or with 2-kang, 3-kang. It's simply reusing the (x1 - x2) field inverse to compute both P + Q and P - Q, where P can be anywhere on the curve.

RetiredCoder uses cheap points to selectively pick the next landing point, since somehow this helps - probably because it increases collision chances if visited points have a heavy bias on the lowest bit.

[WanderingPhilospher]

Mirror = takes advantage of group symmetry - you have both P and -P with the same X. If DP is on X and a DP is found, then you basically have two DPs found instead of one. Also this helps with more collisions.

This doesn't make sense to me. Why would you need the same point in the database. I don't see how this is useful.

[Veliquant]

Mirror = takes advantage of group symmetry - you have both P and -P with the same X. If DP is on X and a DP is found, then you basically have two DPs found instead of one. Also this helps with more collisions.

This doesn't make sense to me. Why would you need the same point in the database. I don't see how this is useful.

In general terms, first you bring the wild kangaroo to the (-N/2, N/2) range, and you are not sure if it landed on the positive side or the negative side of the range, so you need a way to calculate the next jump, taking in to consideration both possibilities but having the same resulting landing point. This means you begin in one point, calculate the negative (-Y) at no cost and then you choose the one with smaller Y to calculate the jump.

In practice if the tamed kangaroo lands on the positive or negative point, it will be a collision, and you will catch it at the next distinguished point.

Also you have the same range N and you double the amount of calculated points but with only 1 point computation per 2 points result cost.

About the database now 1 distinguished point will "Include" twice as much points in the trailing paths. Remember the X coordinate is the same for both points so the probability of finding one distinguished point stays the same. Also as KtimesG says you will have 2 distinguished points instead of 1, the same X with n trailing zeroes and different Y, one with +Y and -Y.

This is the paper:
Steven D. Galbraith and Raminder S. Ruprai "Using Equivalence Classes to Accelerate Solving the Discrete Logarithm Problem in a Short Interval"

[WanderingPhilospher]

Mirror = takes advantage of group symmetry - you have both P and -P with the same X. If DP is on X and a DP is found, then you basically have two DPs found instead of one. Also this helps with more collisions.

This doesn't make sense to me. Why would you need the same point in the database. I don't see how this is useful.

In general terms, first you bring the wild kangaroo to the (-N/2, N/2) range, and you are not sure if it landed on the positive side or the negative side of the range, so you need a way to calculate the next jump, taking in to consideration both possibilities but having the same resulting landing point. This means you begin in one point, calculate the negative (-Y) at no cost and then you choose the one with smaller Y to calculate the jump.

In practice if the tamed kangaroo lands on the positive or negative point, it will be a collision, and you will catch it at the next distinguished point.

Also you have the same range N and you double the amount of calculated points but with only 1 point computation per 2 points result cost.

About the database now 1 distinguished point will "Include" twice as much points in the trailing paths. Remember the X coordinate is the same for both points so the probability of finding one distinguished point stays the same. Also as KtimesG says you will have 2 distinguished points instead of 1, the same X with n trailing zeroes and different Y, one with +Y and -Y.

Yeah but if I am storing X points, I don't really care about having 2 in the database "will have 2 distinguished points instead of 1, the same X with n trailing zeroes and different Y, one with +Y and -Y"; I only need one of them stored to solve.

[kTimesG]

Mirror = takes advantage of group symmetry - you have both P and -P with the same X. If DP is on X and a DP is found, then you basically have two DPs found instead of one. Also this helps with more collisions.

This doesn't make sense to me. Why would you need the same point in the database. I don't see how this is useful.

Well a DP entry has a key (hash or whatever) and a value (distance from base point).

If the DP hash matches, you can compute for two possible values for each distance, because the collision may have happened on either the odd or even Y coord.

So, a 4-way match instead of just one. For tames, you know the distance, so you can compute both key values. For wilds, you can similarly consider the distance as being on the left or right side of the interval, so they can both be used as a potential match. It all checks out.

[Veliquant]

Mirror = takes advantage of group symmetry - you have both P and -P with the same X. If DP is on X and a DP is found, then you basically have two DPs found instead of one. Also this helps with more collisions.

This doesn't make sense to me. Why would you need the same point in the database. I don't see how this is useful.

In general terms, first you bring the wild kangaroo to the (-N/2, N/2) range, and you are not sure if it landed on the positive side or the negative side of the range, so you need a way to calculate the next jump, taking in to consideration both possibilities but having the same resulting landing point. This means you begin in one point, calculate the negative (-Y) at no cost and then you choose the one with smaller Y to calculate the jump.

In practice if the tamed kangaroo lands on the positive or negative point, it will be a collision, and you will catch it at the next distinguished point.

Also you have the same range N and you double the amount of calculated points but with only 1 point computation per 2 points result cost.

About the database now 1 distinguished point will "Include" twice as much points in the trailing paths. Remember the X coordinate is the same for both points so the probability of finding one distinguished point stays the same. Also as KtimesG says you will have 2 distinguished points instead of 1, the same X with n trailing zeroes and different Y, one with +Y and -Y.

Yeah but if I am storing X points, I don't really care about having 2 in the database "will have 2 distinguished points instead of 1, the same X with n trailing zeroes and different Y, one with +Y and -Y"; I only need one of them stored to solve.

Yes I believe, you only need to store the X coordinate (or its hash) and the corresponding Kangaroo ID

[WanderingPhilospher]

Mirror = takes advantage of group symmetry - you have both P and -P with the same X. If DP is on X and a DP is found, then you basically have two DPs found instead of one. Also this helps with more collisions.

This doesn't make sense to me. Why would you need the same point in the database. I don't see how this is useful.

Well a DP entry has a key (hash or whatever) and a value (distance from base point).

If the DP hash matches, you can compute for two possible values for each distance, because the collision may have happened on either the odd or even Y coord.

So, a 4-way match instead of just one. For tames, you know the distance, so you can compute both key values. For wilds, you can similarly consider the distance as being on the left or right side of the interval, so they can both be used as a potential match. It all checks out.

I still do not get why you have to store both, tame or wild, or both, all 4 DPs, a 4-way match as you said. Or just going back to the original statement, why it makes sense to store both, "...then you basically have two DPs found instead of one".

The kicker is, if you found one, you know that you have found both. They are the same value +/-. So I do not know why one would save both in a table.

Let us say we are searching for private key 0x15, public key 02352bbf4a4cdd12564f93fa332ce333301d9ad40271f8107181340aef25be59d5 at DP 0.

I have a tame that landed on private key (point) 0x16, point and distance stored:
421F5FC9A21065445C96FDB91C0C1E2F2431741C72713B4B99DDCB316F31E9FC :  16

Let's say we had a tame land on the + and the -; right or left side, etc. of private key (point) 0x1, or fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140; the point and distance stored would be:
421F5FC9A21065445C96FDB91C0C1E2F2431741C72713B4B99DDCB316F31E9FC :  1

or if you program in some wacky kind of way, it would be stored as:
421F5FC9A21065445C96FDB91C0C1E2F2431741C72713B4B99DDCB316F31E9FC :  fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140

Now you can jumble up the table and add some kind of switch that lets you know if it is right/left +/-, or have your solver code check both +/-, but I would never store the same exact points, for tames nor wilds. Just one for me

[kTimesG]

I still do not get why you have to store both, tame or wild, or both, all 4 DPs, a 4-way match as you said. Or just going back to the original statement, why it makes sense to store both, "...then you basically have two DPs found instead of one".

I think it was misunderstood. Where did I mention that both DPs need to be stored?

I said that when a DP is found, then you basically have two DPs. In a single database entry, since they both have the same X, hence the same hash (if Y is not used to affect the hash of the DP entry).

It shouldn't even be possible to store both - DP database keys must be unique for fast search. So an insertion will fail when a collision is detected, or when the DP hash collides, or when some kangaroo type collides with itself (and dies if the landed point is the stored DP point, not its opposite).

[JackMazzoni]

How many rtx 4090 gpu needed to solve puzzle 135 using your software?

[Cricktor]

~~~

Do you understand that the way you asked your question is plain stupid? And because you didn't put much effort into your question, I will answer deliberately on the same level: you need just one RTX 4090 to solve puzzle 135 eventually, in few hundreds of years. You could also use just zero RTX 4090 and go cpu-only, we're then in a time frame of many thousands of years.

I'm sure it's not precisely the answer you were looking for. Ask your questions with a bit more brain involved.