Topic: Bitcoin puzzle transaction ~32 BTC prize to who solves it - page 290. (Read 208283 times)
Why stop at fitting 2, 3, 4, etc. Keys? Now that we know the first 40 private keys it would be very easy to enter all 40 keys and get a polynomial to perfectly fit all 40 keys. Unfortunately the function will not predict the 41st key.
The values 1 and 8, suggest that the formula can be something like this:
2^n * x, where x is = 1 OR 2^n + x, where x is = 0
Value 1 is in the position 0, value 8 is in the position 3.
Position 0 has the value 1, which is 2^0*1 OR 2^0+0
Position 3 has the value 8, which is 2^3*1 OR 2^3+0
It means that the calculation of x for the positions 0 and 3 result in 0 or 1.
2^n * x, where x is = 1 OR 2^n + x, where x is = 0
Value 1 is in the position 0, value 8 is in the position 3.
Position 0 has the value 1, which is 2^0*1 OR 2^0+0
Position 3 has the value 8, which is 2^3*1 OR 2^3+0
It means that the calculation of x for the positions 0 and 3 result in 0 or 1.
Lets see if that's right...
Position 1 has the value of 3, which is 21*1 = 2 OR 21+0 = 2
Hmm. That didn't work.
Position 2 has the value of 7, which is 22*1 = 4 OR 22+0 = 4
Hmm. That didn't work either.
Position 4 has the value of 21, which is 24*1 = 16 OR 24+0 = 16
Hmm. Still no good.
Position 5 has the value of 49, which is 25*1 = 32 OR 25+0 = 32
This isn't looking like it's going to work.
Lets think about this logically.
If (as many of us have presumed) the first key (position 0) is completely random in the range between 20 and 21-1 then all the possible values are 1 and, well, um, I guess that's it. Can't be anything else.
If the third key is then completely random in the range between 23 and 24-1, then there are 4 possibilities 5, 6, 7, and 8. So there's a 25% chance of it being 8.
If you just pick any 2 of the lower positions the possible values are so limited that it's pretty easy to imagine that you see patterns in the numbers. The problem is none of the patterns people seem think they see work out as soon as you add another position or two. If you're having to come up with a brand new "formula" to fit the data every time you add a position, then its important to consider the possibility that you are looking at random data and simply calculating a convoluted and useless formula that fits your current limited set and none of the rest of the set.
The source also pointed out this example:
If you calculate the Prime Factor of 21 (Position 4), the result is 3 and 7. (these numbers are in the position 1 and 2).
If you calculate the Prime Factor of 21 (Position 4), the result is 3 and 7. (these numbers are in the position 1 and 2).
Prime factors of 76 are 2 and 19 (which don't occur in any positions).
Prime factors of 224 are 2 and 7. Now 7 was already used as a factor for 21, and 2 is a factor of 76 and doesn't occur in the list of positions.
Prime factors of 467 are 467 and that's it. (467 is prime).
If you like I can give you a formula that will work "perfectly" for 39 and 40 (mostly because 2 points define a line and it's pretty easy to create an equation for a line). It won't work for pretty much any others, but then all we have to do is figure out how to "tweak" the formula, right?
If you like, I can give you a formula that will work "perfectly" for 38, 39, and 40 (mostly because 3 points define a parabola, and it's pretty easy to create an equation for a parabola). It won't work for pretty much any others, but then all we have to do is figure out how to "tweak" the formula, right?
Here's a formula that I suspect will work EVERY time:
Given zero based position n
Private key k will always be:
k = 2n + x
Where x will always be in the range between 0 and 2n
x will be different every time (and almost certainly random), but once you figure out x (through brute force) at any position, you'll have the private key at that position.
Another way to look at it is that k will always be random but limited to a random number in the range:
2n <= k < 2n+1
I got an information from someone pointing out some interesting facts.
Maybe there is a solution for a formula after all.
If you look at the sequence:
1
3
7
8
21
49
76
224
467
etc.
The values 1 and 8, suggest that the formula can be something like this:
2^n * x, where x is = 1 OR 2^n + x, where x is = 0
Position 0 has the value 1, which is 2^0*1 OR 2^0+0
Position 3 has the value 8, which is 2^3*1 OR 2^3+0
It means that the calculation of x for the positions 0 and 3 result in 0 or 1.
Finding the formula for this "x" can be the holy grail of this puzzle.
The source also pointed out this example:
If you calculate the Prime Factor of 21 (Position 4), the result is 3 and 7. (these numbers are in the position 1 and 2).
You can check the prime factor here:
http://www.calculatorsoup.com/calculators/math/prime-factors.php
Maybe there is a solution for a formula after all.
If you look at the sequence:
1
3
7
8
21
49
76
224
467
etc.
The values 1 and 8, suggest that the formula can be something like this:
2^n * x, where x is = 1 OR 2^n + x, where x is = 0
Position 0 has the value 1, which is 2^0*1 OR 2^0+0
Position 3 has the value 8, which is 2^3*1 OR 2^3+0
It means that the calculation of x for the positions 0 and 3 result in 0 or 1.
Finding the formula for this "x" can be the holy grail of this puzzle.
The source also pointed out this example:
If you calculate the Prime Factor of 21 (Position 4), the result is 3 and 7. (these numbers are in the position 1 and 2).
You can check the prime factor here:
http://www.calculatorsoup.com/calculators/math/prime-factors.php
Do you happen to know anything about the author of the trasaction?
nothing.
amaclin,
Do you happen to know anything about the author of the trasaction?
Just curios.
Do you happen to know anything about the author of the trasaction?
Just curios.
The first 20 addresses were spent in the same block with the puzzle transaction, surely by the author.
Wrong. I took several of these small outputs, but I am not a creator of https://blockchain.info/tx/08389f34c98c606322740c0be6a7125d9860bb8d5cb182c02f98461e5fa6cd15
The first 20 addresses were spent in the same block with the puzzle transaction, surely by the author. Would the author be a miner? This also raises the question whether someone else rather than the author did cash out 
Would be great if someone could find out who did this transaction.
We know that the funds came from this address:
https://blockchain.info/address/173ujrhEVGqaZvPHXLqwXiSmPVMo225cqT
It's quite a big player, with transactions every day.
Is this an exchange?
Like someone was saying here before, the guy that holds those 256 addresses has now some power over us, if suddenly we see that the addresses from 50 to 256 are spent, we will all feel a bit scared, no?
We wouldn't know if they were actually cracked (and this would raise some questions) or if it was an intentional transaction from the holder...
We know that the funds came from this address:
https://blockchain.info/address/173ujrhEVGqaZvPHXLqwXiSmPVMo225cqT
It's quite a big player, with transactions every day.
Is this an exchange?
Like someone was saying here before, the guy that holds those 256 addresses has now some power over us, if suddenly we see that the addresses from 50 to 256 are spent, we will all feel a bit scared, no?
We wouldn't know if they were actually cracked (and this would raise some questions) or if it was an intentional transaction from the holder...
Why would he spend them? If it was not his intention to male a puzzle like this, he would've moved them after the first coins were moved.
Maybe you can try sending a message to that address, maybe well get a hint or something in return.
Would be great if someone could find out who did this transaction.
We know that the funds came from this address:
https://blockchain.info/address/173ujrhEVGqaZvPHXLqwXiSmPVMo225cqT
It's quite a big player, with transactions every day.
Is this an exchange?
Like someone was saying here before, the guy that holds those 256 addresses has now some power over us, if suddenly we see that the addresses from 50 to 256 are spent, we will all feel a bit scared, no?
We wouldn't know if they were actually cracked (and this would raise some questions) or if it was an intentional transaction from the holder...
We know that the funds came from this address:
https://blockchain.info/address/173ujrhEVGqaZvPHXLqwXiSmPVMo225cqT
It's quite a big player, with transactions every day.
Is this an exchange?
Like someone was saying here before, the guy that holds those 256 addresses has now some power over us, if suddenly we see that the addresses from 50 to 256 are spent, we will all feel a bit scared, no?
We wouldn't know if they were actually cracked (and this would raise some questions) or if it was an intentional transaction from the holder...
long time lurker; not much of a poster...
Nice work!
Unlike mining, this challenge won't get harder. If 1 BTC = 1,000,000 USD, which address will be cracked up to?
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.
long time lurker; not much of a poster...
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:
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:
VanityGen
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.
... 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%.
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%.
BTW, whoever created this challenge will be able to manipulate BTC price, won't she/he?
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?
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.
If you find the right formula can you post the results for each address so we know exactly what ranges we can count with?
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.
I get the same performance as you, but EC_POINT_add isn't the slowest step, it's the call to EC_POINT_point2oct.
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?
Guys with brute force we won't go anywhere.
How precise is this formula?
How precise is this formula?
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).
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.
So, basically I was wrong because we have to calculate λ to add the two points.
If you find the right formula can you post the results for each address so we know exactly what ranges we can count with?
BTW, whoever created this challenge will be able to manipulate BTC price, won't she/he?
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?
Unlike hash operations, elliptic curve operations have unpredictable machine cycle count.
I would expect a single point addition operation (P3 = P1 + P2) to have a very predictable machine cycle count. It should be something like:x3 = λ2+a1λ−a2−x1−x2
y3 = −a1x3−a3−λx3+λx1−y1
λ = (y2−y1) / (x2−x1)
From: https://crypto.stanford.edu/pbc/notes/elliptic/explicit.html
How precise is this formula?
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:
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.
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
Which step above is using the slow EC_POINT_point2oct function?
Code:
Initialization:
Set BitcoinAddresses[256] = the list of bitcoin addresses from the transaction, binary form without the checksum
Set BitcoinAddressIndex = 0;
Set PrivateKey = 1;
Set PublicKey = G;
Loop Until BitcoinAddressIndex == 256: // == "forever"
Call Convert PublicKey to BitcoinAddress [but just to the binary form, do not calculate the checksum or encode to ASCII]
If BitcoinAddress == BitcoinAddresses[BitcoinAddressIndex] Then
Log BitcoinAddressIndex, PrivateKey, PublicKey, BitcoinAddress
Create transaction and claim Bitcoins if any available at BitcoinAddress
Endif
++PrivateKey;
Call Increment PublicKey by G // Highly optimized, very specialized function to just compute PublicKey = PublicKey + G
EndLoop
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.
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
Which step above is using the slow EC_POINT_point2oct function?
I get the same performance as you, but EC_POINT_add isn't the slowest step, it's the call to EC_POINT_point2oct.
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?
Guys with brute force we won't go anywhere.
How precise is this formula?
How precise is this formula?
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.
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.
Jump to: