#!/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()