[ARCHIVE] Bitcoin challenge discusion

[Kakmakr]

It is unfortunate that challenges like these are so complicated and that only a few people with specialized hardware and knowledge can take part in this. We need challenges like this that can give open participation to a lot more people, without specialized knowledge to garner a lot more publicity for Bitcoin.

I know it is difficult to create something that would be more accessible for the average guy on the street, but it can be something that can be done by a group of people with different knowledge on several topics and something where groups can all benefit from the rewards. We had something like this before, but the prize was not this big. 

[malevolent]

It is unfortunate that challenges like these are so complicated and that only a few people with specialized hardware and knowledge can take part in this. We need challenges like this that can give open participation to a lot more people, without specialized knowledge to garner a lot more publicity for Bitcoin.

Earlier on the puzzle was accessible to everyone with a cheap computer, if it was any easier a single person could have quickly snagged the whole prize. Making each key progressively more difficult to find ensures the challenge will remain open to all for a very long time.

[zielar]

For my certainty: what range applies to address 105 (this is the first of the unused, which has the output and pubkey transactions). Something I have to check, high compartment, and it's time to waste a pity :-) According to my calculations, the beginning is 0000000000000000000000000000000000000100000000000000000000000000?

[girors]

For my certainty: what range applies to address 105 (this is the first of the unused, which has the output and pubkey transactions). Something I have to check, high compartment, and it's time to waste a pity :-) According to my calculations, the beginning is 0000000000000000000000000000000000000100000000000000000000000000?

Correct me if I'm wrong but start: 100000000000000000000000000 2^104
                                          end: 1ffffffffffffffffffffffffff 2^105 -1
Plz share if you get any luck

[racminer]

For my certainty: what range applies to address 105 (this is the first of the unused, which has the output and pubkey transactions). Something I have to check, high compartment, and it's time to waste a pity :-) According to my calculations, the beginning is 0000000000000000000000000000000000000100000000000000000000000000?

Correct me if I'm wrong but start: 100000000000000000000000000 2^104
                                          end: 1ffffffffffffffffffffffffff 2^105 -1
Plz share if you get any luck

105 bits = 1 + 26x4bits,  so the  range is  obviously
100000000000000000000000000  to 1FFFFFFFFFFFFFFFFFFFFFFFFFF
good luck 

[pooya87]

By the way, isn't it kinda scary that a few keys in 80 and 90 bit ranges were already found? Many users have passwords with less bits of security, and passwords also aren't random, so bruteforce can be optimized. Or am I missing something, and those keys were cracked with some algorithm rather than brute force?

you are missing the difference between Asymmetric (elliptic curve) cryptography and Encryption (like Block ciphers). i am not an expert but the algorithms are very different. for example in this topic's case the algorithm (when starting from a certain private key like 2^90) can be simplified to a very simple single point addition but in breaking something like AES you still need to brute force the whole thing.

if you want to have fun, you can program something. i did that a while ago in c# for small ones as a "challenge" to my skills knowing there is no other reward.

So, I did it and it takes 2.5 ms for me to calculate an address from a raw private key 

doesn't seem that bad. my normal point multiplication takes 42 ms using BigIntegers...
that's not the whole thing though, it is all about the LOOP where you have to repeat the same thing, and  you shouldn't work with raw private key and addresses. you start with the bytes and end with hash bytes and skip any unnecessary conversions.

It is unfortunate that challenges like these are so complicated and that only a few people with specialized hardware and knowledge can take part in this. We need challenges like this that can give open participation to a lot more people, without specialized knowledge to garner a lot more publicity for Bitcoin.

I know it is difficult to create something that would be more accessible for the average guy on the street, but it can be something that can be done by a group of people with different knowledge on several topics and something where groups can all benefit from the rewards. We had something like this before, but the prize was not this big. 

this is not a giveaway. i believe it is more like a test of the security of a 256 bit elliptic curve, and the incentive is the way to keep an eye on it. the conclusion so far is that 256 is very safe since so far after years of work only ~90 bits of it is searched and the "rewards" were claimed. because of that it is not for the "average guy" while that average guy can still start learning more about ECC and gets his hands dirty...

