Re: Bitcoin puzzle transaction ~32 BTC prize to who solves it

Quote from: kTimesG on Today at 12:33:14 PM

1. The Scooby Doo method (the original version) boosts the success rate of the corresponding sequential order method just as good as the prefix method, without ever needing to check for any prefixes. In other words, if one would have to choose between a method that pretty much does nothing except increase the statistical variance, and the prefix method, he has a valid choice that works just as well.

Quote from: mcdouglasx on April 24, 2025, 07:20:00 PM

But let's compare my method with ktimesg (Scooby-Doo):

Code:

import hashlib
import random
import time

# Configuration
TOTAL_SIZE = 100_000
RANGE_SIZE = 5_000
PREFIX_LENGTH = 3
SIMULATIONS = 500
SECP256K1_ORDER = int("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141", 16)

print(f"""
=== Configuration ===
Total numbers: {TOTAL_SIZE:,}
Block size: {RANGE_SIZE:,}
Prefix: {PREFIX_LENGTH} characters (16^{PREFIX_LENGTH} combinations)
Simulations: {SIMULATIONS}
secp256k1 Order: {SECP256K1_ORDER}
""")

def generate_h160(data):
    h = hashlib.new('ripemd160', str(data).encode('utf-8'))
    return h.hexdigest()

def shuffled_range(n):
    arr = list(range(n + 1))
    random.shuffle(arr)
    return arr

def Scooby_Doo(dataset, block, target_hash, order):
    checks = 0
    ranges = []
    for idx in order:
        start = idx * block
        end = start + block
        marked = False
        for i in range(start, end):
            checks += 1
            h = generate_h160(dataset[i])
            if h == target_hash:
                return {"checks": checks, "found": True}
            if not marked and random.randint(0, 5000) == 0:  # ktimesg randomness
                marked = True
                ranges.append({"start": i + 1, "end": end})
                break
    for r in ranges:
        for i in range(r["end"] - 1, r["start"] - 1, -1):
            checks += 1
            if generate_h160(dataset[i]) == target_hash:
                return {"checks": checks, "found": True}
    return {"checks": checks, "found": False}

def prefixes_search(dataset, block, prefix, target_hash, order):
    prefix_hash = target_hash[:prefix]
    checks = 0
    ranges = []
    for idx in order:
        start = idx * block
        end = start + block
        found_prefix = False
        for i in range(start, end):
            checks += 1
            h = generate_h160(dataset[i])
            if h == target_hash:
                return {"checks": checks, "found": True}
            if not found_prefix and h.startswith(prefix_hash):
                found_prefix = True
                ranges.append({"start": i + 1, "end": end})
                break
    for r in ranges:
        for i in range(r["end"] - 1, r["start"] - 1, -1):
            checks += 1
            if generate_h160(dataset[i]) == target_hash:
                return {"checks": checks, "found": True}
    return {"checks": checks, "found": False}

def compare_methods():
    results = {
        "Scooby_Doo": {"wins": 0, "total_checks": 0, "total_time": 0},
        "prefixes": {"wins": 0, "total_checks": 0, "total_time": 0},
        "ties": 0
    }

    for i in range(SIMULATIONS):
        max_range = SECP256K1_ORDER - TOTAL_SIZE - 1
        random_offset = random.randrange(max_range)
        R = 1 + random_offset

        dataset = [R + i for i in range(TOTAL_SIZE)]
        target_num = random.choice(dataset)
        target_hash = generate_h160(target_num)
        blocks = TOTAL_SIZE // RANGE_SIZE
        order = shuffled_range(blocks - 1)

        start_time = time.perf_counter()
        seq_result = Scooby_Doo(dataset, RANGE_SIZE, target_hash, order)
        end_time = time.perf_counter()
        seq_time = end_time - start_time

        start_time = time.perf_counter()
        pre_result = prefixes_search(dataset, RANGE_SIZE, PREFIX_LENGTH, target_hash, order)
        end_time = time.perf_counter()
        pre_time = end_time - start_time

        results["Scooby_Doo"]["total_checks"] += seq_result["checks"]
        results["prefixes"]["total_checks"] += pre_result["checks"]
        results["Scooby_Doo"]["total_time"] += seq_time
        results["prefixes"]["total_time"] += pre_time

        if seq_result["checks"] < pre_result["checks"]:
            results["Scooby_Doo"]["wins"] += 1
        elif seq_result["checks"] > pre_result["checks"]:
            results["prefixes"]["wins"] += 1
        else:
            results["ties"] += 1

        print(f"Simulation {i + 1}: Scooby_Doo = {seq_result['checks']} checks in {seq_time:.6f}s | Prefix = {pre_result['checks']} checks in {pre_time:.6f}s")

    avg_success_rate_Scooby_Doo = (results["Scooby_Doo"]["total_checks"] / results["Scooby_Doo"]["wins"]
                                   if results["Scooby_Doo"]["wins"] > 0 else float('inf'))
    avg_success_rate_prefixes = (results["prefixes"]["total_checks"] / results["prefixes"]["wins"]
                                if results["prefixes"]["wins"] > 0 else float('inf'))
    avg_time_Scooby_Doo = (results["Scooby_Doo"]["total_time"] / results["Scooby_Doo"]["wins"]
                           if results["Scooby_Doo"]["wins"] > 0 else float('inf'))
    avg_time_prefixes = (results["prefixes"]["total_time"] / results["prefixes"]["wins"]
                        if results["prefixes"]["wins"] > 0 else float('inf'))

    print(f"""
=== FINAL RESULTS ===
Wins:
Scooby_Doo: {results['Scooby_Doo']['wins']}
Prefix: {results['prefixes']['wins']}
Ties: {results['ties']}

Total Checks:

Scooby_Doo: {results['Scooby_Doo']['total_checks']}
Prefix: {results['prefixes']['total_checks']}
Total Time:

Scooby_Doo: {results['Scooby_Doo']['total_time']:.6f} seconds
Prefix: {results['prefixes']['total_time']:.6f} seconds

Averages (Total Time / Wins):

Scooby_Doo : {avg_time_Scooby_Doo:.6f} seconds/victory
Prefix : {avg_time_prefixes:.6f} seconds/victory

Checks per Win:
Scooby_Doo : {avg_success_rate_Scooby_Doo:.2f} checks/win
Prefix : {avg_success_rate_prefixes:.2f} checks/win
""")

if __name__ == '__main__':
    compare_methods()

test 1

Code:

=== FINAL RESULTS ===
Wins:
Scooby_Doo: 228
Prefix: 260
Ties: 12

Total Checks:

Scooby_Doo: 24851576
Prefix: 25623847
Total Time:

Scooby_Doo: 342.907286 seconds
Prefix: 280.652503 seconds

Averages (Total Time / Wins):

Scooby_Doo : 1.503979 seconds/victory
Prefix : 1.079433 seconds/victory

Checks per Win:
Scooby_Doo : 108998.14 checks/win
Prefix : 98553.26 checks/win

test 2

Code:

=== FINAL RESULTS ===
Wins:
Scooby_Doo: 225
Prefix: 263
Ties: 12

Total Checks:

Scooby_Doo: 24624530
Prefix: 25240078
Total Time:

Scooby_Doo: 340.911049 seconds
Prefix: 278.872279 seconds

Averages (Total Time / Wins):

Scooby_Doo : 1.515160 seconds/victory
Prefix : 1.060351 seconds/victory

Checks per Win:
Scooby_Doo : 109442.36 checks/win
Prefix : 95969.88 checks/win

test 3

Code:

=== FINAL RESULTS ===
Wins:
Scooby_Doo: 229
Prefix: 265
Ties: 6

Total Checks:

Scooby_Doo: 24905305
Prefix: 24688332
Total Time:

Scooby_Doo: 348.265537 seconds
Prefix: 263.037687 seconds

Averages (Total Time / Wins):

Scooby_Doo : 1.520810 seconds/victory
Prefix : 0.992595 seconds/victory

