Thanks for the quick reply.
I was digging through the bitcoinJ code and had it mostly figured out.
From my understanding, the new clients (that know about this special rule) will do an extra check, but old clients that don't treat it specially will not do the extra check, thus making a situation where an invalid scriptSig evaluation occurs would validate as correct? And anyone trying to spend them will only end up in blocks that are mined by old clients, and those blocks will be orphaned since the majority of the network will do the extra validation. Is this correct?
Topic: Implementing External State Contracts - Feedback Requested - page 3. (Read 11232 times)
P2SH is implemented as a special case in the VerifyScript() routine:
// Additional validation for spend-to-script-hash transactions:
if ((flags & SCRIPT_VERIFY_P2SH) && scriptPubKey.IsPayToScriptHash())
{
if (!scriptSig.IsPushOnly()) // scriptSig must be literals-only
return false; // or validation fails
// stackCopy cannot be empty here, because if it was the
// P2SH HASH <> EQUAL scriptPubKey would be evaluated with
// an empty stack and the EvalScript above would return false.
assert(!stackCopy.empty());
const valtype& pubKeySerialized = stackCopy.back();
CScript pubKey2(pubKeySerialized.begin(), pubKeySerialized.end());
popstack(stackCopy);
if (!EvalScript(stackCopy, pubKey2, txTo, nIn, flags, nHashType))
return false;
if (stackCopy.empty())
return false;
return CastToBool(stackCopy.back());
}
So what that does is if the scriptPubKey has the exact magic P2SH format, there are actually two scripts that run, three if you include the scriptSig: first the scriptSig is evaluated as it normally would be, creating a stack. A copy of this stack is made, called stackCopy. Then the scriptPubKey is evaluated using that stack. Up to this point everything is as normally happens.
However if the scriptPubKey matches the magic P2SH format exactly the top item of the stackCopy is removed and deserialized. This is called the pubKey2, basically scriptPubKey #2. It's evaluated with what remains on the stack and if it also returns true, the whole script is considered a success.
The key that I think you missed is that P2SH is handled specially; the second round of validation logic isn't expressed in the script itself. Way back when P2SH was being designed an alternate proposal to this whole mechanism was called OP_EVAL which would have simply executed a serialized script, but it was found that OP_EVAL allowed for recursive evaluation, and loops, and people got scared enough that the code review had missed that so the decision was made to use the much more limited P2SH mechanism instead. There was also Luke-Jr's OP_CHECKHASHVERIFY proposal around that time, but that's a story in of itself.
// Additional validation for spend-to-script-hash transactions:
if ((flags & SCRIPT_VERIFY_P2SH) && scriptPubKey.IsPayToScriptHash())
{
if (!scriptSig.IsPushOnly()) // scriptSig must be literals-only
return false; // or validation fails
// stackCopy cannot be empty here, because if it was the
// P2SH HASH <> EQUAL scriptPubKey would be evaluated with
// an empty stack and the EvalScript above would return false.
assert(!stackCopy.empty());
const valtype& pubKeySerialized = stackCopy.back();
CScript pubKey2(pubKeySerialized.begin(), pubKeySerialized.end());
popstack(stackCopy);
if (!EvalScript(stackCopy, pubKey2, txTo, nIn, flags, nHashType))
return false;
if (stackCopy.empty())
return false;
return CastToBool(stackCopy.back());
}
So what that does is if the scriptPubKey has the exact magic P2SH format, there are actually two scripts that run, three if you include the scriptSig: first the scriptSig is evaluated as it normally would be, creating a stack. A copy of this stack is made, called stackCopy. Then the scriptPubKey is evaluated using that stack. Up to this point everything is as normally happens.
However if the scriptPubKey matches the magic P2SH format exactly the top item of the stackCopy is removed and deserialized. This is called the pubKey2, basically scriptPubKey #2. It's evaluated with what remains on the stack and if it also returns true, the whole script is considered a success.
The key that I think you missed is that P2SH is handled specially; the second round of validation logic isn't expressed in the script itself. Way back when P2SH was being designed an alternate proposal to this whole mechanism was called OP_EVAL which would have simply executed a serialized script, but it was found that OP_EVAL allowed for recursive evaluation, and loops, and people got scared enough that the code review had missed that so the decision was made to use the much more limited P2SH mechanism instead. There was also Luke-Jr's OP_CHECKHASHVERIFY proposal around that time, but that's a story in of itself.
I was able to switch to using the nonce-hash script and it so far has gone very well.
I had some questions about P2SH, though. Here is the example used for it:
scriptSig: [signature] {[pubkey] OP_CHECKSIG}
scriptPubKey: OP_HASH160 [20-byte-hash of {[pubkey] OP_CHECKSIG} ] OP_EQUAL
If I understand how the script processing works, you push all of the scriptSig onto the hash, then start processing the scriptPubKey. I presume that the {[pubkey] OP_CHECKSIG} in this example is a single piece of data that is pushed onto the stack, and not the actual operations. It's a bit unclear to me. So assume its just data.
We end up with the stack as:
{[pubkey] OP_CHECKSIG}
[signature]
Then we get the hash operation, which will replace the top item on the stack with the 20-byte-hash of that data. So the stack is now:
[hash]
[signature]
We add another hash that should match:
[hash]
[hash]
[signature]
Then we get OP_EQUAL, and the top two items are equal, so we have
1
[signature]
on the stack, and it's valid.
This makes it seem like the signature is not needed at all. I must be missing something. What is evaluating the script that's part of the scriptSig?
I had some questions about P2SH, though. Here is the example used for it:
scriptSig: [signature] {[pubkey] OP_CHECKSIG}
scriptPubKey: OP_HASH160 [20-byte-hash of {[pubkey] OP_CHECKSIG} ] OP_EQUAL
If I understand how the script processing works, you push all of the scriptSig onto the hash, then start processing the scriptPubKey. I presume that the {[pubkey] OP_CHECKSIG} in this example is a single piece of data that is pushed onto the stack, and not the actual operations. It's a bit unclear to me. So assume its just data.
We end up with the stack as:
{[pubkey] OP_CHECKSIG}
[signature]
Then we get the hash operation, which will replace the top item on the stack with the 20-byte-hash of that data. So the stack is now:
[hash]
[signature]
We add another hash that should match:
[hash]
[hash]
[signature]
Then we get OP_EQUAL, and the top two items are equal, so we have
1
[signature]
on the stack, and it's valid.
This makes it seem like the signature is not needed at all. I must be missing something. What is evaluating the script that's part of the scriptSig?
Alp: This work looks really interesting. I'm also excited how Peter figured out how to use the nonce-based way of implementing it to protect savings accounts in wallets, really nice work!
Between these two uses, and existing uses for multiple CHECK(MULTI)SIG's in a scriptPubKey, I think it makes sense to create a whitelist for opcodes least likely to cause us problems and allow them in serialized scripts for use with P2SH. That removes the UTXO bloat problem of allowing anything, and limits the risk from opcodes we haven't implemented correctly. (I left out arithmetic from my initial whitelist, just boolean AND and OR for now) I posted my full proposal to the bitcoin-development email list: http://www.mail-archive.com/[email protected]/msg02606.html
You should post your thoughts to the list, especially to figure out if the restriction to just boolean opcodes is ok for the first trials. I think it is, we can always extend it later, but if you have a really good argument for arithmetic make your case. Just remember that there have been some serious bugs found related to arithmetic before, so IMO playing it safe initially is a good idea.
Between these two uses, and existing uses for multiple CHECK(MULTI)SIG's in a scriptPubKey, I think it makes sense to create a whitelist for opcodes least likely to cause us problems and allow them in serialized scripts for use with P2SH. That removes the UTXO bloat problem of allowing anything, and limits the risk from opcodes we haven't implemented correctly. (I left out arithmetic from my initial whitelist, just boolean AND and OR for now) I posted my full proposal to the bitcoin-development email list: http://www.mail-archive.com/[email protected]/msg02606.html
You should post your thoughts to the list, especially to figure out if the restriction to just boolean opcodes is ok for the first trials. I think it is, we can always extend it later, but if you have a really good argument for arithmetic make your case. Just remember that there have been some serious bugs found related to arithmetic before, so IMO playing it safe initially is a good idea.
Another way to process arbitrary data is to regularly publish a list of questions
and ask miners to act as arbiter by encoding a few extra bits per block. Vanitygen abuse perhaps?
Assuming it's about typical general interest prediction market stuff like
Dems win/Reps win, BTCUSD higher/lower than last year, major city nuked/not nuked, etc.
What percentage of pools, and miners voting by proxy, would participate?
Can be a small minority, just significantly more than those who would actively sabotage it
and you have your oracle built directly into the client with no need to access outside data sources.
I had a similar idea, might even be an alt-coin with this type of thing, but there needs to be an incentive to give the right answer. Kenneth Massey (he has a ranking system used in the BCS for college football), has a weighted ranking system where he takes inputs from anyone, and if they don't correlate well to everyone else, they are not weighted as heavily. Perhaps you cold have a system where pick what event actually happened, and if they answer with the majority, they get rewarded from any saboteurs and any fees that people betting might pay for arbitration. Still not sure how it would work, maybe some alt-coin just for answering events whether they occur or not? Might be a lofty goal for down the road, I'm sure someone smart can come up with a way for this to actually work if its possible.
Another reason is that you want to be able to process arbitrary data, like by downloading a web page. Otherwise your oracle has to be specifically programmed to know about every possible kind of event, which sucks. Now, what the hash-checking scripts design does is let you have an arbitrary program structured like this:
Code:
var event_a = get_nonce(0);
var event_b = get_nonce(1);
if (wget("...").contains("blah")) {
reveal(event_a);
} else {
reveal(event_b);
}
Another way to process arbitrary data is to regularly publish a list of questions
and ask miners to act as arbiter by encoding a few extra bits per block. Vanitygen abuse perhaps?
Assuming it's about typical general interest prediction market stuff like
Dems win/Reps win, BTCUSD higher/lower than last year, major city nuked/not nuked, etc.
What percentage of pools, and miners voting by proxy, would participate?
Can be a small minority, just significantly more than those who would actively sabotage it
and you have your oracle built directly into the client with no need to access outside data sources.
Mike: good point about the escrow version of the oracle being able to change output amounts; it's yet another reason why a future scripting system upgrade should allow for spending transactions to be constrained by the script itself. Go ahead and update the wiki.
re: state a nice trick with these oracles is to have a master secret key and use HMAC to calculate the nonces. For instance if I promise to release nonces for the statements "The Steelers won the 2014 Superbowl" and "The Steelers did not win the 2014 Superbowl" I can calculate those nonces with H(master-key, H(statement)), which means I only have to backup one key safely with high security, the backups for the statements aren't as sensitive. It'd be ideal to make all of this into an easy to use standalone app so the oracle could have a dedicated off-line laptop where they type in their statements and nonces and H(nonce)'s are generated securely as needed. Overkill for some applications, but for important stuff that kind of security is worthwhile.
Maps quite nicely to the scripting case too:
where reveal() returns H(secret + H(H(script) + H(statement))) - add a second layer of indirection to what reveal does make it easy to calculate H(nonce)'s in advance with some kind of statement table or something attached to the script.
Note that if the oracle needs to make money for their service, the statements can just as easily be "Alice and Bob: The Steelers won the 2014 Superbowl".
alp: Yup. Listen to Timo's talk on contracts, it's a very clever mechanism and he's done a good job of fleshing out all the details. That said at this point I really think the hash-based mechanism is the most interesting one in that the infrastructure on the oracle's side can be incredibly simple and robust - just what you want to make people confident enough to take on that role. I'd be a lot more hesitant to be setting up an exploitable automated signature signing thing myself until the code was validated much more carefully.
Regarding non-standard transactions you can dodge the problem: have Alice and Bob first jointly create a standard 2 2 CHECKMULTISIG txout. Then jointly spend that txout to the oracle scriptPubKey with a second transaction, but don't broadcast it. (optionally set nLockTime so it can't be broadcast until closer to the date the oracle will release their nonce)
Now when the oracle does release the nonce, if Alice and Bob are willing to co-operate they can just spend that first tx to whomever won the bet. (might as well give whomever party lost the small amount that would have had to be spent on transaction fees to get the larger oracle tx mined as a token of thanks) If either party isn't willing to co-operate, or can't, then use the already signed oracle script as the backup method to complete the transaction.
You only need the non-standard transaction as a backup basically - usually Alice and Bob might as well co-operate given who will get the funds in the end is a foregone conclusion anyway. The advantage is that now even after the transaction has concluded the oracle can't know if their nonce was used at all unless the backup tx has to be used, and it means you can reasonably implement the system now even though the transactions are non-standard.
re: state a nice trick with these oracles is to have a master secret key and use HMAC to calculate the nonces. For instance if I promise to release nonces for the statements "The Steelers won the 2014 Superbowl" and "The Steelers did not win the 2014 Superbowl" I can calculate those nonces with H(master-key, H(statement)), which means I only have to backup one key safely with high security, the backups for the statements aren't as sensitive. It'd be ideal to make all of this into an easy to use standalone app so the oracle could have a dedicated off-line laptop where they type in their statements and nonces and H(nonce)'s are generated securely as needed. Overkill for some applications, but for important stuff that kind of security is worthwhile.
Maps quite nicely to the scripting case too:
Code:
var event_a = get_nonce(0);
var event_b = get_nonce(1);
if (wget("http://foo.org").contains("blah")) {
reveal("http://foo.org did contain blah");
} else {
reveal("http://foo.org didn't contain blah");
}
where reveal() returns H(secret + H(H(script) + H(statement))) - add a second layer of indirection to what reveal does make it easy to calculate H(nonce)'s in advance with some kind of statement table or something attached to the script.
Note that if the oracle needs to make money for their service, the statements can just as easily be "Alice and Bob: The Steelers won the 2014 Superbowl".
alp: Yup. Listen to Timo's talk on contracts, it's a very clever mechanism and he's done a good job of fleshing out all the details. That said at this point I really think the hash-based mechanism is the most interesting one in that the infrastructure on the oracle's side can be incredibly simple and robust - just what you want to make people confident enough to take on that role. I'd be a lot more hesitant to be setting up an exploitable automated signature signing thing myself until the code was validated much more carefully.
Regarding non-standard transactions you can dodge the problem: have Alice and Bob first jointly create a standard 2
Now when the oracle does release the nonce, if Alice and Bob are willing to co-operate they can just spend that first tx to whomever won the bet. (might as well give whomever party lost the small amount that would have had to be spent on transaction fees to get the larger oracle tx mined as a token of thanks) If either party isn't willing to co-operate, or can't, then use the already signed oracle script as the backup method to complete the transaction.
You only need the non-standard transaction as a backup basically - usually Alice and Bob might as well co-operate given who will get the funds in the end is a foregone conclusion anyway. The advantage is that now even after the transaction has concluded the oracle can't know if their nonce was used at all unless the backup tx has to be used, and it means you can reasonably implement the system now even though the transactions are non-standard.
Mike,
If you could update the wiki, it would be great, I bet it is more clear what needs to be changed to you than me.
One thing about the oracle being stateless, I am considering that right now, where the oracle is split into two entities. One that will provide external state, and one that will validate it. The desire for a stateless oracle is nice, but somewhere a state is needed to be maintained (obviously this could be google, a sports website, etc...), I'm just not sure it's as convincing of a use-case and maintaining the nonces seems like a trivial problem. There's a security risk, but keeping the nonces offline and only transferring when needed could at least give some security. Splitting the oracle into a "news service" and a signing service shifts the problem around, and it could make the script simplify to "go check this news service with this event and go get its nonce.". Oracles can be dumb and maintain no state, although the burden just shifts. But in this case, you pretty much eliminate for the oracle, since you program the hashes of the nonce right into the script. Maybe there's a use case for both? When you can easily automate it into a script, the script method, for simple events that will be published in a known way that publishes nonces, use this other way.
retep,
Re: the derivative pubkey, I assume this is mechanism serves a similar purpose to the expression hash in the original proposal? The oracle doesn't want to sign a transaction unless he agrees it should be paid out, and he has no idea what the contract was if he doesn't have a derivative pubkey to use. He can validate that the derivative key was in fact the one that should be generated by the original contract. But if we go with the nonce idea, this all isn't important because oracles become naive to transactions. Do I understand this correct?
I'll update my proposal based on Mike's changes to the Wiki and make sure I have everything correct before working any more on the code.
If you could update the wiki, it would be great, I bet it is more clear what needs to be changed to you than me.
One thing about the oracle being stateless, I am considering that right now, where the oracle is split into two entities. One that will provide external state, and one that will validate it. The desire for a stateless oracle is nice, but somewhere a state is needed to be maintained (obviously this could be google, a sports website, etc...), I'm just not sure it's as convincing of a use-case and maintaining the nonces seems like a trivial problem. There's a security risk, but keeping the nonces offline and only transferring when needed could at least give some security. Splitting the oracle into a "news service" and a signing service shifts the problem around, and it could make the script simplify to "go check this news service with this event and go get its nonce.". Oracles can be dumb and maintain no state, although the burden just shifts. But in this case, you pretty much eliminate for the oracle, since you program the hashes of the nonce right into the script. Maybe there's a use case for both? When you can easily automate it into a script, the script method, for simple events that will be published in a known way that publishes nonces, use this other way.
retep,
Re: the derivative pubkey, I assume this is mechanism serves a similar purpose to the expression hash in the original proposal? The oracle doesn't want to sign a transaction unless he agrees it should be paid out, and he has no idea what the contract was if he doesn't have a derivative pubkey to use. He can validate that the derivative key was in fact the one that should be generated by the original contract. But if we go with the nonce idea, this all isn't important because oracles become naive to transactions. Do I understand this correct?
I'll update my proposal based on Mike's changes to the Wiki and make sure I have everything correct before working any more on the code.
MASTs make a lot of sense.
bitcoinj lacks all the code to do P2SH, it's not even partially implemented. You need to be able to store the scripts in the wallet, the wallet needs to add them to the bloom filter, etc.
The original oracle proposal used scripts that resulted in signing transactions for a few reasons. One is that way you can split up the output values in fractional way rather than it being a binary claim/not claim on an output. For the "when a grandfather dies" use case it makes no difference of course, but for things like bets on currency movements it probably does.
Another reason is that you want to be able to process arbitrary data, like by downloading a web page. Otherwise your oracle has to be specifically programmed to know about every possible kind of event, which sucks. Now, what the hash-checking scripts design does is let you have an arbitrary program structured like this:
and then your oracle script API knows how to manage the hashed nonces behind the scenes.
Oh, a final reason is that the signing based design lets the oracle be basically stateless. Done the above way, the oracle needs to store the nonces and not lose them. It's a relatively minor thing, I think.
The wiki protocol was written years ago, before I knew about the point multiplication trick. I think it does indeed make more sense to do that than use OP_DROP.
This is a nice set of improvements. Does someone want to refresh the wiki article, or shall I do it?
bitcoinj lacks all the code to do P2SH, it's not even partially implemented. You need to be able to store the scripts in the wallet, the wallet needs to add them to the bloom filter, etc.
The original oracle proposal used scripts that resulted in signing transactions for a few reasons. One is that way you can split up the output values in fractional way rather than it being a binary claim/not claim on an output. For the "when a grandfather dies" use case it makes no difference of course, but for things like bets on currency movements it probably does.
Another reason is that you want to be able to process arbitrary data, like by downloading a web page. Otherwise your oracle has to be specifically programmed to know about every possible kind of event, which sucks. Now, what the hash-checking scripts design does is let you have an arbitrary program structured like this:
Code:
var event_a = get_nonce(0);
var event_b = get_nonce(1);
if (wget("...").contains("blah")) {
reveal(event_a);
} else {
reveal(event_b);
}
and then your oracle script API knows how to manage the hashed nonces behind the scenes.
Oh, a final reason is that the signing based design lets the oracle be basically stateless. Done the above way, the oracle needs to store the nonces and not lose them. It's a relatively minor thing, I think.
The wiki protocol was written years ago, before I knew about the point multiplication trick. I think it does indeed make more sense to do that than use OP_DROP.
This is a nice set of improvements. Does someone want to refresh the wiki article, or shall I do it?
Indeed... "If dies, I will make public n such that H(n)==0x4a5e1e4baab89f3a32518a88c31bc8"
Did you have to use that example? 
Disclaimer: Bitcoin leaks a lot of information, don't do these.Heh, of course even just being an oracle for stock prices is probably enough to raise interesting legal questions...
Indeed... "If dies, I will make public n such that H(n)==0x4a5e1e4baab89f3a32518a88c31bc8"
Did you have to use that example? Disclaimer: Bitcoin leaks a lot of information, don't do these. retep - Thanks for the post. I'll need some time to digest to see how to modify my approach based on this.
This should simplify how oracles work quite a bit (and give them some plausible deniability if an oracle service just published nonces for various events).
This should simplify how oracles work quite a bit (and give them some plausible deniability if an oracle service just published nonces for various events).
Indeed... "If
Incidentally, keep in mind you can do "multisignature" oracles easily:
HASH160
HASH160
ADD
HASH160
ADD
1
GREATERTHAN
I'm going to toy around with things a bit and see if I can implement what you proposed. It is quite promising.
The standard/non-standard transaction stuff is something I am aware of, I've been working with non-standard transactions on testnet, so this is not terribly new for me. I'd like to see if I can find something general purpose and simple enough to get traction to be added as a standard transaction if needed, but a good case would have to be made. The OP_DROP proposal already exists, so it was easy to piggy back on that. My first implementation had a complex script similar to what you described in your first post, and Mike suggested I move to the other script. A standard transaction that would work would be far superior, of course, because I wouldn't have to convince anyone, or wait on nodes to upgrade.
Can you explain in slight more detail where I would use P2SH? In particular, which transactions would need to be modified for that to work? I presume the contract transaction. The redemption transaction is already a standard output, so that wouldn't be needed.
The standard/non-standard transaction stuff is something I am aware of, I've been working with non-standard transactions on testnet, so this is not terribly new for me. I'd like to see if I can find something general purpose and simple enough to get traction to be added as a standard transaction if needed, but a good case would have to be made. The OP_DROP
Can you explain in slight more detail where I would use P2SH? In particular, which transactions would need to be modified for that to work? I presume the contract transaction. The redemption transaction is already a standard output, so that wouldn't be needed.
Actually they're both considered non-standard - spending a non-standard transaction makes the transaction non-standard too, see AreInputsStandard()
P2SH is very general: basically the idea is that for any transaction output rather than storing the scriptPubKey itself, store the hash of that script and provide the script when you spend the transaction. This keeps the UTXO set size small - very important - and in this case provides even more plausible deniability for the oracles because they can't see the scripts making use of their service at all until they're spent. For that reason alone I'd strongly recommend you only use P2SH outputs. bitcoinj doesn't support P2SH fully (Mike's been against the idea for ages) but the part that was left out, calculating addresses and the like, is just a few lines of code.
There is one disadvantage to P2SH: your scriptPubKey must fit in 520 bytes due to the limit on the size of any individual PUSHDATA payload. Probably not a big deal - that's a lot of conditions.
In the future we'll probably eventually implement an even more advanced version of P2SH known as merkelized abstract syntax trees. (MAST) Basically the idea is to take the AST of your script, and hash every node, very similar to what is done in a merkle tree. Then when your script is executed, rather than provide the full script, replace branches that aren't executed with the digest of that part of the tree. It'll make stuff like this much more efficient because even if you have a crazy complex script with tonnes of possible branches, you only have to include the code that actually runs when you spend the txout.
When you say the oracle needs to be interactive, I presume that means the oracle needs to sign the transaction because we would have to make a non-standard transaction otherwise? And the benefit of using the Multisig here (compared to drop) is its standard? And we basically need to compute a public key for the oracle based on a contract expression? Then we sign the redemption contract ourselves, and have the oracle sign it (assuming he agrees with the contract and its payout).
That's all correct. The reason you'd want to compute a derivative pubkey is to make it clear exactly what contract is being committed too; it's optional but a good idea.
I'm looking pretty long term, so I'd like to design for the best architecture long term and push for those features to be standardized and relayed. I'm not in a hurry to make this work on anything other than testnet for some time.
Yeah, I wouldn't shy away from non-standard transactions myself. You've got an application where the scripting system has very real advantages, and it's also not important for those transactions to be mined immediately. Non-standard just means that nodes using the reference implementation won't relay the transactions, and won't mine them; non-standard doesn't ban such transactions entirely. Eligius will mine non-standard txs for instance. (although lately something seems to be wrong with the submission process) Instructions here: https://en.bitcoin.it/wiki/Free_transaction_relay_policy Patch your bitcoind with Luke's nonstdtxn patch: https://github.com/luke-jr/bitcoin/tree/accept_nonstdtxn
retep - Thanks for the post. I'll need some time to digest to see how to modify my approach based on this.
This should simplify how oracles work quite a bit (and give them some plausible deniability if an oracle service just published nonces for various events).
I'm going to toy around with things a bit and see if I can implement what you proposed. It is quite promising.
The standard/non-standard transaction stuff is something I am aware of, I've been working with non-standard transactions on testnet, so this is not terribly new for me. I'd like to see if I can find something general purpose and simple enough to get traction to be added as a standard transaction if needed, but a good case would have to be made. The OP_DROP proposal already exists, so it was easy to piggy back on that. My first implementation had a complex script similar to what you described in your first post, and Mike suggested I move to the other script. A standard transaction that would work would be far superior, of course, because I wouldn't have to convince anyone, or wait on nodes to upgrade.
Can you explain in slight more detail where I would use P2SH? In particular, which transactions would need to be modified for that to work? I presume the contract transaction. The redemption transaction is already a standard output, so that wouldn't be needed.
When you say the oracle needs to be interactive, I presume that means the oracle needs to sign the transaction because we would have to make a non-standard transaction otherwise? And the benefit of using the Multisig here (compared to drop) is its standard? And we basically need to compute a public key for the oracle based on a contract expression? Then we sign the redemption contract ourselves, and have the oracle sign it (assuming he agrees with the contract and its payout).
I'm looking pretty long term, so I'd like to design for the best architecture long term and push for those features to be standardized and relayed. I'm not in a hurry to make this work on anything other than testnet for some time.
This should simplify how oracles work quite a bit (and give them some plausible deniability if an oracle service just published nonces for various events).
I'm going to toy around with things a bit and see if I can implement what you proposed. It is quite promising.
The standard/non-standard transaction stuff is something I am aware of, I've been working with non-standard transactions on testnet, so this is not terribly new for me. I'd like to see if I can find something general purpose and simple enough to get traction to be added as a standard transaction if needed, but a good case would have to be made. The OP_DROP
Can you explain in slight more detail where I would use P2SH? In particular, which transactions would need to be modified for that to work? I presume the contract transaction. The redemption transaction is already a standard output, so that wouldn't be needed.
When you say the oracle needs to be interactive, I presume that means the oracle needs to sign the transaction because we would have to make a non-standard transaction otherwise? And the benefit of using the Multisig here (compared to drop) is its standard? And we basically need to compute a public key for the oracle based on a contract expression? Then we sign the redemption contract ourselves, and have the oracle sign it (assuming he agrees with the contract and its payout).
I'm looking pretty long term, so I'd like to design for the best architecture long term and push for those features to be standardized and relayed. I'm not in a hurry to make this work on anything other than testnet for some time.
You sign a previous output when you spend it. An output from Tx1 is an input in Tx2. You need to sign it in Tx2. Signing an output in Tx1 is not a concept that exists.
Step 2 reads:
"The user creates transaction Tx1 (the payment) putting 10 BTC into an output that requires both user and website to sign, but does not broadcast it. They use the key from the previous step for the site."
Your questions are coming from fundamentally not understanding how transactions work. If you are interested in that, start a new thread, ask questions or read the link Mike sent. Once you are up to speed, apply that knowledge to the topic at hand.
outputs are future inputs. That's the simplest thing. Outputs can be spent by inputs that sign transactions. Read the transactions wiki page, read it again, then read it a third time. Then start a new thread if anything is unclear.
I didn't ask a question. I simply quoted the wiki (i.e., I am trying to identify my area of confusion). Thanks for the feedback though. Sorry about the thread diversion. It seems you're getting some good feedback now.
I need to look at this closer but I had a similar thought when looking at this, and dismissed it thinking it couldn't protect against the losing party using the signed nonce condition against him, but it really looks like your scripts are better for this. I may try playing around with this and see if I can get it to work and what the implications are.
Thanks for your contribution!
Thanks for your contribution!
Glad to help.
EDIT: Keep in mind that all the transactions I outlined above are considered non-standard and thus are hard to actually create or spend on mainnet. (testnet disables the IsStandard() test) For something that can actually be used right now you'll need to use the CHECKMULTISIG version of the protocol and make the oracle be interactive. The wiki for some reason has a
2
The * represents ECC multiplication, and deterministically derives a pubkey from the oracles main one; read about Timo Hanke's pay-to-contract stuff for how that derivation works. I'm sure he'd be interested in an implementation of his work, he might even have code for it.
You'll also want to use P2SH so that the money is sent to an actual address and the protocol is compatible with any wallet software, and hardware wallets. (or I should say, will be compatible as multi-sig wallet software is developed) Most of the Bitcoin developers are of the opinion that non-P2SH scriptPubKeys should be eventually banned so take that into account; P2SH works with the pure hash-based versions of all of the above too.
Obviously the nonce would have to be a pretty large data set, as you could just hash over all possible values and figure out how to spend it. That seems like the only concern I can think of- someone could just brute force this to figure out what the nonce was. I'm not sure if scripting allows for checking that a signature matches on some arbitrary set of data, but it seems like you could have an issue there where someone could brute force attack until he finds one that matches, then cashes out the bet prematurely.
Well this is a basic cryptography question actually: How big should your digest be?
If you don't already know the answer you probably should read more on cryptography; I recommend the book Practical Cryptography.
The short answer to your question is use a nonce as big as the digest produced by the hash function, and a 160bit nonce, or 20 bytes, is fine; that's a big enough nonce to make these transactions just as secure as any standard transaction. But really you read that book so you understand why I'm right.
You sign a previous output when you spend it. An output from Tx1 is an input in Tx2. You need to sign it in Tx2. Signing an output in Tx1 is not a concept that exists.
Step 2 reads:
"The user creates transaction Tx1 (the payment) putting 10 BTC into an output that requires both user and website to sign, but does not broadcast it. They use the key from the previous step for the site."
Your questions are coming from fundamentally not understanding how transactions work. If you are interested in that, start a new thread, ask questions or read the link Mike sent. Once you are up to speed, apply that knowledge to the topic at hand.
outputs are future inputs. That's the simplest thing. Outputs can be spent by inputs that sign transactions. Read the transactions wiki page, read it again, then read it a third time. Then start a new thread if anything is unclear.
Regarding oracles there is a much simpler way to implement them that doesn't even need to require interaction with the oracle or signatures.
Suppose I'm an oracle who will attest to whether or not the Steelers won the 2014 Superbowl. I say that if they do win, I'll make public some nonce, nSteelersLose, and if they win, I'll provide another nonce, nSteelersWin. In the meantime I make public the values of H(nSteelersLose) and H(nSteelersWin) upfront. (where H(d) is some cryptographic hash function)
Now Alice can make a bet with her friend Bob as to whether or not the Steelers win. (Alice and Bob are such committed Steelers fan's that they are sure they'll make it to the playoffs) They jointly author a transaction with two inputs, one from Alice, and one from Bob, and a single output. That output has the following scriptPubKey:
HASH160 H(nSteelersWin) EQUAL
IF
CHECKSIG
ELSE
HASH160 EQUALVERIFY
CHECKSIG
ENDIF
If the Steelers win, the oracle will publish nSteelersWin and Alice can spend the output with the following scriptSig:
signature nSteelersWin
If the Steelers lose on the other hand, only Bob can spend the output:
signature nSteelersLose 0
What's really nice about using hashes rather than signatures is that it's scalable: there could be a million Alice's and Bob's making these bets, and the oracle doesn't have to even know. The oracle can also attest to as many different teams or conditions as required, or there could even be multiple oracles. For instance I could also bet that the Steelers will win and the Democrats win the next election and Canada is invaded by the United States:
HASH160 H(nSteelersWin) EQUAL
HASH160 H(nDemocratsWin) EQUAL
AND
HASH160 H(nCanadaInvaded) EQUAL
AND
HASH160 H(nSteelersLose) EQUAL
OR
HASH160 H(nDemocratsLose) EQUAL
OR
HASH160 H(nCanadaNotInvaded) EQUAL
OR
Of course, Alice and Bob might also want to be protected in case the oracle fails. For instance the oracle might go out of business and stop publishing. But they can modify their script so that Alice and Bob can also mutually agree to a different set of conditions at any time:
HASH160 H(nSteelersWin) EQUAL
IF
CHECKSIG
ELSE
HASH160 EQUAL
IF
CHECKSIG
ELSE
0
ENDIF
ENDIF
IF
1
ELSE
2 2 CHECKMULTISIG
ENDIF
(FWIW there's lots of ways to make these scripts shorter)
They can sign a transaction in advance that is timelocked so that even if one or the other party is unavailable, if a month after the Superbowl is supposed to happen the oracle still hasn't published either one can trigger the backup condition and cancel the bet and return the money. It's even possible to handle the oracle revealing both values, either accidentally or maliciously, by setting up inputs spent by timelocked transactions to effectively cancel the bet, but that gets complex...
Finally if the oracle can be directly involved in your transaction you can simplify all of this by asking the oracle to commit to a contract. Basically the contract just outlines exactly what the oracle is attesting too, whatever that is, and the oracle promises to reveal specific nonces for specific outcomes. The oracle does not need to sign transactions and the oracle can simple publish the correct nonces in a public place when the event is triggered.
This also means that the problem of making sure the oracle is honest with challenges is irrelevant. Honest is just a matter of what values the oracle publishes and has nothing to do with transactions at all. For that matter, the oracle doesn't even have to know anything about Bitcoin at all: all the oracle does is make promises to make public certain short bits of data if certain events happen.
Suppose I'm an oracle who will attest to whether or not the Steelers won the 2014 Superbowl. I say that if they do win, I'll make public some nonce, nSteelersLose, and if they win, I'll provide another nonce, nSteelersWin. In the meantime I make public the values of H(nSteelersLose) and H(nSteelersWin) upfront. (where H(d) is some cryptographic hash function)
Now Alice can make a bet with her friend Bob as to whether or not the Steelers win. (Alice and Bob are such committed Steelers fan's that they are sure they'll make it to the playoffs) They jointly author a transaction with two inputs, one from Alice, and one from Bob, and a single output. That output has the following scriptPubKey:
HASH160 H(nSteelersWin) EQUAL
IF
ELSE
HASH160
ENDIF
If the Steelers win, the oracle will publish nSteelersWin and Alice can spend the output with the following scriptSig:
signature nSteelersWin
If the Steelers lose on the other hand, only Bob can spend the output:
signature nSteelersLose 0
What's really nice about using hashes rather than signatures is that it's scalable: there could be a million Alice's and Bob's making these bets, and the oracle doesn't have to even know. The oracle can also attest to as many different teams or conditions as required, or there could even be multiple oracles. For instance I could also bet that the Steelers will win and the Democrats win the next election and Canada is invaded by the United States:
HASH160 H(nSteelersWin) EQUAL
HASH160 H(nDemocratsWin) EQUAL
AND
HASH160 H(nCanadaInvaded) EQUAL
AND
HASH160 H(nSteelersLose) EQUAL
OR
HASH160 H(nDemocratsLose) EQUAL
OR
HASH160 H(nCanadaNotInvaded) EQUAL
OR
Of course, Alice and Bob might also want to be protected in case the oracle fails. For instance the oracle might go out of business and stop publishing. But they can modify their script so that Alice and Bob can also mutually agree to a different set of conditions at any time:
HASH160 H(nSteelersWin) EQUAL
IF
ELSE
HASH160
IF
ELSE
0
ENDIF
ENDIF
IF
1
ELSE
2
ENDIF
(FWIW there's lots of ways to make these scripts shorter)
They can sign a transaction in advance that is timelocked so that even if one or the other party is unavailable, if a month after the Superbowl is supposed to happen the oracle still hasn't published either one can trigger the backup condition and cancel the bet and return the money. It's even possible to handle the oracle revealing both values, either accidentally or maliciously, by setting up inputs spent by timelocked transactions to effectively cancel the bet, but that gets complex...
Finally if the oracle can be directly involved in your transaction you can simplify all of this by asking the oracle to commit to a contract. Basically the contract just outlines exactly what the oracle is attesting too, whatever that is, and the oracle promises to reveal specific nonces for specific outcomes. The oracle does not need to sign transactions and the oracle can simple publish the correct nonces in a public place when the event is triggered.
This also means that the problem of making sure the oracle is honest with challenges is irrelevant. Honest is just a matter of what values the oracle publishes and has nothing to do with transactions at all. For that matter, the oracle doesn't even have to know anything about Bitcoin at all: all the oracle does is make promises to make public certain short bits of data if certain events happen.
You sign a previous output when you spend it. An output from Tx1 is an input in Tx2. You need to sign it in Tx2. Signing an output in Tx1 is not a concept that exists.
Step 2 reads:
"The user creates transaction Tx1 (the payment) putting 10 BTC into an output that requires both user and website to sign, but does not broadcast it. They use the key from the previous step for the site."
Which parts of a tx are signed is covered in the theory section of the contracts page:
https://en.bitcoin.it/wiki/Contracts
Let me know if you find that unclear.
https://en.bitcoin.it/wiki/Contracts
Let me know if you find that unclear.
Mike, in Example 1: Providing a deposit, it is unclear when and where/what (i.e., input or output) is to be signed. I've deduced that in step #2, the user is not suppose to sign the input or the output except with zeros; making it impossible for the website to broadcast it. And in step#4, the website is suppose to sign the output of Tx1 and input & output of Tx2. And in step #5, the user replaces the zeros on both the input and output in Tx1.
Or did I miss something?
You sign a previous output when you spend it. An output from Tx1 is an input in Tx2. You need to sign it in Tx2. Signing an output in Tx1 is not a concept that exists.
Jump to: