Proposal: relax the IsStandard rules for P2SH transactions
10 messages, 17 Jun to 29 Sep 2014. Started by Gavin Andresen.
Peter Todd (5), Gavin Andresen (3), Wladimir J. van der Laan, Alan Reiner
Assuming there is rough consensus, I'll make this a pull request (see https://github.com/gavinandresen/bitcoin-git/tree/relax_isstandard for code changes).
----
Now that we are finally starting to see the use of multi-signature and other more complicated transaction forms in applications I think it is time to open up the "IsStandard" transaction rules on the main Bitcoin network.
There are two main risks to doing this:
1. The risk that one of the seldom-used opcodes has a not-yet-discovered chain-forking bug. I believe that risk to be very low; we have never seen such a bug on the test network (where all transaction forms are allowed) and have never found a bug after writing extensive unit tests. 2. The risk of opening up a denial-of-service attack (either bloat the blockchain or use an excessive amount of CPU time) via a very expensive-to-store-or-verify transaction. This proposal does not entirely eliminate IsStandard checks to mitigate the potential for DoS attacks.
Proposal -------- Allow any Script containing 15 or fewer signature operations as a pay-to-script-hash (P2SH) Script to be relayed and mined by the reference implementation.
This should be a simple change to the AreInputsStandard() method in the reference implementation.
Discussion ---------- P2SH Scripts are limited to 520 bytes, and are currently limited to one of the "standard" transaction forms on the main network. In practice that means you can currently encode a n-of-15 OP_CHECKMULTISIG which can be redeemed as a 'standard' transaction.
Allowing any P2SH Script would allow an attacker to craft a single standard transaction output that requires on the order of 200 ECDSA signature checking operations to validate-- an order of magnitude more than is currently allowed. Therefore I am proposing that we keep the current 15-signature-checking-operations-per-transaction-output limit in place, but allow any combination of enabled Script opcodes. So, for example, you might have a P2SH Script that is redeemed with 2-of-2 OR 2-of-3 using: ``` OP_IF 2 pubkey1 pubkey2 2 OP_CHECKMULTISIG OP_ELSE 2 pubkey3 pubkey4 pubkey5 3 OP_CHECKMULTISIG OP_ENDIF ``` (this would count as 5 signature operations)
Restricting arbitrary Scripts to P2SH transaction types limits unspent transaction output set bloat in two ways: 1. The Scripts are not stored in UTXO set. 2. They are limited to 520 bytes by the Script rule on the amount of data that can be pushed onto the stack.
The reference implementation's wallet will still only recognize P2SH transactions that use one of the standard transaction forms. To actually USE a new transaction form will require specialized wallets or specialized applications.
On Tue, Jun 17, 2014 at 03:40:36PM -0400, Gavin Andresen wrote:
Quoted text (3 lines)
> Assuming there is rough consensus, I'll make this a pull request (see > https://github.com/gavinandresen/bitcoin-git/tree/relax_isstandard for code > changes).
I'm also working on a very similar patch with some additional protections to ensure forwards compatibility during soft-fork upgrades and provide protections against transaction malleability.
Quoted text (3 lines)
> Now that we are finally starting to see the use of multi-signature and > other more complicated transaction forms in applications I think it is time > to open up the "IsStandard" transaction rules on the main Bitcoin network.
Agreed.
Quoted text (6 lines)
> There are two main risks to doing this: > > 1. The risk that one of the seldom-used opcodes has a not-yet-discovered > chain-forking bug. I believe that risk to be very low; we have never seen > such a bug on the test network (where all transaction forms are allowed) > and have never found a bug after writing extensive unit tests.
Agreed.
The script execution code is probably in the 99.9th percentile of open source code in terms of code review.
Quoted text (4 lines)
> 2. The risk of opening up a denial-of-service attack (either bloat the > blockchain or use an excessive amount of CPU time) via a very > expensive-to-store-or-verify transaction. This proposal does not entirely > eliminate IsStandard checks to mitigate the potential for DoS attacks.
3. The risk that non-upgraded miners produce invalid blocks after a soft-fork due to them mining transactions that are now invalid.
4. Transaction malleability.
Quoted text (8 lines)
> Proposal > -------- > Allow any Script containing 15 or fewer signature operations as a > pay-to-script-hash (P2SH) Script to be relayed and mined by the reference > implementation. > > This should be a simple change to the AreInputsStandard() method in the > reference implementation.
In addition to these changes the soft-fork-safe patch I'm working on would do the following:
a) Define an opcode whitelist of soft-fork-safe opcodes.
This whitelist includes every opcode but the invalid opcodes, and most importantly, the OP_NOPx opcodes that may be redefined in a future soft-fork with new behavior. This rule, along with rejecting transations with unknown nVersion's, ensures that a miner still running an old version of Bitcoin Core will only mine transactions that the new version of Bitcoin Core considers valid.
b) Consider scripts that leave extra items on the stack after execution to be non-standard.
As per Pieter Wuille's BIP62 "Dealing with malleability" extra scriptSig pushes are a malleability source. If adding extra pushes causes a transaction to be invalid, scriptPubKeys will in most cases be automatically non-malleable. This change I've already submitted as a separate pull-req: https://github.com/bitcoin/bitcoin/pull/4311
I'd be happy to add the above to your existing patch and submit the pull-req for you.
On Tue, Jun 17, 2014 at 9:40 PM, Gavin Andresen <gavin@bitcoinfoundation•org> wrote:
Quoted text (9 lines)
> Assuming there is rough consensus, I'll make this a pull request (see > https://github.com/gavinandresen/bitcoin-git/tree/relax_isstandard for code > changes). > > ---- > > Now that we are finally starting to see the use of multi-signature and other > more complicated transaction forms in applications I think it is time to > open up the "IsStandard" transaction rules on the main Bitcoin network.
Agreed!
Quoted text (9 lines)
> Discussion > ---------- > Allowing any P2SH Script would allow an attacker to craft a single standard > transaction output that requires on the order of 200 ECDSA signature > checking operations to validate-- an order of magnitude more than is > currently allowed. Therefore I am proposing that we keep the current > 15-signature-checking-operations-per-transaction-output limit in place, but > allow any combination of enabled Script opcodes. So, for example, you might > have a P2SH Script that is redeemed with 2-of-2 OR 2-of-3 using:
Soungs good to me - to lift the restrictions and increase flexibility, but also to be a careful and keep the DoS limits.
Quoted text (4 lines)
> The reference implementation's wallet will still only recognize P2SH > transactions that use one of the standard transaction forms. To actually USE > a new transaction form will require specialized wallets or specialized > applications.
That's of course completely separate. As we all know, most wallet innovation doesn't happen in the reference implementation wallet, and it should not be used as the guide here.
Wladimir
RE: most of Peter Todd's comments:
All of that should be separate pull requests. Big Honking Pull Requests are harder to review and are more likely to be bike-shedded to death.
RE: not relaying/mining transactions with OP_NOPs so miners don't mine up-version transactions that are invalid under future-new-rules: I'm not convinced it is worth adding more code (more potential for bugs) to protect against something that isn't going to happen because up-version transactions are non-standard (due to version check) in any case.
In any case, lets make that a separate pull request.
I'm going to take the lack of immediate "That's a Terrible Idea!" as rough consensus...
On Wed, Jun 18, 2014 at 08:52:22AM -0400, Gavin Andresen wrote:
Quoted text (4 lines)
> RE: most of Peter Todd's comments: > > All of that should be separate pull requests. Big Honking Pull Requests > are harder to review and are more likely to be bike-shedded to death.
Well, just doing one and not the rest isn't necessarily a good idea. The malleability protection definitely seems like a good idea, and has had quite a bit of review.
Quoted text (5 lines)
> RE: not relaying/mining transactions with OP_NOPs so miners don't mine > up-version transactions that are invalid under future-new-rules: I'm not > convinced it is worth adding more code (more potential for bugs) to protect > against something that isn't going to happen because up-version > transactions are non-standard (due to version check) in any case.
Do we have consensus that future soft-forks to add new opcodes will always be done in conjunction with a transaction nVersion bump? If so, then that's ok, if not, then we should have a whitelist.
The code to restrict the opcodes to the softfork-safe subset is trivial, a GetOp() loop and a switch statement. It can always be removed later.
Something that comes to mind is if we do always bump nVersion then OP_NOPx always will have a parallel "do-nothing" behavior, which means EvalScript() will always have to have code enabling that backwards compatible behavior.
RE: soft-forks bumping version numbers:
Yes, we have consensus that is the way we will do it. I should probably turn https://gist.github.com/gavinandresen/2355445 into an informational BIP.
RE: malleability:
Orthogonal (but related) issue to IsStandard.
Detecting Scripts that leave extra items on the stack will be done in a different part of the code than the code addressed by this pull reques. No need to execute the Script twice to figure out if it leaves extra stuff, and the idea behind IsStandard is to get to a quick yes/no before running a potentially expensive Script execution.
On Thu, Jun 19, 2014 at 09:54:31AM -0400, Gavin Andresen wrote:
Quoted text (5 lines)
> RE: soft-forks bumping version numbers: > > Yes, we have consensus that is the way we will do it. I should probably > turn https://gist.github.com/gavinandresen/2355445 into an informational > BIP.
Sounds like it could turn EvalScript() into a mess over time, but that's a long way away. Anyway a BIP will be useful.
Quoted text (9 lines)
> RE: malleability: > > Orthogonal (but related) issue to IsStandard. > > Detecting Scripts that leave extra items on the stack will be done in a > different part of the code than the code addressed by this pull reques. No > need to execute the Script twice to figure out if it leaves extra stuff, > and the idea behind IsStandard is to get to a quick yes/no before running a > potentially expensive Script execution.
Yeah, that's what I implemented in https://github.com/bitcoin/bitcoin/pull/4311
On Thu, Jun 19, 2014 at 09:54:31AM -0400, Gavin Andresen wrote:
Quoted text (5 lines)
> RE: soft-forks bumping version numbers: > > Yes, we have consensus that is the way we will do it. I should probably > turn https://gist.github.com/gavinandresen/2355445 into an informational > BIP.
That gist is mistaken. To see the problem consider the "re-define OP_NOP1 to be OP_Q_CHECKSIGVERIFY" example. It says "Transactions that use the new opcode are given a new version number." The problem is in the definition of "use"
Lets first suppose that the evaluation of a scriptPubKey was done according to the transaction version # of the transaction creating the scriptPubKey. This is technically feasible as the UTXO set records the version of the transaction creating the txout. However if I create a P2SH address whose redeemScript makes use of a new opcode - say the new OP_Q_CHECKSIGVERIFY - non-upgraded clients sending funds to that address will be creating scriptPubKeys whose contents can be spent by anyone. Not exactly ideal! This can be solved by upgrading the address format at the same time to let senders know they must send the funds in a transaction with an increased version number, but obviously needing new addresses for every new opcode defeats the purpose of P2SH.
On the other hand suppose scriptPubKey evaluation is done according to the version of the transaction spending the scriptPubKey. This is insecure as now transaction outputs using the new opcode can be trivially spent by just spending them in a transaction with the previous version number; the OP_Q_CHECKSIGVERIFY is evaluated as OP_NOP and checks nothing.
If txouts be spent only by transactions with nVersion >= the nVersion of the transaction spending them, but again you're forced to upgrade the address format for every new opcode. Interestingly this shows that the common assertion that "P2SH should have been done by upgrading the tx version #" is in fact wrong except for the fact that P2SH required an address format upgrade anyway; doing that for future opcode upgrades would be a mistake.
With the above in mind the "Relax IsStandard rules for P2SH transactions" pull-req(1) is incomplete as it doesn't blacklist usage of the upgradable NOPx opcodes. After a future soft-fork redefining a NOPx opcodes' behavior non-upgraded nodes will accept and mine transactions that may now be invalid, the latter creating invalid blocks and thus false confirmations. I've created a pull-req to fix this issue by specifically blacklisting the NOPx opcodes if they are executed:
https://github.com/bitcoin/bitcoin/pull/5000
Secondly the "Blockchain Rule Update Process" gist above should be rewritten to say that new opcodes will be enabled for all scripts by the block nVersion upgrade mechanism; scripts must never depend on a NOPx opcode being executed least they be rendered unspendable by a future upgrade.
By comparison BIP62 proposes that the transaction version # be increased to indicate that the sender wants anti-malleability rules to be applied. This is an appropriate usage of tx version numbers as in this case the person creating the transaction wants the anti-malleability rules applied; the creator of the scriptPubKey's being spent does not care whether or not they are spent in a transaction that is or is not malleable. Equally the new owners of the txouts being created don't in general care how they were created. (modulo certain special-purpose protocols where they would have the transaction anyway)
1) https://github.com/bitcoin/bitcoin/pull/4365
On 09/28/2014 10:35 PM, Peter Todd wrote:
Quoted text (4 lines)
> This can be solved by upgrading the address format at > the same time to let senders know they must send the funds in a > transaction with an increased version number, but obviously needing new > addresses for every new opcode defeats the purpose of P2SH.
Can't this be solved with a single update to the address format, allowing a tx version number to be part of the address serialization? Then the sending software will apply that version to the payment tx. Of course, I'm not sure if allowing nodes to create transactions with version numbers outside of their programming is safe. It seems like it should be since we're talking about soft forks anyway, but there's probably some subtleties I'm overlooking.
On Mon, Sep 29, 2014 at 12:30:11AM -0400, Alan Reiner wrote:
Quoted text (13 lines)
> On 09/28/2014 10:35 PM, Peter Todd wrote: > > This can be solved by upgrading the address format at > > the same time to let senders know they must send the funds in a > > transaction with an increased version number, but obviously needing new > > addresses for every new opcode defeats the purpose of P2SH. > > Can't this be solved with a single update to the address format, > allowing a tx version number to be part of the address serialization? > Then the sending software will apply that version to the payment tx. > Of course, I'm not sure if allowing nodes to create transactions with > version numbers outside of their programming is safe. It seems like it > should be since we're talking about soft forks anyway, but there's > probably some subtleties I'm overlooking.
Keep in mind that when a *wallet* - not a node - creates a transaction the scriptPubKeys in the transaction outputs have been specified by the receiver(s) and aren't executed until they are spent. Modulo sigops(1) there is absolutely no reason why the wallet should care what the contents of those scriptPubKeys are at all.
This is particularly apparent when you remember that there may be multiple recipients of a transaction. If I'm paying Alice and Bob, who have specified that they want the transaction to have version number 2 and 3 respectively, now what? Do we take the highest of the two and constrain ourselves for how scripts are interpreted for all eternity? It just doesn't make very much sense.
Meanwhile the man-hours of effort that would be required to implement that "one-time" address format change is huge - it took literally years for everyone to update their software to just support P2SH addresses. I'm working on a CHECKLOCKTIMEVERIFY implementation right now, and know of exchanges who would like to use it ASAP. Why make them wait years for everyone to upgrade?
On that basis alone I think the question ought to be why should we use transaction version numbers to enable new opcodes rather than just enabling them globally based on block version numbers.
1) Satoshi implemented a per-block sigop limit to prevent blocks from causing an unreasonable number of signature checking operations, but rather than computing that limit based on the scripts actually executed, the limit is computed based on the contents of all scriptSigs and scriptPubKeys in the block. This is bizzare given that the contents of the latter are *not* executed, and the former misses the prevout scriptPubKeys that *are* executed. In short this means you can create a block that passes the sigop limit, yet executes millions of expensive signature operations by being filled with scriptSigs spending txouts with large numbers of sigops in their scriptPubKeys. P2SH improves on this situation somewhat by counting the sigops in redeemScripts towards the limit, but missed the opportunity to just count all sigops in all scriptSigs directly.