[Bitcoin-development] Proposal: relax the IsStandard rules for P2SH transactions

[Bitcoin-development] Proposal: relax the IsStandard rules for P2SH transactions

[Gavin Andresen]

[-- Attachment #1: Type: text/plain, Size: 2791 bytes --]

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.

-- 
--
Gavin Andresen
Chief Scientist, Bitcoin Foundation
https://www.bitcoinfoundation.org/

[-- Attachment #2: Type: text/html, Size: 3188 bytes --]

Re: [Bitcoin-development] Proposal: relax the IsStandard rules for P2SH transactions

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 3082 bytes --]

On Tue, Jun 17, 2014 at 03:40:36PM -0400, Gavin Andresen wrote:
> 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.

> 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.

> 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.

> 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.

> 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.

-- 
'peter'[:-1]@petertodd.org
0000000000000000407e409a626b01bfb275cb88768ca74f3ea9bd87b2e7e1d9

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 685 bytes --]

Re: [Bitcoin-development] Proposal: relax the IsStandard rules for P2SH transactions

[Gavin Andresen]

[-- Attachment #1: Type: text/plain, Size: 768 bytes --]

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...

-- 
--
Gavin Andresen
Chief Scientist, Bitcoin Foundation
https://www.bitcoinfoundation.org/

[-- Attachment #2: Type: text/html, Size: 1196 bytes --]

Re: [Bitcoin-development] Proposal: relax the IsStandard rules for P2SH transactions

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 1477 bytes --]

On Wed, Jun 18, 2014 at 08:52:22AM -0400, Gavin Andresen wrote:
> 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.

> 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.

-- 
'peter'[:-1]@petertodd.org
000000000000000004e51d8d00eedb31ec1505d245f48960896b79f0e7193c2a

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 685 bytes --]

Re: [Bitcoin-development] Proposal: relax the IsStandard rules for P2SH transactions

[Gavin Andresen]

[-- Attachment #1: Type: text/plain, Size: 691 bytes --]

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.



-- 
--
Gavin Andresen
Chief Scientist, Bitcoin Foundation
https://www.bitcoinfoundation.org/

[-- Attachment #2: Type: text/html, Size: 1108 bytes --]

Re: [Bitcoin-development] Proposal: relax the IsStandard rules for P2SH transactions

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 1010 bytes --]

On Thu, Jun 19, 2014 at 09:54:31AM -0400, Gavin Andresen wrote:
> 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.

> 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

-- 
'peter'[:-1]@petertodd.org
00000000000000004f73d48c972aa30493526191aa009f95e4a71dcfbdca08b2

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 685 bytes --]

[Bitcoin-development] New opcodes and transaction version numbers (was 'relax the IsStandard rules for P2SH transactions')

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 3707 bytes --]

On Thu, Jun 19, 2014 at 09:54:31AM -0400, Gavin Andresen wrote:
> 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

-- 
'peter'[:-1]@petertodd.org
000000000000000005ec432fd4c506119a0123a028911fa3981bcde0568b66ab

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]

Re: [Bitcoin-development] New opcodes and transaction version numbers (was 'relax the IsStandard rules for P2SH transactions')

[Alan Reiner]

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.

Re: [Bitcoin-development] New opcodes and transaction version numbers (was 'relax the IsStandard rules for P2SH transactions')

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 3144 bytes --]

On Mon, Sep 29, 2014 at 12:30:11AM -0400, Alan Reiner wrote:
> 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.

-- 
'peter'[:-1]@petertodd.org
0000000000000000092e056ab9c5a3242bfa911ba9a0a8a3836bcd4b5fcab2f8

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 650 bytes --]

Re: [Bitcoin-development] Proposal: relax the IsStandard rules for P2SH transactions

[Wladimir]

On Tue, Jun 17, 2014 at 9:40 PM, Gavin Andresen
<gavin@bitcoinfoundation.org> wrote:
> 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!

> 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.

> 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