Bitcoin puzzle transaction ~32 BTC prize to who solves it

[bdb]

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

[1714898528]

1714898528

[1714898528]

1714898528

[werty98]

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]

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]

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

[NorrisK]

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

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]

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  

[amaclin]

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]

amaclin,

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

Just curios.

[amaclin]

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

nothing.

[Bulista]

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]

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 2¹*1 = 2 OR 2¹+0 = 2
Hmm.  That didn't work.

Position 2 has the value of 7, which is 2²*1 = 4 OR 2²+0 = 4
Hmm. That didn't work either.

Position 4 has the value of 21, which is 2⁴*1 = 16 OR 2⁴+0 = 16
Hmm. Still no good.

Position 5 has the value of 49, which is 2⁵*1 = 32 OR 2⁵+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 2⁰ and 2¹-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 2³ and 2⁴-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 = 2ⁿ + x
Where x will always be in the range between 0 and 2ⁿ

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:
2ⁿ <= k < 2ⁿ⁺¹

[BurtW]

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.

[DannyHamilton]

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 2^n-1 * 0.5 (which I think would be 2^n-2) away from the actual private key.  So for the 41st key I can get you a value that will be within 2³⁹ of the actual key (with a 50% chance that my value is actually within 2³⁸ and a 25% chance that my value is within 2³⁷).

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]

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 2^n-1 * 0.5 (which I think would be 2^n-2) away from the actual private key.  So for the 41st key I can get you a value that will be within 2³⁹ of the actual key (with a 50% chance that my value is actually within 2³⁸ and a 25% chance that my value is within 2³⁷).

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

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

[Bulista]

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 2¹*1 = 2 OR 2¹+0 = 2
Hmm.  That didn't work.

Position 2 has the value of 7, which is 2²*1 = 4 OR 2²+0 = 4
Hmm. That didn't work either.

Position 4 has the value of 21, which is 2⁴*1 = 16 OR 2⁴+0 = 16
Hmm. Still no good.

Position 5 has the value of 49, which is 2⁵*1 = 32 OR 2⁵+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:

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]

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]

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
0	1	1.00000000	0
1	3	1.50000000	1
2	7	1.75000000	3
3	8	1.00000000	0
4	21	1.31250000	5
5	49	1.53125000	17
6	76	1.18750000	12
7	224	1.75000000	96
8	467	1.82421875	211
9	514	1.00390625	2
10	1155	1.12792969	131
11	2683	1.31005859	635
12	5216	1.27343750	1120
13	10544	1.28710938	2352
14	26867	1.63983154	10483
15	51510	1.57196045	18742
16	95823	1.46214294	30287
17	198669	1.51572418	67597
18	357535	1.36388779	95391
19	863317	1.64664650	339029
20	1811764	1.72783279	763188
21	3007503	1.43408918	910351
22	5598802	1.33485842	1404498
23	14428676	1.72003222	6040068
24	33185509	1.97801048	16408293
25	54538862	1.62538475	20984430
26	111949941	1.66818412	44841077
27	227634408	1.69600850	93416680
28	400708894	1.49275696	132273438
29	1033162084	1.92441434	496291172
30	2102388551	1.95800192	1028646727
31	3093472814	1.44051053	945989166
32	7137437912	1.66181426	2842470616
33	14133072157	1.64530614	5543137565
34	20112871792	1.17072322	2933002608
35	42387769980	1.23364647	8028031612
36	100251560595	1.45885221	31532083859
37	146971536592	1.06935867	9532583120
38	323724968937	1.17770458	48847061993
39	1003651412950	1.82563129	453895599062

[BurtW]

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
0	1	1.00000000	0
1	3	1.50000000	1
2	7	1.75000000	3
3	8	1.00000000	0
4	21	1.31250000	5
5	49	1.53125000	17
6	76	1.18750000	12
7	224	1.75000000	96
8	467	1.82421875	211
9	514	1.00390625	2
10	1155	1.12792969	131
11	2683	1.31005859	635
12	5216	1.27343750	1120
13	10544	1.28710938	2352
14	26867	1.63983154	10483
15	51510	1.57196045	18742
16	95823	1.46214294	30287
17	198669	1.51572418	67597
18	357535	1.36388779	95391
19	863317	1.64664650	339029
20	1811764	1.72783279	763188
21	3007503	1.43408918	910351
22	5598802	1.33485842	1404498
23	14428676	1.72003222	6040068
24	33185509	1.97801048	16408293
25	54538862	1.62538475	20984430
26	111949941	1.66818412	44841077
27	227634408	1.69600850	93416680
28	400708894	1.49275696	132273438
29	1033162084	1.92441434	496291172
30	2102388551	1.95800192	1028646727
31	3093472814	1.44051053	945989166
32	7137437912	1.66181426	2842470616
33	14133072157	1.64530614	5543137565
34	20112871792	1.17072322	2933002608
35	42387769980	1.23364647	8028031612
36	100251560595	1.45885221	31532083859
37	146971536592	1.06935867	9532583120
38	323724968937	1.17770458	48847061993
39	1003651412950	1.82563129	453895599062

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

[Bulista]

-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

[werty98]

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.