Bitcoin puzzle transaction ~32 BTC prize to who solves it

[oldbute]

Why the fuck am I now downloading http://www.sagemath.org/ ?

Please stay focused. I'm refreshing the Marshal Long thread every few minutes

[Gleb Gamow]

Why the fuck am I now downloading http://www.sagemath.org/ ?

That is why everyone calls you Gleb "Gullible" Gamow

Any day now I should be able to open what I downloaded. Hope there's eggnog inside for my efforts.

[DannyHamilton]

Since I had a bit of time on my hands (and I wanted to try my hand at writing a program to generate bitcoin addresses from private keys), I put together a C program that attempts to brute force as many of these addresses as it can.

The program starts with a private key of 2⁰-1 and then increments private keys until it finds the first address.
Then it skips to 2¹-1 and increments private keys until it finds the second address.
Then it skips to 2²-1 and increments private keys until it finds the third address.
Then it skips to 2³-1 and increments private keys until it finds the fourth address.
And so on until it gets to the 51st address.

It's been running for a maybe a half hour now and I've gotten all the private keys through the 24th address (1rSnXMr63jdCuegJFuidJqWxUPV7AtUf7)

I expect each additional address to take twice as long as the previous address, so I doubt I'll get to 50 (or even 35) addresses the way the program is currently written.  I'll need to optimize it more if I can find the time.

Possible speed improvements (placing these here as a reminder to myself):
Instead of computing the full address, I should convert each target address to its binary RIPEMD160 hash value. Then when checking private keys, I don't need to add the version byte, compute the checksum, and convert to base58.  Since I'm currently doing that for every private key that I attempt, I suspect that I'd get a significant performance improvement.

Instead of attempting the private keys in order, I wonder if it would be better to first try every binary combination where half the digits are zeros, then every binary combination where half+1 of the digits are zeros, then every binary combination where half-1 of the digits are zeros, then every binary combination where half+2 of the digits are zeros, then every binary combination where half-2 of the digits are zeros, and so on.  This shouldn't make things any slower, but depending on how the private keys were chosen in the first place, it may result in a performance improvement.

Clean up the code, and strip out all the unnecessary functions.  The program was first written as a generic utility that accepted a single private key as a command line argument and wrote the resulting bitcoin address to stdout.  Then I butchered the program into something that could attempt to brute force these addresses. The idea was first just to see how fast or slow it would be without any improvements.  Now that I've got a feel for it, there's a lot of old code that either isn't being used or is not handling the process efficiently.

[NorrisK]

Nice attempt DannyHamilton! There must be a way to make it much more efficient as the last three addresses were found so fast it couldn't have been by brute forcing.

Maybe if we learn a bit more from how the numbers were generated it could greatly optimize the program.

[shorena]

Nice attempt DannyHamilton! There must be a way to make it much more efficient as the last three addresses were found so fast it couldn't have been by brute forcing.

Maybe if we learn a bit more from how the numbers were generated it could greatly optimize the program.

"7" and "8" are close together as well. Even if the numbers are created randomly is not that unreasonable to assume that a few numbers in the series are close together.

@Danny does the tool you wrote/modified support using a GPU by any chance? I would suspect thats the only way to get to 50+ bit within a reasonable amount of time. If we assume similar performance to vanitygen, we can expect 30-40 million keys per modern GPU.

[jaydipmodhwadia]

Nice attempt DannyHamilton! There must be a way to make it much more efficient as the last three addresses were found so fast it couldn't have been by brute forcing.

Maybe if we learn a bit more from how the numbers were generated it could greatly optimize the program.

"7" and "8" are close together as well. Even if the numbers are created randomly is not that unreasonable to assume that a few numbers in the series are close together.

@Danny does the tool you wrote/modified support using a GPU by any chance? I would suspect thats the only way to get to 50+ bit within a reasonable amount of time. If we assume similar performance to vanitygen, we can expect 30-40 million keys per modern GPU.

Shorena, I think you have a gtx 970? If so, that would be a faster way of making the program which cracks the keys quicker however, this depends on whether the program supports the cracking via a gpu...

How much of a faster process would it be? 200%?

[shorena]