[j2002ba2]

#100 - af55fc59c335c8ec67ed24826

Lucky with only 69% of the expected time - 1d 22:49:48 of the 2d 19:46:27 expected.

[supika]

#100 - af55fc59c335c8ec67ed24826

Lucky with only 69% of the expected time - 1d 22:49:48 of the 2d 19:46:27 expected.

What tool and what hardware you have used?

[BurtW]

#100 - af55fc59c335c8ec67ed24826

Lucky with only 69% of the expected time - 1d 22:49:48 of the 2d 19:46:27 expected.

Great!  zielar can fill in the #100 entry in the table in the OP.  Congrats on your 1 BTC (approx $10,000) bounty!

For private key 000000000000000000000000000000000000000af55fc59c335c8ec67ed24826

I get:

Uncompressed Bitcoin Address:  1Bv8fD7w52gWTRpnAMTLPvMrsfpX6bySpe
Compressed Bitcoin Address: 1KCgMv8fo2TPBpddVi9jqmMmcne9uSNJ5F

What is your expected time for #105 (approx another $10,500)?

My "back of the envelope" estimate for the estimated times, assuming you can afford or have access to the required hardware:

#100 = 50.0 bits of security was estimated at about 3 days
#105 = 52.5 bits of security will be about 3 x 2^2.5 = about 17 days
#110 = 55.0 bits of security will be about 3 x 2^5.0 = about 96 days
#115 = 57.5 bits of security will be about 3 x 2^7.5 = about 543 days = 1.49 years
#120 = 60.0 bits of security will be about 3 x 2^10.0 = about 3,072 days = 8.41 years ^***
#125 = 62.5 bits of security will be about 3 x 2^12.5 = about 17,378 days = 47.56 years
#130 = 65.0 bits of security will be about 3 x 2^15.0 = about 98,304 days = 269.14 years

The last one would be:

#160 = 80.0 bits of security will be about 3 x 2^30.0 = about 3,221,225,472 days = 8,819,234 years

^*** From what I understand 120 bits would be a new world record for "cracking" an EC key pair.

On 2 December 2016, Daniel J. Bernstein, Susanne Engels, Tanja Lange, Ruben Niederhagen, Christof Paar, Peter Schwabe, and Ralf Zimmermann announced the solution of a generic 117.35-bit elliptic curve discrete logarithm problem on a binary curve, using an optimized FPGA implementation of a parallel version of Pollard's rho algorithm. The attack ran for about six months on 64 to 576 FPGAs in parallel.[30]

From https://en.wikipedia.org/wiki/Discrete_logarithm_records

[j2002ba2]

What is your expected time for #105?

I was using 4x Tesla V100 for it. Here is a table with expected times:

|------+-------------------+-------------------|-------------------|
| bits |      4x V100      |     100x V100     |    27648x V100    |
|------+-------------------+-------------------|-------------------|
|  100 |       2d 19:52:51 |          02:42:54 |          00:00:35 |
|  105 |           16 days |          15:21:34 |          00:03:19 |
|  110 |           90 days |       3d 14:53:14 |          00:18:51 |
|  115 |  1 year  147 days |           20 days |          01:46:39 |
|  120 |  7 years 341 days |          116 days |          10:03:23 |
|  125 | 44 years 323 days |  1 year  290 days |       2d 08:53:15 |
|  130 |       253 years   | 10 years  57 days |      13d 09:48:19 |
|  135 |     1,436 years   | 57 years 166 days |      75d 20:24:23 |
|  140 |     8,125 years   |         325 years |  1 year   64 days |
|  145 |    45,964 years   |       1,838 years |  6 years 237 days |
|  150 |   260,011 years   |      10,400 years | 37 years 225 days |
|  155 | 1,470,848 years   |      58,833 years |         212 years |
|  160 | 8,320,376 years   |     332,815 years |       1,203 years |
|------+-------------------+-------------------|-------------------|

