Bitcoin Forum
October 16, 2018, 05:40:05 PM *
News: Make sure you are not using versions of Bitcoin Core other than 0.17.0 [Torrent], 0.16.3, 0.15.2, or 0.14.3. More info.
 
   Home   Help Search Donate Login Register  
Pages: « 1 2 3 4 5 6 7 [8] 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 »  All
  Print  
Author Topic: Bitcoin puzzle transaction ~32 BTC prize to who solves it  (Read 31696 times)
bdb
Newbie
*
Offline Offline

Activity: 2
Merit: 0


View Profile
January 04, 2016, 09:49:33 PM
 #141

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%.


Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1539711605
Hero Member
*
Offline Offline

Posts: 1539711605

View Profile Personal Message (Offline)

Ignore
1539711605
Reply with quote  #2

1539711605
Report to moderator
werty98
Newbie
*
Offline Offline

Activity: 8
Merit: 0


View Profile
January 05, 2016, 06:47:23 AM
 #142

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?
NorrisK
Legendary
*
Offline Offline

Activity: 1722
Merit: 1003



View Profile
January 05, 2016, 07:03:53 AM
 #143

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.
Bulista
Member
**
Offline Offline

Activity: 126
Merit: 10


View Profile
January 05, 2016, 09:35:04 AM
 #144

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?  Cheesy

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...
NorrisK
Legendary
*
Offline Offline

Activity: 1722
Merit: 1003



View Profile
January 05, 2016, 09:54:28 AM
 #145

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?  Cheesy

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.
werty98
Newbie
*
Offline Offline

Activity: 8
Merit: 0


View Profile
January 05, 2016, 01:47:00 PM
 #146

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  Roll Eyes

amaclin
Legendary
*
Offline Offline

Activity: 1260
Merit: 1000


View Profile
January 05, 2016, 02:02:46 PM
 #147

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
BurtW
Legendary
*
Offline Offline

Activity: 2310
Merit: 1009

All paid signature campaigns should be banned.


View Profile WWW
January 05, 2016, 02:10:53 PM
 #148

amaclin,

Do you happen to know anything about the author of the trasaction?

Just curios.

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
amaclin
Legendary
*
Offline Offline

Activity: 1260
Merit: 1000


View Profile
January 05, 2016, 03:19:50 PM
 #149

Do you happen to know anything about the author of the trasaction?
nothing.
Bulista
Member
**
Offline Offline

Activity: 126
Merit: 10


View Profile
January 06, 2016, 01:44:34 AM
 #150

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
DannyHamilton
Legendary
*
Offline Offline

Activity: 2198
Merit: 1381



View Profile
January 06, 2016, 02:32:53 AM
 #151

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.

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).

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


BurtW
Legendary
*
Offline Offline

Activity: 2310
Merit: 1009

All paid signature campaigns should be banned.


View Profile WWW
January 06, 2016, 02:47:30 AM
 #152

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.

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
DannyHamilton
Legendary
*
Offline Offline

Activity: 2198
Merit: 1381



View Profile
January 06, 2016, 03:04:15 AM
 #153

Unfortunately the function will not predict the 41st key.

No, but (depending on how you define "close") I'll bet I can get you close to the 41st key.  Specifically, I'm nearly certain that I can find you a formula that will result in a value that is less than 2n-1 * 0.5 (which I think would be 2n-2) away from the actual private key.  So for the 41st key I can get you a value that will be within 239 of the actual key (with a 50% chance that my value is actually within 238 and a 25% chance that my value is within 237).

While I'm being truthful here, those who are aware of the ranges that the random numbers fall between will probably notice the obviousness in my statement.

Quickseller
Copper Member
Legendary
*
Offline Offline

Activity: 1568
Merit: 1186


View Profile WWW
January 06, 2016, 05:58:16 AM
 #154

Unfortunately the function will not predict the 41st key.

No, but (depending on how you define "close") I'll bet I can get you close to the 41st key.  Specifically, I'm nearly certain that I can find you a formula that will result in a value that is less than 2n-1 * 0.5 (which I think would be 2n-2) away from the actual private key.  So for the 41st key I can get you a value that will be within 239 of the actual key (with a 50% chance that my value is actually within 238 and a 25% chance that my value is within 237).

While I'm being truthful here, those who are aware of the ranges that the random numbers fall between will probably notice the obviousness in my statement.
Sure, all you need to do is calculate the midpoint of the potential values of the private key for the 41st key.

I am not sure if this would get someone "close" to the 41st private key, although I do not think it matters if you are "close" because AFAIK, for private key n, you receive no benefit for knowing private key n+1, and there is no indication that you are only "+1" away from n.

(BTW, I was able to accurately predict the principle behind my response without even reading anything except this post, although my specific response was only formulated after reading the entire thread......and having most of the formulas go way over my head). Smiley  



--snip--

One thing I noticed:

The first address in the transaction is tagged on blockchain.info with "1st Bitcoin Address Compressed".

So probably this transaction was done by the Bitcoin devs? or even... satoshi?
That address links to a website that appears to be a Chinese version of directory.io (that has recently been taken offline).

3PjXm2XYDKLV5mN3oiKzNTyVvSkqP3ujeq <-- tipping address Advertise here
Bulista
Member
**
Offline Offline

Activity: 126
Merit: 10


View Profile
January 06, 2016, 06:50:53 AM
 #155

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.

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.


You didn't get the idea. I was also not getting it at first.

Look:

Quote
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

This means x = 1 or x = 0 for the positions 0 and 3 (Only), it's just a superficial demonstration of the formula.

