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

Compare linear scan vs new c-bit prefilter with the puzzle 17 for test.

"""

import hashlib
from ecdsa import SECP256k1, util

# --- Configuration ---
ADDRESS_TARGET = "1HduPEXZRdG26SUT5Yk83mLkPyjnZuJ7Bm"
RANGE_HEX      = "10000:1ffff"
FILTER_BITS    = 2   # c ≥ 1 ⇒ guaranteed >5% reduction
THRESHOLD      = 5.0 # percent
# ---------------------

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

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

def serialize_pubkey(x: int) -> bytes:
    P = x * G
    prefix = b'\x02' if (P.y() & 1)==0 else b'\x03'
    return prefix + util.number_to_string(P.x(), ORDER)

def hash160_pubkey(x: int) -> bytes:
    pub = serialize_pubkey(x)
    return hashlib.new('ripemd160', hashlib.sha256(pub).digest()).digest()

def derive_address(x: int) -> str:
    h2 = hash160_pubkey(x)
    payload = b'\x00' + h2
    chk     = hashlib.sha256(hashlib.sha256(payload).digest()).digest()[:4]
    full    = payload + chk
    num = int.from_bytes(full, 'big')
    s = ""
    while num > 0:
        num, r = divmod(num, 58)
        s = B58[r] + s
    return '1' * full.startswith(b'\x00') + s

def get_filter_target(addr: str, c: int) -> int:
    payload = b58decode(addr)
    h160    = payload[1:]
    val     = int.from_bytes(h160, 'big')
    return val >> (160 - c)

def get_filter_candidate(x: int, c: int) -> int:
    h2  = hash160_pubkey(x)
    val = int.from_bytes(h2, 'big')
    return val >> (160 - c)

def linear_scan(start: int, end: int, target: str):
    ops = 0
    for x in range(start, end+1):
        ops += 1
        if derive_address(x) == target:
            return x, ops
    return None, ops

def prefilter_scan(start: int, end: int, target: str, c: int):
    t1  = get_filter_target(target, c)
    ops = 0
    for x in range(start, end+1):
        if get_filter_candidate(x, c) != t1:
            continue
        ops += 1
        if derive_address(x) == target:
            return x, ops
    return None, ops

def main():
    s_hex, e_hex = RANGE_HEX.split(':')
    start, end = int(s_hex, 16), int(e_hex, 16)
    N = end - start + 1

    print(f"Target address: {ADDRESS_TARGET}")
    print(f"Range: 0x{s_hex} .. 0x{e_hex} (N = {N})")
    print(f"Filter bits (c): {FILTER_BITS}\n")

    # Linear scan
    print("→ Linear scan…")
    x_lin, ops_lin = linear_scan(start, end, ADDRESS_TARGET)
    if x_lin is None:
        print(f"  ⚠️ Not found after {ops_lin} ops (full range).")
    else:
        print(f"  ✅ Found x = 0x{x_lin:x} in {ops_lin} ops")

    # Prefilter scan
    print("\n→ Prefilter scan…")
    x_pre, ops_pre = prefilter_scan(start, end, ADDRESS_TARGET, FILTER_BITS)
    if x_pre is None:
        print(f"  ⚠️ Not found after {ops_pre} heavy ops (filter exhausted).")
    else:
        print(f"  ✅ Found x = 0x{x_pre:x} in {ops_pre} heavy ops")

    # Compute percentages
    if x_lin is not None and x_pre is not None:
        pct_lin = 100.0
        pct_pre = ops_pre / ops_lin * 100.0
        reduction = pct_lin - pct_pre

        print(f"\nPercent heavy checks: linear = {pct_lin:.2f}%, prefilter = {pct_pre:.2f}%")
        print(f"Reduction = {reduction:.2f}%")
        # Validation du seuil
        if reduction > THRESHOLD:
            print(f"✅ Reduction exceeds {THRESHOLD:.1f}% threshold.")
        else:
            print(f"⚠️ Reduction below {THRESHOLD:.1f}% threshold.")

        # Annonce du gagnant
        if ops_pre < ops_lin:
            print("🏆 Winner: Prefilter scan (fewer heavy ops)")
        elif ops_pre > ops_lin:
            print("🏆 Winner: Linear scan (fewer heavy ops)")
        else:
            print("🤝 Tie: both methods used the same number of ops")

if __name__ == "__main__":
    main()