[bitcoin-dev] Version 1 witness programs (first draft)

[bitcoin-dev] Version 1 witness programs (first draft)

[Luke Dashjr]

I've put together a first draft for what I hope to be a good next step for 
Segwit and Bitcoin scripting:
    https://github.com/luke-jr/bips/blob/witnessv1/bip-witnessv1.mediawiki

This introduces 5 key changes:

1. Minor versions for witnesses, inside the witness itself. Essentially the 
witness [major] version 1 simply indicates the witness commitment is SHA256d, 
and nothing more.

The remaining two are witness version 1.0 (major 1, minor 0):

2. As previously discussed, undefined opcodes immediately cause the script to 
exit with success, making future opcode softforks a lot more flexible.

3. If the final stack element is not exactly true or false, it is interpreted 
as a tail-call Script and executed. (Credit to Mark Friedenbach)

4. A new shorter fixed-length signature format, eliminating the need to guess 
the signature size in advance. All signatures are 65 bytes, unless a condition 
script is included (see #5).

5. The ability for signatures to commit to additional conditions, expressed in 
the form of a serialized Script in the signature itself. This would be useful 
in combination with OP_CHECKBLOCKATHEIGHT (BIP 115), hopefully ending the 
whole replay protection argument by introducing it early to Bitcoin before any 
further splits.

This last part is a big ugly right now: the signature must commit to the 
script interpreter flags and internal "sigversion", which basically serve the 
same purpose. The reason for this, is that otherwise someone could move the 
signature to a different context in an attempt to exploit differences in the 
various Script interpretation modes. I don't consider the BIP deployable 
without this getting resolved, but I'm not sure what the best approach would 
be. Maybe it should be replaced with a witness [major] version and witness 
stack?

There is also draft code implementing [the consensus side of] this:
    https://github.com/bitcoin/bitcoin/compare/master...luke-jr:witnessv1

Thoughts? Anything I've overlooked / left missing that would be 
uncontroversial and desirable? (Is any of this unexpectedly controversial for 
some reason?)

Luke

Re: [bitcoin-dev] Version 1 witness programs (first draft)

[Mark Friedenbach]

The CLEANSTACK rule should be eliminated, and instead the number of items on the stack should be incorporated into the signature hash. That way any script with a CHECKSIG is protected from witness extension malleability, and those rare ones that do not use signature operations can have a “DEPTH 1 EQUALVERIFY” at the end. This allows for much simpler tail-call evaluation as you don’t need to pass arguments on the alt-stack.

> On Sep 30, 2017, at 6:13 PM, Luke Dashjr via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
> I've put together a first draft for what I hope to be a good next step for 
> Segwit and Bitcoin scripting:
>    https://github.com/luke-jr/bips/blob/witnessv1/bip-witnessv1.mediawiki
> 
> This introduces 5 key changes:
> 
> 1. Minor versions for witnesses, inside the witness itself. Essentially the 
> witness [major] version 1 simply indicates the witness commitment is SHA256d, 
> and nothing more.
> 
> The remaining two are witness version 1.0 (major 1, minor 0):
> 
> 2. As previously discussed, undefined opcodes immediately cause the script to 
> exit with success, making future opcode softforks a lot more flexible.
> 
> 3. If the final stack element is not exactly true or false, it is interpreted 
> as a tail-call Script and executed. (Credit to Mark Friedenbach)
> 
> 4. A new shorter fixed-length signature format, eliminating the need to guess 
> the signature size in advance. All signatures are 65 bytes, unless a condition 
> script is included (see #5).
> 
> 5. The ability for signatures to commit to additional conditions, expressed in 
> the form of a serialized Script in the signature itself. This would be useful 
> in combination with OP_CHECKBLOCKATHEIGHT (BIP 115), hopefully ending the 
> whole replay protection argument by introducing it early to Bitcoin before any 
> further splits.
> 
> This last part is a big ugly right now: the signature must commit to the 
> script interpreter flags and internal "sigversion", which basically serve the 
> same purpose. The reason for this, is that otherwise someone could move the 
> signature to a different context in an attempt to exploit differences in the 
> various Script interpretation modes. I don't consider the BIP deployable 
> without this getting resolved, but I'm not sure what the best approach would 
> be. Maybe it should be replaced with a witness [major] version and witness 
> stack?
> 
> There is also draft code implementing [the consensus side of] this:
>    https://github.com/bitcoin/bitcoin/compare/master...luke-jr:witnessv1
> 
> Thoughts? Anything I've overlooked / left missing that would be 
> uncontroversial and desirable? (Is any of this unexpectedly controversial for 
> some reason?)
> 
> Luke
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Version 1 witness programs (first draft)

[Luke Dashjr]

Should it perhaps commit to the length of the serialised witness data instead 
or additionally? Now that signatures are no longer variable-length, that'd be 
possible...

As far as tail-call needs are concerned, CLEANSTACK wouldn't have been checked 
until AFTER the tail-call in the first draft. But I suppose eliminating it for 
other possible future purposes is still useful.

Luke


On Sunday 01 October 2017 2:23:47 AM Mark Friedenbach wrote:
> The CLEANSTACK rule should be eliminated, and instead the number of items
> on the stack should be incorporated into the signature hash. That way any
> script with a CHECKSIG is protected from witness extension malleability,
> and those rare ones that do not use signature operations can have a “DEPTH
> 1 EQUALVERIFY” at the end. This allows for much simpler tail-call
> evaluation as you don’t need to pass arguments on the alt-stack.
> 
> > On Sep 30, 2017, at 6:13 PM, Luke Dashjr via bitcoin-dev
> > <bitcoin-dev@lists.linuxfoundation.org> wrote:
> > 
> > I've put together a first draft for what I hope to be a good next step
> > for
> > 
> > Segwit and Bitcoin scripting:
> >    https://github.com/luke-jr/bips/blob/witnessv1/bip-witnessv1.mediawiki
> > 
> > This introduces 5 key changes:
> > 
> > 1. Minor versions for witnesses, inside the witness itself. Essentially
> > the witness [major] version 1 simply indicates the witness commitment is
> > SHA256d, and nothing more.
> > 
> > The remaining two are witness version 1.0 (major 1, minor 0):
> > 
> > 2. As previously discussed, undefined opcodes immediately cause the
> > script to exit with success, making future opcode softforks a lot more
> > flexible.
> > 
> > 3. If the final stack element is not exactly true or false, it is
> > interpreted as a tail-call Script and executed. (Credit to Mark
> > Friedenbach)
> > 
> > 4. A new shorter fixed-length signature format, eliminating the need to
> > guess the signature size in advance. All signatures are 65 bytes, unless
> > a condition script is included (see #5).
> > 
> > 5. The ability for signatures to commit to additional conditions,
> > expressed in the form of a serialized Script in the signature itself.
> > This would be useful in combination with OP_CHECKBLOCKATHEIGHT (BIP
> > 115), hopefully ending the whole replay protection argument by
> > introducing it early to Bitcoin before any further splits.
> > 
> > This last part is a big ugly right now: the signature must commit to the
> > script interpreter flags and internal "sigversion", which basically serve
> > the same purpose. The reason for this, is that otherwise someone could
> > move the signature to a different context in an attempt to exploit
> > differences in the various Script interpretation modes. I don't consider
> > the BIP deployable without this getting resolved, but I'm not sure what
> > the best approach would be. Maybe it should be replaced with a witness
> > [major] version and witness stack?
> > 
> > There is also draft code implementing [the consensus side of] this:
> >    https://github.com/bitcoin/bitcoin/compare/master...luke-jr:witnessv1
> > 
> > Thoughts? Anything I've overlooked / left missing that would be
> > uncontroversial and desirable? (Is any of this unexpectedly controversial
> > for some reason?)
> > 
> > Luke
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Version 1 witness programs (first draft)

[Mark Friedenbach]

Clean stack should be eliminated for other possible future uses, the most obvious of which is recursive tail-call for general computation capability. I’m not arguing for that at this time, just arguing that we shouldn’t prematurely cut off an easy implementation of such should we want to. Clean stack must still exist as policy for future soft-fork safety, but being a consensus requirement was only to avoid witness malleability, which committing to the size of the witness also accomplishes.

Committing to the number of witness elements is fully sufficient, and using the number of elements avoids problems of not knowing the actual size in bytes at the time of signing, e.g. because the witness contains a merkle proof generated by another party from an unbalanced tree, and unbalanced trees are expected to be common (so that elements can be placed higher in the tree in accordance with their higher expected probability of usage). Other future extensions might also have variable-length proofs.

> On Sep 30, 2017, at 7:47 PM, Luke Dashjr <luke@dashjr.org> wrote:
> 
> Should it perhaps commit to the length of the serialised witness data instead 
> or additionally? Now that signatures are no longer variable-length, that'd be 
> possible...
> 
> As far as tail-call needs are concerned, CLEANSTACK wouldn't have been checked 
> until AFTER the tail-call in the first draft. But I suppose eliminating it for 
> other possible future purposes is still useful.
> 
> Luke

Re: [bitcoin-dev] Version 1 witness programs (first draft)

[Felix Weis]

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

Just a simple suggestion since the signature format is changed. Can this be
designed so that possible future hard forks can simply change 1 constant in
the code and turn on cross chain replay protection?

On Sun, Oct 1, 2017 at 1:05 PM Mark Friedenbach via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Clean stack should be eliminated for other possible future uses, the most
> obvious of which is recursive tail-call for general computation capability.
> I’m not arguing for that at this time, just arguing that we shouldn’t
> prematurely cut off an easy implementation of such should we want to. Clean
> stack must still exist as policy for future soft-fork safety, but being a
> consensus requirement was only to avoid witness malleability, which
> committing to the size of the witness also accomplishes.
>
> Committing to the number of witness elements is fully sufficient, and
> using the number of elements avoids problems of not knowing the actual size
> in bytes at the time of signing, e.g. because the witness contains a merkle
> proof generated by another party from an unbalanced tree, and unbalanced
> trees are expected to be common (so that elements can be placed higher in
> the tree in accordance with their higher expected probability of usage).
> Other future extensions might also have variable-length proofs.
>
> > On Sep 30, 2017, at 7:47 PM, Luke Dashjr <luke@dashjr.org> wrote:
> >
> > Should it perhaps commit to the length of the serialised witness data
> instead
> > or additionally? Now that signatures are no longer variable-length,
> that'd be
> > possible...
> >
> > As far as tail-call needs are concerned, CLEANSTACK wouldn't have been
> checked
> > until AFTER the tail-call in the first draft. But I suppose eliminating
> it for
> > other possible future purposes is still useful.
> >
> > Luke
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

Re: [bitcoin-dev] Version 1 witness programs (first draft)

[Luke Dashjr]

BIP 115 provides fork-independent opt-in replay protection, which can be used 
in combination with the new signature condition scripts in this proposal.

Perhaps the code can have a flag for new altcoins to easily make it mandatory 
(and we can use it on testnet?).

Luke


On Sunday 01 October 2017 11:22:30 AM Felix Weis wrote:
> Just a simple suggestion since the signature format is changed. Can this be
> designed so that possible future hard forks can simply change 1 constant in
> the code and turn on cross chain replay protection?
> 
> On Sun, Oct 1, 2017 at 1:05 PM Mark Friedenbach via bitcoin-dev <
> 
> bitcoin-dev@lists.linuxfoundation.org> wrote:
> > Clean stack should be eliminated for other possible future uses, the most
> > obvious of which is recursive tail-call for general computation
> > capability. I’m not arguing for that at this time, just arguing that we
> > shouldn’t prematurely cut off an easy implementation of such should we
> > want to. Clean stack must still exist as policy for future soft-fork
> > safety, but being a consensus requirement was only to avoid witness
> > malleability, which committing to the size of the witness also
> > accomplishes.
> > 
> > Committing to the number of witness elements is fully sufficient, and
> > using the number of elements avoids problems of not knowing the actual
> > size in bytes at the time of signing, e.g. because the witness contains
> > a merkle proof generated by another party from an unbalanced tree, and
> > unbalanced trees are expected to be common (so that elements can be
> > placed higher in the tree in accordance with their higher expected
> > probability of usage). Other future extensions might also have
> > variable-length proofs.
> > 
> > > On Sep 30, 2017, at 7:47 PM, Luke Dashjr <luke@dashjr.org> wrote:
> > > 
> > > Should it perhaps commit to the length of the serialised witness data
> > 
> > instead
> > 
> > > or additionally? Now that signatures are no longer variable-length,
> > 
> > that'd be
> > 
> > > possible...
> > > 
> > > As far as tail-call needs are concerned, CLEANSTACK wouldn't have been
> > 
> > checked
> > 
> > > until AFTER the tail-call in the first draft. But I suppose eliminating
> > 
> > it for
> > 
> > > other possible future purposes is still useful.
> > > 
> > > Luke
> > 
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Version 1 witness programs (first draft)

[Russell O'Connor]

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

Given the proposed fixed signature size, It seems better to me that we
create a SIGHASH_WITNESS_WEIGHT flag as opposed to SIGHASH_WITNESS_DEPTH.

Mark, you seem to be arguing that in general we still want weight
malleability even with witness depth fixed, but I don't understand in what
scenario we would want that.

It strikes me that is most scenarios all parties signing an input would do
so after an execution path through the script has been agreed upon by all
parties, in which case the witness weight can be fixed.
In rare cases where the smart contract requires that some parties sign in
advance of the decision about the execution path (for example, I'm thinking
about delegation here, but I want to keep my remarks general), we wouldn't
want to fix the witness depth either.

A SIGHASH_WITNESS_WEIGHT would prevent all possible malleability that would
modify the transaction's fee/weight priority (at least for that one input),
and greatly reduce the overall attack surface of witness malleability
issues.

On Sun, Oct 1, 2017 at 1:04 AM, Mark Friedenbach via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Clean stack should be eliminated for other possible future uses, the most
> obvious of which is recursive tail-call for general computation capability.
> I’m not arguing for that at this time, just arguing that we shouldn’t
> prematurely cut off an easy implementation of such should we want to. Clean
> stack must still exist as policy for future soft-fork safety, but being a
> consensus requirement was only to avoid witness malleability, which
> committing to the size of the witness also accomplishes.
>
> Committing to the number of witness elements is fully sufficient, and
> using the number of elements avoids problems of not knowing the actual size
> in bytes at the time of signing, e.g. because the witness contains a merkle
> proof generated by another party from an unbalanced tree, and unbalanced
> trees are expected to be common (so that elements can be placed higher in
> the tree in accordance with their higher expected probability of usage).
> Other future extensions might also have variable-length proofs.
>
> > On Sep 30, 2017, at 7:47 PM, Luke Dashjr <luke@dashjr.org> wrote:
> >
> > Should it perhaps commit to the length of the serialised witness data
> instead
> > or additionally? Now that signatures are no longer variable-length,
> that'd be
> > possible...
> >
> > As far as tail-call needs are concerned, CLEANSTACK wouldn't have been
> checked
> > until AFTER the tail-call in the first draft. But I suppose eliminating
> it for
> > other possible future purposes is still useful.
> >
> > Luke
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

Re: [bitcoin-dev] Version 1 witness programs (first draft)

[Mark Friedenbach]

> On Oct 1, 2017, at 12:05 PM, Russell O'Connor <roconnor@blockstream.io> wrote:
> 
> Given the proposed fixed signature size, It seems better to me that we create a SIGHASH_WITNESS_WEIGHT flag as opposed to SIGHASH_WITNESS_DEPTH.

For what benefit? If your script actually uses all the items on the stack, and if your script is not written in such a way as to allow malleability (which cannot be prevented in general), then they’re equivalent. Using weight instead of depth only needlessly restricts other parties to select a witness size up-front.

And to be clear, signing witness weight doesn’t mean the witness is not malleable. The signer could sign again with a different ECDSA nonce. Or if the signer is signing from a 2-of-3 wallet, a common scenario I hope, there are 3 possible key combinations that could be used. If using MBV, a 3-element tree is inherently unbalanced and the common use case can have a smaller proof size.

Witnesses are not 3rd party malleable and we will maintain that property going forward with future opcodes.

> Mark, you seem to be arguing that in general we still want weight malleability even with witness depth fixed, but I don't understand in what scenario we would want that.

Any time all parties are not online at the same time in an interactive signing protocol, or for which individual parties have to reconfigure their signing choices due to failures. We should not restrict our script signature system to such a degree that it becomes difficult to create realistic signing setups for people using best practices (multi-key, 2FA, etc.) to sign. If I am a participant in a signing protocol, it would be layer violating to treat me as anything other than a black box, such that internal errors and timeouts in my signing setup don’t propagate upwards to the multi-party protocol.

For example, I should be able to try to 2FA sign, and if that fails go fetch my backup key and sign with that. But because it’s my infrequently used backup key, it might be placed deeper in the key tree and therefore signatures using it are larger. All the other signers need care is that slot #3 in the witness is where my Merkle proof goes. They shouldn’t have to restart and resign because my proof was a little larger than anticipated — and maybe they can’t resign because double-spend protections!

Re: [bitcoin-dev] Version 1 witness programs (first draft)

[Russell O'Connor]

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

On Sun, Oct 1, 2017 at 3:27 PM, Mark Friedenbach <mark@friedenbach.org>
wrote:

> > On Oct 1, 2017, at 12:05 PM, Russell O'Connor <roconnor@blockstream.io>
> wrote:
> >
> > Given the proposed fixed signature size, It seems better to me that we
> create a SIGHASH_WITNESS_WEIGHT flag as opposed to SIGHASH_WITNESS_DEPTH.
>
> For what benefit? If your script actually uses all the items on the stack,
> and if your script is not written in such a way as to allow malleability
> (which cannot be prevented in general), then they’re equivalent. Using
> weight instead of depth only needlessly restricts other parties to select a
> witness size up-front.
>

Creating a Bitcoin script that does not allow malleability is difficult and
requires wasting a lot of bytes to do so, typically when handling issues
around non-0-or-1 witness values being used with OP_IF, and dealing with
non-standard-zero values, etc.  Adding a witness weight flag cuts through
the worst of all this, and makes script design enormously simpler and makes
scripts smaller and cheaper.


> And to be clear, signing witness weight doesn’t mean the witness is not
> malleable. The signer could sign again with a different ECDSA nonce. Or if
> the signer is signing from a 2-of-3 wallet, a common scenario I hope, there
> are 3 possible key combinations that could be used. If using MBV, a
> 3-element tree is inherently unbalanced and the common use case can have a
> smaller proof size.
>
> Witnesses are not 3rd party malleable and we will maintain that property
> going forward with future opcodes.
>
> > Mark, you seem to be arguing that in general we still want weight
> malleability even with witness depth fixed, but I don't understand in what
> scenario we would want that.
>
> Any time all parties are not online at the same time in an interactive
> signing protocol, or for which individual parties have to reconfigure their
> signing choices due to failures. We should not restrict our script
> signature system to such a degree that it becomes difficult to create
> realistic signing setups for people using best practices (multi-key, 2FA,
> etc.) to sign. If I am a participant in a signing protocol, it would be
> layer violating to treat me as anything other than a black box, such that
> internal errors and timeouts in my signing setup don’t propagate upwards to
> the multi-party protocol.
>
> For example, I should be able to try to 2FA sign, and if that fails go
> fetch my backup key and sign with that. But because it’s my infrequently
> used backup key, it might be placed deeper in the key tree and therefore
> signatures using it are larger. All the other signers need care is that
> slot #3 in the witness is where my Merkle proof goes. They shouldn’t have
> to restart and resign because my proof was a little larger than anticipated
> — and maybe they can’t resign because double-spend protections!
>

I'll argue that I don't want my counter-party going off and using a very
deeply nested key in order to subvert the fee rate we've agreed upon after
I've signed my part of the input.  If we are doing multi-party signing of
inputs we need to communicate anyways to construct the transaction.  I see
no problem with requiring my counter-party to choose their keys before I
sign so that I know up front what our fee rate is going to be.  If they
lose their keys and need a backup, they should have to come back to me to
resign in order that we can negotiate a new fee rate for the transaction
and who is going to be covering how much of the fee and on which inputs.

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

Re: [bitcoin-dev] Version 1 witness programs (first draft)

[Mark Friedenbach]

> On Oct 1, 2017, at 12:41 PM, Russell O'Connor <roconnor@blockstream.io> wrote:
> 
> Creating a Bitcoin script that does not allow malleability is difficult and requires wasting a lot of bytes to do so, typically when handling issues around non-0-or-1 witness values being used with OP_IF, and dealing with non-standard-zero values, etc.

Script validation flags of the correct place to do this. We already have policy validation flags that check for these things. They were not made consensus rules with Segwit v0 mainly due to concern over scope creep in an already large overhaul, of my memory is correct. Script versions and quadratic hashing fixes where the minimum necessary to allow segwit to activate safely while still enabling future upgrades that would otherwise have been hard forks. We knew that we would be later changing the EC signature scheme to be something that supported signature aggregation, and that would be more appropriate time to discuss such changes. As we are considering to do now (although witness versions means we don’t need to omnibus the script upgrade here either, so a v1 before signature aggregation is ready is fine IMHO).

In any case if there is any general witness malleability due to opcode semantics that it’s not fixed by one of our existing policy flags, that is a bug and I would encourage you to report it.
> I'll argue that I don't want my counter-party going off and using a very deeply nested key in order to subvert the fee rate we've agreed upon after I've signed my part of the input.  If we are doing multi-party signing of inputs we need to communicate anyways to construct the transaction.  I see no problem with requiring my counter-party to choose their keys before I sign so that I know up front what our fee rate is going to be.  If they lose their keys and need a backup, they should have to come back to me to resign in order that we can negotiate a new fee rate for the transaction and who is going to be covering how much of the fee and on which inputs.

Arguing that every single user should be forced to restart an interactive signing session. That’s a very strong statement based on something that I would say is a preference that depends on circumstances.

What about an optional commitment to witness size in bytes? The value zero meaning “I don’t care.” I would argue that it should be a maximum however, and therefor serialized as part of the witness. The serialization of this would be very compact (1 plus the difference between actual and maximum, with zero meaning not used.)

Re: [bitcoin-dev] Version 1 witness programs (first draft)

[Luke Dashjr]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: Text/Plain; charset="gb18030", Size: 486 bytes --]

On Sunday 01 October 2017 8:39:11 PM Mark Friedenbach wrote:
> What about an optional commitment to witness size in bytes? The value zero
> meaning ¡°I don¡¯t care.¡± I would argue that it should be a maximum however,
> and therefor serialized as part of the witness. The serialization of this
> would be very compact (1 plus the difference between actual and maximum,
> with zero meaning not used.)

Could just do SIGHASH_WITNESS_SIZE in addition to SIGHASH_WITNESS_DEPTH...

Re: [bitcoin-dev] Version 1 witness programs (first draft)

[Russell O'Connor]

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

On Sun, Oct 1, 2017 at 4:39 PM, Mark Friedenbach <mark@friedenbach.org>
wrote:

>
> > On Oct 1, 2017, at 12:41 PM, Russell O'Connor <roconnor@blockstream.io>
> wrote:
> >
> > Creating a Bitcoin script that does not allow malleability is difficult
> and requires wasting a lot of bytes to do so, typically when handling
> issues around non-0-or-1 witness values being used with OP_IF, and dealing
> with non-standard-zero values, etc.
>
> Script validation flags of the correct place to do this. We already have
> policy validation flags that check for these things. They were not made
> consensus rules with Segwit v0 mainly due to concern over scope creep in an
> already large overhaul, of my memory is correct. Script versions and
> quadratic hashing fixes where the minimum necessary to allow segwit to
> activate safely while still enabling future upgrades that would otherwise
> have been hard forks. We knew that we would be later changing the EC
> signature scheme to be something that supported signature aggregation, and
> that would be more appropriate time to discuss such changes. As we are
> considering to do now (although witness versions means we don’t need to
> omnibus the script upgrade here either, so a v1 before signature
> aggregation is ready is fine IMHO).
>

Script validation isn't the correct place to do this.  The reason is that
script operations are not aware of whether the stack items they are
processing are witness malleable items or Script computed values.  Let me
take OP_IF as one example.  When OP_IF operates directly on witness data,
it is subject to witness malleability, and therefore one needs to add extra
code around that to prevent witness malleability.  On the other hand, when
OP_IF operates on computed data, it isn't subject to malleability and can
safely process non-zero-or-one values. If OP_IF were restricted to
requiring canonical inputs, then for the cases that OP_IF operates on
computed data, they will need to add extra code to canonicalize their
inputs.  I don't think there is a correct answer here.  That is because I
believe this isn't the correct place to aim to restrict witness
malleability.

OTOH, signatures are a fine place to aim to restrict witness malleability.
In fact, if signatures could securely cover all witness data, I think
everyone here would jump at the opportunity to implement that.  However,
since that isn't known to be possible, we are left with doing the best we
can, which is to have signatures cover weight (or bytes).  This prevents
the worst effects of witness malleability and does so without burdening
Script development.  (This also requires signatures have a fixed size, so
it is understandable that signature-covers-weight wasn't included in Segwit
v0 scripts).


> In any case if there is any general witness malleability due to opcode
> semantics that it’s not fixed by one of our existing policy flags, that is
> a bug and I would encourage you to report it.
> > I'll argue that I don't want my counter-party going off and using a very
> deeply nested key in order to subvert the fee rate we've agreed upon after
> I've signed my part of the input.  If we are doing multi-party signing of
> inputs we need to communicate anyways to construct the transaction.  I see
> no problem with requiring my counter-party to choose their keys before I
> sign so that I know up front what our fee rate is going to be.  If they
> lose their keys and need a backup, they should have to come back to me to
> resign in order that we can negotiate a new fee rate for the transaction
> and who is going to be covering how much of the fee and on which inputs.
>
> Arguing that every single user should be forced to restart an interactive
> signing session. That’s a very strong statement based on something that I
> would say is a preference that depends on circumstances.
>
> What about an optional commitment to witness size in bytes? The value zero
> meaning “I don’t care.” I would argue that it should be a maximum however,
> and therefor serialized as part of the witness. The serialization of this
> would be very compact (1 plus the difference between actual and maximum,
> with zero meaning not used.)


I would be fine your suggestion above, though I think Luke's suggestion of
having both SIGHASH_WITNESS_SIZE and SIGHASH_WITNESS_DEPTH flag is better
because it is simpler.

Those people worried about restarting interactive signing session in the
unlikely event of parties not knowing what keys they are planning to use
can use just the SIGHASH_WITNESS_DEPTH flag.  Those people worried about
counterparties fiddling with fee rates can use both flags.  The choice
doesn't even need to be made at script commitment time.

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

Re: [bitcoin-dev] Version 1 witness programs (first draft)

[Mark Friedenbach]

I would also suggest that the 520 byte push limitation be removed for v1 scripts as well. MERKLEBRANCHVERIFY in particular could benefit from larger proof sizes. To do so safely would require reworking script internals to use indirect pointers and reference counting for items on stack, but this is worth doing generally, and introducing a per-input hashing limit equal to a small multiple of the witness size (or retaining the opcount limit).

> On Sep 30, 2017, at 6:13 PM, Luke Dashjr via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
> I've put together a first draft for what I hope to be a good next step for 
> Segwit and Bitcoin scripting:
>    https://github.com/luke-jr/bips/blob/witnessv1/bip-witnessv1.mediawiki
> 
> This introduces 5 key changes:
> 
> 1. Minor versions for witnesses, inside the witness itself. Essentially the 
> witness [major] version 1 simply indicates the witness commitment is SHA256d, 
> and nothing more.
> 
> The remaining two are witness version 1.0 (major 1, minor 0):
> 
> 2. As previously discussed, undefined opcodes immediately cause the script to 
> exit with success, making future opcode softforks a lot more flexible.
> 
> 3. If the final stack element is not exactly true or false, it is interpreted 
> as a tail-call Script and executed. (Credit to Mark Friedenbach)
> 
> 4. A new shorter fixed-length signature format, eliminating the need to guess 
> the signature size in advance. All signatures are 65 bytes, unless a condition 
> script is included (see #5).
> 
> 5. The ability for signatures to commit to additional conditions, expressed in 
> the form of a serialized Script in the signature itself. This would be useful 
> in combination with OP_CHECKBLOCKATHEIGHT (BIP 115), hopefully ending the 
> whole replay protection argument by introducing it early to Bitcoin before any 
> further splits.
> 
> This last part is a big ugly right now: the signature must commit to the 
> script interpreter flags and internal "sigversion", which basically serve the 
> same purpose. The reason for this, is that otherwise someone could move the 
> signature to a different context in an attempt to exploit differences in the 
> various Script interpretation modes. I don't consider the BIP deployable 
> without this getting resolved, but I'm not sure what the best approach would 
> be. Maybe it should be replaced with a witness [major] version and witness 
> stack?
> 
> There is also draft code implementing [the consensus side of] this:
>    https://github.com/bitcoin/bitcoin/compare/master...luke-jr:witnessv1
> 
> Thoughts? Anything I've overlooked / left missing that would be 
> uncontroversial and desirable? (Is any of this unexpectedly controversial for 
> some reason?)
> 
> Luke
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Version 1 witness programs (first draft)

[Johnson Lau]

So there are 3 proposals with similar goal but different designs. I try to summarise some questions below:

1. How do we allow further upgrade within v1 witness? Here are some options:
a. Minor version in witness. (Johnson / Luke) I prefer this way, but we may end up with many minor versions.
b. OP_RETURNTRUE (Luke). I proposed this in an earlier version of BIP114 but now I think it doesn’t interact well with signature aggregation, and I worry that it would have some other unexpected effects.
c. Generalised NOP method: user has to provide the returned value, so even VERIFY-type code could do anything

2. Do we want to allow signature-time commitment of extra scripts?
I think all proposals allow this, just with different way
a. Tail-call semantics with CHECKSIGFROMSTACK (Mark). I think this is too rigid as it works only with specially designed scriptPubKey
b. scriptWitCode: extra scripts are put in some fixed location in witness (Johnson). This makes sure static analysability.
c. Extra-data as script in OP_CHECKSIG (Luke)

3. Do we want to allow static analysis of sigop?
BIP114 and the related proposals are specifically designed to allow static analysis of sigop. I think this was one of the main reason of OP_EVAL not being accepted. This was also the main reason of Ethereum failing to do a DAO hacker softfork, leading to the ETH/ETC split. I’m not sure if we really want to give up this property. Once we do it, we have to support it forever.

——
Johnson

Re: [bitcoin-dev] Version 1 witness programs (first draft)

[Mark Friedenbach]

> On Oct 1, 2017, at 2:32 PM, Johnson Lau <jl2012@xbt.hk> wrote:
> 
> So there are 3 proposals with similar goal but different designs. I try to summarise some questions below:
> 
> 1. How do we allow further upgrade within v1 witness? Here are some options:
> a. Minor version in witness. (Johnson / Luke) I prefer this way, but we may end up with many minor versions.

I'm not sure I agree with the "minor version" nomenclature, or that we would necessarily end up with any consensus-visible fields beyond 2.  There are two separate soft-fork version fields that were, I think it is fair to say now, inappropriately merged in the "script version” feature of segregated witness as described in BIP141.

First there is the witness type, which combined with the length of the commitment that follows specifies how data from the witness stack is used to calculate/verify the witness commitment in the scriptPubKey of the output being spent.  For v0 with a 20-byte hash, it says that those 20 bytes are the HASH160 of the top element of the stack.  For v0 with a 32-byte hash, it says that those 32 bytes are the HASH256 of the top element of the stack.

Second there is the script version, which is not present as a separate field for witness type v0.  Implicitly though, the script version for v0,20-byte is that the witness consists of two elements, and these are interpreted as a pubkey and a signature.  For v0,32-byte the script version is that the witness consists of 1 or more elements; with max 520 byte size constraints for all but the top element, which has a higher limit of 10,000 bytes; and the top-most element is interpreted as a script and executed with the modified CHECKSIG behavior defined by BIP141 and the CLEANSTACK rule enforced.

These are separate roles, one not being derivative of the other.  In an ideal world the witness type (of which there are only 16 remaining without obsoleting BIP141) is used only to specify a new function for transforming the witness stack into a commitment for verification purposes.  Merklized script would be one example: v2,32-byte could be defined to require a witness stack of at least two elements, the top most of which is a Merkle inclusion proof of the second item in a tree whose root is given in the 32-byte payload of the output.  Maybe v3 would prove inclusion by means of some sort of RSA accumulator or something.

Such a specification says nothing about the features of the subscript drawn from the Merkle tree, or even whether it is bitcoin script at all vs something else (Simplicity, DEX, RISC-V, Joy, whatever).  All that is necessary is that a convention be adopted about where to find the script version from whatever data is left on the stack after doing the witness type check (hashing the script, calculating a Merkle root, checking inclusion in an RSA accumulator, whatever).  A simple rule is that it is serialized and prefixed to the beginning of the string that was checked against the commitment in the output.

So v0,32-byte says that the top item is hashed and that hash must match the 32-byte value in the output.  This new v1,32-byte witness type being talked about in this thread would have exactly the same hashing rules, but will execute the resulting string based on its prefix, the script version, which is first removed before execution.

Sure first script version used could be a cleaned up script with a bunch of the weirdness removed (CHECKMULTISIG, I'm looking at you!); CLTV, CSV, and MBV drop arguments; disabled opcodes and unassigned NOPs become "return true"; etc.  Maybe v2 adds new opcodes.  But we can imagine script version that do something totally different, like introduce a new script based on a strongly-typed Merklized lambda calculus, or a RISC-V executable format, or whatever.

This has pragmatic implications with the separation of witness type and script version: we could then define a "MAST" output that proves the script used is drawn from a set represented by the Merkle tree.  However different scripts in that tree can use different versions.  It would be useful if the most common script is the key aggregated everyone-signs outcome, which looks like a regular bitcoin payment, and then contingency cases can be handled by means of a complicated script written in some newly added general computation language or a whole emulated RISC-V virtual machine.

> b. OP_RETURNTRUE (Luke). I proposed this in an earlier version of BIP114 but now I think it doesn’t interact well with signature aggregation, and I worry that it would have some other unexpected effects.
> c. Generalised NOP method: user has to provide the returned value, so even VERIFY-type code could do anything

I see no reason to do either. Gate new behavior based on script execution flags, which are set based on the script version.  Script versions not understood are treated as "return true" to begin with.  The interpreter isn't even going to try to decode the script according to the old rules, let alone try to execute it, so there's no reason for the old soft-fork compatability tricks.

The new soft-fork trick is that you increment the script version number.  That is all.

> 2. Do we want to allow signature-time commitment of extra scripts?
> I think all proposals allow this, just with different way
> a. Tail-call semantics with CHECKSIGFROMSTACK (Mark). I think this is too rigid as it works only with specially designed scriptPubKey

This is not signature-time commitment of extra script. Not without CHECKSIGFROMSTACK or something like it.

> b. scriptWitCode: extra scripts are put in some fixed location in witness (Johnson). This makes sure static analysability.
> c. Extra-data as script in OP_CHECKSIG (Luke)

Propose these as their own script updates.  Script versioning makes such new features cheap.  There's no reason to create some sort of complex omnibus overhaul that does everything.

> 3. Do we want to allow static analysis of sigop?
> BIP114 and the related proposals are specifically designed to allow static analysis of sigop. I think this was one of the main reason of OP_EVAL not being accepted. This was also the main reason of Ethereum failing to do a DAO hacker softfork, leading to the ETH/ETC split. I’m not sure if we really want to give up this property. Once we do it, we have to support it forever.

Again, this is off-topic for this thread.  I don't think a v1 witness type upgrade should do any of these things.  The v1 witness type should add a proper script version in the witness, and remove or simplify limits or unnecessary verification rules that are no longer necessary and/or hindering progress.  That’s it.

For example, I don't think a v1 witness version should be coupled with my tail-call semantics or the introduction of MERKLEBRANCHVERIFY (but if MBV was released already we could have it drop its arguments, which would be nice).  However it should drop the CLEANSTACK rule in favor of something else (like signatures committing to the witness depth and/or weight) since the tail-call BIP demonstrates it to be an impediment to extensibility and alternatives are not.  And it should drop the 520 byte push limitation, as the MBV BIP demonstrates use cases that have serialized proofs larger than that, like a k-of-N threshold with N=16.

Re: [bitcoin-dev] Version 1 witness programs (first draft)

[Luke Dashjr]

On Monday 02 October 2017 12:35:38 AM Mark Friedenbach wrote:
> > b. OP_RETURNTRUE (Luke). I proposed this in an earlier version of BIP114
> > but now I think it doesn’t interact well with signature aggregation, and
> > I worry that it would have some other unexpected effects. c. Generalised
> > NOP method: user has to provide the returned value, so even VERIFY-type
> > code could do anything
> 
> I see no reason to do either. Gate new behavior based on script execution
> flags, which are set based on the script version.  Script versions not
> understood are treated as "return true" to begin with.  The interpreter
> isn't even going to try to decode the script according to the old rules,
> let alone try to execute it, so there's no reason for the old soft-fork
> compatability tricks.
> 
> The new soft-fork trick is that you increment the script version number. 
> That is all.

This breaks parallel softfork deployments.

> > b. scriptWitCode: extra scripts are put in some fixed location in witness
> > (Johnson). This makes sure static analysability. c. Extra-data as script
> > in OP_CHECKSIG (Luke)
> 
> Propose these as their own script updates.  Script versioning makes such
> new features cheap.  There's no reason to create some sort of complex
> omnibus overhaul that does everything.

Only if there's common code to implement both versions, which doesn't work if 
the changes from A to B to C are drastic. To avoid such drastic changes, the 
overall design/layout needs to at least be planned to cover the desired use 
cases in advance.

Luke

Re: [bitcoin-dev] Version 1 witness programs (first draft)

[Sjors Provoost]

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

Op 2 okt. 2017, om 03:56 heeft Luke Dashjr via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> het volgende geschreven:
> 
> On Monday 02 October 2017 12:35:38 AM Mark Friedenbach wrote:
>>> b. OP_RETURNTRUE (Luke). I proposed this in an earlier version of BIP114
>>> but now I think it doesn’t interact well with signature aggregation, and
>>> I worry that it would have some other unexpected effects. c. Generalised
>>> NOP method: user has to provide the returned value, so even VERIFY-type
>>> code could do anything
>> 
>> I see no reason to do either. Gate new behavior based on script execution
>> flags, which are set based on the script version.  Script versions not
>> understood are treated as "return true" to begin with.  The interpreter
>> isn't even going to try to decode the script according to the old rules,
>> let alone try to execute it, so there's no reason for the old soft-fork
>> compatability tricks.
>> 
>> The new soft-fork trick is that you increment the script version number.
>> That is all.
> 
> This breaks parallel softfork deployments.

If unknown script versions are treated as "return true", there's no need for versions to be deployed in sequence, right? Maybe they should be called numbered script types, rather than script versions.

Sjors

[-- Attachment #2: Message signed with OpenPGP --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [bitcoin-dev] Version 1 witness programs (first draft)

[Luke Dashjr]

On Sunday 01 October 2017 9:32:56 PM Johnson Lau wrote:
> 1. How do we allow further upgrade within v1 witness? Here are some
> options: a. Minor version in witness. (Johnson / Luke) I prefer this way,
> but we may end up with many minor versions. b. OP_RETURNTRUE (Luke). I
> proposed this in an earlier version of BIP114 but now I think it doesn’t
> interact well with signature aggregation, and I worry that it would have
> some other unexpected effects. c. Generalised NOP method: user has to
> provide the returned value, so even VERIFY-type code could do anything

I like (A) and (B). Use B when practical, and (A) when more fundamental 
changes are needed. SigAgg is a concern, but there are ways to adapt it.

(C) is harmless, but I think unnecessary with (A) and/or (B).

> 2. Do we want to allow signature-time commitment of extra scripts?
> I think all proposals allow this, just with different way
> a. Tail-call semantics with CHECKSIGFROMSTACK (Mark). I think this is too
> rigid as it works only with specially designed scriptPubKey b.
> scriptWitCode: extra scripts are put in some fixed location in witness
> (Johnson). This makes sure static analysability. c. Extra-data as script
> in OP_CHECKSIG (Luke)

Note that my BIP draft supports both (A) and (C).

> 3. Do we want to allow static analysis of sigop?
> BIP114 and the related proposals are specifically designed to allow static
> analysis of sigop. I think this was one of the main reason of OP_EVAL not
> being accepted. This was also the main reason of Ethereum failing to do a
> DAO hacker softfork, leading to the ETH/ETC split. I’m not sure if we
> really want to give up this property. Once we do it, we have to support it
> forever.

It seems inevitable at this point. Maybe we could add a separate "executable-
witness" array (in the same manner as the current witness was softforked in), 
and require tail-call and condition scripts to merely reference these by hash, 
but I'm not sure it's worth the effort?

Thinking further, we could avoid adding a separate executable-witness 
commitment by either:
A) Define that all the witness elements in v1 are type-tagged (put the minor
   witness version on them all, and redefine minor 0 as a stack item?); or
B) Use an empty element as a delimiter between stack and executable items.

To avoid witness malleability, the executable items can be required to be 
sorted in some manner.

The downside of these approaches is that we now need an addition 20 or 32 
bytes per script reference... which IMO may possibly be worse than losing 
static analysis. I wonder if there's a way to avoid that overhead?

Luke

Re: [bitcoin-dev] Version 1 witness programs (first draft)

[Mark Friedenbach]

Here’s an additional (uncontroversial?) idea due to Russell O’Connor:

Instead of requiring that the last item popped off the stack in a CHECKMULTISIG be zero, have it instead be required that it is a bitfield specifying which pubkeys are used, or more likely the complement thereof. This allows signatures to be matched to pubkeys in the order given, and batch validated, with no risk of 3rd party malleability.

Mark

> On Sep 30, 2017, at 6:13 PM, Luke Dashjr via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
> I've put together a first draft for what I hope to be a good next step for 
> Segwit and Bitcoin scripting:
>    https://github.com/luke-jr/bips/blob/witnessv1/bip-witnessv1.mediawiki
> 
> This introduces 5 key changes:
> 
> 1. Minor versions for witnesses, inside the witness itself. Essentially the 
> witness [major] version 1 simply indicates the witness commitment is SHA256d, 
> and nothing more.
> 
> The remaining two are witness version 1.0 (major 1, minor 0):
> 
> 2. As previously discussed, undefined opcodes immediately cause the script to 
> exit with success, making future opcode softforks a lot more flexible.
> 
> 3. If the final stack element is not exactly true or false, it is interpreted 
> as a tail-call Script and executed. (Credit to Mark Friedenbach)
> 
> 4. A new shorter fixed-length signature format, eliminating the need to guess 
> the signature size in advance. All signatures are 65 bytes, unless a condition 
> script is included (see #5).
> 
> 5. The ability for signatures to commit to additional conditions, expressed in 
> the form of a serialized Script in the signature itself. This would be useful 
> in combination with OP_CHECKBLOCKATHEIGHT (BIP 115), hopefully ending the 
> whole replay protection argument by introducing it early to Bitcoin before any 
> further splits.
> 
> This last part is a big ugly right now: the signature must commit to the 
> script interpreter flags and internal "sigversion", which basically serve the 
> same purpose. The reason for this, is that otherwise someone could move the 
> signature to a different context in an attempt to exploit differences in the 
> various Script interpretation modes. I don't consider the BIP deployable 
> without this getting resolved, but I'm not sure what the best approach would 
> be. Maybe it should be replaced with a witness [major] version and witness 
> stack?
> 
> There is also draft code implementing [the consensus side of] this:
>    https://github.com/bitcoin/bitcoin/compare/master...luke-jr:witnessv1
> 
> Thoughts? Anything I've overlooked / left missing that would be 
> uncontroversial and desirable? (Is any of this unexpectedly controversial for 
> some reason?)
> 
> Luke
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Version 1 witness programs (first draft)

[Russell O'Connor]

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

On Thu, Oct 5, 2017 at 4:33 PM, Mark Friedenbach via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Here’s an additional (uncontroversial?) idea due to Russell O’Connor:
>

For the record, it's Johnson Lau's proposal where I read this idea.

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