Bitcoin Forum

Suppose you want to put a bounty on a problem that has a hard-to-find but easy-to-verify (computer-verifiable) solution, such as the factors of a certain prime large number. Would it be possible to create an oracle that would sign a transaction paying the bounty to the first person to send it the solution followed by a (the solver's) Bitcoin address, without enabling anyone else - even those with access to the oracle's code - to steal the funds in the originating wallet? In other words, a piece of code that maintains the ability to sign a transaction to an arbitrary recipient (only those meeting a certain very difficult criterion - this part I assume is possible) while not enabling even people who inspect the code to know the private key.

If this could somehow be done, you could have verifiably guaranteed payouts for certain types of bounties.  

Am I misunderstanding this example?  I mustn't be reading it right, because as far as I can tell this is not a "hard-to-find" solution?

Yeah, oops. Not factors of a prime, of course, but the factors of a large number that is the product of two large, unknown primes (for instance).

I remember that there is a tx a4bfa8ab6435ae5f25dae9d89e4eb67dfa94283ca751f393c1ddc5a837bbc31b,
with its output "OP_HASH256 6fe28c0ab6f1b372c1a6a246ae63f74f931e8365e15a089c68d6190000000000 OP_EQUAL", which can be unlocked with the genesis block.

but if the redeem tx is released, it can be forged so anyone could spend it. some kind of risky.

I don't think it's possible
How could you know if the output address was modified or not?

If it does not matter if the solution is visible in public, you might do it using a bitcoin script, so there would be no external system involved except for the blockchain.
For the example problem of factoring a large number, you might send the bounty in a transaction with a script that checks whether the product of two (or more) input numbers is actually the target number. If you want to be able to retract the bounty in case no solution is found within some time, you can construct the scriptPubKey such that it is a combination of the factor checking code with the normal scriptPubKey logic.
When someone finds a solution, he would post a transaction claiming the bounty and signed with his solution.

Onkel Paul

That still doesn't prevent a miner to steal the coins

Why do you think so? To claim the coins, you need to post a transaction with the solution. There would be no other way (except the possible retraction) to access the coins.
However, a look at https://en.bitcoin.it/wiki/Script indicates that the multiplication operations are disabled - I thought that the whole set of operations specified would actually be available. So my scheme would most likely not work.

Onkel Paul

The miner would see your transaction and replace your address with his

Can't you make the factors of your large number be part of the private key? That way, when the solution is found, he gets to spend the bounty that's sitting at the address.

You only supply the part that can't be provided, depending on the difficulty of your problem, on the assumption that you already know the answer to your problem.

You can't do this on a problem which you don't have an answer to yet.

Perhaps this is a dumb question, but you can have a program for which the source code is public, but it loads a wallet file that is private and that's where the hidden private key is.

I see, you're correct.

Onkel Paul

It's unclear if you've also forbidden the oracle to have access to some secret data. If so, it's trivial.

If not, then what you really was is a zero-knowledge signature-of-knowledge directly in Bitcoin. We may have one of those someday, but we don't today.

Absent that, if you're able to trust the oracle to continue to exist while you solve the problem, then a zero-knowledge contingent payment (https://en.bitcoin.it/wiki/User:Gmaxwell/why_hash_locked) might achieve what you're looking for.  (I'm looking for a fun example to use to actually perform one of these transactions, FWIW).

It would be helpful if you'd sketch out what you're trying to achieve without mention of how you think you can achieve it (e.g. no 'oracles'. Just a "Alice wants to send a secret message to bob, but doesn't trust carol." level description).