Implementing External State Contracts - Feedback Requested

[Peter Todd]

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.

[alp]

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?

[Peter Todd]

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?

That's exactly the idea. The general idea is called a soft-fork because only miners need to upgrade to add additional validation rules making formerly valid transactions invalid; the opposite is called a hard-fork where a formerly invalid transactions or blocks are made valid, thus requiring all clients to upgrade at once. Soft-forks are much easier and safer to implement than hard-forks.

Of course P2SH is now supported by 100% of the mining hashing power now, so you won't find invalid P2SH transactions in the blockchain except in historic blocks from about a year and a half ago.

[alp]

I was able to make quite a bit of progress on this and completed all the main test cases.  I need to start creating a test app and a protocol for communicating for users.

I had to make some very basic changes to the script to get it to work.  Here is a quick summary of the process that is used:

Each user drafts a funding transaction that goes to a 2 of 2 mulitisig output, but does not sign or broadcast it.

Each user sends the draft to each other along with a refund transaction that spends each funding transaction by sending it back to its owner.  The other user signs this transaction and sends back the signature so each user has a way to get their money out of the 2 of 2 multisig output in case the other user never signs and broadcasts his funding transaction.  The refund transactions have a sequence number of 0 and a lock time of 1 hour after the current time.

One of the users also creates a contract transaction that uses a P2SH output that spends the two funding transactions.  He sends it to the other user to sign.  This transaction has a higher sequence number for its inputs and a final lock time, so it should replace the refunds once it is signed and valid.  After both signatures are added, this transaction can be broadcast.  The script for the output is as follows:

OP_RIPEMD160 OP_DUP [trueNonceHash] OP_EQUAL
OP_IF
 OP_DROP [trueUserPubKey] OP_CHECKSIG
OP_ELSE
 [falseNonceHash] OP_EQUAL
 OP_IF
  [falseUserPubKey] OP_CHECKSIG
 OP_ELSE
  2 [trueUserPubKey] [falseUserPubKey] 2 OP_CHECKMULTISIG
 OP_ENDIF
OP_ENDIF

It's a slight modification of the one retep suggested.  To spend it, you have a few options.  If you can cash it in alone because you know the nonce values, need to add the nonce and your signature to the scriptSig.  If you want to redeem it with the mulitisig option (for example, if the oracle disappears or you wish to have an early buy-out), you need to add a scriptsig of 0 [trueUserSig] [falseUserSig] 0.  The first 0 is there to get hashed by the RIPEMD160 function and not be equal so we get to the final else case.  The last zero is there to account for a bug in checkmultisig that pops an extra item off of the stack.

Users can automatically create the "no oracle refund" ahead of time as well, and set a lockTime on the transaction of well past the event (say a week) in case the oracle cannot be found, and set it with a 0 sequence number on the input.  Then the transaction is replaced by anyone who can redeem it.

I've only run basic unit tests on this code so far, need to clean it up a bit before publishing, but plan to start making a very basic app for testnet to actually start publishing some transactions and seeing if this works.  If it does, I'll try to start working on the protocol and possibly some demo websites that anyone can use (on testnet for now).

[Mike Hearn]

Recall that transaction replacement doesn't work. Sequence numbers are essentially useless on todays networks.

[alp]

Recall that transaction replacement doesn't work. Sequence numbers are essentially useless on todays networks.

I need to understand exactly what the limitation is.  My understanding is the network won't even relay anything that has a timelock < currenttime.  In this case, the sequence number doesn't cause any issues, as the transactions are ignored, since every sequence 0 is timelocked.  The sequence number is used just in case the network starts relaying these transactions (and supports replacement).

Unless I am way off on how what the limitations are.

[Mike Hearn]

No, your understanding is correct. You were talking about replacements and so on without mentioning that, so just wanted to double check.

[Peter Todd]

FWIW if you happen to be in Toronto tonight I'm giving a talk about one-time-password wallet protection which will also include information about the oracle application. My apologies for the 2.5 hour notice; it's rather last minute because I was called in to substitute for a different speaker.

http://www.meetup.com/Bitcoin-Toronto/events/130155842/

alp: I'll look at your design more later. In the meantime replace your use of RIPEMD160 with HASH160 - you want these scripts to have the same security as standard scripts, and HASH160 adds an additional SHA256 step which makes a flaw in RIPEMD160 less likely to cause problems. More importantly, you are using P2SH which already depends on HASH160, so there is no reason to use a mechanism that could have a different flaw thus making you vulnerable to two types of flaws rather than just one.

[alp]

