Quote from: Bram24732 on Today at 11:37:59 AM

Quote from: Virtuose on Today at 10:28:26 AM

I'm going to end up believing that you're just lucky Tongue

Your method only returns the number of operations from the thread which finds the key. It discards all the tries of the 3 other threads which do not find it.
ChatGPTor not, if you want that bounty you need to up your game

Because it doesn't change much in the results, I don't know what more you want, you have the solution right in front of you if you want better than linear.. But you turn a deaf ear Grin

But I'm nice

Code:

#!/usr/bin/env python3
# coding: utf-8
"""
proof.py

Hash160 linear scan vs. double c-bit prefilter on puzzle 21.
Uses only hash160 comparisons and no Base58 encoding. Progress bars via tqdm.
"""

import hashlib
import math
from ecdsa import SECP256k1, util
from multiprocessing import Pool, cpu_count, Value
from tqdm import tqdm

# --- Default configuration ---
ADDRESS_TARGET        = "114oFNXucftsHiUMY8uctg6N487riuyXs4h"
HASH160_TARGET        = "29a78213caa9eea824acf08022ab9dfc83414f56"
RANGE_HEX             = "100000:1fffff"
FILTER_BITS           = 2    # number of c-bits to prefilter on H160
SHA_PREFILTER_BITS    = 8    # number of d-bits to prefilter on pubkey
THRESHOLD             = 5.0  # percent reduction threshold
# -------------------------------

G     = SECP256k1.generator
ORDER = SECP256k1.order
B58   = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"

# Shared counter for “heavy” operations (H160)
heavy_op_counter: Value

def init_worker(counter):
    """Initialize the shared heavy_op_counter in each worker process."""
    global heavy_op_counter
    heavy_op_counter = counter

def b58decode(s: str) -> bytes:
    """Decode a Base58Check-encoded string to raw bytes."""
    num = 0
    for ch in s:
        num = num * 58 + B58.index(ch)
    full = num.to_bytes((num.bit_length() + 7) // 8, 'big')
    pad = len(s) - len(s.lstrip('1'))
    full = b'\x00' * pad + full
    payload, checksum = full[:-4], full[-4:]
    if hashlib.sha256(hashlib.sha256(payload).digest()).digest()[:4] != checksum:
        raise ValueError("Invalid Base58 checksum")
    return payload

def hash160_pubkey(x: int) -> bytes:
    """Compute RIPEMD-160 of SHA-256 of the compressed public key corresponding to scalar x."""
    P = x * G
    prefix = b'\x02' if (P.y() & 1) == 0 else b'\x03'
    pub = prefix + util.number_to_string(P.x(), ORDER)
    return hashlib.new('ripemd160', hashlib.sha256(pub).digest()).digest()

def get_target_h160() -> bytes:
    """Return the target HASH160, either directly or by decoding ADDRESS_TARGET."""
    if HASH160_TARGET:
        return bytes.fromhex(HASH160_TARGET)
    payload = b58decode(ADDRESS_TARGET)
    return payload[1:]  # drop version byte

def linear_scan(start: int, end: int, target_h: bytes):
    """Brute-force scan comparing every hash160 to target_h."""
    ops = 0
    for x in tqdm(range(start, end + 1), desc="Linear scan", unit="key"):
        ops += 1
        if hash160_pubkey(x) == target_h:
            return x, ops
    return None, ops

def prefilter_chunk(args):
    """Worker function: scan a chunk with optional SHA256 prefilter and count heavy ops."""
    _, start, end, c, d, t1, t2, target_h = args
    for x in range(start, end + 1):
        # 1) SHA256 prefilter
        P = x * G
        prefix = b'\x02' if (P.y() & 1) == 0 else b'\x03'
        pub = prefix + util.number_to_string(P.x(), ORDER)
        sha = hashlib.sha256(pub).digest()
        if d and t2 is not None:
            if (int.from_bytes(sha, 'big') >> (256 - d)) != t2:
                continue

        # 2) heavy operation = H160
        with heavy_op_counter.get_lock():
            heavy_op_counter.value += 1

        rip = hashlib.new('ripemd160', sha).digest()
        if (int.from_bytes(rip, 'big') >> (160 - c)) != t1:
            continue
        if rip == target_h:
            return x

    return None

def parallel_prefilter(start: int, end: int, c: int, d: int,
                       target_h: bytes, t2: int, workers: int):
    """
    Run a parallel prefilter scan:
    - c bits from H160 of pubkey
    - optional d bits from SHA256(pubkey)
    """
    total_keys = end - start + 1
    chunk_size = math.ceil(total_keys / workers)
    t1 = int.from_bytes(target_h, 'big') >> (160 - c)

    # arguments for each worker chunk
    args = []
    for i in range(workers):
        s = start + i * chunk_size
        e = min(start + (i + 1) * chunk_size - 1, end)
        args.append((i, s, e, c, d, t1, t2, target_h))

    # Pool with shared counter init
    with Pool(workers, initializer=init_worker, initargs=(heavy_op_counter,)) as pool:
        for x in tqdm(pool.imap_unordered(prefilter_chunk, args),
                      total=len(args),
                      desc="Prefilter chunks",
                      unit="chunk"):
            if x is not None:
                total_ops = heavy_op_counter.value
                return x, total_ops

    return None, 0

def main():
    import argparse
    parser = argparse.ArgumentParser()
    parser.add_argument("--workers", type=int, default=0,
                        help="number of processes (default = CPU count)")
    parser.add_argument("--pubkey", type=str, default=None,
                        help="hex of compressed pubkey for SHA256 prefilter")
    args = parser.parse_args()

    workers = args.workers or cpu_count()
    s_hex, e_hex = RANGE_HEX.split(':')
    start, end = int(s_hex, 16), int(e_hex, 16)
    total_keys = end - start + 1

    print(f"Target address: {ADDRESS_TARGET}")
    print(f"Range: 0x{s_hex} .. 0x{e_hex} (total keys = {total_keys})")
    print(f"RIPEMD c-bits: {FILTER_BITS}, SHA256 d-bits: {SHA_PREFILTER_BITS}, "
          f"processes: {workers}\n")

    target_h = get_target_h160()

    # Init shared counter
    global heavy_op_counter
    heavy_op_counter = Value('L', 0)

    # Compute t2 for SHA256 prefilter if pubkey provided
    t2 = None
    if args.pubkey:
        pub_bytes = bytes.fromhex(args.pubkey)
        sha_target = hashlib.sha256(pub_bytes).digest()
        t2 = int.from_bytes(sha_target, 'big') >> (256 - SHA_PREFILTER_BITS)

    # Linear scan
    print("→ Linear hash160 scan…")
    x_lin, ops_lin = linear_scan(start, end, target_h)
    print(f"  ✅ Found x = 0x{x_lin:x} in {ops_lin} H160 operations\n")

    # Parallel double-prefilter scan
    print("→ Parallel double-prefilter scan…")
    x_pre, ops_pre = parallel_prefilter(start, end,
                                        FILTER_BITS,
                                        SHA_PREFILTER_BITS,
                                        target_h,
                                        t2,
                                        workers)
    print(f"  ✅ Found x = 0x{x_pre:x} in {ops_pre} heavy operations\n")

    # Statistics
    pct_lin = 100.0
    pct_pre = ops_pre / ops_lin * 100.0 if ops_lin else 0.0
    reduction = pct_lin - pct_pre

    print(f"Percent of checks: linear = {pct_lin:.2f}%, prefilter = {pct_pre:.2f}%")
    print(f"Reduction = {reduction:.2f}%")
    print(("✅" if reduction > THRESHOLD else "⚠️") +
          f" Reduction {'exceeds' if reduction > THRESHOLD else 'below'} {THRESHOLD}%")
    winner = "Prefilter" if ops_pre < ops_lin else "Hash160"
    print("🏆 Winner: " + winner + " scan")

if __name__ == "__main__":
    main()

root:~# python3 proof.py --pubkey 031a746c78f72754e0be046186df8a20cdce5c79b2eda76013c647af08d306e49e
Target address: 114oFNXucftsHiUMY8uctg6N487riuyXs4h
Range: 0x100000 .. 0x1fffff (total keys = 1048576)
RIPEMD c-bits: 2, SHA256 d-bits: 8, processes: 4

→ Linear hash160 scan…
Linear scan: 73%|███████████████████████████████████████████████████████████████████████████████████████████████████████████▋ | 763188/1048576 [01:00<00:22, 12530.40key/s]
✅ Found x = 0x1ba534 in 763189 H160 operations

→ Parallel double-prefilter scan…
Prefilter chunks: 0%| | 0/4 [00:40<?, ?chunk/s]
✅ Found x = 0x1ba534 in 3783 heavy operations

Percent of checks: linear = 100.00%, prefilter = 0.50%
Reduction = 99.50%
✅ Reduction exceeds 5.0%
🏆 Winner: Prefilter scan