Topic: Bitcoin puzzle transaction ~32 BTC prize to who solves it - page 293. (Read 208393 times)

EDIT: changed title


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:


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://bitcointalksearch.org/topic/m.1007449), 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...

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?

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

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

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

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

-snip-


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

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

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

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.

That is why everyone calls you Gleb "Gullible" Gamow

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

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

So basically we are back to the one and only brute force impossible option. 

I made some research and I believe that the numbers are results of a polynomial (ring) function.

It also seems that someone already got into this in February 2015. Probably the guy who cashed out the first addresses.
http://pastebin.com/erN0F1ce


If you put for x the values 0 to 15, you will get exactly the first 16 numbers.

[b]f[/b]
-673909/1307674368000*x^15 + 5004253/87178291200*x^14 - 151337/52254720*x^13 + 9320029/106444800*x^12 - 25409989753/14370048000*x^11 + 2192506957/87091200*x^10 - 19011117413/73156608*x^9 + 1200887962891/609638400*x^8 - 3585932821063/326592000*x^7 + 647416874047/14515200*x^6 - 18586394742863/143700480*x^5 + 30899291755337/119750400*x^4 - 274137631043849/825552000*x^3 + 36933161067083/151351200*x^2 - 87781079/1155*x + 1

Just figured out that the formula i have previously posted is missing a +1. if you post x = 0, then 1 comes out. Otherwise the formula would not be correct.

static void Main(string[] args)
        {
            for (int x = 0; x <= 15; x++)
            { 
                double result =
                    -673909 / 1307674368000 * Math.Pow(x, 15)
                    + 5004253 / 87178291200 * Math.Pow(x, 14)
                    - 151337 / 52254720 * Math.Pow(x, 13)
                    + 9320029 / 106444800 * Math.Pow(x, 12)
                    - 25409989753 / 14370048000 * Math.Pow(x, 11)
                    + 2192506957 / 87091200 * Math.Pow(x, 10)
                    - 19011117413 / 73156608 * Math.Pow(x, 9)
                    + 1200887962891 / 609638400 * Math.Pow(x, 8)
                    - 3585932821063 / 326592000 * Math.Pow(x, 7)
                    + 647416874047 / 14515200 * Math.Pow(x, 6)
                    - 18586394742863 / 143700480 * Math.Pow(x, 5)
                    + 30899291755337 / 119750400 * Math.Pow(x, 4)
                    - 274137631043849 / 825552000 * Math.Pow(x, 3)
                    + 36933161067083 / 151351200 * Math.Pow(x, 2)
                    - 87781079 / 1155 * x + 1;

                Console.WriteLine(result);
            }            
            Console.ReadLine();
        }

1
4
1361
96586
1933729
19056176
118685569
532788166
1856709761
5229236764
12049777201
22087674434
27586770721
-1063387064
-145598392351
-598037460674