FWIW if you happen to be in Toronto tonight I'm giving a talk about one-time-password wallet protection which will also include information about the oracle application. My apologies for the 2.5 hour notice; it's rather last minute because I was called in to substitute for a different speaker.

http://www.meetup.com/Bitcoin-Toronto/events/130155842/

alp: I'll look at your design more later. In the meantime replace your use of RIPEMD160 with HASH160 - you want these scripts to have the same security as standard scripts, and HASH160 adds an additional SHA256 step which makes a flaw in RIPEMD160 less likely to cause problems. More importantly, you are using P2SH which already depends on HASH160, so there is no reason to use a mechanism that could have a different flaw thus making you vulnerable to two types of flaws rather than just one.

I am agnostic to the hashing algorithm used, so I can easily switch.  The only reason I used RIPEMD160 is I had some test cases that I ran through an online hash webpage that used RIPEMD160 and it let me calculate the hash values independently.

I'll change the code when I get home, but I just need to calculate the nonce hashes using that algorithm, which I believe should be pretty easy to do using the same webpage I used to calculate the nonce hashes.

If you have any notes from the presentation, I'd be interested in seeing how it applies to the oracle application.  I'll likely try to present something to our local meetup group in the future.  It's a tough balance to tread between being overly technical and simplistic with these audiences.  I think it would be a lot better to have a sample app that people could use to play with and really touch and feel.  In the mean time, I might try to put together some type of youtube video that shows how it might work in action.

[alp]

No, your understanding is correct. You were talking about replacements and so on without mentioning that, so just wanted to double check.

I probably should have mentioned it.  I'm glad I understood it correctly, it's one of those things I was a bit shaky on.  From my understanding, everything should work as expected with both the way everything is currently set up and should continue to work even if transaction replacement is enabled in the future.

[Peter Todd]

I am agnostic to the hashing algorithm used, so I can easily switch.  The only reason I used RIPEMD160 is I had some test cases that I ran through an online hash webpage that used RIPEMD160 and it let me calculate the hash values independently.

Cool, just don't forget to change it prior to releasing your beta!

I'll change the code when I get home, but I just need to calculate the nonce hashes using that algorithm, which I believe should be pretty easy to do using the same webpage I used to calculate the nonce hashes.

If you have any notes from the presentation, I'd be interested in seeing how it applies to the oracle application.  I'll likely try to present something to our local meetup group in the future.  It's a tough balance to tread between being overly technical and simplistic with these audiences.  I think it would be a lot better to have a sample app that people could use to play with and really touch and feel.  In the mean time, I might try to put together some type of youtube video that shows how it might work in action.

Will do.

One reason I wanted to present sooner rather than later was to hear from people who might actually use the software, both oracle and wallet protection. It'll also help get a feel for what explanations work; I've actually got a fine arts degree and used to make electronics-based art so I've got years of experience explaining technical ideas to the public and really enjoy doing it. I want to use the wallet-protection application as a way to lead into explaining the oracle application.

[alp]

I'd really like to make some type of youtube video animated presentation on it with voiceovers and all, but that is completely new territory for me, so I may have to settle for something basic.  Although the test app is much more important to have for people to play with.  I've made a lot of progress quickly with the prototyping, but making a real app, even if a bit clunky and ugly, will be more work, especially since I'm just working on this stuff only a few hours a week in my free time.

[alp]

I have updated my repository with the latest updates, including using OP_HASH160 instead of OP_RIPEMD160:
https://code.google.com/r/allenpiscitello-oracle2/

I still have a substantial effort to clean up the code and actually put most of the contract and redemption creation as part of the standard library rather than as a test case, but I expect to start on that shortly and actually integrate it.  Then on to the protocol and test application!

[alp]

One drawback with this approach is the lack of ability to have a proportional payout (e.g. a Bitcoin mining difficulty contract that pays out proportionally based on how close to 100M difficulty the next difficulty will be), but I thought about it a bit more and it at least is possible through having multiple outputs on the contract that kick in at different conditions. It's not entirely as flexible as a purely proportional payout, but you could have it in steps and get virtually the same effect:

For example, rather than betting if the next difficulty increase will be over 80,000,000, you could have a contract that pays proportionally at 10,000,000 increments.

You collect 1BTC from 2 people betting, and then make 10 outputs for example.  Each output will pay to Party A if the difficulty is above 10M*(N+1) (where N is the output number).  If the difficulty ended up being 92M, then the first 9 outputs would pay to Party A, and the last one would pay to Party B.  So you get a close-enough proportional contract in this.  The downside of this is you have 5x as many fees for redeeming as a pure proportional, and it's still got some big chunks.  I'm not sure that's a big enough concern, and of course, a transaction aware oracle could be introduced to handle such cases.  I'm a fan of keeping it simple, and until that becomes unfeasible, or there becomes demand for it, stick with the simple case.

