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

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.

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?


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

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

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

  Thank's for your answer.

I have other question:
I have studied bitcrack and kangaroo (From Jean-Luc Pons) in detail. In the Pollard method with only 2 heards, Pollard recommends using a jump formula of powers of 2. When I tried to understand the Van-Oorschot method of parallelization, I realized that if you double the amount of Kangaroos, you must double the jump size mean. This results in huge jumps for a big range and a big number of kangaroos if you use powers of 2. Do you recommend better selecting the jump size using random K's in a given interval?

Thanks

Good Morning RetiredCoder:

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 would like to ask if you can give me some advice.

I believe the Pollard methods can be improved using this observations I have made:

The key to accelerate the Pollard method computations is to improve the efficiency of the inversion part.

Teske in her paper says it is ok to use 32 types of jumps to give enough randomness. What about using more jump types, let´s say 2**32 types of jumps? Then you select every jump by the first 32 bits of the X coordinate. You store the X and Y in a database, which index is the first 32 bits of X. Now the jump formula considers the 32 most significant bits of the actual point, and adds the corresponding point in the database, with the same 32 bits .

This has the advantage that X2-X1 for the inversion, can be selected to give a number of only 224 Bits instead of 256. When you calculate the batch inversion, let's say you make 400 inversions, you can multiply a 256 bit number times a 224 bit number for the partial product part.

I also have made an algorithm for batch inversion using instead a pairwise multiplication, where I think you could improve the efficiency a little bit more, because you will begin making 224 bit*224 bit multiplications. 

Does this make any sense? Will the big database search at every jump make the program slower vs the speedup of the multiplication of smaller numbers?

Thanks for your time.

Good afternoon Alberto:

I have been studying BSGS, and Pollard's Kangaroo methods for a while now. I have made an observation trying to mix BSGS with the Kangaroo method that I believe could be helpful.

I have figured out you can use the concept of distinguished points used in the kangaroo method to improve BSGS.

Here is a simple example of what I have observed:

One of the big restraints in the BSGS is the available memory to store the database, each X coordinate you calculate (every jump or every step you make) goes against the database. The other big restraint is that each point has a lookup cost against the database. (1 Point = 1 search). I understand you use a bloom filter in your program to make the search on the database a lot faster and make the database as small as possible in order to fit in the RAM available.

Here is my idea: what about if you store only distinguished points in the database, this means only X coordinates with an amount of N leading zeroes. This has 3 big benefits, one, you can discard all the points that does not have N leading zeroes on the fly, with a very small cost. Second, only compare against the database the small X coordinates. Third, you will store less bits per X coordinates.

This will improve the speed of the algorithm because you will make the same amount of comparisons but most of them only discarding the bigger X's, and then compare only the small X coordinates not discarded.

The other big benefit is that your database won't be restrained anymore by RAM, instead use RAM to store only the distinguished points found and in a latter step, compare against a big stored database in a server. 

The draw-back is that you will spend more point computations building the database, but this is made only once.

By example a very simple case:

Case 1:
You set a database of 1024 X coordinates (baby steps), you can jump a distance of 2048 (because of symmetry) and each jump has to be compared using the bloom filter.
Cost : 1 jump of distance 2024 = 1 database search

Case 2:
You set N to be 8 bits, so you store only the X coordinates beginning with 8 leading zero bits. You search for the first 1024 distinguished points, with a mean search size of 256 points per distinguished point. To make the database, you have to search 1024*256 = 262.144 points to get the 1024 distinguished points needed. Now you can make  jumps of  262.144 * 2 = 524.288 (2 **19), and search for the next distinguished point after landing ( one very big jump, many small jumps).  You make the first jump 2**19, then find the next distinguished point ( with a step of one), then jump 2**19 again. On each step you discard the big X coordinates, and keep only the small X's, this small ones are the only you need to compare. So the mean jump length on average is the same (2**19/256) = 2048, but you only made 256 comparisons on average against the first byte of the coordinate ( a very small lookup cost) and stored temporarily only one small X coordinate that will be later compared against the database.

cost : To build the database calculate 2**18 points, then for 1 jump average 2024 distance = 1  leading zeroes comparison + 1/256 database search.

I 'm trying this idea using a slightly modified version of "Bitcrack", but it has been difficult for me because I'm new at cuda programming.

Does your implementation of the bloom filter takes this observation in to consideration?

Do you think this is a good idea?

Thanks

Good afternoon, I´m positive about only needing to calculate 2^23 coordinates if you use the BSGS algorithm and pre compute 2^41 points.

The set I propose is like this:

You precompute points from k =1 to k=2^41 with a step of 1 (small step sequentially), store the last 64 bits of every x coordinate in a database.
Because of the symmetry of the secp256k1 curve over the x axis, you can set the big step to 2*2^41= 2^42. Every +k point is equivalent to -k.

If the target coordinate of the unknown K is near 2^66 (worst case), first you subtract the point (x,y) = 2^65, so now your range is from 0 to 2^65.

Then beginning from your unknown (x,y) you will subtract sequentially (x,y)= 2^42 * n times, checking each step x coordinate against the x coordinates on the database.

Because of symmetry, k = (x,y) and -k = (x, -y) have the same x coordinate, so computing the positive x's is equivalent to compute the negative x's.

If you jump 2^23 jumps *2^42 distance, you get 2^65 total distance, and at most 2^23 you have to land in the database in a deterministic way.

I was able to discard the first 2^65 Keys in puzze 130 , with my own implementation of the BSGS algorithm in python on CPU only, and a 2TB database.

I see it as a reverse BSGS because you go backwards from the unknown K to k = 0 in big jumps.

I understand Shank's algorithm is at most 2*sqrt(N) operations with no use of symmetry.

If you use symmetry, every point is like calculating 2, and now the total number of operations should be at most 2*sqrt(N/2) = sqrt(2)*sqrt(N) approx. 1.4 sqrt(N) operations.

Instead of calculating 2^32 for the database and 2^32 points, you trade more storage and more operations now, for less operations later.

My very slow implementation in 1 CPU an python manages to calculate 200.000 coordinates/sec, I have 12 cores, I make 2.4 million keys/second.

I believe I could solve it in less than 4 seconds if I manage to build a 16 TB database instead.

Sadly... the moment a lucky person finds the private key to puzzle 66, and post the transaction using the private key found,
the transaction itself will reveal the public key that it contains.

Right now the public key is not known (only the hash is known), the only way to solve the puzzle is guessing every possible private key,
calculate the public key, sha256 hash, and the ripemd 160.

Then compare each value to the already known hash value of the public key. There is no way to use Big Step,
Little Step algorithm or to use Pollard's Kangaroo method without knowing the public key in advance.

When the public key is revealed, then the puzzle 66 could be solved in less than one second using a normal computer with BSLS.

If you precompute a big enough database, let´s say 2^41 public key coordinates, you will only need to calculate about 8 million more points (2^23),
and solve the puzzle.

A RTX 1650 can get about 300 million keys/second so the puzzle will be effectively 100% sure, as you say, snatched by the bots.

If you post the transaction, with a very big transaction fee (6btc), all the money will go to the mining pool instead.

How will it work if many bots spend from the same address, all with very high fees?