PULL request #748 : Pay-to-script-hash (OP_EVAL replacement)

[Gavin Andresen]

piuk:  please read BIP 0001, it describes the process for getting BIP numbers assigned.

[fivebells]

I read through the bitcoin-dev archive's discussion of OP_EVAL, and don't understand the extent of the concern about Turing completeness.  Guaranteeing resource limits on script execution is important, but runtime constraints like limiting numbers of recursions already go a long way toward imposing these guarantees.  Defense in depth of these guarantees is important, too, but if such a heavily-scrutinized proposal can go months without anyone noting that it affords Turing-completeness then relying on formal analysis Script-the-language to guarantee resource constraints by static analysis is infeasibly delicate and unreliable. 

A more direct and robust defense-in-depth would be for bitcoin's Script implementation to track the resource usage resulting from the execution of each opcode, and reject the script as invalid when usages exceed some thresholds.  If static analysis is currently valuable for miners assessing whether it's worth their while to process a given transaction, then OP_EVAL could be extended to include guarantees on the memory usage and counts of the opcodes and signatures executed by the script which invokes it, guarantees which could be ensured by simply rejecting the script if it violates them. 

Beyond the advantage of greatly strengthening the resource constraints, this approach would probably be much less expensive than junking all the analysis, development and testing put into OP_EVAL so far.

[ShadowOfHarbringer]

The issue you are discussing is way too complex for me to understand, however i got an idea:

Can we perhaps invite all developers (who already wrote "some" Bitcoin code) here to vote on this before implementing in the mainline client ?
Perhaps a closed dev-only poll (done with posts) would suffice.

[ShadowOfHarbringer]

If we manage to get 55% or better on Feb 1, then for the next two week's I'll be sending out the message "Upgrade or you might be on the short end of a blockchain split come Feb 15" -- and I expect the result to be a large majority of miners supporting P2SH by the Feb 15'th switchover date. If we're still at 55% on Feb 7'th then I'll be worried, too, and might advise miners to push the hard switchover date a couple of weeks (if they're using the patches I'm creating then it is a command-line argument to bitcoind).

You know Gavin - after some thinking i understand that we need to constantly move forward, but you are perhaps going too fast about this.
Shouldn't there be a longer wait period before implementation of something that can split chains ?

I mean this is a serious change. Shouldn't this be programmed in a way so that it is activated at, for example, block 190.000 ? This way we would lower the risk of splitting chains & stuff.

Why the rush ? This may be actually dangerous for the network. Can't we have more time to adapt ?

[da2ce7]

I read through the bitcoin-dev archive's discussion of OP_EVAL, and don't understand the extent of the concern about Turing completeness.  Guaranteeing resource limits on script execution is important, but runtime constraints like limiting numbers of recursions already go a long way toward imposing these guarantees.  Defense in depth of these guarantees is important, too, but if such a heavily-scrutinized proposal can go months without anyone noting that it affords Turing-completeness then relying on formal analysis Script-the-language to guarantee resource constraints by static analysis is infeasibly delicate and unreliable. 

A more direct and robust defense-in-depth would be for bitcoin's Script implementation to track the resource usage resulting from the execution of each opcode, and reject the script as invalid when usages exceed some thresholds.  If static analysis is currently valuable for miners assessing whether it's worth their while to process a given transaction, then OP_EVAL could be extended to include guarantees on the memory usage and counts of the opcodes and signatures executed by the script which invokes it, guarantees which could be ensured by simply rejecting the script if it violates them. 

Beyond the advantage of greatly strengthening the resource constraints, this approach would probably be much less expensive than junking all the analysis, development and testing put into OP_EVAL so far.

I really like the idea of having a full featured scripting engine; and using resource tracking to decide if the script is valid or not.  This is where the cost lies, before the fact static analysis is nice… however the real cost is in the difficulty to execute a script -  not what functions the script implements.

[Gavin Andresen]

You know Gavin - after some thinking i understand that we need to constantly move forward, but you are perhaps going too fast about this.
Shouldn't there be a longer wait period before implementation of something that can split chains ?