Nice attempt DannyHamilton! There must be a way to make it much more efficient as the last three addresses were found so fast it couldn't have been by brute forcing.

Maybe if we learn a bit more from how the numbers were generated it could greatly optimize the program.

"7" and "8" are close together as well. Even if the numbers are created randomly is not that unreasonable to assume that a few numbers in the series are close together.

@Danny does the tool you wrote/modified support using a GPU by any chance? I would suspect thats the only way to get to 50+ bit within a reasonable amount of time. If we assume similar performance to vanitygen, we can expect 30-40 million keys per modern GPU.

Shorena, I think you have a gtx 970?

Yes, but I am not at home until January 2nd.

If so, that would be a faster way of making the program which cracks the keys quicker however, this depends on whether the program supports the cracking via a gpu...

How much of a faster process would it be? 200%?

Not sure what performance Danny gets out of their CPU. Speed-up for a GPU is more in terms of 20-60 times vs. a CPU

[Bulista]

-snip-

If so, that would be a faster way of making the program which cracks the keys quicker however, this depends on whether the program supports the cracking via a gpu...

How much of a faster process would it be? 200%?

Not sure what performance Danny gets out of their CPU. Speed-up for a GPU is more in terms of 20-60 times vs. a CPU

He said he got to the #24 in half an hour, that's something like 9684243 per 30 minutes, 5380 per second.

[amaclin]

Instead of computing the full address, I should convert each target address to its binary RIPEMD160 hash value

You do not even need to use addresses.
You can get public keys from these 50 privkeys from the blockchain

[DannyHamilton]

- snip -
Not sure what performance Danny gets out of their CPU.

I'm on a late 2013 Mac Book Pro.

• 2.6 GHz Intel Core i5
• 16 GB 1600 MHz DDR3

As for graphics, the specs state:

• Intel Iris 1536 MB

@Danny does the tool you wrote/modified support using a GPU by any chance?

Nope.  I've never done any GPU programming.  Like, ever in my entire life.  So for my first attempt I just jumped in to what I was most familiar with. "C" programming for a CPU.  Making use of the GPU would be an interesting challenge, I hadn't even thought of it.  Maybe I'll see if I can find some time in the next few days to do that.  If I do, maybe I'll see if I can find a friend with a better graphics card than me to try running it.

You do not even need to use addresses.
You can get public keys from these 50 privkeys from the blockchain

True, the 50 that are already taken can be figured out using the public key.  However, if I was going to have any chance at finding the next un-taken value then I needed a program that works with the RIPEMD160 hash.

[Soros Shorts]

I haven't done any Bitcoin programming in a while. Is Sipa's secp256k1 libary still the fastest code available for computing the public key from a private key?

[DannyHamilton]

I haven't done any Bitcoin programming in a while. Is Sipa's secp256k1 libary still the fastest code available for computing the public key from a private key?

I don't know.  For the purposes of my program I just used openssl's EC_POINT_mul()

Code:

BIGNUM *get_ecdsa_bn_pubkey_from_privkey(BIGNUM *bn_privkey, BN_CTX *ctx)
{
        EC_KEY    *eckey   = NULL;
        EC_POINT  *pub_key = NULL;
  const EC_GROUP  *group   = NULL;
        BIGNUM    *bn_pubkey;

  bn_pubkey = BN_new();

  eckey = EC_KEY_new_by_curve_name(NID_secp256k1);
  group = EC_KEY_get0_group(eckey);
  pub_key = EC_POINT_new(group);

  EC_KEY_set_private_key(eckey,bn_privkey);

  EC_POINT_mul(group, pub_key, bn_privkey, NULL, NULL, ctx);

  return EC_POINT_point2bn(group, pub_key, POINT_CONVERSION_COMPRESSED, bn_pubkey, ctx);
}

Clearly since I'm re-setting eckey, group, and pub_key in the beginning of this function every time, I've probably got room for performance improvement here.

[Bulista]

@Danny, Did you get already any results > #24?

[Gleb Gamow]

Why hasn't this blog post been mentioned yet on this thread?: http://blog.richardkiss.com/?p=371

The Bitcoin address is the hashed base 58 representation of the hash160 value.

The bu utility will accept input in nearly any format, automatically determining the input type, and display output of all values that can calculated. (Obviously if you enter a Bitcoin address, you won't get the corresponding WIF!)


$ bu 55066263022277343669578718895168534326250603453777594175500187360389116729240,32670510020758816978083085130507043184471273380659243275938904335757337482424
public pair x:   55066263022277343669578718895168534326250603453777594175500187360389116729240
public pair y:   32670510020758816978083085130507043184471273380659243275938904335757337482424
  x as hex:      79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
  y as hex:      483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
even
key pair as sec: 0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
  uncompressed:  0479be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798\
                   483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
hash160:         751e76e8199196d454941c45d1b3a323f1433bd6
  uncompressed:  91b24bf9f5288532960ac687abb035127b1d28a5
Bitcoin address: 1BgGZ9tcN4rm9KBzDn7KprQz87SZ26SAMH
  uncompressed:  1EHNa6Q4Jz2uvNExL497mE43ikXhwF6kZm

Mentioned in the OP: https://blockchain.info/tx/08389f34c98c606322740c0be6a7125d9860bb8d5cb182c02f98461e5fa6cd15



Even Peter Todd mentions the 1BgGZ9tcN4rm9KBzDn7KprQz87SZ26SAMH address January 2013:

EDIT: changed title

Code:

0100000001d1b311d665b94ad270007deeaa696d487ea0bcd2d11e2c9a5407e7d25097f0ed000000006c493046022100a940f6147a70b98fa7f5bd0e76156ca71347207fca0336c93ce1b5165d653011022100ef0cc31be261178074e1cd854d4ea47e2b62d7ac5add4f1ae50474d841b60ce60121028f2bb71ec2c796cab46d5b61c28ad6cde73dacacf60f18943788053d6040eacdffffffff01009f240000000000dc4cc0010000000127478b07dae63322d1999419115cf287c69ff0f11de3f96d46df6926de61143c010000006b483045022100cca50bfed991240a7603eea19340f6e24102b29db2dfcc56fdfe549dacddcc6402207eefe2688670d349615ed184d1f84ac54365afd258524e55266c992ce2d68b7f012102ff9d6e0c33fb3cfc677857d2cd654db91fe051811433654d25442ee0182dac52000000000180969800000000001976a914751e76e8199196d454941c45d1b3a323f1433bd688accc5003007576a914fb99bed1a4ea8d1d01d879581fce07b27ab5357f88ac00000000

{
    "txid" : "2bf4ff04b40d03ff71570877d8267aed91d3595d172737d096241d08277135e2",
    "version" : 1,
    "locktime" : 0,
    "vin" : [
        {
            "txid" : "edf09750d2e707549a2c1ed1d2bca07e486d69aaee7d0070d24ab965d611b3d1",
            "vout" : 0,
            "scriptSig" : {
                "asm" : "3046022100a940f6147a70b98fa7f5bd0e76156ca71347207fca0336c93ce1b5165d653011022100ef0cc31be261178074e1cd854d4ea47e2b62d7ac5add4f1ae50474d841b60ce601 028f2bb71ec2c796cab46d5b61c28ad6cde73dacacf60f18943788053d6040eacd",
                "hex" : "493046022100a940f6147a70b98fa7f5bd0e76156ca71347207fca0336c93ce1b5165d653011022100ef0cc31be261178074e1cd854d4ea47e2b62d7ac5add4f1ae50474d841b60ce60121028f2bb71ec2c796cab46d5b61c28ad6cde73dacacf60f18943788053d6040eacd"
            },
            "sequence" : 4294967295
        }
    ],
    "vout" : [
        {
            "value" : 0.02400000,
            "n" : 0,
            "scriptPubKey" : {
                "asm" : "010000000127478b07dae63322d1999419115cf287c69ff0f11de3f96d46df6926de61143c010000006b483045022100cca50bfed991240a7603eea19340f6e24102b29db2dfcc56fdfe549dacddcc6402207eefe2688670d349615ed184d1f84ac54365afd258524e55266c992ce2d68b7f012102ff9d6e0c33fb3cfc677857d2cd654db91fe051811433654d25442ee0182dac52000000000180969800000000001976a914751e76e8199196d454941c45d1b3a323f1433bd688accc500300 OP_DROP OP_DUP OP_HASH160 fb99bed1a4ea8d1d01d879581fce07b27ab5357f OP_EQUALVERIFY OP_CHECKSIG",
                "hex" : "4cc0010000000127478b07dae63322d1999419115cf287c69ff0f11de3f96d46df6926de61143c010000006b483045022100cca50bfed991240a7603eea19340f6e24102b29db2dfcc56fdfe549dacddcc6402207eefe2688670d349615ed184d1f84ac54365afd258524e55266c992ce2d68b7f012102ff9d6e0c33fb3cfc677857d2cd654db91fe051811433654d25442ee0182dac52000000000180969800000000001976a914751e76e8199196d454941c45d1b3a323f1433bd688accc5003007576a914fb99bed1a4ea8d1d01d879581fce07b27ab5357f88ac",
                "type" : "nonstandard"
            }
        }
    ]
}

So what I've done in the above is created a transaction that embeds a different transaction within it using OP_DROP. The inner transaction is as follows:

Code:

{
    "txid" : "8608a914d3e217ebfaa5cf04974a657d5b80b940fd46b9efee823feed43102ef",
    "version" : 1,
    "locktime" : 217292,
    "vin" : [
        {
            "txid" : "3c1461de2669df466df9e31df1f09fc687f25c11199499d12233e6da078b4727",
            "vout" : 1,
            "scriptSig" : {
                "asm" : "3045022100cca50bfed991240a7603eea19340f6e24102b29db2dfcc56fdfe549dacddcc6402207eefe2688670d349615ed184d1f84ac54365afd258524e55266c992ce2d68b7f01 02ff9d6e0c33fb3cfc677857d2cd654db91fe051811433654d25442ee0182dac52",
                "hex" : "483045022100cca50bfed991240a7603eea19340f6e24102b29db2dfcc56fdfe549dacddcc6402207eefe2688670d349615ed184d1f84ac54365afd258524e55266c992ce2d68b7f012102ff9d6e0c33fb3cfc677857d2cd654db91fe051811433654d25442ee0182dac52"
            },
            "sequence" : 0
        }
    ],
    "vout" : [
        {
            "value" : 0.10000000,
            "n" : 0,
            "scriptPubKey" : {
                "asm" : "OP_DUP OP_HASH160 751e76e8199196d454941c45d1b3a323f1433bd6 OP_EQUALVERIFY OP_CHECKSIG",
                "hex" : "76a914751e76e8199196d454941c45d1b3a323f1433bd688ac",
                "reqSigs" : 1,
                "type" : "pubkeyhash",
                "addresses" : [
                    "1BgGZ9tcN4rm9KBzDn7KprQz87SZ26SAMH"
                ]
            }
        }
    ]
}

The inner transaction is fully signed and valid, sending 0.1BTC to 1BgGZ9tcN4rm9KBzDn7KprQz87SZ26SAMH(1) and spending a hefty 0.4BTC in fees. However since nLockTime is set to be a bit over 2000 blocks in the future it'll be some time before anyone can spend it. On the other hand since the first transaction is public, and will be embedded into the blockchain once someone mines it, provided the second transaction is mined after the first the existence of both transactions proves I threw away 0.4BTC in fees to the miners as once the transaction is made public the sender has no control what-so-ever over who mines it. Basically this is a more sophisticated mechanism to achieve the "trusted identities through value destruction" I proposed earlier (https://bitcointalk.org/index.php?topic=91487.msg1007449), with the advantages that this implementation requires just two transactions and as long as nLockTime is set reasonably far into the future the value destruction will always be valid.

The maximum value you can destroy in this manner, assuming the mechanism is known and there are miners watching the blockchain for these special transactions, is then a function of the number of blocks between the two special transactions. Basically a miner could work on getting mining successive blocks, then publishing the whole chain, however that becomes exponentially more difficult and expensive in terms of opportunity cost. 10 or 100 blocks should be plenty. Of course the expected value lost is proportional to the mining power you control, but mining power is pretty well distributed.

An actual implementation can do better than just a simple OP_DROP. For one thing the message should go in the scriptSig to aid pruning. Secondly the inner transaction doesn't need to be provided in full; much of it can be snipped out if a template it used. Even the whole scriptPubKey can be left out if the output always goes to a known address. The minimum required length is just the ~80 byte signature and the 32byte tx id for the input, and at that point you can probably stuff the whole thing into one of the "isStandard OP_DROP" type proposals or similar. Either way, what's important is to agree on a standard so the value destruction is valid.

EDIT: Just to make things clear, double-spending the inner tx isn't a problem. Remember that the whole point of this is to prove after the fact that you threw away bitcoins. If you double-spend the inner tx, you have no proof.

EDIT2: Miners don't have a disincentive to mine the outer. After all, the inner can be published separately and put into the mempool whether or not the outer tx exists. The decision to mine the outer is orthogonal and subject to the same logic as any other transaction.

1) ...which is really throwing away another 0.1BTC...

[dalek]

According to this, that address belongs to Luke Jr.: https://github.com/bitcoinjs/bip21/blob/master/test/fixtures.json

[BurtW]

According to this, that address belongs to Luke Jr.: https://github.com/bitcoinjs/bip21/blob/master/test/fixtures.json

The Bitcoin address 1BgGZ9tcN4rm9KBzDn7KprQz87SZ26SAMH "belongs" to whoever knows the private key.

The private key is 1

So everyone that knows that the private key is 1, including you, now "owns" that address.

BTW the Bitcoin address 1EHNa6Q4Jz2uvNExL497mE43ikXhwF6kZm also has a private key equal to 1 so now, since you know the private key, you also "own" that address.

[unamis76]

According to this, that address belongs to Luke Jr.: https://github.com/bitcoinjs/bip21/blob/master/test/fixtures.json

The Bitcoin address 1BgGZ9tcN4rm9KBzDn7KprQz87SZ26SAMH "belongs" to whoever knows the private key.

The private key is 1

So everyone that knows that the private key is 1, including you, now "owns" that address.

BTW the Bitcoin address 1EHNa6Q4Jz2uvNExL497mE43ikXhwF6kZm also has a private key equal to 1 so now, since you know the private key, you also "own" that address.

What I don't understand exactly is how 1 encodes to a private key. Do I need to follow this in order to get there?

[DannyHamilton]

What I don't understand exactly is how 1 encodes to a private key.

1 doesn't "encode to a private key", 1 IS a private key.

An ECDSA private key is simply a number.  For bitcoin, it is ANY number between 1 and 115792089237316195423570985008687907852837564279074904382605163141518161494336
(when represented in base 10)

That number can be represented in any of various forms such as binary, hexadecimal, octal, decimal, base58, or Wallet Import Format (also known as base58check or WIF).

Perhaps you are asking how to represent the decimal value of 1 in WIF?

[eddie13]

Maybe someone paced this "puzzle" into the blockchain for people to work on so it would like a thermometer of how safe Bitcoin still is. More of these wallets getting cracked is like the temperature going up. By however many wallets in this puzzle have been cracked you can see how close people are to cracking bitcoin itself by each successive address being harder and harder to crack and by the end of the list you would be able to crack any BTC addy..

Maybe this is linked to the "secret alert codes" or something like that so if we ever get close to being able to crack bitcoin (crcaking many/most of these addys) it would be an alert that the cryptography of bitcoin needs to be upgraded to stay ahead of current cracking power..

Assuming all bruteforce and there is no key to the puzzle.

Does this make any sense or do I completely not understand what you guys are on about in this thread? Very possible..

[unamis76]

What I don't understand exactly is how 1 encodes to a private key.

1 doesn't "encode to a private key", 1 IS a private key.

An ECDSA private key is simply a number.  For bitcoin, it is ANY number between 1 and 115792089237316195423570985008687907852837564279074904382605163141518161494336
(when represented in base 10)

That number can be represented in any of various forms such as binary, hexadecimal, octal, decimal, base58, or Wallet Import Format (also known as base58check or WIF).

Perhaps you are asking how to represent the decimal value of 1 in WIF?

Yes, sometimes asking the right questions is also an issue... And I think that's the right question I wanted to ask. Tried fiddling with this but haven't reached a working WIF for 1.

I guess there is yet much more to learn about Bitcoin than I could ever imagine