Checks per Win:
Scooby_Doo : 108756.79 checks/win
Prefix : 93163.52 checks/win

test 4

Code:

=== FINAL RESULTS ===
Wins:
Scooby_Doo: 222
Prefix: 267
Ties: 11

Total Checks:

Scooby_Doo: 25225653
Prefix: 25081620
Total Time:

Scooby_Doo: 335.807665 seconds
Prefix: 260.804346 seconds

Averages (Total Time / Wins):

Scooby_Doo : 1.512647 seconds/victory
Prefix : 0.976795 seconds/victory

Checks per Win:
Scooby_Doo : 113629.07 checks/win
Prefix : 93938.65 checks/win

Quote from: kTimesG on Today at 12:33:14 PM

2. Are you OK? The Scooby Doo: The Mystery Returns! method proved that reverse sequential search is faster than the prefix method. In other words, if one would want to choose of finding a key faster, than the Scooby Doo: The Mystery Returns! method is the one that a sane person would choose.

3. In the same way, Scooby Doo: Origins method proved that a sequential search is faster than the Tweaked Prefix Method That Beats Scooby Doo 2. In other words, if one would want to find a key faster, and he can choose between these 2 methods, the one to choose would be Scooby Doo: Origins.

Quote from: mcdouglasx on April 26, 2025, 08:12:10 PM

I only modified the prefix function that @ktimesg intentionally miscompares. I'm certain that the only exact comparison method is for both to follow the same path... but he simply avoids doing so to deceive—a "fool hunter".

Code:

import hashlib
import random
import time

# Configuration
TOTAL_SIZE = 100_000
RANGE_SIZE = 5_000
PREFIX_LENGTH = 3
SIMULATIONS = 500
SECP256K1_ORDER = int("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141", 16)

# ENABLE REPRODUCIBLE TESTING
# Note: this line can be safely kept for a release build
random.seed(int.from_bytes(b'mcdouglasx'))

def ScoobyDoo_ReturnOfTheSequential(dataset, block, target_hash, order):
    checks = 0
    for k in reversed(dataset):
        checks += 1
        if generate_h160(k) == target_hash:
            return {"checks": checks, "found": True}

    raise Exception('OHNOES. Your Programming Language Is Rigged!')

def generate_h160(data):
    h = hashlib.new('ripemd160', str(data).encode('utf-8'))
    return h.hexdigest()

def shuffled_range(n):
    arr = list(range(n + 1))
    random.shuffle(arr)
    return arr

def prefixes_search(dataset, block, prefix, target_hash, order):
    prefix_hash = target_hash[:prefix]
    checks = 0
    skipped_indices = []
    skip_window = 4096
    skip_percentage = 0.3 
    
    i = len(dataset) - 1
    while i >= 0:
        checks += 1
        h = generate_h160(dataset[i])
        
        if h == target_hash:
            return {"checks": checks, "found": True}
        
        if h.startswith(prefix_hash):
            skip_count = int(skip_window * skip_percentage)
            
            for j in range(i-1, max(i-1 - skip_count, -1), -1):
                skipped_indices.append(j)
            
            i -= skip_count + 1  # +1 
        else:
            i -= 1
    
    for idx in sorted(skipped_indices, reverse=True):
        checks += 1
        if generate_h160(dataset[idx]) == target_hash:
            return {"checks": checks, "found": True}
    
    return {"checks": checks, "found": False}

