Computational bounty using output scripts?

[TalkingAntColony]

Say someone sent some BTC to an output with a script of math operations that are equivalent to a complex equation. The input script, or what the redeemer of these BTC needs to supply, is the solution to this equation. The BTC are thus a "bounty" to solving this equation. With a limit of 10kb and 201 instructions, one could come up with some fairly complex equations. By including the text "bounty" in the script, others could be made aware of it.
Has anyone else thought about this? Do you think we will ever see this become a feasible idea?

Example 1: find the square root of 9
ScriptPubKey: BOUNTY OP_DROP OP_DUP OP_MUL 9 OP_EQUAL
ScriptSig: 3
Explanation: squares the input and checks if it is equal to 9

Note: OP_MUL is currently disabled...

Example 2: find a SHA256 hash collision
ScriptPubKey: BOUNTY OP_DROP OP_2DUP OP_EQUAL OP_IF OP_RETURN OP_ELSE OP_SHA256 OP_SWAP OP_SHA256 OP_EQUAL OP_ENDIF
ScriptSig: <string1> <string2>
Explanation: Check that string1 and string2 are not equal, then SHA256 each one and check that they are equal

[etotheipi]

The problem is that there is nothing stopping the miners from taking the solution that you just submitted in a sigscript, and putting it their own transaction to themselves (and dropping yours).  In fact, any of your peers could replace the TxOut to themselves before forwarding to other peers/miners.   It's because there's no signature field that locks the TxOuts (of the redeeming script) into the sigscript. 

You'd have to mine it yourself, so the first time anyone sees it is after it's already in a block.  Better hope it's not orphaned!

[jackjack]

Etotheipi ninja'd me with basically the same answer
I just had one more thing in my post: if you really want bounties I think p2pool would reduce the risk of a rogue miner stealing your money
That way honest miners would have the correct transaction (p2pool have good connections with big pools I guess)

Even if I'm right that'd just reduce the risk though, I wouldn't play with this kind of things

[TalkingAntColony]

Yes it seems true that the solution finder has no way to protect their claim without mining their own block. I suppose you could add extra conditions to require certain public keys, such as to issue the bounty to specific individuals. You could for instance make a contract with a supercomputing company to find a solution by requiring their public key and signature in addition to whatever other conditions in the script. The problem there is that the funds are locked up unless there is some backup key to redeem them if the company fails to find a solution. Regardless, I think we will see more complex uses for output scripts as time goes on...

[jackjack]

Yes it seems true that the solution finder has no way to protect their claim without mining their own block. I suppose you could add extra conditions to require certain public keys, such as to issue the bounty to specific individuals. You could for instance make a contract with a supercomputing company to find a solution by requiring their public key and signature in addition to whatever other conditions in the script. The problem there is that the funds are locked up unless there is some backup key to redeem them if the company fails to find a solution. Regardless, I think we will see more complex uses for output scripts as time goes on...

Yeah, scripts have HUGE potential
The problem is security and developers' unwillingness to accept more op codes (ie making them standard)

[Gavin Andresen]

The problem is security and developers' unwillingness to accept more op codes (ie making them standard)

Security, yes (including potential for denial-of-service attacks of various sorts).

But demonstrate a spiffy, compelling use of new opcodes on testnet and we'll talk about making them standard.

[LvM]

The problem is that there is nothing stopping the miners from taking the solution that you just submitted in a sigscript, and putting it their own transaction to themselves (and dropping yours).  In fact, any of your peers could replace the TxOut to themselves before forwarding to other peers/miners.   It's because there's no signature field that locks the TxOuts (of the redeeming script) into the sigscript. 

You'd have to mine it yourself, so the first time anyone sees it is after it's already in a block.  Better hope it's not orphaned!

That beats everything!