Good point, effectively they are just copies. 

Great idea!

But for our problem it is not suitable, we have to maximize the chance to get a collision inside an interval.
In a small interval [a*G, ..., b*G] (80 bit) probably you won't find 2 points with the same x or the same y, we don't work in the entire space.

We tried to move [a*G, ..., b*G] to [-(b-a)/2*G, +(b-a)/2*G]  because it is precisely the way to have all points with the opposite in the same subgroup. Then for each 'x' we have 2 points for sure.



If you work in 3 spaces of points and you change the generator and the jumps accordingly:

           point                                scalar                                                                             jumps
[a*G,   (a+1)*G, ....,  b*G]     <-> [a,b]   interval 1                                         (1*G, 2*G, 4*G,...., 2^(n-1)*G)
[a*G',  (a+1)*G', ....,  b*G']    <-> [a,b]   interval 2  where G'=lambda*G      (1*G', 2*G', 4*G',...., 2^(n-1)*G')
[a*G'', (a+1)*G'', ...., b*G'']   <-> [a,b]   interval 3  where G''=lambda*G    (1*G'', 2*G'', 4*G'',...., 2^(n-1)*G'')

you will have three intervals of consecutive points. In this way any movement in the interval 1 has its own "copy" in the other 2 intervals.

Only negative jumps? I would try with positive/negative jumps and a greater average (my sensation)
To me it looks promising. 1.50sqrt(N) would be amazing!
Another thing to pay attention to is: when we translate our interval, we have only 2^(n-1) x-coordinates, and then half DP. For the tuning it's like we worked in a 2^(n-1) space.


I was thinking another thing,
if you want to overcome/avoid the brownian-motion tuning problem,

go back and put together

1) the linearity (and therefore the simplicity) of the classic approach (that you used in the release 1.3)
2) the power of the symmetry

Exploiting the symmetry means that we use equivalence classes to increase the probability of a collision (same number of tries, half 'points'); in our case, given a point P(x,y), 'x' decides the width of the jump and 'y' only the direction.
In the secp256k1 there are 2 points that share the same 'x', (x,y) and (x,-y).

In a interval of consecutive points, all x-coordinates are different, but if we move the interval like we did it becomes symmetric.

The drawback of our approach is that the kangaroo, instead of going in only one direction, keep going back and forth, creating many loops. Besides, not only we don't know where a wild kangaroo is (obviously we don't know its position-private key), but we don't control even the direction of its motion (and often it comes out from the interval)


But this curve has another symmetry that respects the linearity (unlike the negative map that overturns the interval and the kangaroo algorithm): endomorphism.

There are 3 points with the same 'y' , that means that this curve has about 2^256 points and
 
1) 2^256 / 2 different x-coordinates
2) 2^256 / 3 different y-coordinates

Why don't we use the symmetry that mantains the linearity of the interval?

We can work on the y-coordinates, and a jump should be depend on 'y' and not on 'x'.
We set equivalence classes where [P] = {P, Q, R} if and only if  yP = yQ = yR

What is the relation between the private key of these points P, Q, R?

If P=k*G, then Q=k*lambda*G and R =k*lambda^2*G (endomorphism)
and P=(x,y) -> Q=(beta*x, y) -> R=(beta^2*x,y)

observation:

if P=k*G, i.e. k is the private key of P respect of the generator G, then
lambda*P = k*lambda*G, i.e. the private key of P'=lambda*P respect of the generator G'=lambda*G is always k.