def compare_methods():
    results = {
        "Scooby_Doo": {"wins": 0, "total_checks": 0, "total_time": 0},
        "prefixes": {"wins": 0, "total_checks": 0, "total_time": 0},
        "ties": 0
    }

    for i in range(SIMULATIONS):
        max_range = SECP256K1_ORDER - TOTAL_SIZE - 1
        random_offset = random.randrange(max_range)
        R = 1 + random_offset

        dataset = [R + i for i in range(TOTAL_SIZE)]
        target_num = random.choice(dataset)
        target_hash = generate_h160(target_num)
        blocks = TOTAL_SIZE // RANGE_SIZE
        order = shuffled_range(blocks - 1)

        start_time = time.perf_counter()
        seq_result = ScoobyDoo_ReturnOfTheSequential(dataset, RANGE_SIZE, target_hash, order)
        end_time = time.perf_counter()
        seq_time = end_time - start_time

        start_time = time.perf_counter()
        pre_result = prefixes_search(dataset, RANGE_SIZE, PREFIX_LENGTH, target_hash, order)
        end_time = time.perf_counter()
        pre_time = end_time - start_time

        results["Scooby_Doo"]["total_checks"] += seq_result["checks"]
        results["prefixes"]["total_checks"] += pre_result["checks"]
        results["Scooby_Doo"]["total_time"] += seq_time
        results["prefixes"]["total_time"] += pre_time

        if seq_result["checks"] < pre_result["checks"]:
            results["Scooby_Doo"]["wins"] += 1
        elif seq_result["checks"] > pre_result["checks"]:
            results["prefixes"]["wins"] += 1
        else:
            results["ties"] += 1

        print(f"Simulation {i + 1}: Scooby_Doo = {seq_result['checks']} checks in {seq_time:.6f}s | Prefix = {pre_result['checks']} checks in {pre_time:.6f}s")

    avg_success_rate_Scooby_Doo = (results["Scooby_Doo"]["total_checks"] / results["Scooby_Doo"]["wins"]
                                   if results["Scooby_Doo"]["wins"] > 0 else float('inf'))
    avg_success_rate_prefixes = (results["prefixes"]["total_checks"] / results["prefixes"]["wins"]
                                 if results["prefixes"]["wins"] > 0 else float('inf'))
    avg_time_Scooby_Doo = (results["Scooby_Doo"]["total_time"] / results["Scooby_Doo"]["wins"]
                           if results["Scooby_Doo"]["wins"] > 0 else float('inf'))
    avg_time_prefixes = (results["prefixes"]["total_time"] / results["prefixes"]["wins"]
                         if results["prefixes"]["wins"] > 0 else float('inf'))

    print(f"""
=== FINAL RESULTS ===
Wins:
Scooby_Doo: {results['Scooby_Doo']['wins']}
Prefix: {results['prefixes']['wins']}
Ties: {results['ties']}

Total Checks:

Scooby_Doo: {results['Scooby_Doo']['total_checks']}
Prefix: {results['prefixes']['total_checks']}
Total Time:

Scooby_Doo: {results['Scooby_Doo']['total_time']:.6f} seconds
Prefix: {results['prefixes']['total_time']:.6f} seconds

Averages (Total Time / Wins):

Scooby_Doo : {avg_time_Scooby_Doo:.6f} seconds/victory
Prefix : {avg_time_prefixes:.6f} seconds/victory

Checks per Win:
Scooby_Doo : {avg_success_rate_Scooby_Doo:.2f} checks/win
Prefix : {avg_success_rate_prefixes:.2f} checks/win
""")

print(f"""
=== Configuration ===
Total numbers: {TOTAL_SIZE:,}
Block size: {RANGE_SIZE:,}
Prefix: {PREFIX_LENGTH} characters (16^{PREFIX_LENGTH} combinations)
Simulations: {SIMULATIONS}
secp256k1 Order: {SECP256K1_ORDER}
""")

if __name__ == '__main__':
    compare_methods()

test

Code:

=== FINAL RESULTS ===
Wins:
Scooby_Doo: 106
Prefix: 371
Ties: 23

Total Checks:

Scooby_Doo: 24626075
Prefix: 24558252
Total Time:

Scooby_Doo: 295.013752 seconds
Prefix: 312.924599 seconds

Averages (Total Time / Wins):

Scooby_Doo : 2.783149 seconds/victory
Prefix : 0.843463 seconds/victory

Checks per Win:
Scooby_Doo : 232321.46 checks/win
Prefix : 66194.75 checks/win

Quote from: kTimesG on Today at 12:33:14 PM

2. Are you OK?

At first, I doubted it too, just like you. But after seeing the evidence, I think you haven’t really read the whole thread. Anyway, this ain’t my fight, so I’ll respect your take.