Bitcoin puzzle transaction ~32 BTC prize to who solves it

[kTimesG]

The goal here is to guess private keys that are already in use. The rule is that there are no rules about what you should use as a random generator.

RTX 4090 is capable of doing 7.0 - 7.1 GK/s to scan a given range, not 4 or 5. Yes, just the keys in a given interval, not the ones with symmetry or endo (in that case, it can surpass 10 GK/s).

What do you guys even use as a random generator if the speed needs to be 10 GK/s?

Zero PRNG. The keys are in sequence, the only difference between hashing keys at random positions, and keys that are in sequence, is that it's much faster to do them in sequence. And there is no risk to hash the same keys twice, because the birthday paradox cannot occur.

Take a sequence of 2**N keys. You need to have a large N.
Split it evenly by number of threads (let's say, for CUDA, we have 16384 blocks * 256 threads each, and each thread does 2048 point additions at every launch).
Compute the first starting key and delta key (that's only two EC point multiplications).
Compute starting keys for all threads, evenly (that's 16384 * 256 EC group additions - very fast).
Run kernel a required amount of times, to scan full range (it only does EC group additions, and hashing of each key).
For symmetry/endo: also compute hashes of X*beta, X*beta2, combined with -Y. No EC math involved. Also, Y does not even need to be computed at all (except once, for the delta jump) - just check both parities for compressed pubKey!

So: only two point multiplications, and a shitload of group additions. This is how one gets to 10 GK/s using just 450 watts.

[tmar777]

The goal here is to guess private keys that are already in use. The rule is that there are no rules about what you should use as a random generator.

RTX 4090 is capable of doing 7.0 - 7.1 GK/s to scan a given range, not 4 or 5. Yes, just the keys in a given interval, not the ones with symmetry or endo (in that case, it can surpass 10 GK/s).

What do you guys even use as a random generator if the speed needs to be 10 GK/s?

Zero PRNG. The keys are in sequence, the only difference between hashing keys at random positions, and keys that are in sequence, is that it's much faster to do them in sequence. And there is no risk to hash the same keys twice, because the birthday paradox cannot occur.

Take a sequence of 2**N keys. You need to have a large N.
Split it evenly by number of threads (let's say, for CUDA, we have 16384 blocks * 256 threads each, and each thread does 2048 point additions at every launch).
Compute the first starting key and delta key (that's only two EC point multiplications).
Compute starting keys for all threads, evenly (that's 16384 * 256 EC group additions - very fast).
Run kernel a required amount of times, to scan full range (it only does EC group additions, and hashing of each key).
For symmetry/endo: also compute hashes of X*beta, X*beta2, combined with -Y. No EC math involved. Also, Y does not even need to be computed at all (except once, for the delta jump) - just check both parities for compressed pubKey!

So: only two point multiplications, and a shitload of group additions. This is how one gets to 10 GK/s using just 450 watts.

Very clever approach! Is this code somewhere available?
I am not an experienced programmer.
Thanks

[nomachine]

10 GB/s refers to the throughput or the rate at which the PRNG can produce random data.
A Bitcoin private key is a 256-bit (32-byte) number. This is the size of the data required to generate one Bitcoin key.

You would need a PRNG or hardware setup that can generate random data at 320 GB/s to achieve 10 GK/s.

P.S. Xoshiro256plus could achieve the required throughput of 320 GB/s with 128 cores.

Do you consider generating an address to be the same as generating a random number? What about the other parts? Hashing, Elliptic curve ,...?

In the code, the Xoshiro256plus PRNG is used to generate random numbers, but it is adjusted to ensure they fall within the valid range using modulo arithmetic.

I tested this with 128 CPU cores. The speed is approximately 936 Mkeys/s with hashing to HASH160.

Without hashing, just capturing the public key, the speed is around 1380 Mkeys/s.

Now, imagine adapting this to the GPU and using AVX2—combining both CPU and GPU power.

An RTX 3060 achieves around 2300 Mkeys/s, and so on.

But yeah, all this is a waste of time on any single GPU. Without 2000 GPUs, none of this can be solved. So, I'm going fishing....

[nomachine]

Honestly, you'll get rich faster selling fish than trying to find the key without some new software created by a genius. 

I wish I were a genius. But I'm not. Maybe someone else here is.   

[kTimesG]

Now, imagine adapting this to the GPU and using AVX2—combining both CPU and GPU power.

An RTX 3060 achieves around 2300 Mkeys/s, and so on.

You are making a wrong assumption here: that you can simply combine GPU output with CPU calculations, or something. The calculations performed by a GPU are internal to the device (no memory transfers between host and device).

If we remove hashing step from the CUDA code, then the speed is like a few times higher. For example, around 25 GK/s just to produce public keys of a sequential range. Even more if we add the sym/endo (but these are derived from a single public key anyway, there is no point doing it on a GPU).

But in in no way you could ever transfer the huge amounts of results back to the CPU world, in order to hash it. You are limited by the memory clock of the GPU, the total memory of the GPU, and the bus width of the PCIe lanes. So the end result is a very lousy speed, grabbing all the actual results a GPU can produce is something that is totally unmanageable by a CPU, no matter how many cores you have.

Or did I understand something wrong?

[Akito S. M. Hosana]

Wait a minute. If he just said that the 3060 achieves around 2300 Mkeys/s, how much does the 4090 achieve? Does it reach 8000 Mkeys/s on the RTX 4090? 8 GK/s ?  In Cyclone GPU ?

Why won't anyone share the fastest GPU code here? Are you hiding the best code for yourselves?  It's all just empty talk and blah blah blah..

[kruk01]

Did anyone check speed of RTX 4070 on KeyHunt??

[Denevron]

Wait a minute. If he just said that the 3060 achieves around 2300 Mkeys/s, how much does the 4090 achieve? Does it reach 8000 Mkeys/s on the RTX 4090? 8 GK/s ?  In Cyclone GPU ?

Why won't anyone share the fastest GPU code here? Are you hiding the best code for yourselves?  It's all just empty talk and blah blah blah..

Because no one is obliged to put their work in the public domain for everyone to see. They spend their time and energy on it.

[Akito S. M. Hosana]

The x-coordinate for puzzle 135 is 76 digits and the y-coordinate is 77 digits?
This may help with searching a sub-range of keys. My terminal process killed running 1E32 but I only have 4GB of RAM.
Try 1E21 and be sure to check the length of the x_values on output they range from 75-77.
Good Luck!

Why are you even saving it to a file? You can do the matching right away.
  

Code:

from ecdsa import SigningKey, SECP256k1
import ecdsa

# Define Puzzle #135 coordinates
x_given = 9210836494447108270027136741376870869791784014198948301625976867708124077590
y_given = 69440582532487379038177105219556131878098716909078780397935812212458092996863

# Define the target x-coordinate to match exactly
target_x = x_given  # You can set this to any specific value

# Define private key search range
k_lower = 21778071482940061661655974875633165533184  # + 10**26 
k_upper = 43556142965880123323311949751266331066367  # - 10**26

def private_key_to_public_xy(private_key):
    """Computes the x and y coordinates of the public key from a given private key."""
    sk = SigningKey.from_secret_exponent(private_key, curve=SECP256k1)
    vk = sk.verifying_key
    # Extract x and y coordinates
    x_coord = int.from_bytes(vk.to_string()[:32], 'big')  # First 32 bytes are x
    y_coord = int.from_bytes(vk.to_string()[32:], 'big')  # Next 32 bytes are y
    return x_coord, y_coord

# Reduce step size to scan more precisely
step_size = int(1e35)  # Smaller step size for finer detail

print("Scanning for private keys that generate x and y values close to the given coordinates...")

for k in range(k_lower, k_upper, step_size):
    x_value, y_value = private_key_to_public_xy(k)
   
    # Check if x_value matches the target_x exactly
    if x_value == target_x:
        print(f"Exact match found! Private Key = {k}, x = {x_value}, y = {y_value}")
        break  # Stop searching after finding the exact match 

You will quickly realize that this is useless. Without a kangaroo, you have no chance of finding a match.

[dastic]

Code:

--- Final Best Candidate ---
Private Key: 27465881482940061352098229436045164806144 (hex: 00000000000000000000000000000050b7085c1533b415567000000000000000)
x-coordinate: 9210790008149297258455471224225729038493158517165492613256687428790137027105 (hex: 145d1f5582595ead4268d635071da2f683076ec96fee811b878a424f599e7a21)
Difference: 46486297811011571665517151141831298625497033455688369289438917987050485

Still pretty useless

[VinIVaderr]

Saving it to file is an extra method and you're right it's not useful.
Others are posting code and I wanted to get feedback.
Searching in steps in this large key space is also not useful.

What do you think is the set it and forget it best method?
I think it's four terminal windows(0x4, 0x5, 0x6, 0x7).

[nomachine]

What do you think is the set it and forget it best method?

To reverse engineer a random seed when the creator designed the puzzle at that specific moment, as far as I know, zahid888 made the most progress in that area. I gave up after puzzle 60 while searching for the seed.   

[Akito S. M. Hosana]

To reverse engineer a random seed when the creator designed the puzzle at that specific moment

How ? 

[nomachine]

How ?  

I think I have about 20 scripts in my archive that attempt this.

For example, Puzzle 67:

Code:

import random
from datetime import datetime, timedelta

# Specify the start and end date and times
start_datetime_pre = datetime(2015, 1, 1, 0, 0, 0)
end_datetime_pre = datetime(2015, 1, 15, 19, 7, 14)

# Define the range of numbers
min_number = 73786976294838206463
max_number = 147573952589676412927

# Specify the target number
target_number = 132656943602386256302

# Specify the target pattern
target_pattern = '13265694'

current_datetime = start_datetime_pre
time_step = timedelta(microseconds=100)  # Use microseconds for higher precision

while current_datetime <= end_datetime_pre:
    # Calculate the time range in seconds with higher precision
    time_range_seconds = 1.0

    # Initialize binary search boundaries with floating-point precision
    low_timestamp = current_datetime.timestamp()
    high_timestamp = (current_datetime + timedelta(seconds=time_range_seconds)).timestamp()
    found_datetime = None  # Initialize found_datetime

    while low_timestamp <= high_timestamp:
        # Calculate the middle timestamp with floating-point precision
        mid_timestamp = (low_timestamp + high_timestamp) / 2.0

        # Use the middle timestamp as the seed to generate a number
        random.seed(mid_timestamp)
        generated_number = random.randint(min_number, max_number)

        # Check if the generated number starts with the specified pattern
        if str(generated_number).startswith(target_pattern):
            found_datetime = datetime.fromtimestamp(mid_timestamp)
            break  # Break out of the inner loop when a match is found

        # Use the target_number to guide the binary search
        if generated_number < target_number:
            low_timestamp = mid_timestamp + 0.000001  # Increment by microseconds
        else:
            high_timestamp = mid_timestamp - 0.000001  # Decrement by microseconds

    if found_datetime is not None:
        print("Pattern Found:", generated_number, "Found Timestamp:", found_datetime.strftime('%Y-%m-%d %H:%M:%S.%f'))

    # Increment the current datetime by a smaller time step for the next timestamp
    current_datetime += time_step

Pattern Found: 132656949029301668323 Found Timestamp: 2015-01-01 00:00:45.558075
Pattern Found: 132656944992576280475 Found Timestamp: 2015-01-01 00:01:07.982988
Pattern Found: 132656940747988305926 Found Timestamp: 2015-01-01 00:01:21.862088
Pattern Found: 132656940747988305926 Found Timestamp: 2015-01-01 00:01:21.862088
Pattern Found: 132656940747988305926 Found Timestamp: 2015-01-01 00:01:21.862088
Pattern Found: 132656944899490185438 Found Timestamp: 2015-01-01 00:01:27.960048
Pattern Found: 132656944899490185438 Found Timestamp: 2015-01-01 00:01:27.960048
Pattern Found: 132656944864645138147 Found Timestamp: 2015-01-01 00:02:03.090600
(This search will continue indefinitely at the microsecond level.)

[POD5]

So you think the address and private key generation could relay on that? 

[nomachine]

So you think the address and private key generation could relay on that? 

After five years of these experiments, I don't think about this topic anymore. I mostly go fishing.

[POD5]

So you think the address and private key generation could relay on that?  

After five years of these experiments, I don't think about this topic anymore. I mostly go fishing.

I used to, when I was 13... But Atlantic is quite dirty.  

Now I sit in front of a PC, tripping with python and C code, trying to makeup them as best as I can.
Will you add more features to your Cyclone version?
N keys to be scanned at once?
Write progress into file (it isn't working yet)
Stride? (I have done some changes in your version, but it is a fix stride, that is, always need to makefile to change it)
Read range list to be scanned from file...

[dastic]

Randomness was most likely realted to hardware events and not timestamps

[tmar777]

What do you think is the set it and forget it best method?

To reverse engineer a random seed when the creator designed the puzzle at that specific moment, as far as I know, zahid888 made the most progress in that area. I gave up after puzzle 60 while searching for the seed.  

what if the seed has a salt involved?
can you quote what you are referring to for zahid888's work on it?

[mcdouglasx]

The Moser circle problem reminds us of the importance of working with solid foundations and avoiding unfounded assumptions. In both mathematics and life, assuming without verifying can lead to erroneous conclusions or suboptimal solutions. As Karl Popper used to say, falsifiability is key to progress: we must always strive to test (and refute, if necessary) our ideas with clear evidence.

That’s why I believe there is a certain degree of ignorance in statistical problems. It’s evident that a private key has no relation to prefixes, but this doesn’t interfere with the probabilities of how often a prefix is more likely to be found. A classic example is the correlation between ice cream sales and the number of people at the beach: when temperatures rise, both increase, but this doesn’t mean they are directly related. This distinction highlights the difference between correlation and causation.