Bitcoin puzzle transaction ~32 BTC prize to who solves it

[JackMazzoni]

What puzzle number would be solved first puzzle 135 or puzzle 69? I bet for puzzle 135 to be solve first.

[Denevron]

Guys, let's solve puzzles not using a GPU, but using a python script and a couple of CPU processors in 15 minutes.

How do you imagine this?)

[kTimesG]

It is faster to solve 135 rather than 69, no matter if you use a CPU, a GPU, or a toaster. I think you missed the entire point. So your claim ("the chances are better with 1 GPU/CPU to scan for p69 than p135") has nothing to do with reality, as it contradicts a basic mathematical comparison of two terms.

If you have very limited computing power, isn't it better to try your long shot on 69 than on 135 due to the non linear nature of the odds of collision ?

I can ask the same question: if you have very limited computing power, isn't it better to try your long shot on 135 (and a lot higher throughput) than on 69 due to not knowing if you're gonna find the key at attempt #1 or at an attempt #2**68?

If you compare them both at their respective points of 50% probability that tends towards success, 135 will finish sooner.

[nomachine]

Guys, let's solve puzzles not using a GPU, but using a python script and a couple of CPU processors in 15 minutes.

How do you imagine this?)

The only acceleration would occur if you wrote the .so extensions for ripemd160_avx2 and sha256_avx2 and used them for hashing in Python. And everything else related to EC. However, the CPU can't handle more than 8M keys per core—that's the maximum I've achieved in C++. Dead end.

[POD5]

Thanks... 

Code:

g++ -shared -fPIC -mavx2 -O3 ripemd160_avx2.cpp -o libripemd160_avx2.so
g++ -shared -fPIC -mavx2 -O3 sha256_avx2.cpp -o libsha256_avx2.so
g++ -shared -fPIC -O3 SECP256K1.cpp Random.cpp -o libsecp256k1.so

[Bram24732]

It is faster to solve 135 rather than 69, no matter if you use a CPU, a GPU, or a toaster. I think you missed the entire point. So your claim ("the chances are better with 1 GPU/CPU to scan for p69 than p135") has nothing to do with reality, as it contradicts a basic mathematical comparison of two terms.

If you have very limited computing power, isn't it better to try your long shot on 69 than on 135 due to the non linear nature of the odds of collision ?

I can ask the same question: if you have very limited computing power, isn't it better to try your long shot on 135 (and a lot higher throughput) than on 69 due to not knowing if you're gonna find the key at attempt #1 or at an attempt #2**68?

If you compare them both at their respective points of 50% probability that tends towards success, 135 will finish sooner.

The difference is that your odds of success in 1yr of bruting 69 are better than in 1yr of bruteforcing 135 because the work done does not compound the same way. That’s what I meant

[nomachine]

Thanks...  

Code:

g++ -shared -fPIC -O3 SECP256K1.cpp Random.cpp -o libsecp256k1.so

I think it has to be all together.

Code:

g++ -shared -fPIC -O3 SECP256K1.cpp Int.cpp Timer.cpp IntGroup.cpp IntMod.cpp Point.cpp Random.cpp -o libsecp256k1.so

[Denevron]

Guys, let's solve puzzles not using a GPU, but using a python script and a couple of CPU processors in 15 minutes.

How do you imagine this?)

The only acceleration would occur if you wrote the .so extensions for ripemd160_avx2 and sha256_avx2 and used them for hashing in Python. And everything else related to EC. However, the CPU can't handle more than 8M keys per core—that's the maximum I've achieved in C++. Dead end.

By the way, your version of mutagen (which you updated not so long ago) has become faster to check, before 300 billion took 12 hours, and now 8 hours. Cut another 6 hours and it will be like in Cyclone 


and also, in mutag there are slightly fewer combinations that need to be changed (the first bit does not need to be changed in the key if it is in position "1")

[Akito S. M. Hosana]

Thanks...  

Code:

g++ -shared -fPIC -O3 SECP256K1.cpp Random.cpp -o libsecp256k1.so

I think it has to be all together.

Code:

g++ -shared -fPIC -O3 SECP256K1.cpp Int.cpp Timer.cpp IntGroup.cpp IntMod.cpp Point.cpp Random.cpp -o libsecp256k1.so

It will be something similar to Iceland. The hardest part is to write a .py file that calls functions from a .so (shared object) file in Python with the ctypes module CFFI/Cython   

[kTimesG]

It is faster to solve 135 rather than 69, no matter if you use a CPU, a GPU, or a toaster. I think you missed the entire point. So your claim ("the chances are better with 1 GPU/CPU to scan for p69 than p135") has nothing to do with reality, as it contradicts a basic mathematical comparison of two terms.

If you have very limited computing power, isn't it better to try your long shot on 69 than on 135 due to the non linear nature of the odds of collision ?

I can ask the same question: if you have very limited computing power, isn't it better to try your long shot on 135 (and a lot higher throughput) than on 69 due to not knowing if you're gonna find the key at attempt #1 or at an attempt #2**68?

If you compare them both at their respective points of 50% probability that tends towards success, 135 will finish sooner.

The difference is that your odds of success in 1yr of bruting 69 are better than in 1yr of bruteforcing 135 because the work done does not compound the same way. That’s what I meant

Yes, you are correct that it does not compound in the same way.

For 135, it grows asymptotically to 100% without ever reaching it.

For 69, it's a straight line from 0 to 100%.

Guess which one reaches 50% faster?

[Niekko]

But how do you implicate Elon Musk in anything? for now he's in a big hole where he's lost billions.

ELON? [gigachad pose] HE HAS A GPU MOUNTAIN!!!

Elon is the creator  

[nomachine]

By the way, your version of mutagen (which you updated not so long ago) has become faster to check, before 300 billion took 12 hours, and now 8 hours. Cut another 6 hours and it will be like in Cyclone  

Code:

        for (int pos : flips) {
            Int mask;
            mask.SetInt32(1);
            mask.ShiftL(pos);
            currentKey.Xor(&mask);
        }

Yes, this is the maximum. Only if you program XOR to work in assembly might it be faster. The same applies to the combination generator - they are a bottleneck  


https://github.com/NoMachine1/Mutagen/commit/ffcddcbcdbf2c4bba12b0439d61a403a08f22d3b

[Bram24732]

It is faster to solve 135 rather than 69, no matter if you use a CPU, a GPU, or a toaster. I think you missed the entire point. So your claim ("the chances are better with 1 GPU/CPU to scan for p69 than p135") has nothing to do with reality, as it contradicts a basic mathematical comparison of two terms.

If you have very limited computing power, isn't it better to try your long shot on 69 than on 135 due to the non linear nature of the odds of collision ?

I can ask the same question: if you have very limited computing power, isn't it better to try your long shot on 135 (and a lot higher throughput) than on 69 due to not knowing if you're gonna find the key at attempt #1 or at an attempt #2**68?

If you compare them both at their respective points of 50% probability that tends towards success, 135 will finish sooner.

The difference is that your odds of success in 1yr of bruting 69 are better than in 1yr of bruteforcing 135 because the work done does not compound the same way. That’s what I meant

Yes, you are correct that it does not compound in the same way.

For 135, it grows asymptotically to 100% without ever reaching it.

For 69, it's a straight line from 0 to 100%.

Guess which one reaches 50% faster?

Depends on K and your DP rate, but my point was that with limited resources you never go beyond 1% on 135 so you’re before the curve inflexion point and you can’t piggy back on a pool progress. That’s why I would recommend 69

[Akito S. M. Hosana]

By the way, your version of mutagen (which you updated not so long ago) has become faster to check, before 300 billion took 12 hours, and now 8 hours. Cut another 6 hours and it will be like in Cyclone  

Code:

        for (int pos : flips) {
            Int mask;
            mask.SetInt32(1);
            mask.ShiftL(pos);
            currentKey.Xor(&mask);
        }

Yes, this is the maximum. Only if you program XOR to work in assembly might it be faster. The same applies to the combination generator - they are a bottleneck  