Means that x is possibly some kind of formula (A giant one, with mods, logs, exponents and whatever, where n is also included) and when n is = 0, result is 1 and x is 1 or 0, when n is = 3 result is 8 and x is 1 or 0.

Values of x for other positions can be also calculated easily, for example position 2:

position 2:

We know the result is 7, so

2^2 * x = 7 OR 2^2 + x = 7
 
Means that x is:

x = 7 / (2^2) = 1.75

OR

x = 7 - 2^2 = 3

That's why I said:


Finding the formula for this "x" can be the holy grail of this puzzle.


About the prime factorization, could be part the solution for finding how this x is calculated.
werty98
Newbie
*
Offline Offline

Activity: 8
Merit: 0


View Profile
January 06, 2016, 07:50:20 AM
 #156

Of course the n-th private key is always in the form 2^n + x; this is the whole point of this puzzle.  The problem is there are 2^n possible values for x!
Bulista
Member
**
Offline Offline

Activity: 126
Merit: 10


View Profile
January 06, 2016, 10:46:00 AM
 #157

Here are the results for the values we know given those 2 mentioned formulas:

y = 2^n * x

and so x = y / 2^n

AND

y = 2^n + x

and so x = y - 2^n


n     Known Results (y)     x = y / 2^n     x = y - 2^n
011.000000000
131.500000001
271.750000003
381.000000000
4211.312500005
5491.5312500017
6761.1875000012
72241.7500000096
84671.82421875211
95141.003906252
1011551.12792969131
1126831.31005859635
1252161.273437501120
13105441.287109382352
14268671.6398315410483
15515101.5719604518742
16958231.4621429430287
171986691.5157241867597
183575351.3638877995391
198633171.64664650339029
2018117641.72783279763188
2130075031.43408918910351
2255988021.334858421404498
23144286761.720032226040068
24331855091.9780104816408293
25545388621.6253847520984430
261119499411.6681841244841077
272276344081.6960085093416680
284007088941.49275696132273438
2910331620841.92441434496291172
3021023885511.958001921028646727
3130934728141.44051053945989166
3271374379121.661814262842470616
33141330721571.645306145543137565
34201128717921.170723222933002608
35423877699801.233646478028031612
361002515605951.4588522131532083859
371469715365921.069358679532583120
383237249689371.1777045848847061993
3910036514129501.82563129453895599062

BurtW
Legendary
*
Offline Offline

Activity: 2310
Merit: 1009

All paid signature campaigns should be banned.


View Profile WWW
January 06, 2016, 02:07:30 PM
 #158

Here are the results for the values we know given those 2 mentioned formulas:

y = 2^n * x

and so x = y / 2^n

AND

y = 2^n + x

and so x = y - 2^n


n     Known Results (y)     x = y / 2^n     x = y - 2^n
011.000000000
131.500000001
271.750000003
381.000000000
4211.312500005
5491.5312500017
6761.1875000012
72241.7500000096
84671.82421875211
95141.003906252
1011551.12792969131
1126831.31005859635
1252161.273437501120
13105441.287109382352
14268671.6398315410483
15515101.5719604518742
16958231.4621429430287
171986691.5157241867597
183575351.3638877995391
198633171.64664650339029
2018117641.72783279763188
2130075031.43408918910351
2255988021.334858421404498
23144286761.720032226040068
24331855091.9780104816408293
25545388621.6253847520984430
261119499411.6681841244841077
272276344081.6960085093416680
284007088941.49275696132273438
2910331620841.92441434496291172
3021023885511.958001921028646727
3130934728141.44051053945989166
3271374379121.661814262842470616
33141330721571.645306145543137565
34201128717921.170723222933002608
35423877699801.233646478028031612
361002515605951.4588522131532083859
371469715365921.069358679532583120
383237249689371.1777045848847061993
3910036514129501.82563129453895599062


I think that what you have done is to pretty much prove it is random and there is no predictive formula.

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
Bulista
Member
**
Offline Offline

Activity: 126
Merit: 10


View Profile
January 06, 2016, 02:54:58 PM
 #159


-snip-

I think that  what you have done is to pretty much prove it is random and there is no predictive formula.

I'm not sure.

I got some infos that are getting me to believe that there is a possible formula behind it.

I give you an example. I'm playing around by creating random formulas, and I get pretty much similar results. Yet they are predictable with a formula.

All I use for inputs are 2 arrays, one with the current position and another with the sequential list of prime numbers.

For example:

Consider n = count, p = prime numbers, and y = sequence based on the formula 2^n + (n mod p) * Log(n+1, 2) <--- Random formula I invented.

y / 2^p + 1 and y-2^p *-1 are similar formulas to what was shown before for the var x in the real sequence, their results also appear to be random...

n     p     y = 2^n + (n mod p) * Log(n+1, 2)     y / 2^p + 1     y-2^p *-1
0     2              1     1.25000000     3
1     3              3     1.37500000     5
2     5              7     1.22406016     25
3     7              14     1.10937500     114
4     11              25     1.01234752     2023
5     13              45     1.00548399     8147
6     17              81     1.00061679     130991

Yet this sequence is breakable with a simple formula.

EDIT: this formula doesn't make any sense I know, just playing around Smiley
werty98
Newbie
*
Offline Offline

Activity: 8
Merit: 0


View Profile
January 06, 2016, 04:02:41 PM
 #160

Maybe these random-like numbers came from hashing operations? For example: n-th key = truncate(SHA256(f((n-1)-th key))). It will be still hopeless if the process involves a strong passphrase though.
Pages: « 1 2 3 4 5 6 7 [8] 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 »  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!