Post
Topic
Board Bitcoin Discussion
Re: Bitcoin puzzle transaction ~32 BTC prize to who solves it
by
Geshma
on 06/02/2025, 21:54:26 UTC
#67 You can solve puzzles using mathematical methods, only requiring 58 to the power of 7 Calculation.

Go get it!

its a bit mumbled up , wanted your perspective  , and not working also as intended , be gentle:

import os
import math
import time
import bisect
from gmpy2 import gmpy2

# --------------------------
# Field and Group Operations (unchanged)
# --------------------------

class S:  # Scalar field (secp256k1 order)
    N = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
    gmp_N = gmpy2.mpz(N)

    @staticmethod
    def add(a, b):
        return gmpy2.mod(gmpy2.add(a, b), S.gmp_N)

    @staticmethod
    def sub(a, b):
        return gmpy2.mod(gmpy2.sub(a, b), S.gmp_N)

    @staticmethod
    def mul(a, b):
        return gmpy2.mod(gmpy2.mul(a, b), S.gmp_N)

class F:  # Prime field (secp256k1 field)
    P = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
    gmp_P = gmpy2.mpz(P)
    gmp_P4 = gmpy2.mpz((P + 1) // 4)

    @staticmethod
    def add(a, b):
        return gmpy2.mod(gmpy2.add(a, b), F.gmp_P)

    @staticmethod
    def sub(a, b):
        return gmpy2.mod(gmpy2.sub(a, b), F.gmp_P)

    @staticmethod
    def mul(a, b):
        return gmpy2.mod(gmpy2.mul(a, b), F.gmp_P)

    @staticmethod
    def pow(b, e):
        return gmpy2.powmod(b, e, F.gmp_P)

    @staticmethod
    def sqrt(a):
        return gmpy2.powmod(a, F.gmp_P4, F.gmp_P)

    @staticmethod
    def inv(a):
        return gmpy2.invert(a, F.gmp_P)

# -----------------
# Point Operations (unchanged)
# -----------------

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

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y       

    @classmethod
    def uncompress(cls, s):
        parity, xh = int(s[:2], 16), s[2:]
        if parity not in [2, 3]:
            raise ValueError("Invalid parity byte")
        return Point(int(xh, 16), 0, parity % 2)

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

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

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

    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 * F.mul(self.x, self.x), F.mul(self.z, F.mul(self.z, self.z)))
       
        x = F.sub(F.mul(m, m), F.mul(2, s))
        y = F.sub(F.mul(m, F.sub(s, x)), F.mul(8, F.mul(y2, y2)))
        z = F.mul(2 * self.y, self.z)
        return JPoint(x, y, z)

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

        z1z1 = F.mul(self.z, self.z)
        z2z2 = F.mul(q.z, q.z)
        u1 = F.mul(self.x, z2z2)
        u2 = F.mul(q.x, z1z1)
        s1 = F.mul(self.y, F.mul(q.z, z2z2))
        s2 = F.mul(q.y, F.mul(self.z, z1z1))

        if u1 == u2:
            return self.double() if s1 == s2 else JPoint(0, 0, 1)
           
        h = F.sub(u2, u1)
        r = F.sub(s2, s1)
        h2 = F.mul(h, h)
        h3 = F.mul(h, h2)
       
        x = F.sub(F.sub(F.mul(r, r), h3), F.mul(2, F.mul(u1, h2)))
        y = F.sub(F.mul(r, F.sub(F.mul(u1, h2), x)), F.mul(s1, h3))
        z = F.mul(h, F.mul(self.z, q.z))
        return JPoint(x, y, z)

    def mul(self, n):
        result = JPoint(0, 0, 1)
        current = self
       
        while n > 0:
            if n % 2 == 1:
                result = result.add(current)
            current = current.double()
            n //= 2
        return result

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

    @staticmethod
    def mul(p: Point, k):
        return JPoint(p.x, p.y, 1).mul(k).affine()

    @staticmethod
    def add(p: Point, q: Point):
        if p.x == q.x:
            raise ValueError("Points with same x-coordinate")
        m = F.mul(F.sub(p.y, q.y), F.inv(F.sub(p.x, q.x)))
        x = F.sub(F.sub(F.mul(m, m), p.x), q.x)
        y = F.sub(F.mul(m, F.sub(p.x, x)), p.y)
        return Point(x, y)

# ------------------
# Enhanced Kangaroo Algorithm with Adjustments
# ------------------

class Kangaroo:
    def __init__(self, start, end, dp_bits=14, herd_size=1024):
        # 1. Initialize critical range parameters FIRST
        self.start = start
        self.end = end
        self.range = end - start + 1
        self.interval_size = self.range  # Key parameter
        self.max_intervals = 1  # Now properly defined

        # 2. Store target reference for herd initialization
        self.target = None  # Will be set in solve()

        # 3. Configure jumps and DPs
        self.dp_mask = (1 << dp_bits) - 1
        self.herd_size = herd_size

        self.tame_points = []  # Initialize tame_points here
        self.wild_points = []  # Initialize wild_points here

        # 4. Initialize jump parameters. This is the code change.
        self.base_alpha = self.herd_size * math.sqrt(self.range) / 2
        self.current_alpha = self.base_alpha
        self.adaptation_interval = 1000  # How often to adjust alpha
        self.jump_history = []  # To track jumps

        self._update_jump_table()  # Initialize jumps

    def _update_jump_table(self):
        """Generate geometrically increasing jumps"""
        self.jump_dists = []
        max_step = int(self.current_alpha)
        step = 1
        while len(self.jump_dists) < 12 and step <= max_step:
            self.jump_dists.append(step)
            step *= 4
        # Add final large step to prevent stagnation
        self.jump_dists.append(max_step)
        self.jump_points = [Group.mul(Group.G, d) for d in self.jump_dists]

    def _search_interval(self, interval):
        """Fixed initialization using stored target"""
        # Tame kangaroos spread through range
        step_size = self.range // self.herd_size
        tame = [Group.mul(Group.G, self.start + i*step_size)
               for i in range(self.herd_size)]
        t_dist = [self.start + i*step_size for i in range(self.herd_size)]
       
        # Wild kangaroos start from TARGET + offsets
        wild = [Group.add(self.target, Group.mul(Group.G, i))
               for i in range(self.herd_size)]
        w_dist = [i for i in range(self.herd_size)]
       
        return tame, t_dist, wild, w_dist

    def _adapt_jump_strategy(self):
        if len(self.jump_history) >= self.adaptation_interval:
            avg_jump = sum(self.jump_history[-self.adaptation_interval:]) / self.adaptation_interval
            if avg_jump < self.current_alpha / 4:
                self.current_alpha = max(self.base_alpha / 4, self.current_alpha * 0.9)
            else:
                self.current_alpha = min(self.base_alpha * 4, self.current_alpha * 1.1)
            self._update_jump_table()
            self.jump_history = []

    def _update_jump_table(self):
        self.jump_dists = []
        max_step = max(1, int(self.current_alpha))
        # Generate jumps optimized for small steps
        a, b = 1, 1
        while len(self.jump_dists) < 8 and a <= max_step:
            self.jump_dists.append(a)
            a, b = b, a + b
        # Fill remaining with 1s to ensure coverage
        while len(self.jump_dists) < 8:
            self.jump_dists.append(1)
        self.jump_points = [Group.mul(Group.G, d) for d in self.jump_dists]

    def _search_interval(self, interval):
        offset = self.start + interval * self.interval_size
        P = Group.mul(Group.G, offset)
        v = max(1, self.interval_size // self.herd_size)
       
        tame = []
        wild = []
        t_dist = []
        w_dist = []
        for i in range(self.herd_size):
            tame_pos = offset + i * v
            tame.append(Group.mul(Group.G, tame_pos))
            t_dist.append(tame_pos)
            wild_pos = (tame_pos + (self.range // 2)) % S.N  # Wild starts offset by half range
            wild.append(Group.mul(Group.G, wild_pos))
            w_dist.append(wild_pos)
        return tame, t_dist, wild, w_dist

    def solve(self, target):
        self.target = target  # Critical: store target reference
        try:
            for interval in range(self.max_intervals):  # Now works
                tame, t_dist, wild, w_dist = self._search_interval(interval)
                ops = 0
                start_time = time.time()
               
                while True:
                    # Process tame herd
                    for i in range(self.herd_size):
                        if (tame.x & self.dp_mask) == 0:
                            parity = tame.y % 2
                            entry = (tame.x, parity)
                            idx = bisect.bisect_left(self.tame_points, entry)
                            if idx < len(self.tame_points) and self.tame_points[idx][:2] == entry:
                                candidate = S.sub(t_dist, self.tame_points[idx][2])
                                if Group.mul(Group.G, candidate) == target:
                                    return candidate
                            bisect.insort(self.tame_points, (tame.x, parity, t_dist))
                       
                        j = tame.x % len(self.jump_dists)
                        tame = Group.add(tame, self.jump_points[j])
                        t_dist = S.add(t_dist, self.jump_dists[j])
                        self.jump_history.append(self.jump_dists[j])

                    # Process wild herd
                    for i in range(self.herd_size):
                        if (wild.x & self.dp_mask) == 0:
                            parity = wild.y % 2
                            entry = (wild.x, parity)
                            idx = bisect.bisect_left(self.wild_points, entry)
                            if idx < len(self.wild_points) and self.wild_points[idx][:2] == entry:
                                candidate = S.sub(w_dist, self.wild_points[idx][2])
                                if Group.mul(Group.G, candidate) == target:
                                    return candidate
                            bisect.insort(self.wild_points, (wild.x, parity, w_dist))
                       
                        j = wild.x % len(self.jump_dists)
                        wild = Group.add(wild, self.jump_points[j])
                        w_dist = S.add(w_dist, self.jump_dists[j])
                        self.jump_history.append(self.jump_dists[j])

                    ops += 2 * self.herd_size
                    self._adapt_jump_strategy()
                   
                    if time.time() - start_time > 2:
                        print(f"Interval {interval} | Ops: {ops:,} | Tame: {len(self.tame_points)} | Wild: {len(self.wild_points)}")
                        start_time = time.time()
       
        except KeyboardInterrupt:
            print("\nSearch halted by user")
            return None

# ----------
# Interface
# ----------

def run_puzzle(start, end, pubkey_hex):
    try:
        target = Point.uncompress(pubkey_hex)
        kang = Kangaroo(start, end)
       
        print(f"Searching range {hex(start)}-{hex(end)} ({(end-start+1):,} keys)")
        start_time = time.time()
        result = kang.solve(target)
       
        if result is not None:
            calc_point = Group.mul(Group.G, result)
            print(f"\nFound candidate: {hex(result)}")
            print(f"Target X:   {target.x:064x}")
            print(f"Calculated X: {calc_point.x:064x}")
            print(f"Y Parity Match: {calc_point.y%2 == target.y%2}")
            if calc_point.x == target.x:
                print("Full Verification:", calc_point.y == target.y)
            else:
                print("Warning: False positive detected")
        else:
            print("\nNo valid solution found")
       
        print(f"Time elapsed: {time.time()-start_time:.2f}s")
   
    except KeyboardInterrupt:
        print("\nOperation cancelled by user")

if __name__ == "__main__":
    run_puzzle(0x1000000, 0x1ffffff, "03057fbea3a2623382628dde556b2a0698e32428d3cd225f3bd034dca82dd7455a")