https://github.com/NoMachine1/Mutagen/commit/ffcddcbcdbf2c4bba12b0439d61a403a08f22d3b

=======================================
=========== SOLUTION FOUND ============
=======================================
Private key: 0x1A96CA8D8
Checked 714563971 combinations
Bit flips: 15
Time: 50.04 seconds (00:00:50)
Speed: 42.27 Mkeys/s
Solution saved to puzzle_33_solution.txt


Why don't you program the whole script like this? Is it too hard? 

[nomachine]

Why don't you program the whole script like this? Is it too hard? 

With what ultimate goal? To solve already-solved puzzles even faster? Pointless. 

[kTimesG]

Depends on K and your DP rate, but my point was that with limited resources you never go beyond 1% on 135 so you’re before the curve inflexion point and you can’t piggy back on a pool progress. That’s why I would recommend 69

I think the least of worries of anyone who intends to use a single device to break either of those puzzles is whether their success rate hangs under the inflexion point or above it

But why is that point even important? I'd think the point of intersection between the two methods is what matters. The different speeds also play a role on how fast you get to where. So it's more complicated.

[mitkopasa]

Could you please convert the following Python code to C++ using the libraries in Mutagen? In this code, I am creating a 69-bit binary, but 32 to 35 of them are 1's and 1's can come in a row at most 6 times.  This python speed is very low. I think i can search faster with sha256_avx2 and ripemd160_avx2. However, I don't know C++ and I couldn't figure out how to integrate the codes in the mutagen.

Code:

import random
import numpy as np
import time
import os
import multiprocessing
from multiprocessing import Pool
import secp256k1 as ice
from random import sample


r = 0
cores=1

def generate_random_bits(n, k):
    while True:
        # Initially all digits are 0
        bits = ['0'] * n
        # Generate random 1
        positions = random.sample(range(n), k)
        for pos in positions:
            bits[pos] = '1'
        
        # How many 1's can in a row?
        if is_valid_combination(bits,max_consecutive_ones):
            return ''.join(bits)

def is_valid_combination(bits,max_consecutive_ones):
    count = 0
    for bit in bits:
        if bit == '1':
            count += 1
            if count > max_consecutive_ones:  # limit for consecutive ones
                return False
        else:
            count = 0
    return True

def priv_key(n, k):
    while True:
        random_bits = generate_random_bits(n, k)
        decimal_representation = int(random_bits, 2)
        if 2**(n-1) < decimal_representation < 2**n:
           return decimal_representation

# Parameters
n = 69  # Puzzle number
max_consecutive_ones = 6  # limit for consecutive ones

def seek(r):
    global num_threads
    LOG_EVERY_N = 100000
    start_time = time.time()
    i = 0
    print("Core " + str(r) +":  Searching Private Key..")
    db = '61eb8a50c86b0584bb727dd65bed8d2400d6d5aa' 
    while True:
        i=i+1
        k = random.randrange(32, 35) # How many 1's are there?
        private_key = priv_key(n,k)
        #print(private_key)
		#public_key = privtopub(private_key)       
        addr = ice.privatekey_to_h160(0, True, private_key).hex()
        time_diff = time.time() - start_time
        if (i % LOG_EVERY_N) == 0:
            print('Itaration :'+str(i)+" K/s = "+ str(i / time_diff))

        if addr in db:
            f = open('KEYFOUND_KEYFOUND_KEYFOUND.txt','a')
            print ('------------------------------------------------------------------------- ')
            print ('!!! ---- KEYFOUND KEYFOUND KEYFOUND!!! ---- ' )
            print('Key: ', hex(private_key)[2:] )
            print('Adress: ', addr )
            f.write(hex(private_key)[2:])
            f.write('     ')
            f.write(addr)
            f.write('\n')
            f.close()
            time.sleep(10)
            print ('------------------------------------------------------------------------- ')


if __name__ == '__main__':
	jobs = []
	for r in range(cores):
		p = multiprocessing.Process(target=seek, args=(r,))
		jobs.append(p)
		p.start()  

[Bram24732]

Depends on K and your DP rate, but my point was that with limited resources you never go beyond 1% on 135 so you’re before the curve inflexion point and you can’t piggy back on a pool progress. That’s why I would recommend 69

I think the least of worries of anyone who intends to use a single device to break either of those puzzles is whether their success rate hangs under the inflexion point or above it

But why is that point even important? I'd think the point of intersection between the two methods is what matters. The different speeds also play a role on how fast you get to where. So it's more complicated.

Oh I agree it’s just a fun math exercise to check at which point one becomes more profitable than the other.

[nomachine]

Could you please convert the following Python code to C++ using the libraries in Mutagen? In this code, I am creating a 69-bit binary, but 32 to 35 of them are 1's and 1's can come in a row at most 6 times.  This python speed is very low. I think i can search faster with sha256_avx2 and ripemd160_avx2. However, I don't know C++ and I couldn't figure out how to integrate the codes in the mutagen.

Replace the code in the mutagen to be like this

Code:

#include <random>

thread_local std::mt19937_64 rng(std::random_device{}());

void RandomXor(Int* currentKey, int bit_length, int flip_count) {
    alignas(32) uint64_t flipMasks[4] = {0};

    // Generate random positions and set bits in batches
    for (int i = 0; i < flip_count; ) {
        // Generate 4 random positions at once
        uint64_t rand_positions[4];
        for (int j = 0; j < 4 && i < flip_count; j++, i++) {
            rand_positions[j] = rng() % bit_length;
            int word = rand_positions[j] / 64;
            int bit = rand_positions[j] % 64;
            flipMasks[word] ^= (1ULL << bit);
        }
    }

    // Apply XOR in one AVX2 operation
    __m256i keyVec = _mm256_loadu_si256((__m256i*)currentKey->bits64);
    __m256i maskVec = _mm256_loadu_si256((__m256i*)flipMasks);
    __m256i result = _mm256_xor_si256(keyVec, maskVec);
    _mm256_storeu_si256((__m256i*)currentKey->bits64, result);

    // Clear masks to zero for next iteration
    memset(flipMasks, 0, sizeof(flipMasks));
}

