Quote from: kTimesG on Today at 08:15:22 AM

Quote from: Virtuose on Today at 07:15:59 AM

Here a direct proof on puzzle 17:

Code:

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

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

You have an error in your script. You do H160 and continue before you increment ops. So the heavy op is not accounted always.

Also - if the key isn't found, the method simply fails.

I also believe that the actual HEAVY operation that actually ever matters is having a public key of the private key - because that is the actual step where you go from the scalar domain into the discrete log injective-only domain.

Yeah, i'm tired right now and made some errors.

Here's a fix with multiprocessors:

Code:

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

Parallel linear scan vs c-bit prefilter on puzzle 21.
Use all CPUs by default; adjust --workers if you want this.
"""

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

# --- Configuration ---
ADDRESS_TARGET = "14oFNXucftsHiUMY8uctg6N487riuyXs4h"
HASH160_TARGET = "29a78213caa9eea824acf08022ab9dfc83414f56" # Skip b58decode (filter boost)
RANGE_HEX      = "100000:1fffff"
FILTER_BITS    = 2     # c ≥ 1 ⇒ >5% reduction
THRESHOLD      = 5.0   # percent
# ---------------------

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

# Base58Check decode (only used if HASH160_TARGET is None)
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

# Serialize scalar x to compressed SEC-format pubkey
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)

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

# Derive full P2PKH address for display
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

# Extract top-c bits from target hash160 (uses HASH160_TARGET if provided)
def get_filter_target(c: int) -> int:
    if HASH160_TARGET:
        raw = bytes.fromhex(HASH160_TARGET)
    else:
        payload = b58decode(ADDRESS_TARGET)
        raw = payload[1:]
    val = int.from_bytes(raw, 'big')
    return val >> (160 - c)

# Extract top-c bits from candidate hash160
def get_filter_candidate(x: int, c: int) -> int:
    h2  = hash160_pubkey(x)
    val = int.from_bytes(h2, 'big')
    return val >> (160 - c)

# Worker for linear scan chunk
def linear_chunk(args):
    idx, start, end = args
    for i, x in enumerate(range(start, end+1), start=1):
        if derive_address(x) == ADDRESS_TARGET:
            return idx, i, x
    return idx, None, None

# Worker for prefilter scan chunk
def prefilter_chunk(args):
    idx, start, end, c, t1 = args
    for i, x in enumerate(range(start, end+1), start=1):
        if get_filter_candidate(x, c) != t1:
            continue
        if derive_address(x) == ADDRESS_TARGET:
            return idx, i, x
    return idx, None, None

# Parallel linear scan
def parallel_linear(start: int, end: int, workers: int):
    N = end - start + 1
    chunk = math.ceil(N / workers)
    args = [(i, start + i*chunk, min(start + (i+1)*chunk - 1, end)) for i in range(workers)]
    with Pool(workers) as p:
        results = p.map(linear_chunk, args)
    for idx, ops, x in sorted(results, key=lambda r: r[0]):
        if ops:
            global_ops = idx * chunk + ops
            return x, global_ops
    return None, 0

# Parallel prefilter scan
def parallel_prefilter(start: int, end: int, c: int, workers: int):
    N = end - start + 1
    chunk = math.ceil(N / workers)
    t1 = get_filter_target(c)
    args = [(i, start + i*chunk, min(start + (i+1)*chunk - 1, end), c, t1) for i in range(workers)]
    with Pool(workers) as p:
        results = p.map(prefilter_chunk, args)
    for idx, ops, x in sorted(results, key=lambda r: r[0]):
        if ops:
            return x, ops
    return None, 0

# Main entry
def main():
    import argparse
    parser = argparse.ArgumentParser()
    parser.add_argument("--workers", type=int, default=0,
                        help="number of processes (default = CPU count)")
    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)
    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: {FILTER_BITS}, Processes: {workers}\n")

    # Linear scan
    print("→ Parallel linear scan…")
    x_lin, ops_lin = parallel_linear(start, end, workers)
    print(f"  ✅ Found x = 0x{x_lin:x} in {ops_lin} ops")

    # Prefilter scan
    print("\n→ Parallel prefilter scan…")
    x_pre, ops_pre = parallel_prefilter(start, end, FILTER_BITS, workers)
    print(f"  ✅ Found x = 0x{x_pre:x} in {ops_pre} heavy ops")

    # 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"\nPercent heavy 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 "Linear"
    print("🏆 Winner: " + winner + " scan")

if __name__ == "__main__":
    main()

(venv) root:~# python3 proof.py
Target address: 14oFNXucftsHiUMY8uctg6N487riuyXs4h
Range: 0x100000 .. 0x1fffff (N = 1048576)
Filter bits: 2, Processes: 4

→ Parallel linear scan…
✅ Found x = 0x1ba534 in 763189 ops

→ Parallel prefilter scan…
✅ Found x = 0x1ba534 in 238901 heavy ops

Percent heavy checks: linear = 100.00%, prefilter = 31.30%
Reduction = 68.70%
✅ Reduction exceeds 5.0%
🏆 Winner: Prefilter scan

My C-bit prefilter is a winner, my friend.
Convinced? ⇒ bc1qvmw6hxf7fhatxstf7vg53cd3n2a4jfa8at9wa6