[alp]

I am starting to test throwing some basic external state contracts into the testnet blockchain.  I ran into a minor issue with testing, but I think it's due to sequence number not working quite like I thought.

I have TX1, TX1Refund, TX2, TX2Refund, and ContractTX.  TX1 comes from user 1, TX2 comes from user 2.  TXRefund spends with a timelock of currenttime+60 minutes and has a sequencenumber of 1 for the input it is associated with.  ContractTX takes TX1 and TX2 as inputs, but with a MAX sequence number and no timelock.

I have not been using bitcoinJ to propogate transactions, but instead sending them through the bitcoin-qt console using "sendrawtransaction".  If I send the refunds, I cannot submit the contract.  Once sequence number is fully supported, I should be able to do this.

What my understanding of the situation, without getting into the bitcoin-qt code, is that the timelocked transactions (refunds) are held in the mempool (I can see this with getrawmempool), and since sequence number is not being honored, it sees it as a double spend if I try to submit the ContractTx, so it rejects the transaction and does not relay it.  The timelocked transactions are held in the mempool but not relayed.  I likely could send a raw transaction of the contract on another client that has not seen the refunds, since they aren't being relayed (until lock time).

This is unfortunate, but not a roadblock.  I can just make the app not submit refunds until after the lock time, thus not making it look like a double-spend.

Is my understanding of what is happening correct?

The worst I can think of that will happen is someone will somehow get the contract refund tx (which expires some time after the nonces should have been published) and gets that transaction into the mempool of a lot of miners, and it blocks the correct user from redeeming the transaction.  Probably not a concern.

BTW, here are some sample transactions in the chain if anyone is curious:

Funding Transaction 1 - Funds from wallet 1 into multisig address
Funding Transaction 2  - Funds from wallet 2 into multisig address
Contract Transaction - Spends funding inputs to a redeemable location by either a) wallet 1 once nonce1 is known, b) wallet 2 ocne nonce2 is known, or c) wallet 1 + wallet2 at any time.
Contract Refund TX - I made a mistake on this one and accidentally divided the fee wrong and ended up paying a huge fee and only refunding half the funding amounts, oops!  This has been fixed.  This is an example of spending with both signatures.

[Mike Hearn]

I suspect the issue is you're bypassing the standard logic that fails to relay timelocked transactions by using sendrawtransaction. If you used bitcoinj to send the tx, it wouldn't enter the mempools at all.

[alp]

I suspect the issue is you're bypassing the standard logic that fails to relay timelocked transactions by using sendrawtransaction. If you used bitcoinj to send the tx, it wouldn't enter the mempools at all.

I haven't tested this theory (having two different bitcoin-qt apps could do this), but what I suspect is the problem is it's staying in my local mempool only, which will reject any transactions that it thinks are a double spend.  Since my local client doesn't understand sequence number, it assumes it's a double spend and rejects it without ever accepting it into the mempool on the local machine even before relaying it.  I'm not sure if the timelocked refund transactions ever get relayed (it's my suspicion they are not relayed until the timelock expires).

[Peter Todd]

I suspect the issue is you're bypassing the standard logic that fails to relay timelocked transactions by using sendrawtransaction. If you used bitcoinj to send the tx, it wouldn't enter the mempools at all.

I haven't tested this theory (having two different bitcoin-qt apps could do this), but what I suspect is the problem is it's staying in my local mempool only, which will reject any transactions that it thinks are a double spend.  Since my local client doesn't understand sequence number, it assumes it's a double spend and rejects it without ever accepting it into the mempool on the local machine even before relaying it.  I'm not sure if the timelocked refund transactions ever get relayed (it's my suspicion they are not relayed until the timelock expires).

They aren't.

You have to remember that relaying timelocked transactions enables DoS attacks by just relaying a ton of transactions that will never get mined, either due to the lock being far in the future, or because you mine a conflicting block before the lock expires; to use up 1GiB of RAM on un-mined mempool tx's only requires the attacker to have ~$30k worth of Bitcoins with the current codebase. Sequence numbers have similar problems because you have to make increasing the sequence be accompanies by a higher fee for the exact same anti-DoS reasons.