Looks like a "world record" would be 120 bits.

Edit: added timings for the fastest (June 2019) top500 supercomputer - Summit.

[BurtW]

Hey, I got the math right this time!  (pats self on back)

But, I did not go look up the original source for the world record and trusted someone else's post on the number.  I have fixed my post above and taken back my pat on the back.

[Firebox]

#100 - af55fc59c335c8ec67ed24826

Lucky with only 69% of the expected time - 1d 22:49:48 of the 2d 19:46:27 expected.

Great!  zielar can fill in the #100 entry in the table in the OP.  Congrats on your 1 BTC (approx $10,000) bounty!

+ about 320 USD from BCH Address.

The last one would be:

#160 = 80.0 bits of security will be about 3 x 230.0 = about 3,221,225,472 days = 8,819,234 years

No problem, we will wait 

[almightyruler]

What is your expected time for #105?

I was using 4x Tesla V100 for it. Here is a table with expected times:

|------+-------------------+-------------------|
| bits |      4x V100      |     100x V100     |
|------+-------------------+-------------------|
|  100 |       2d 19:52:51 |          02:42:54 |
|  105 |           16 days |          15:21:34 |
|  110 |           90 days |       3d 14:53:14 |
|  115 |  1 year  147 days |           20 days |
|  120 |  7 years 341 days |          116 days |
|  125 | 44 years 323 days |  1 year  290 days |
|  130 |       253 years   | 10 years  57 days |
|  135 |     1,436 years   | 57 years 166 days |
|  140 |     8,125 years   |         325 years |
|  145 |    45,964 years   |       1,838 years |
|  150 |   260,011 years   |      10,400 years |
|  155 | 1,470,848 years   |      58,833 years |
|  160 | 8,320,376 years   |     332,815 years |
|------+-------------------+-------------------|

Looks like a "world record" would be 120 bits.

Congratulations on your find! Now go buy some cloud GPU time with your big bounty and crack the next one.

[bigvito19]

