Zangelbert Bingledack (OP)
Legendary
 Offline
Activity: 1036
Merit: 1000
|
 |
September 20, 2013, 07:04:59 AM
Last edit: September 20, 2013, 08:33:13 AM by Zangelbert Bingledack |
|
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.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
According to NIST and ECRYPT II, the cryptographic algorithms used in
Bitcoin are expected to be strong until at least 2030. (After that, it
will not be too difficult to transition to different algorithms.)
|
|
|
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
|
|
|
|
|
DannyHamilton
Legendary
Offline
Activity: 3388
Merit: 4615
|
|
September 20, 2013, 08:22:03 AM |
|
- snip -
the factors of a certain large prime.
- snip -
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? |
|
|
|
|
Zangelbert Bingledack (OP)
Legendary
Offline
Activity: 1036
Merit: 1000
|
|
September 20, 2013, 08:31:56 AM |
|
- snip -
the factors of a certain large prime.
- snip -
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). |
|
|
|
|
|
techwtf
|
|
September 20, 2013, 10:49:37 AM |
|
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.
|
|
|
|
|
jackjack
Legendary
Offline
Activity: 1176
Merit: 1233
May Bitcoin be touched by his Noodly Appendage
|
|
September 20, 2013, 11:17:40 AM |
|
I don't think it's possible
How could you know if the output address was modified or not?
|
Own address: 19QkqAza7BHFTuoz9N8UQkryP4E9jHo4N3 - Pywallet support: 1AQDfx22pKGgXnUZFL1e4UKos3QqvRzNh5 - Bitcointalk++ script support: 1Pxeccscj1ygseTdSV1qUqQCanp2B2NMM2 Pywallet: instructions. Encrypted wallet support, export/import keys/addresses, backup wallets, export/import CSV data from/into wallet, merge wallets, delete/import addresses and transactions, recover altcoins sent to bitcoin addresses, sign/verify messages and files with Bitcoin addresses, recover deleted wallets, etc. |
|
|
OnkelPaul
Legendary
Offline
Activity: 1039
Merit: 1003
|
|
September 20, 2013, 11:58:01 AM |
|
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
|
|
|
|
jackjack
Legendary
Offline
Activity: 1176
Merit: 1233
May Bitcoin be touched by his Noodly Appendage
|
|
September 20, 2013, 11:59:23 AM |
|
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 |
Own address: 19QkqAza7BHFTuoz9N8UQkryP4E9jHo4N3 - Pywallet support: 1AQDfx22pKGgXnUZFL1e4UKos3QqvRzNh5 - Bitcointalk++ script support: 1Pxeccscj1ygseTdSV1qUqQCanp2B2NMM2 Pywallet: instructions. Encrypted wallet support, export/import keys/addresses, backup wallets, export/import CSV data from/into wallet, merge wallets, delete/import addresses and transactions, recover altcoins sent to bitcoin addresses, sign/verify messages and files with Bitcoin addresses, recover deleted wallets, etc. |
|
|
OnkelPaul
Legendary
Offline
Activity: 1039
Merit: 1003
|
|
September 20, 2013, 12:07:41 PM |
|
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 |
|
|
|
jackjack
Legendary
Offline
Activity: 1176
Merit: 1233
May Bitcoin be touched by his Noodly Appendage
|
|
September 20, 2013, 12:52:36 PM |
|
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. The miner would see your transaction and replace your address with his |
Own address: 19QkqAza7BHFTuoz9N8UQkryP4E9jHo4N3 - Pywallet support: 1AQDfx22pKGgXnUZFL1e4UKos3QqvRzNh5 - Bitcointalk++ script support: 1Pxeccscj1ygseTdSV1qUqQCanp2B2NMM2 Pywallet: instructions. Encrypted wallet support, export/import keys/addresses, backup wallets, export/import CSV data from/into wallet, merge wallets, delete/import addresses and transactions, recover altcoins sent to bitcoin addresses, sign/verify messages and files with Bitcoin addresses, recover deleted wallets, etc. |
|
|
Dabs
Legendary
Offline
Activity: 3416
Merit: 1912
The Concierge of Crypto
|
|
September 20, 2013, 01:23:28 PM |
|
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.
|
|
|
|
Mike Hearn
Legendary
Offline
Activity: 1526
Merit: 1129
|
|
September 20, 2013, 01:37:36 PM |
|
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.
|
|
|
|
|
OnkelPaul
Legendary
Offline
Activity: 1039
Merit: 1003
|
|
September 20, 2013, 02:02:23 PM |
|
The miner would see your transaction and replace your address with his
I see, you're correct. Onkel Paul |
|
|
|
gmaxwell
Moderator
Legendary
Offline
Activity: 4158
Merit: 8382
|
|
September 20, 2013, 04:58:49 PM |
|
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 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). |
|
|
|
|
|