In other words, if we know that k lies in [a,b], resolving the problem P=k*G is equivalent to resolve the problem P'=k*G'
The interval is the same (from the scalar's point of view) but there are actually 3 different intervals of points. They are all consecutive from a different generator's point of view:

           point                                scalar
[a*G,   (a+1)*G, ....,  b*G]     <-> [a,b]   interval 1
[a*G',  (a+1)*G', ....,  b*G']    <-> [a,b]   interval 2  where G'=lambda*G
[a*G'', (a+1)*G'', ...., b*G'']   <-> [a,b]   interval 3  where G''=lambda*G

We could work on  3 "spaces" simultaneously :

P=k*G, with all points with generator G   -> interval 1     jumps (1*G, 2*G, ,,,2^(n-1)*G)

P'=k*G' with all points with generator G' -> interval 2     jumps(lambda*G, lambda*2*G, .... lambda*2^(n-1)*G)

P''=k*G'' with all points with generator G'' -> interval 3  jumps(lambda^2*G, lambda^2*2*G, .... lambda^2*2^(n-1)*G)

if the movements of a kangaroo depends only by the y-coordinates, that means that if a kangaroo reach a point T in the first interval and another kangaroo reachs a point W in the second interval with the same y, we will have a collision!
From that point they will walk together along the same path (across the same equivalence classes) until they reach a DP (in this case a y-coordinate with some zero bits), we detect this collision.

EDIT:
We work in this way in a space of 3*2^n points (3 intervals), but with only 2^n y-coordinates, then we should have a collision with a higher probability.  WRONG

If you shift the range [a,b] -> [-(b-a)/2, (b-a)/2], each point P in this interval has the property that -P is in interval too. No other operations are needed.

We do have fast inversions. Inversion in additive group means: -P, and -P is pratically for free.

But with both signs (+-) or not?

Could you try with an average of 2^21 - 2^22 instead?

Your jumps are: +-G, +-2*G, ...., +-2^19*G ?

You cannot loose the symmetry.

Are you sure that the algorithm goes outside the range so often? I don't think so, with this kind of jump (back and forth), I would use longer jumps, because you in sqrt(n) steps shouldn't go outside of the interval (on average) like the classic version.

I suppose the main problem is the loops (a single kangaroo with itself)

Many thanks!!!  I didn't know it !

EDIT:

from the article:

Now:

tamei = rand(0..(k2-k1)) # Scalar operation
wildi = rand(0..(k2-k1)) - (k2-k1)/2 # Scalar operation
wildPosi = P + wildi.G # Group operation


My proposal (assuming that private key of P is for sure in [-(k2-k1)/2, (k2-k1)/2])

tamei = rand(0,..(k2-k1)/2) # Scalar operation (you can avoid negative numbers for tame)
wildi = rand(-(k2-k1)/4,...(k2-k1)/4) # Scalar operation
wildPosi = P + wildi.G # Group operation

The start interval must be: [-(b-a)/2, +(b-a)/2]

and yes, I want to add a condition on the y parity to determine the jump's direction.

In this way a wild and a tame collide if they reach:

1) the same point
2) two symetric points

In the interval [-(b-a)/2, +(b-a)/2], the x-coordinates of [1, +(b-a)/2] are equal to the x-coordinates of [-(b-a)/2, -1]; we should get more collisions, because we work in a space of 2^(n-1) points instead of 2^n.

We introduce a equivalence class [P], where P ~ Q if Q = -P and the jump function goes from [P] to [P1], i.e. it is defined between 2 equivalence classes instead of between 2 points.


A problem could be that many paths could enter in a loop before they reach a DP, because each kangaroo jumps back and forth and then a single kangaroo can collide with itself.

Good point!


It is enough to modify slightly the way we generate the next jump:

+ jP[tamePosi.x % n]*G if y > p/2,  - jP[tamePosi.x % n]*G is y <p/2

(then I will indicate 'y' if y > p/2, '-y' if y < p/2)


in this way when a tame T reaches a point Q = (x,y) and a wild W reaches a point Q' = -Q = (x,-y), this become a collision

The tame and the wild will go on with 2 specular paths:

Q -> Q + k*G -> Q + k*G -r*G ->  ... -> DP
(x,y)    (x1,-y1)          (x2,y2)              (x0, y0)

-Q -> -Q -k*G -> -Q - k*G +r*G -> ... -> DP
(x,-y)  (x1,y1)         (x2, -y2)              (x0, -y0)

until they reach 2 symetric DP, for both of which we know the private key.



I have created a sort of "brownian motion", my kangaroos keep jumping back and forth.