01 0000000000000000000000000000000000000000000000000000000000000001 1BgGZ9tcN4rm9KBzDn7KprQz87SZ26SAMH
02 0000000000000000000000000000000000000000000000000000000000000003 1CUNEBjYrCn2y1SdiUMohaKUi4wpP326Lb
03 0000000000000000000000000000000000000000000000000000000000000007 19ZewH8Kk1PDbSNdJ97FP4EiCjTRaZMZQA
04 0000000000000000000000000000000000000000000000000000000000000008 1EhqbyUMvvs7BfL8goY6qcPbD6YKfPqb7e
05 0000000000000000000000000000000000000000000000000000000000000015 1E6NuFjCi27W5zoXg8TRdcSRq84zJeBW3k
06 0000000000000000000000000000000000000000000000000000000000000031 1PitScNLyp2HCygzadCh7FveTnfmpPbfp8
07 000000000000000000000000000000000000000000000000000000000000004c 1McVt1vMtCC7yn5b9wgX1833yCcLXzueeC
08 00000000000000000000000000000000000000000000000000000000000000e0 1M92tSqNmQLYw33fuBvjmeadirh1ysMBxK
09 00000000000000000000000000000000000000000000000000000000000001d3 1CQFwcjw1dwhtkVWBttNLDtqL7ivBonGPV
10 0000000000000000000000000000000000000000000000000000000000000202 1LeBZP5QCwwgXRtmVUvTVrraqPUokyLHqe
11 0000000000000000000000000000000000000000000000000000000000000483 1PgQVLmst3Z314JrQn5TNiys8Hc38TcXJu
12 0000000000000000000000000000000000000000000000000000000000000a7b 1DBaumZxUkM4qMQRt2LVWyFJq5kDtSZQot
13 0000000000000000000000000000000000000000000000000000000000001460 1Pie8JkxBT6MGPz9Nvi3fsPkr2D8q3GBc1
14 0000000000000000000000000000000000000000000000000000000000002930 1ErZWg5cFCe4Vw5BzgfzB74VNLaXEiEkhk
15 00000000000000000000000000000000000000000000000000000000000068f3 1QCbW9HWnwQWiQqVo5exhAnmfqKRrCRsvW
16 000000000000000000000000000000000000000000000000000000000000c936 1BDyrQ6WoF8VN3g9SAS1iKZcPzFfnDVieY
17 000000000000000000000000000000000000000000000000000000000001764f 1HduPEXZRdG26SUT5Yk83mLkPyjnZuJ7Bm
18 000000000000000000000000000000000000000000000000000000000003080d 1GnNTmTVLZiqQfLbAdp9DVdicEnB5GoERE
19 000000000000000000000000000000000000000000000000000000000005749f 1NWmZRpHH4XSPwsW6dsS3nrNWfL1yrJj4w
20 00000000000000000000000000000000000000000000000000000000000d2c55 1HsMJxNiV7TLxmoF6uJNkydxPFDog4NQum
21 00000000000000000000000000000000000000000000000000000000001ba534 14oFNXucftsHiUMY8uctg6N487riuyXs4h
22 00000000000000000000000000000000000000000000000000000000002de40f 1CfZWK1QTQE3eS9qn61dQjV89KDjZzfNcv
23 0000000000000000000000000000000000000000000000000000000000556e52 1L2GM8eE7mJWLdo3HZS6su1832NX2txaac
24 0000000000000000000000000000000000000000000000000000000000dc2a04 1rSnXMr63jdCuegJFuidJqWxUPV7AtUf7
25 0000000000000000000000000000000000000000000000000000000001fa5ee5 15JhYXn6Mx3oF4Y7PcTAv2wVVAuCFFQNiP
26 000000000000000000000000000000000000000000000000000000000340326e 1JVnST957hGztonaWK6FougdtjxzHzRMMg
27 0000000000000000000000000000000000000000000000000000000006ac3875 128z5d7nN7PkCuX5qoA4Ys6pmxUYnEy86k
28 000000000000000000000000000000000000000000000000000000000d916ce8 12jbtzBb54r97TCwW3G1gCFoumpckRAPdY
29 0000000000000000000000000000000000000000000000000000000017e2551e 19EEC52krRUK1RkUAEZmQdjTyHT7Gp1TYT
30 000000000000000000000000000000000000000000000000000000003d94cd64 1LHtnpd8nU5VHEMkG2TMYYNUjjLc992bps
31 000000000000000000000000000000000000000000000000000000007d4fe747 1LhE6sCTuGae42Axu1L1ZB7L96yi9irEBE
32 00000000000000000000000000000000000000000000000000000000b862a62e 1FRoHA9xewq7DjrZ1psWJVeTer8gHRqEvR
33 00000000000000000000000000000000000000000000000000000001a96ca8d8 187swFMjz1G54ycVU56B7jZFHFTNVQFDiu
34 000000000000000000000000000000000000000000000000000000034a65911d 1PWABE7oUahG2AFFQhhvViQovnCr4rEv7Q
35 00000000000000000000000000000000000000000000000000000004aed21170 1PWCx5fovoEaoBowAvF5k91m2Xat9bMgwb
36 00000000000000000000000000000000000000000000000000000009de820a7c 1Be2UF9NLfyLFbtm3TCbmuocc9N1Kduci1
37 0000000000000000000000000000000000000000000000000000001757756a93 14iXhn8bGajVWegZHJ18vJLHhntcpL4dex
38 00000000000000000000000000000000000000000000000000000022382facd0 1HBtApAFA9B2YZw3G2YKSMCtb3dVnjuNe2
39 0000000000000000000000000000000000000000000000000000004b5f8303e9 122AJhKLEfkFBaGAd84pLp1kfE7xK3GdT8
40 000000000000000000000000000000000000000000000000000000e9ae4933d6 1EeAxcprB2PpCnr34VfZdFrkUWuxyiNEFv
41 00000000000000000000000000000000000000000000000000000153869acc5b 1L5sU9qvJeuwQUdt4y1eiLmquFxKjtHr3E
42 000000000000000000000000000000000000000000000000000002a221c58d8f 1E32GPWgDyeyQac4aJxm9HVoLrrEYPnM4N
43 000000000000000000000000000000000000000000000000000006bd3b27c591 1PiFuqGpG8yGM5v6rNHWS3TjsG6awgEGA1
44 00000000000000000000000000000000000000000000000000000e02b35a358f 1CkR2uS7LmFwc3T2jV8C1BhWb5mQaoxedF
45 0000000000000000000000000000000000000000000000000000122fca143c05  1NtiLNGegHWE3Mp9g2JPkgx6wUg4TW7bbk
46 00000000000000000000000000000000000000000000000000002ec18388d544 1F3JRMWudBaj48EhwcHDdpeuy2jwACNxjP
47 00000000000000000000000000000000000000000000000000006cd610b53cba 1Pd8VvT49sHKsmqrQiP61RsVwmXCZ6ay7Z
48 0000000000000000000000000000000000000000000000000000ade6d7ce3b9b 1DFYhaB2J9q1LLZJWKTnscPWos9VBqDHzv
49 000000000000000000000000000000000000000000000000000174176b015f4d 12CiUhYVTTH33w3SPUBqcpMoqnApAV4WCF
50 00000000000000000000000000000000000000000000000000022bd43c2e9354 1MEzite4ReNuWaL5Ds17ePKt2dCxWEofwk
51 00000000000000000000000000000000000000000000000000075070a1a009d4 1NpnQyZ7x24ud82b7WiRNvPm6N8bqGQnaS
52 000000000000000000000000000000000000000000000000000efae164cb9e3c  15z9c9sVpu6fwNiK7dMAFgMYSK4GqsGZim
53 00000000000000000000000000000000000000000000000000180788e47e326c 15K1YKJMiJ4fpesTVUcByoz334rHmknxmT
54 00000000000000000000000000000000000000000000000000236fb6d5ad1f43  1KYUv7nSvXx4642TKeuC2SNdTk326uUpFy
55 000000000000000000000000000000000000000000000000006abe1f9b67e114 1LzhS3k3e9Ub8i2W1V8xQFdB8n2MYCHPCa
56 000000000000000000000000000000000000000000000000009d18b63ac4ffdf   17aPYR1m6pVAacXg1PTDDU7XafvK1dxvhi
57 00000000000000000000000000000000000000000000000001eb25c90795d61c 15c9mPGLku1HuW9LRtBf4jcHVpBUt8txKz
58 00000000000000000000000000000000000000000000000002c675b852189a21 1Dn8NF8qDyyfHMktmuoQLGyjWmZXgvosXf
59 00000000000000000000000000000000000000000000000007496cbb87cab44f  1HAX2n9Uruu9YDt4cqRgYcvtGvZj1rbUyt
60 0000000000000000000000000000000000000000000000000fc07a1825367bbe  1Kn5h2qpgw9mWE5jKpk8PP4qvvJ1QVy8su
61 00000000000000000000000000000000000000000000000013C96A3742F64906 1AVJKwzs9AskraJLGHAZPiaZcrpDr1U6AB
62 000000000000000000000000000000000000000000000000363D541EB611ABEE 1Me6EfpwZK5kQziBwBfvLiHjaPGxCKLoJi                 
63 0000000000000000000000000000000000000000000000007CCE5EFDACCF6808 1NpYjtLira16LfGbGwZJ5JbDPh3ai9bjf4

65 000000000000000000000000000000000000000000000001A838B13505B26867 18ZMbwUFLMHoZBbfpCjUJQTCMCbktshgpe

70 0000000000000000000000000000000000000000000000349B84B6431A6C4EF1 19YZECXj3SxEZMoUeJ1yiPsw8xANe7M7QR

75 0000000000000000000000000000000000000000000004C5CE114686A1336E07 1J36UjUByGroXcCvmj13U6uwaVv9caEeAt
 
80 00000000000000000000000000000000000000000000ea1a5c66dcc11b5ad180  1BCf6rHUW6m3iH2ptsvnjgLruAiPQQepLe

85 00000000000000000000000000000000000000000011720c4f018d51b8cebba8  1Kh22PvXERd2xpTQk3ur6pPEqFeckCJfAr

90 000000000000000000000000000000000000000002ce00bb2136a445c71e85bf  1L12FHH2FHjvTviyanuiFVfmzCy46RRATU

95 0000000000000000000000000000000000000000527a792b183c7f64a0e8b1f4  19eVSDuizydXxhohGh8Ki9WY9KsHdSwoQC

100 000000000000000000000000000000000000000af55fc59c335c8ec67ed24826 1KCgMv8fo2TPBpddVi9jqmMmcne9uSNJ5F