I mean this is a serious change. Shouldn't this be programmed in a way so that it is activated at, for example, block 190.000 ? This way we would lower the risk of splitting chains & stuff.

Why the rush ? This may be actually dangerous for the network. Can't we have more time to adapt ?

The code is written and committed to the master branch, backports are available for every bitcoin release since 0.3.19, and I'm as confident as I can be there are no major bugs or "gotchas" hiding in the pay-to-script-hash code. Several of the big mining pools have been testing it and will start deploying it on the main network.

"This stuff" IS programmed in a way so it is only activated on the main network after an agreed-upon time.

There are still two weeks until we look and see how much support it has, and almost a month before /P2SH/ transactions are fully validated on the main network. You want to wait 30,000 more blocks?  More than 7 months? That's a darn good way to get everybody to ignore the issue for 6 months and then restart this debate from square one with 1 month to go and a whole fresh set of people who think they're being helpful suggesting using OP_ADD to combine private keys because they don't realize we thought about and discarded that idea 4 months ago.

[piuk]

fresh set of people who think they're being helpful suggesting using OP_ADD to combine private keys because they don't realize we thought about and discarded that idea 4 months ago.

It's not a big deal to take a few seconds to say this idea won't work or to post a link to where it has previously been discussed. No need to be arsey about it.

P.S. It was not documented that math operations are limited to 4 bytes, for example the BitcoinArmory client will not abide by this.

[kjj]

Hey Gavin, what do you think about making the new P2SH transaction recognition explicit rather than implicit?

Ok, since none of the options are perfect, how about we try to satisfy everyone with a hybrid solution?

How about we just redefine OP_NOP1 to mean "do nothing right now, but if the rest of this script is valid in the normal sense, then unpack the second script and run it too".  It'll break old clients, and we have to deal with that, but this way we don't have a special case second code path.  Essentially do exactly what P2SH does, but make the recognition explicit with a dedicated opcode, and not implicit.  Make it a flag that can only be set by the OP_P2SH opcode and can't be cleared, maybe even make the new opcode trigger an immediate validation failure if found by the second pass interpreter so that people can't try to sneak recursion in with it.

So, the default P2SH scriptPubKey would become:

Code:

scriptPubKey: OP_P2SH OP_HASH160 [20-byte-hash of {[pubkey] OP_CHECKSIG} ] OP_EQUAL

I think that this would address Luke's (somewhat valid) complaint about the magic transaction special case code path, while still being exactly P2SH.

[Steve]

I just read the BIP and a few of the messages in this thread (not all).  The BIP states:

"The purpose of pay-to-script-hash is to move the responsibility for supplying the conditions to redeem a transaction from the sender of the funds to the redeemer."

Could someone tell me why this is a transaction/protocol level problem and not just limitation of current clients?  Why is it not sufficient to simply solve this problem by having the sender send to a normal address that the recipient then turns around and sends to another address that imposes whatever rules they would like?  This has already been discussed as the approach to enable the recipient to set the transaction fees (sender creates a fee-less transaction and the recipient then sends back to themselves with a fee attached).

It seems to me that this BIP isn't solving an actual problem or limitation and it doesn't actually provide a multi-sig capability.  Why can't multi-sig simply be handled as a two step process…sender crafts a transaction to a normal address that the recipient then sends to an address that imposes a multi-sig rule.  If such transactions are sent directly from sender to recipient, a single use address could be generated by the recipient software, given to the sender and the recipient software would automatically generate the follow-on transaction that moves everything to the multi-sig transaction.  This could all be done in a transparent way for the user (to them, they are just asking the software to create a multi-sig address to give to the sender).

[kjj]

I just read the BIP and a few of the messages in this thread (not all).  The BIP states:

"The purpose of pay-to-script-hash is to move the responsibility for supplying the conditions to redeem a transaction from the sender of the funds to the redeemer."

Could someone tell me why this is a transaction/protocol level problem and not just limitation of current clients?  Why is it not sufficient to simply solve this problem by having the sender send to a normal address that the recipient then turns around and sends to another address that imposes whatever rules they would like?  This has already been discussed as the approach to enable the recipient to set the transaction fees (sender creates a fee-less transaction and the recipient then sends back to themselves with a fee attached).

It seems to me that this BIP isn't solving an actual problem or limitation and it doesn't actually provide a multi-sig capability.  Why can't multi-sig simply be handled as a two step process…sender crafts a transaction to a normal address that the recipient then sends to an address that imposes a multi-sig rule.  If such transactions are sent directly from sender to recipient, a single use address could be generated by the recipient software, given to the sender and the recipient software would automatically generate the follow-on transaction that moves everything to the multi-sig transaction.  This could all be done in a transparent way for the user (to them, they are just asking the software to create a multi-sig address to give to the sender).

What you describe is an ugly hack, in my opinion.  But you are right that it is an entirely doable ugly hack.

First, that scheme requires that the recipient have an active node running at all times, or at least often enough to sweep receipts occasionally.  Second, it requires more transactions, up to twice as many, but less if the system gathers multiple transactions before sweeping.  Third, it requires that the extra transactions embed the all of the key hashes, making them rather large, and combined with the second point, it means a lot of needless bloat.  Also, it means a lot of hard to predict fees, since all of the extra transactions will be working from new, fresh transaction outputs.

In P2SH, there are no extra transactions, all transactions can be small regardless of the complexity of the redemption scheme, fees will be low since the ordinary oldest coins first policy can be kept, and it can all be done offline.

Also, I just realized that the sweeping scheme can reduce privacy and anonymity, since a sender will be able to watch for their payment to get swept and try to deduce extra information from the protection scheme.  In P2SH, all details of the protection stay hidden until the coins are redeemed.

[Steve]

What you describe is an ugly hack, in my opinion.  But you are right that it is an entirely doable ugly hack.

Yep, I agree but figured I'd ask the question anyway.  Has this been tested on testnet yet?

[Gavin Andresen]

Has this been tested on testnet yet?

Yes, of course. I did most of my testing on 'testnet-in-a-box' nodes, but spent a day producing P2SH blocks and transactions on testnet; see, for example this transaction that spends a P2SH transaction:
  http://blockexplorer.com/testnet/tx/cff697a07fa21780b2553c6e86bf956cb42838b0e9b226da2c6b3cd7754da736

Today I created a smart 'transaction fuzzer', and tomorrow I'll be creating and running stress-tests for the new p2sh and multisignature code to try to catch anything code review and unit tests might have missed.

[Gavin Andresen]

Hey Gavin, what do you think about making the new P2SH transaction recognition explicit rather than implicit?
....

So, the default P2SH scriptPubKey would become:

Code:

scriptPubKey: OP_P2SH OP_HASH160 [20-byte-hash of {[pubkey] OP_CHECKSIG} ] OP_EQUAL

I think that this would address Luke's (somewhat valid) complaint about the magic transaction special case code path, while still being exactly P2SH.

So what happens if I put two OP_P2SH's in a scriptPubKey?  What happens if I put one in a scriptSig? What if I put it inside an OP_IF ... OP_ENDIF ?

I think you're really just suggesting that the "magic" scriptPubKey be 24 bytes big instead of 23, and start with one of the NOP opcodes-- yes? In which case there is going to be a special case code path anyway.

[kjj]

Hey Gavin, what do you think about making the new P2SH transaction recognition explicit rather than implicit?
....

So, the default P2SH scriptPubKey would become:

Code:

scriptPubKey: OP_P2SH OP_HASH160 [20-byte-hash of {[pubkey] OP_CHECKSIG} ] OP_EQUAL

I think that this would address Luke's (somewhat valid) complaint about the magic transaction special case code path, while still being exactly P2SH.

So what happens if I put two OP_P2SH's in a scriptPubKey?

Either ignore it and leave the flag set, or reject the transaction as invalid.  Ignoring it should be safe enough, but setting a limit (like 1) will prevent people from spamming up the chain with tons of pointless repeated NOPs.

  What happens if I put one in a scriptSig?

Bounce the transaction, at least for now.  Maybe some day in the future we will be able to safely handle a full blown OP_EVAL, but we don't have to treat it like one right now.

What if I put it inside an OP_IF ... OP_ENDIF ?

You could either allow it to be set conditionally when encountered inside the script, or ignore placement and set the flag either way based on finding the opcode during static analysis.  Conditionally setting the flag might actually be useful.  I need to study up on the conditionals, but it could end up being a pretty short path to (N of M) or K, with transactions that could be triggered by either the P2SH script, or by the ordinary key.

We could even require that it be the first opcode for now, with the desire that the restriction be relaxed in the future, if safe to do so.

I think you're really just suggesting that the "magic" scriptPubKey be 24 bytes big instead of 23, and start with one of the NOP opcodes-- yes? In which case there is going to be a special case code path anyway.

Well, not really.  There wouldn't be any magic scriptPubKey.  Any valid scriptPubKey could become magic by including the NOP.  In practice, this means that most P2SH scripts would be identical to NOP + the current magic script, but down the road when scripting is better developed, people would be able to trigger P2SH from an arbitrary script, maybe.

It could possibly turn out that there are no useful cases for combining ordinary scripts with P2SH, in which case it would turn out that all we've done is made the magic codes one byte longer.  Even then, having an explicit marker for "hey, I'm a special transaction" could turn out to be worth the ~5% bloat.

[mndrix]

P2SH is the best solution I've seen (or thought of) for moving redemption logic to the redeemer.  I'm far more comfortable with it than the old OP_EVAL proposal.  I think BIP 16 is a move in the right direction although I haven't thoroughly reviewed the pull request.

I only say something because there seems to be a lot of opposition in this thread.  I figured a +1 from the gallery might be more valuable in that case.

[Steve]

P2SH is the best solution I've seen (or thought of) for moving redemption logic to the redeemer.  I'm far more comfortable with it than the old OP_EVAL proposal.  I think BIP 16 is a move in the right direction although I haven't thoroughly reviewed the pull request.

I only say something because there seems to be a lot of opposition in this thread.  I figured a +1 from the gallery might be more valuable in that case.

I think you're correct (I think it's just that changes like this make people nervous).  What then is the next step to enable multi-sig?  Is everything needed already in the scripting language?  Is it just a matter of updating clients and miners to no longer reject such transactions?

[Gavin Andresen]

I think you're correct (I think it's just that changes like this make people nervous).  What then is the next step to enable multi-sig?  Is everything needed already in the scripting language?  Is it just a matter of updating clients and miners to no longer reject such transactions?

Yes, the next step is to get miners and clients to recognize a new 'standard' transaction type that does multisig.  BIP 11 describes them, they're already supported in git HEAD and by the p2sh code, and old miners and clients will recognize and validate blocks that contain OP_CHECKMULTISIG transactions.

[Syke]

I run two kinds of nodes, a bitcoind node and a phoenix-miner node. Which one, or both, of these nodes needs to be updated to support P2SH?

[interlagos]

I'm wondering if the following scenario is possible with P2SH:

"Ex:  I want to buy a FPGA miner for 100 bitcoins.

I put 100 in escrow.  The seller is required to put some amount, maybe 10%  along with mine in to escrow.  Range could be a sliding scale from 1% to 100% of the amount I put in escrow.  Escrow now contains 110 coins.

You would have to be a pretty rich jerk to maliciously scam people repeatedly.  Worst case scenario, untrusting buyers could demand 100% matching escrows for first time transactions."

quoted from:
https://bitcointalk.org/index.php?topic=60158.msg701749#msg701749

[Gavin Andresen]

I run two kinds of nodes, a bitcoind node and a phoenix-miner node. Which one, or both, of these nodes needs to be updated to support P2SH?

Just the bitcoind node.