No. I meant: translate tame and wild. Not only tame. In a interval with 2^n points but only 2^(n-1) coordinates 'x' (instead of 2^n) to increase the probability to have a collision. If you do the same number of steps in a half space (from coordinates x point of view), the chance should be higher. Half number of x coordinates, half DP, same number of steps, more chance.

Like I said before, a tame kangaroo and a wild kangaroo in this scenario collide not only if they fall in the same position but if they fall in 2 different positions (but symetric respect of the center of the interval) as well.

If you instead translate this interval in any other position of the curve, when a tame kangaroo and a wild kangaroo fall in 2 positions symetric respect of the center of the interval, your current algorithm doesn't detect a collision, simply because it can't know (without more computation) the x coordinate of the symetric point (respect of (a+b)/2 * G) of any DP that lies in the hashtable (and a symetric point of a DP generally is not a DP)


My idea goes a little in that direction too, cause the jumps are always positive but the points generated go in both direction, exploiting the symetrie of the curve.

Example:

when a sequence starts from -k*G (negative part):

-k*G, (-k + 2^17)*G, (-k +2^17 + 2^3)*G, ....  forth -->

but in this way you have too (for free) the x coordinates of :

+k*G, (+k - 2^17)*G, (+k- 2^17 - 2^3)*G, ....       <-- back

the movement is like this:

             zero point
(-->                            <--)         extreme:  -k*G, k*G
   (-->                    <--)              extreme:   (-k+2^17)*G,  -(-k+2^17)*G
          (-->   <--)                        extreme:   (-k+2^17+2^3)*G,  -(-k+2^17+2^3)*G



when a sequence starts/arrives in the positive part:

k*G, (k + 2^8)*G, (k +2^8 + 2^31)*G, ....  forth -->
-k*G, (-k - 2^8)*G, (-k -2^8 - 2^31)*G, ....   <-- back

                zero point
           <-- (        )-->                        extreme:  -k*G, k*G
       <--(                  )-->                   extreme:   -(k+2^8)*G,  (k+2^8)*G
  <--(                            )-->              extreme:   -(k+2^8+2^31)*G,  (k+2^8+2^31)*G

Another idea:
do you use the symetrie?
If you shift the range from [a,b] to [-(b-a)/2, (b-a)/2] and you generate tame in this range, for each point you create actually a couple of opposite points in the same interval (same x), in this way you probably should have more collisions.

The tame points starting from the negative part of the interval create a couple of points that move towards the center of the interval, while the tame points starting from the positive part create a couple of points that move towards the extreme of the interval. In this way, each tame walks across the double of the points in the interval (with the same computational cost). Same for the wild ones.

In other words a tame kangaroo and a wild kangaroo collide if they fall in the same position or if they fall in 2 different positions but symetric respect of the center of the interval.

In other words : an interval of this type has only 2**(n-1) different x coordinates.

Ok.

I think that it would be faster if you used a hashtable with precomputed distinguished points (the tame points).

The speed should double.

Yes, this is clear, but these points seem to me not to be really (pseudo)random. There is a order. You can move only forward (from private key's point of view). Therefor many collisions are just impossible to get (instead in the birthday paradox, each new distinguished point has the chance to produce a collision with any previous distinguished point, for example that happens in BTCCollider, because in that case you can jump in any position, you go back and forth across the entire space)

Example with only 2 sequences:

If we suppose that W_100 is = (2^37)*G and T_100 is (2^38)*G, than between T_101, T_102, .... , T_2**32 it is no longer possible to find a single distinguished point with the same coordinate of any distinguished point that lies in W_0, W_1, W_2, ....., W_100. For sure.

Then how do you apply in this case birthday paradox?

It is impossible to get a collision in the path of the same tame kangaroo too, because the same kangaroo cannot turn back, then this is a pseudorandom sequence very particular ...

Hi,

let's see if I have understood this Kangaroo algorithm:

P=k*G, you know P and you know that a < k < b, for semplicity :  0 < k < a, for example: 0 < k < 2^64 (starting interval)

you generate many sequence of 2 type of points:

1) tame: each sequence starts from a random point T0 that lies in the starting interval, then

T0, T1, T2, ….     the difference between 2 consecutive points is: G, or 2*G, or 4*G, or 8*G, …, or 2^32*G

2) wild: each sequence starts from P + r*G, where r*G is a random point with a random r private key between 0 < k < 2^31), then:

W0, W1, W2, ….. the difference between 2 consecutive points is: G, or 2*G, or 4*G, …, or 2^32*G

each jump towards the next point depends on the x coordinate (mod 33) of the current point; in this way if a tame kangaroo reach a points already reached from a wild kangaroo (or viceversa), you have a collision and then same path from there.  

In that case T = W ->  t*G = w*G ->  t*G = P + w*G  ->  t*G = k*G + w*G -> k = (t-w) mod n

Besides you use distinguished points to detect this collision.


In this example you generate about 2^32 points  (T points) in the interval [1*G, (2^64+(2^32)(2^32))*G]
and about 2^32 points (W points) in the interval [P+r*G, ((k+r)+(2^32*2^32))*G]

let's say that both type of points have for sure their private keys in [1, 2^65] interval

But can you treat these points like if they were random? Can you apply in this case the birthday paradox?

Nuovo modello di PlanB per la previsione del prezzo di btc:

https://medium.com/@100trillionUSD/bitcoin-stock-to-flow-cross-asset-model-50d260feed12

Ok, I tried with "unsigned char c" (I removed the check):

from
2**(33.42) keys / (13*60+44)s = 13.947.463 = 14 MKeys/s  your program with volatile

to
2**(32.18) keys / (4*60+12.0)s = 19.308.330 = 19,3 MKeys/s with unsigned char

and the bug is still there, with unsigned char I get this error:

./kangaroo -d 8 input
Kangaroo v1.3
ParsePublicKeyHex: Error invalid public key specified (Not lie on elliptic curve)
input, error line 2: 0459A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC994327554CED8 87AAE5D211A2407CDD025CFC3779ECB9C9D7F2F1A1DDF3E9FF8
Start:49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E0000000000000000
Stop :49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EFFFFFFFFFFFFFFFF

it's weird that the program doesn't stop, I think it should terminate in this case.

Yes, you're right.
Besides when I compile I get this message:

warning: #warning "GCC lass than 7.3 detected, upgrade gcc to get best perfromance" [-Wcpp]
   #warning "GCC lass than 7.3 detected, upgrade gcc to get best perfromance"

Maybe with a new version of gcc the performance of your function would be better on my system.



I replaced ModSquareK1(Int *a) too:

./kangaroo -d 8 input
Kangaroo v1.3
Start:49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E0000000000000000
Stop :49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EFFFFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 8
Range width: 2^64
Number of random walk: 2^13.00 (Max DP=17)
DP size: 8 [0xff00000000000000]
SolveKeyCPU Thread 0: 1024 kangaroos
SolveKeyCPU Thread 2: 1024 kangaroos
SolveKeyCPU Thread 3: 1024 kangaroos
SolveKeyCPU Thread 1: 1024 kangaroos
SolveKeyCPU Thread 7: 1024 kangaroos
SolveKeyCPU Thread 4: 1024 kangaroos
SolveKeyCPU Thread 6: 1024 kangaroos
SolveKeyCPU Thread 5: 1024 kangaroos
[24.33 MKey/s][GPU 0.00 MKey/s][Count 2^33.42][Dead 2][08:56][3440.8MB]  
Key# 0 Pub:  0x0259A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EBB3EF3883C1866D4

Done: Total time 09:15


from 16 to 24 MKeys/s, +50% ...




EDIT:

2**(33.42) keys / (13*60+44)s = 13.947.463 = 14 MKeys/s  your program

2**(32.47) keys / (5*60+26)s = 18.248.465 = 18,2 MKeys/s  ModMul replaced

2**(33.42) keys / (9*60+15)s = 20707585 = 20,7 MKeys/s  ModMul+ModSqr replaced

2**(33.24) keys / (7*60+58)s = 21223116 = 21,2 MKeys/s  ModMul+ModSqr+ModSub replaced


from 14 to 21,2 MKeys/s: +50%