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

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.

Read this post, just a few posts back:

https://bitcointalksearch.org/topic/m.13424809

If you want to know more please read the entire thread.  It is only 7 pages long.

After  reading into this puzzle post ..I have a question maybe someone can answer

1   5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreAnchuDf
2   5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreAvUcVfH
3   5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreB1FQ8BZ
4   5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreB4AD8Yi
5   5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreBF8or94
6   5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreBKdE2NK
7   5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreBR6zCMU
8   5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreBbMaQX1
9   5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreBd7uGcN   
A   5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreBoNWTw6
B   5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreBquB4Rj
C   5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreC4p2u5o
D   5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreCAVyVnh
E   5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreCHK2Zzv
F   5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreCMUnXUo

These are all valid private keys....  Just how many "NON valid" keys are in between each of the first 16 valid keys
and is there a pattern..

I am a little rusty with my Base58 math skills and maybe I should have done it in WIF Compressed....

You obviously do not know me very well.

This idea is not even a mole on the ass of a gnat on the ass of the dumpest idea I have ever had.

Thinking about is a bit further the cooperative method of finding the next prize can be simplified to just giving the entire prize, all 0.051 x $433.42 = $22.10 to whoever is lucky enough to be assigned the lucky section of private keys by the server.

That way we would not have to figure out which charity, or how to prove work, etc.

It would just be a lottery with a $22.10 prize for using up an immense amount of electricity.

I was already utilizing the point addition function instead of point multiplication.

No. Currently I don't try to discover any values above 2⁴⁰.
I'll continue the search if:

• I learn how to code on GPU one day
• I gain access to many computers equipped with a powerfull GPU

Most dump idea ever.
You made my day.

We should form a cooperative and search the private key space for the next correct value in much the same way GIMPS (http://www.mersenne.org/) searches for prime numbers.

Everyone that wants to participate would run a client in the background on their computer.

There would be a central server which would dole out search spaces of one billion or trillion consecutive private keys (whatever makes sense as a chunk size) to the connected clients and the clients would grind through their assigned search spaces using my suggested (increment by G) algorithm.

When a client was done with its assignment it would request another chunk of private key space from the server.

If a client did find the correct private key then the winner would keep the 0.051 BTC.

we could do something with the BTC, suggestions are:

split it among all clients proportional to work done [but method to prove work would need to be figured out]
donate it to charity
open to other suggestions

Very nicely done.  I especially like the graphical binary form and the log2 is also informative.

Thanks for this.

Are you currently trying to discover the values above 40?

It seems to me that you guys should not be using the ECC scalar multiplication function at all, just a very fast, totally optimized "increment by G" function:


This algorithm, when optimized, and split up so that many loops could be done in parallel, is as fast as it can be done.

Note on the PublicKey to BitcoinAddress conversion function:

You only need to do the first 3 of the 9 steps in this process.

1 - Take the PublicKey and format it properly (add the 1 byte of 0x04, change to compressed form if needed)
2 - Perform SHA-256 hashing on the result
3 - Perform RIPEMD-160 hashing on the result of SHA-256

This result can be compared directly to the BitcoinAddresses[] array assuming you have stored the 256 Bitcoin addresses in the proper binary form.

Not sure a miner would help as it only does one of the steps in the PublicKey to BitcoinAddress conversion.

Of course an FPGA could be programmed to do this.  And, of course, if you had the resources an ASIC could be made to do this.

Final note on the BitcoinAddresses[] array values:

To get the proper values for this array simply undo the last 6 steps of the PublicKey to BitcoinAddress function for each of the 256 Bitcoin addresses in the transaction:

1 - Decode the base58 string to a binary byte array
2 - Strip off the 4 checksum bytes from the tail
3 - Strip off the version byte (0x00) from the front
4 - Store the result in the array

Miners can only do sha256d. What is needed here is pubkey(ECDSA privkey) and ripemd160(sha256(0x04pubkeyxpubkeyy)). Everything else can be ignored if we compare to the ripemd160 hash. Its certainly possible to design an ASIC for this and it might even be profitable for someone to do so in the future.

Exactly.

One thing I was wondering is if it is possible somehow to tweak some ASIC miner out there to turn it into a cracker?

I have no idea if such thing is possible as I never used any ASIC miner.

A GPU cracker would take at most ~a year for solving the next 2⁵¹ address at 35,000,000 keys/s. I guess it will be cracked too in future, but for fun and not for money.

I don't know who made this pizzle.