Testnet however *does* relay timelocked transactions right now because that test was implemented in the IsStandard() code, which is turned off on testnet. I think it's time we change that and make relaying a timelocked tx fail on testnet too; it'll never be possible to relay timelocked transactions on the network directly due to the DoS attack risk, so we shouldn't confuse developers.

[alp]

I suspect the issue is you're bypassing the standard logic that fails to relay timelocked transactions by using sendrawtransaction. If you used bitcoinj to send the tx, it wouldn't enter the mempools at all.

I haven't tested this theory (having two different bitcoin-qt apps could do this), but what I suspect is the problem is it's staying in my local mempool only, which will reject any transactions that it thinks are a double spend.  Since my local client doesn't understand sequence number, it assumes it's a double spend and rejects it without ever accepting it into the mempool on the local machine even before relaying it.  I'm not sure if the timelocked refund transactions ever get relayed (it's my suspicion they are not relayed until the timelock expires).

They aren't.

You have to remember that relaying timelocked transactions enables DoS attacks by just relaying a ton of transactions that will never get mined, either due to the lock being far in the future, or because you mine a conflicting block before the lock expires; to use up 1GiB of RAM on un-mined mempool tx's only requires the attacker to have ~$30k worth of Bitcoins with the current codebase. Sequence numbers have similar problems because you have to make increasing the sequence be accompanies by a higher fee for the exact same anti-DoS reasons.

Testnet however *does* relay timelocked transactions right now because that test was implemented in the IsStandard() code, which is turned off on testnet. I think it's time we change that and make relaying a timelocked tx fail on testnet too; it'll never be possible to relay timelocked transactions on the network directly due to the DoS attack risk, so we shouldn't confuse developers.

So a summary of what is happening on testnet and what would happen on mainnet:

1)  Funding transactions will be relayed and immediately* included in blocks in both networks.
2)  Refund transactions, which have a timelock and zero sequence number, are relayed in testnet, but not in mainnet.
3)  Contract transactions are relayed and immediately* included in blocks in both networks, but if a refund transaction has been relayed already, this transaction is marked as invalid since it thinks its a double spend.  Currently only a problem in testnet, since mainnet will not even relay the refund transactions.

Is my understanding correct?  If so, it seems like I only have a testnet issue, since stopping relaying of timelock transactions solves the problem of the nodes not understanding sequence number replacement (at least in my use case, where I don't have a timelock on the overriding transaction).

This can be easily solved in client software that stores transactions and only relays at appropriate times (and worst case scenario, you end up with a refund when someone submits a refund before the timelock expires, and only on testnet).

[Peter Todd]

So a summary of what is happening on testnet and what would happen on mainnet:

1)  Funding transactions will be relayed and immediately* included in blocks in both networks.
2)  Refund transactions, which have a timelock and zero sequence number, are relayed in testnet, but not in mainnet.
3)  Contract transactions are relayed and immediately* included in blocks in both networks, but if a refund transaction has been relayed already, this transaction is marked as invalid since it thinks its a double spend.  Currently only a problem in testnet, since mainnet will not even relay the refund transactions.

Is my understanding correct?  If so, it seems like I only have a testnet issue, since stopping relaying of timelock transactions solves the problem of the nodes not understanding sequence number replacement (at least in my use case, where I don't have a timelock on the overriding transaction).

This can be easily solved in client software that stores transactions and only relays at appropriate times (and worst case scenario, you end up with a refund when someone submits a refund before the timelock expires, and only on testnet).

Yup, long story short: don't relay transactions you don't want mined.

Regarding sequence number replacement, it's a very flawed idea that just another variant of zero-conf transactions. It's been suggested to re-use sequence numbers for something totally different, such as gmaxwell's transaction checkpoints, so it'd be helpful if you only used the sequence numbers 0xFFFFFFFF for final transactions, and 0xFFFFFFFE for ones that are timelocked. A re-use might also include a bump in transaction version number, but it'll simplify things all the same.

On the other hand there is another version of transaction replacement called replace-by-fee. There you simply make the conflicting replacement transaction pay a higher fee, both absolute as well as in terms of fees-per-KB. Any miner has an economic incentive to include the second transaction instead of the first one provided the fee bump is high enough to account for the higher orphan risk. (may or may not be small - complex question) Counter-intuitively this can also be used to make zero-conf transactions fairly safe: https://bitcointalk.org/index.php?topic=251233.msg2669189#msg2669189

In your case it's not totally obvious if you want the refund tx to take priority over the contract one; maybe you don't? Or maybe you want the contract to take priority over the refund? I suspect the latter, in that if the contract is in a state where it can be completed, that's probably what the users want to get mined.