[racminer]

Update

format #n x%    --> n is case #n and x is how far in % is the key from the lower bound of the corresponding keyspace.

#08 75% ,  #09  82% ,  #10  00% ,  #11  13% ,  #12  31% ,  #13  27% ,   #14  29% ,  #15  64% ,
#16  57% ,  #17  46% ,  #18  52% ,  #19  36% ,  #20  65% ,  #21  73% ,  #22  43% ,  #23  33% ,
#24  72% ,  #25  98% ,  #26  63% ,  #27  67% ,  #28  70% ,  #29  49% ,  #30  92% ,  #31  96% ,
#32  44% ,  #33  66% ,  #34  65% ,  #35  17% ,  #36  23% ,  #37  46% ,  #38  07% ,  #39  18% ,
#40  83% ,  #41  33% ,  #42  32% ,  #43  68% ,  #44  75% ,  #45  14% ,  #46  46% ,  #47  70% ,
#48  36% ,  #49  45% ,  #50  09% ,  #51  83% ,  #52  87% ,  #53  50% ,  #54  11% ,  #55  67% ,
#56  23% ,  #57  92% ,  #58  39% ,  #59  82% ,  #60  97% ,  #61  24% ,  #63  95% ,  #65  66% ,
#70  64% ,  #75  19% ,  #80  83% ,  #85  09% ,  #90  40% ,  #95  29% ,  #100  37%   

He is the resulting histogram (10 bins) which display how these keys are distributed

   0% -  10%        ∎∎∎∎
 10% -  20%        ∎∎∎∎∎∎
 20% -  30%        ∎∎∎∎∎∎
 30% -  40%        ∎∎∎∎∎∎∎∎
 40% -  50%        ∎∎∎∎∎∎∎∎
 50% -  60%        ∎∎∎
 60% -  70%        ∎∎∎∎∎∎∎∎∎∎
 70% -  80%        ∎∎∎∎∎∎
 80% -  90%        ∎∎∎∎∎∎
 90% - 100%       ∎∎∎∎∎∎

[paniker]

i think today/tomorrow i open 62

[paniker]

Amazing!
Some could change his life with 'simply' solving this one

yap

i studying python + mathematics + probability theory + bitcoin insideout)))
)) oit's really interesting

[Firebox]

drotika, open your PM for newbies please.

[pikachunakapika]

Drotika:
Bit: 75
Pubkey: 049f6eee498ebd1f4430e9af95e212c365da105b525973b59b17bcf4c4cda3f71da4750479a47af b676ebcc0e7ff10e116c2b810c173f602ae0d95602b1a26fd2c
Pubkey (compressed): 029f6eee498ebd1f4430e9af95e212c365da105b525973b59b17bcf4c4cda3f71d
Address: 1DdM6MipUFcHADvxSjg2NvNvDj4eU9Y7sP
Address (compressed): 1HzpRSSBdpgFBwq2P7a8fvAssVimy9d3RP

Sorry, but 75 bit is easy with pollard kangaroo

[PrivatePerson]

https://github.com/ralphleon/Python-Algorithms/blob/master/Cryptology/pollard.py
https://gist.github.com/natmchugh/7dbd7e4f7c55d915db1e
https://gist.github.com/thomdixon/dd1e280681f16535fbf1

which one is it?