Quote from: kTimesG on Today at 02:32:42 PM

Quote from: nomachine on Today at 07:02:45 AM

Quote from: kTimesG on July 22, 2024, 03:53:40 PM

You can use nomachine's Rust Kangaroo a few posts back, or write a Python script that does the job according to your requirements (e.g. "that actually works").
Too slow? Well, don't expect to find something that "actually works", is fast, and solves 130, sitting out there for you to snug up and inherit 13 BTC tomorrow.

Not in Rust. Pure C++ with GMP. Here is the latest version that goes 470K Hops per second.

Theoretically, with 12 cores, it can achieve 5 million hops per second.
The more cores you have, the better the result will be.
However, it's not worth using this for a puzzle above 70bit. A GPU must be used instead....

Pure self-contained Python Kangaroo with no libraries required. 225K Hops per second.

DO NOT USE THIS TO SEARCH FOR 130. It is just an educational, reference-only example. All the math uses Python integers.

kangaroo.py

Code:

import math, os, sys, time

class S: # Scalar field
   N = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

   @staticmethod
   def add(a, b):
   return (a + b) % S.N

class F: # Curve field
   P = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f

   @staticmethod
   def add(a, b):
   return (a + b) % F.P

   @staticmethod
   def mul(a, b):
   return (a * b) % F.P

   @staticmethod
   def pow(b, e):
   return pow(b, e, F.P)

   @staticmethod
   def sqrt(a):
   return F.pow(a, (F.P + 1) // 4)

   @staticmethod
   def inv(a):
   if a == 0:
   return 0

   r = 1
   s = 0
   low = a % F.P
   high = F.P

   while low > 1:
   q = high // low
   nm = s - q * r
   nw = high - low * q
   high = low
   s = r
   low = nw
   r = nm

   return r % F.P

class Point: # Affine point
   def __init__(self, x, y, parity=-1):
   self.x = x
   self.y = y if parity == -1 else Point.calc_y(x, parity)

   @classmethod
   def uncompress(cls, s):
   parity, xh = int(s[:2], 16), s[2:]
   if parity not in [2, 3]:
   raise Exception("Expected parity 02 or 03")
   return Point(int(xh, 16), 0, parity % 2)

   @staticmethod
   def calc_y(x, parity):
   y = F.sqrt(F.add(F.pow(x, 3), 7)) # y = sqrt(x**3 + 7)
   return y if parity == y % 2 else F.P - y

class JPoint: # Jacobian point
   def __init__(self, x, y, z):
   self.x = x
   self.y = y
   self.z = z

   def affine(self):
   z = F.inv(self.z)
   z2 = F.mul(z, z)
   return Point(F.mul(self.x, z2), F.mul(self.y, F.mul(z, z2)))

   def mul(self, n):
   if self.y == 0 or n == 0:
   return JPoint(0, 0, 1)

   if n == 1:
   return self

   if n < 0 or n >= S.N:
   return self.mul(n % S.N)

   if (n % 2) == 0:
   return self.mul(n // 2).double()

   return self.mul(n // 2).double().add(self)

   def double(self):
   if self.y == 0:
   return JPoint(0, 0, 0)

   y2 = F.mul(self.y, self.y)
   s = F.mul(4 * self.x, y2)
   M = F.mul(3 * self.x, self.x)

   x = F.add(F.mul(M, M), - 2 * s)
   return JPoint(x, F.add(F.mul(M, s - x), -F.mul(8 * y2, y2)), F.mul(2 * self.y, self.z))

   def add(self, q):
   if self.y == 0:
   return q
   if q.y == 0:
   return self

   qz2 = F.mul(q.z, q.z)
   pz2 = F.mul(self.z, self.z)
   U1 = F.mul(self.x, qz2)
   U2 = F.mul(q.x, pz2)
   S1 = F.mul(self.y, F.mul(q.z, qz2))
   S2 = F.mul(q.y, F.mul(self.z, pz2))

   if U1 == U2:
   if S1 != S2:
   return JPoint(0, 0, 1)
   return self.double()

   H = F.add(U2, -U1)
   R = F.add(S2, -S1)
   H2 = F.mul(H, H)
   H3 = F.mul(H, H2)
   U1H2 = F.mul(U1, H2)
   nx = F.add(F.mul(R, R), -F.add(H3, 2 * U1H2))
   ny = F.add(F.mul(R, F.add(U1H2, -nx)), -F.mul(S1, H3))
   nz = F.mul(H * self.z, q.z)

   return JPoint(nx, ny, nz)

class Group:
   G = Point(
   0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,
   0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
   )

   @staticmethod
   def add(p, q):
   m = F.mul(F.add(p.y, -q.y), F.inv(F.add(p.x, -q.x)))
   x = F.add(F.add(F.mul(m, m), -p.x), -q.x)
   return Point(x, F.add(F.mul(m, F.add(q.x, -x)), -q.y))

   @classmethod
   def mul(cls, p, k):
   # [k]P point scalar multiplication
   return JPoint(p.x, p.y, 1).mul(k).affine()

   @classmethod
   def batch_add(cls, ga, gb):
   n = len(ga)
   d = [0] * n
   p = [0] * n
   z = 1
   for i in range(n):
   d[i] = F.add(ga[i].x, -gb[i].x)
   z = F.mul(z, d[i])
   p[i] = z

   t = F.inv(z)

   for i in range(n - 1, -1, -1):
   if i > 0:
   xi = F.mul(t, p[i - 1])
   t = F.mul(t, d[i])
   else:
   xi = t

   m = F.mul(F.add(ga[i].y, -gb[i].y), xi)
   ga[i].x = F.add(F.add(F.mul(m, m), -ga[i].x), -gb[i].x)
   ga[i].y = F.add(F.mul(m, F.add(gb[i].x, -ga[i].x)), -gb[i].y)

class TrueRandom:
   def __init__(self, max_value: int, num_bits: int, min_value: int = 0):
   self.upper_bound = max_value - min_value + 1
   self.min = min_value
   self.num_bits = num_bits
   self.domain = 2 ** num_bits
   self.num_bytes = math.ceil(num_bits / 8)
   self.shift = 8 * self.num_bytes - num_bits

   def get_next(self):
   random_bytes = os.urandom(self.num_bytes)

   # trim to num_bits
   random_int = int.from_bytes(random_bytes, byteorder='big') >> self.shift

   # normalize from domain range to target range
   sample = self.upper_bound * random_int // self.domain

   return sample + self.min

def kangaroo_with_results(k1, k2, P, dp, herd_size):
   k_cand, counter, tbl_size = kangaroo(k1, k2, P, dp, herd_size=herd_size)

   k = k_cand[0]
   if k1 <= k <= k2:
   P_check = Group.mul(Group.G, k)
   if P_check.x == P.x:
   print(f'Key: {hex(k)}\nGroup ops: {counter}')

   return k_cand, counter, tbl_size

def create_kangaroo(kang_type, pos: int, herd_pts, herd_distances, k1, k2, P, rnd: TrueRandom, v):
   if kang_type == 0:
   # d = rnd.get_next() # [0, k2 - k1)
   d = (k2 - k1 + 1) + pos * v # b/2 + i*v
   # d = (k2 - k1 + 1) // 2
   herd_distances[pos] = d
   herd_pts[pos] = Group.mul(Group.G, k1 + d)
   else:
   # d = rnd.get_next() - (k2 - k1 + 1) // 2 # [-(k2-k1)/2, (k2-k1)/2]
   d = (k2 - k1 + 1) // 2 + pos * v # b + i*v
   # d = 0
   herd_distances[pos] = d
   herd_pts[pos] = Group.add(P, Group.mul(Group.G, d))

def check_col(kang_type, hashmap, herd, dist, pos, k1, k2, P, dp_mask, R, v_rnd,
   respawn_dead=True,
   stop_at_dp=True):
   x = herd[pos].x

   if x & dp_mask == 0:
   item = hashmap.get(x)

   if item is not None:
   if item[0] == kang_type ^ 1:
   # collision
   d_wild, d_tame = (item[1], dist[pos]) if kang_type == 0 else (dist[pos], item[1])
   return [S.add(k1 + d_tame, - d_wild)], 0
   else:
   # print(f'Dead kangaroo at {pos}')
   if respawn_dead:
   # create_kangaroo(kang_type, pos, herd, dist, k1, k2, P, R)
   # move along with a small random value
   d = v_rnd.get_next()
   dist[pos] += d
   herd[pos] = Group.add(herd[pos], Group.mul(Group.G, d))

   # this will recurse until a non-dead kangaroo is produced
   k, created = check_col(kang_type, hashmap, herd, dist, pos, k1, k2, P, dp_mask, R, v_rnd)
   return k, 1 + created
   else:
   hashmap[x] = (kang_type, dist[pos])

   return 0, 0

def build_jump_distances(alpha, with_points=False):
   jump_points = []
   jump_distances = []

   # compute A (jump distances) such that average(A) is closest to expected alpha
   # Pollard says choosing A as powers of two feels like "needs more investigation"
   min_diff = 1
   while True:
   jump_distance = 2 ** len(jump_distances)
   jump_distances.append(jump_distance)
   if with_points:
   jump_points.append(Group.mul(Group.G, jump_distance))

   alpha_real = sum(jump_distances) / len(jump_distances)
   diff = abs(1 - alpha_real / alpha)
   if alpha_real >= alpha:
   if diff > min_diff:
   jump_distances.pop()
   break
   if diff < min_diff:
   min_diff = diff

   return jump_distances, jump_points

def kangaroo(k1, k2, P, dp: int, herd_size: int = 128):
   b = k2 - k1 + 1 # size of search interval
   m = herd_size + herd_size # m/2 + m/2
   # parallel case - minimize alpha for total number of jumps
   alpha = m * math.sqrt(b) / 4 # m * sqrt(b) / 4

   jump_distances, jump_points = build_jump_distances(alpha, with_points=True)
   alpha_real = sum(jump_distances) / len(jump_distances)

   n = len(jump_distances)

   # adjust alpha to the actual average jump distance
   alpha_expected = alpha
   alpha = alpha_real

   # expected total number of jumps for each trailing kangaroo (1 per processor)
   expected_trailing_jumps = 2 * math.sqrt(b) / m # 2 * sqrt(b) / m

   # beta = 0.553 # serial case
   # ab_jumps = int(alpha * beta) # serial case
   # max_tame_distance = int(alpha * alpha * beta + b // 2)

   # expected number of jumps done by a trailing kangaroo after it enters the [b, ...] region
   # this would equal the number of jumps done by a tame kangaroo that starts from b
   num_tame_jumps = 4 * alpha / (m * m) # 4 * alpha / (m**2)
   max_tame_distance = int(alpha * num_tame_jumps + b) # average jump size * num jumps + start
   # max_wild_distance = int(alpha * num_tame_jumps + b/2) # average jump size * num jumps + start
   # = (2*a/m)**2 = (sqrt(b) / 2)**2

   # set v to the "partition" size for a processor, and not a power of two
   v = b // m - 1 # (b/2) / (m/2)
   # v = herd_size
   v_rnd = TrueRandom(v, 256)

   hashmap = {}
   wilds: list = [None] * herd_size
   tames: list = [None] * herd_size
   w_dist = [0] * herd_size
   t_dist = [0] * herd_size
   counter = 0
   done_ab_jumps = 0

   expected_total_jumps = math.ceil((num_tame_jumps + expected_trailing_jumps) * herd_size)
   print(
   f'processors: {m}'
   f'\n num jump distances: {n}'
   f'\nmax jumps per tame kangaroo: {math.ceil(num_tame_jumps)}'
   f'\nmax jumps per wild kangaroo: {math.ceil(expected_trailing_jumps)}'
   f'\n expected total jumps: {expected_total_jumps} {math.log2(expected_total_jumps):.2f} bits'
   f'\n avg real jump distance: {round(alpha_real)} {math.log2(alpha_real):.2f} bits'
   f'\n avg expected jump distance: {round(alpha_expected)} {math.log2(alpha_expected):.2f} bits'
   f'\n expected max tame distance: {max_tame_distance} {math.log2(max_tame_distance):.2f} bits'
   # f'\n expected max wild distance: {max_wild_distance} {math.log2(max_wild_distance):.2f} bits'
   )

   R = TrueRandom(k2 - k1, 256, 0)
   dp_mask = (1 << dp) - 1

   for idx in range(herd_size):
   create_kangaroo(0, idx, tames, t_dist, k1, k2, P, R, v)
   counter += 1

   k, born = check_col(0, hashmap, tames, t_dist, idx, k1, k2, P, dp_mask, R, v_rnd)
   counter += born
   if k:
   return k, counter, len(hashmap)

   create_kangaroo(1, idx, wilds, w_dist, k1, k2, P, R, v)
   counter += 1

   k, born = check_col(1, hashmap, wilds, w_dist, idx, k1, k2, P, dp_mask, R, v_rnd)
   counter += born
   if k:
   return k, counter, len(hashmap)

   batch_jp: list = [None] * herd_size

   start_time = time.time()
   last_p_time = 0
   while True:
   if done_ab_jumps < num_tame_jumps:
   # jump tames
   for idx in range(herd_size):
   d = tames[idx].x % n
   # tames[idx] = Group.add(tames[idx], jump_points[d]) # un-batched addition
   batch_jp[idx] = jump_points[d]
   t_dist[idx] += jump_distances[d]

   Group.batch_add(tames, batch_jp)

   for idx in range(herd_size):
   counter += 1

   k, born = check_col(0, hashmap, tames, t_dist, idx, k1, k2, P, dp_mask, R, v_rnd)
   counter += born
   if k:
   return k, counter, len(hashmap)

   done_ab_jumps += 1
   if done_ab_jumps >= num_tame_jumps:
   # new_max = max(t_dist)
   # avg_dist = sum(t_dist) / len(t_dist)
   # print(
   # f'Tames are done.'
   # f'\nExpected max tame distance: {max_tame_distance} {math.log2(max_tame_distance):.2f} bits'
   # f'\nAverage max tame distance: {avg_dist} {math.log2(avg_dist):.2f} bits'
   # f'\nActual max tame distance: {new_max} {math.log2(new_max):.2f} bits'
   # )
   # max_tame_distance = max(max_tame_distance, new_max)
   # max_wild_distance = int(max_tame_distance + b / 2) # add initial tame - wild gap

   # create new tames herd
   for idx in range(herd_size):
   d = b + idx * v + v_rnd.get_next() # b/2 + i*v + z

   t_dist[idx] = d
   tames[idx] = Group.mul(Group.G, k1 + d)
   counter += 1

   done_ab_jumps = 0

   for idx in range(herd_size):
   d = wilds[idx].x % n
   # wilds[idx] = Group.add(wilds[idx], jump_points[d]) # unbatched addition
   batch_jp[idx] = jump_points[d]
   w_dist[idx] += jump_distances[d]

   Group.batch_add(wilds, batch_jp)

   for idx in range(herd_size):
   counter += 1

   k, born = check_col(1, hashmap, wilds, w_dist, idx, k1, k2, P, dp_mask, R, v_rnd)
   counter += born
   if k:
   return k, counter, len(hashmap)

   if w_dist[idx] > max_tame_distance:
   # create_kangaroo(1, idx, wilds, w_dist, k1, k2, P, R)
   z = v_rnd.get_next()
   d = b // 2 + idx * v + z # b + i*v + z

   w_dist[idx] = d
   wilds[idx] = Group.add(P, Group.mul(Group.G, d))

   counter += 1

   total_time = time.time() - start_time
   if total_time - last_p_time > 3:
   last_p_time = total_time
   print(f'Ops: {counter} Table size: {len(hashmap)} Speed: {counter / total_time:.0f} ops/s')

def run_puzzle(idx: int, pub_key, dp: int = 0, herd_size: int = 128, benchmark=0):
   # puzzle #X has (X - 1) unknown bits
   k1 = 1 << (idx - 1)
   k2 = (k1 << 1) - 1

   # subtract k1 to search in a [0, k2 - k1) interval
   k2 -= k1
   k1 = 0

   P = Point.uncompress(pub_key)

   # subtract (k2 - k1)G from P to bring target point's k to [0, k2 - k1) interval
   P = Group.add(P, Group.mul(Group.G, -(k2 + 1)))

   now = time.time()
   _, ops, hashmap_size = kangaroo_with_results(k1, k2, P, dp, herd_size)
   total_time = time.time() - now
   print(f'Ops: {ops} Stored: {hashmap_size}')
   print(f'Speed: {ops / total_time:.0f} ops/s')

if __name__ == '__main__':
   # r, p = int(sys.argv[1]), sys.argv[2]
   # run_puzzle(r, p, dp=0, herd_size=128)

   # run_puzzle(32, '0209c58240e50e3ba3f833c82655e8725c037a2294e14cf5d73a5df8d56159de69',
   # herd_size=512)

   run_puzzle(48, '0291bee5cf4b14c291c650732faa166040e4c18a14731f9a930c1e87d3ec12debb',
   dp=8, herd_size=1024)

Puzzle 48:

Code:

processors: 2048
   num jump distances: 38
max jumps per tame kangaroo: 6899
max jumps per wild kangaroo: 11586
   expected total jumps: 18927375 24.17 bits
   avg real jump distance: 7233629130 32.75 bits
avg expected jump distance: 6074001000 32.50 bits
expected max tame distance: 190638869267657 47.44 bits
...
Ops: 17607859 Table size: 68719 Speed: 225400 ops/s
Key: 0x2de6d7ce3b9b
Group ops: 18288933
Ops: 18288933 Stored: 71317
Speed: 222616 ops/s

I have almost same script in C++ but using #include <boost/multiprecision/cpp_int.hpp>