Topic: Bitcoin puzzle transaction ~32 BTC prize to who solves it - page 340. (Read 235243 times)

Without a clear pattern it will be quite hard to get far. It is basically like generating addresses with a certain entropy to them.

I doubt we will get much further than the 50 range without additional info or significant calculating power.

Nice work!

Unlike mining, this challenge won't get harder. If 1 BTC = 1,000,000 USD, which address will be cracked up to?

long time lurker; not much of a poster...

With simple C code, on a single thread, my cpu gets ~20K keys/second.
roughly broken down as:

    EC_POINT_add:       19808 ticks
    EC_POINT_point2oct: 120116 ticks
    sha256:             27840 ticks
    ripemd160:          3152 ticks
Scanned 763188 keys in 40 seconds, 19079 keys/second

i.e. as noted in this thread, the EC point conversion takes most of the time.
This can be further optimised in several ways - ignore the Y component or as noted in the VanityGen code; batch up a set of results and
use EC_POINTs_make_affine to simplify this operation.


I then patched the VanityGen code to solve the same problem.
This is only a very small mod.
- set the initial private key = 1, rather than random
- change the pattern matching [you could probably even use the existing one; but there is no need to convert to b58]


BitcoinPuzzle
roughly broken down as:

    EC_POINT_add:           5300 ticks
    EC_POINTs_make_affine 1193800 ticks     [called once per 256 keys]
                       i.e. 4663 ticks  per key
    EC_POINT_point2oct:     2760 ticks
    sha256:                 1216 ticks
    ripemd160:              1484 ticks
 [186.63 Kkey/s]

VanityGen

 [167 Kkey/s]

The saving on the EC point conversion can be seen, as can the better quality hash code used by OpenSSL compared to the code I was using.

If I run this on all cores; I get ~1.4M keys/second.
I've not tried the GPU version; but would expect comparable results to VanityGen generation.
The VanityGen thread suggests that a reasonable GPU can do ~30Mkeys/second.



Now, consider that the average time to find a key is half the search space.
So, for a 40 bit key, the average search  = 1/4 * 2^40 = 2.74877906944 x10^11
i.e.

bits        search_len          rate        time
25          8388608             1.4M        6 secs
40          274877906944        1.4M        196341 secs      = 3.15 days
40          274877906944        30M         9163 secs        = 2.5 hours
50          281474976710656     30M         9382500 secs     = 109 days
51          562949953421312     30M         18765000 secs    = 217 days

... I'm not going to be running for 200 days for $20

Burt,  after generating the public key, it requires converting from elliptic curve coordinates to bytes.
The operation is 'simply'  X' = X/Z^2 - but that means a divide in the finite field.
I *think* that make_affine step forces Z to be a constant for all the block that are affined, so this division only has to be done once per block.
EC_POINT_point2oct actually calculates both X'= X/Z^2 and Y'=Y/Z^3; but as we are using a compressed key, we don't need the Y' term.
I've not checked to see if this code gets optimised away properly; if not, it might save 10%.

Yeah, that's what I meant 

Anyway, as Einstein said, investors' behavior is the only thing in this universe that does not follow any physics law.

So far there is nothing to indicate that there is a "right formula" to predict the next private key given all the found private keys.

I believe the underlying sequence of private keys before masking to produce the shortened values was probably a secure RNG.

Well we wont get 5 TH/s or anything close for sure, but if we were able to generate 100 million keys per second we would break the #51 in about 3.5 months... And I believe it will be very hard to get to 100 million / s even with GPU.

Yes of course we can try it for the fun, but it wont be much fun when you get home and your GPU is burning plus your electricity bill

But of course if your formula brings down the range of keys to generate then we can have some chance.


If you find the right formula can you post the results for each address so we know exactly what ranges we can count with?

I am not sure exactly what you mean.  I do see a scenario where the creator of the challenge could possibly cause a panic sell off.  Is that what you are talking about?

The creator still has the private keys so they can spend the rewards at any time.  So, they could claim a bunch of the rewards thus simulating a weakness in the Bitcoin crypto?  This could possibly cause a panic sell off if the market believed it?

That is the mathematics behind the point addition.  The actual implementation of point addition would be optimized and very different.  

I was just trying to make the point that a single point addition operation should take the same amount of time (same number of machine instructions) no matter what the actual point values are.

This is in contrast to the scalar multiplication function P = p*G which will take different amounts of time (different numbers of machine instructions) depending on the value of p.

But I see now that the division operation (or equivalently calculating the inverse of the denominator) could take varying amounts of time.

So, basically I was wrong because we have to calculate λ to add the two points.

This is a basic description of the algorithm which should yield the fastest results:


Which step above is using the slow EC_POINT_point2oct function?

Do you know why EC_POINT_point2oct is slow? I called EC_POINT_get_affine_coordinates_GFp instead, but they seem to do the same thing. If EC_POINT_add stores the point in Cartesian coordination (X-Y), will extracting the public key be a trivial task?


I think all of us know that brute force is not viable for sure, but it is fun to estimate how long it will take to break the 51st, 52nd, ... addresses.

That division isn't the conventional division. It has perfect precision (http://www.johannes-bauer.com/compsci/ecc/#anchor07).

It is impossible to get all the rewards.

It is possible to get the next reward (0.051 BTC) in the sequence.

There are only 1,125,899,906,842,620 possible keys for the next unclaimed reward of 0.051 BTC.

At your rate of 5,000,000,000,000 trial per second it would only take a bit over 225 seconds to try all of them.

There is no hope of getting all the remaining rewards but it should be totally possible to get a few more small rewards from the sequence.

Guys with brute force we won't go anywhere.

Let us assume we would be able somehow to generate a brute force of 5 TH/s (The max ASIC Miner speed today that I found out there).

That's like 5000000000000 Hashes per second. Of course with CPU/GPU we won't get anywhere near.

But let us assume for a second that this performance would be possible somehow, we would need ~303150594339750000000000000000000000000000000000000000000 years to break until the address 256 already counting with starting each address generation from 2^X-1. (EDIT: Not even counting with all the addresses before )

So it's kind of useless to brute force this.


How precise is this formula?

I get the same performance as you, but EC_POINT_add isn't the slowest step, it's the call to EC_POINT_point2oct.

I did use that EC point increment method, otherwise the program would be 20x slower. Those multiplications/divisions are modulus but not conventional integer operators; they don't have predictable machine cycle count.

I would expect a single point addition operation (P₃ = P₁ + P₂) to have a very predictable machine cycle count.  It should be something like:

x₃ = λ²+a₁λ−a₂−x₁−x₂

y₃ = −a₁x₃−a₃−λx₃+λx₁−y₁

λ = (y₂−y₁) / (x₂−x₁)

From:  https://crypto.stanford.edu/pbc/notes/elliptic/explicit.html

I've tried my first version using openssl and got about 25,000 keys/s (single-thread). You seem to use something other than openssl.

Unlike hash operations, elliptic curve operations have unpredictable machine cycle count. Thus, speed-up on SIMD processors (e.g. GPUs) won't be great.

BTW, whoever created this challenge will be able to manipulate BTC price, won't she/he?

Its an easy way to check whether the first bit is always 1 for a given step, which it is. Thus you can limit the search space. For step n you do not need to search for any possible solutions from step n-1.

NOW, that's interesting! I see a pattern that may now be solvable.

I see somebody has a jumpstart: https://bitcointalksearch.org/topic/m.13424809 But why Log(2)?

What you posted weren't the actual raw private keys but the base58 encoded and WIF formatted version of the private keys with the information stating it's uncompressed.

The hex representation of a base58 encoded and WIF formatted uncompressed key is:
80 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX YYYYYYYY
The hex representation of a base58 encoded and WIF formatted compressed key is:
80 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 01 YYYYYYYY
where XX is the raw private key and YY the checksum.

Your question regarding "how many invalid keys are in between" is ambiguous. You might also consider to open a new thread to reach appropriate audience.