void worker(Secp256K1* secp, int bit_length, int flip_count, int threadId, AVXCounter start, AVXCounter end) {
    const int fullBatchSize = 2 * POINTS_BATCH_SIZE;
    alignas(32) uint8_t localPubKeys[HASH_BATCH_SIZE][33];
    alignas(32) uint8_t localHashResults[HASH_BATCH_SIZE][20];
    alignas(32) int pointIndices[HASH_BATCH_SIZE];

    __m256i target16 = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(TARGET_HASH160_RAW.data()));

    alignas(32) Point plusPoints[POINTS_BATCH_SIZE];
    alignas(32) Point minusPoints[POINTS_BATCH_SIZE];

    for (int i = 0; i < POINTS_BATCH_SIZE; i++) {
        Int tmp;
        tmp.SetInt32(i);
        plusPoints[i] = secp->ComputePublicKey(&tmp);
        minusPoints[i] = plusPoints[i];
        minusPoints[i].y.ModNeg();
    }

    alignas(32) Int deltaX[POINTS_BATCH_SIZE];
    IntGroup modGroup(POINTS_BATCH_SIZE);
    alignas(32) Int pointBatchX[fullBatchSize];
    alignas(32) Int pointBatchY[fullBatchSize];

    CombinationGenerator gen(bit_length, flip_count);
    gen.unrank(start.load());

    AVXCounter count;
    count.store(start.load());

    uint64_t actual_work_done = 0;
    auto last_report = chrono::high_resolution_clock::now();

    while (!stop_event.load() && count < end) {
    Int currentKey;
    currentKey.Set(&BASE_KEY);
    
    RandomXor(&currentKey, bit_length, flip_count);

    string keyStr = currentKey.GetBase16();
    keyStr = string(64 - keyStr.length(), '0') + keyStr;

     #pragma omp critical
    {
        g_threadPrivateKeys[threadId] = keyStr;
    }

No other random implementation will work properly (beyond Puzzle 64); it must be either 128-bit or 256-bit.

[Akito S. M. Hosana]

Could you please convert the following Python code to C++ using the libraries in Mutagen? In this code, I am creating a 69-bit binary, but 32 to 35 of them are 1's and 1's can come in a row at most 6 times.  This python speed is very low. I think i can search faster with sha256_avx2 and ripemd160_avx2. However, I don't know C++ and I couldn't figure out how to integrate the codes in the mutagen.

Replace the code in the mutagen to be like this

Code:

#include <random>

thread_local std::mt19937_64 rng(std::random_device{}());

void RandomXor(Int* currentKey, int bit_length, int flip_count) {
    alignas(32) uint64_t flipMasks[4] = {0};

    // Generate random positions and set bits in batches
    for (int i = 0; i < flip_count; ) {
        // Generate 4 random positions at once
        uint64_t rand_positions[4];
        for (int j = 0; j < 4 && i < flip_count; j++, i++) {
            rand_positions[j] = rng() % bit_length;
            int word = rand_positions[j] / 64;
            int bit = rand_positions[j] % 64;
            flipMasks[word] ^= (1ULL << bit);
        }
    }

    // Apply XOR in one AVX2 operation
    __m256i keyVec = _mm256_loadu_si256((__m256i*)currentKey->bits64);
    __m256i maskVec = _mm256_loadu_si256((__m256i*)flipMasks);
    __m256i result = _mm256_xor_si256(keyVec, maskVec);
    _mm256_storeu_si256((__m256i*)currentKey->bits64, result);

    // Clear masks to zero for next iteration
    memset(flipMasks, 0, sizeof(flipMasks));
}

void worker(Secp256K1* secp, int bit_length, int flip_count, int threadId, AVXCounter start, AVXCounter end) {
    const int fullBatchSize = 2 * POINTS_BATCH_SIZE;
    alignas(32) uint8_t localPubKeys[HASH_BATCH_SIZE][33];
    alignas(32) uint8_t localHashResults[HASH_BATCH_SIZE][20];
    alignas(32) int pointIndices[HASH_BATCH_SIZE];

    __m256i target16 = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(TARGET_HASH160_RAW.data()));

    alignas(32) Point plusPoints[POINTS_BATCH_SIZE];
    alignas(32) Point minusPoints[POINTS_BATCH_SIZE];

    for (int i = 0; i < POINTS_BATCH_SIZE; i++) {
        Int tmp;
        tmp.SetInt32(i);
        plusPoints[i] = secp->ComputePublicKey(&tmp);
        minusPoints[i] = plusPoints[i];
        minusPoints[i].y.ModNeg();
    }

    alignas(32) Int deltaX[POINTS_BATCH_SIZE];
    IntGroup modGroup(POINTS_BATCH_SIZE);
    alignas(32) Int pointBatchX[fullBatchSize];
    alignas(32) Int pointBatchY[fullBatchSize];

    CombinationGenerator gen(bit_length, flip_count);
    gen.unrank(start.load());

    AVXCounter count;
    count.store(start.load());

    uint64_t actual_work_done = 0;
    auto last_report = chrono::high_resolution_clock::now();

    while (!stop_event.load() && count < end) {
    Int currentKey;
    currentKey.Set(&BASE_KEY);
    
    RandomXor(&currentKey, bit_length, flip_count);

    string keyStr = currentKey.GetBase16();
    keyStr = string(64 - keyStr.length(), '0') + keyStr;

     #pragma omp critical
    {
        g_threadPrivateKeys[threadId] = keyStr;
    }

No other random implementation will work properly (beyond Puzzle 64); it must be either 128-bit or 256-bit.

=======================================
=========== SOLUTION FOUND ============
=======================================
Private key: 0x1A96CA8D8
Checked 10920739 combinations
Bit flips: 15
Time: 2.86 seconds (00:00:02)
Speed: 31.35 Mkeys/s
Solution saved to puzzle_33_solution.txt

Solved puzzle 33 in 2 seconds with this random code.