Discussion:
Version 1 witness programs (first draft)
(too old to reply)
Luke Dashjr via bitcoin-dev
2017-10-01 01:13:29 UTC
Permalink
Raw Message
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
Mark Friedenbach via bitcoin-dev
2017-10-01 02:23:47 UTC
Permalink
Raw Message
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.
Post by Luke Dashjr via bitcoin-dev
I've put together a first draft for what I hope to be a good next step for
https://github.com/luke-jr/bips/blob/witnessv1/bip-witnessv1.mediawiki
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.
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?
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
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Luke Dashjr via bitcoin-dev
2017-10-01 02:47:41 UTC
Permalink
Raw Message
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
Post by Mark Friedenbach via bitcoin-dev
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
I've put together a first draft for what I hope to be a good next step for
https://github.com/luke-jr/bips/blob/witnessv1/bip-witnessv1.mediawiki
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.
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?
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
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Mark Friedenbach via bitcoin-dev
2017-10-01 05:04:32 UTC
Permalink
Raw Message
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.
Post by Luke Dashjr via bitcoin-dev
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
Felix Weis via bitcoin-dev
2017-10-01 11:22:30 UTC
Permalink
Raw Message
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 <
Post by Mark Friedenbach via bitcoin-dev
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.
Post by Luke Dashjr via bitcoin-dev
Should it perhaps commit to the length of the serialised witness data
instead
Post by Luke Dashjr via bitcoin-dev
or additionally? Now that signatures are no longer variable-length,
that'd be
Post by Luke Dashjr via bitcoin-dev
possible...
As far as tail-call needs are concerned, CLEANSTACK wouldn't have been
checked
Post by Luke Dashjr via bitcoin-dev
until AFTER the tail-call in the first draft. But I suppose eliminating
it for
Post by Luke Dashjr via bitcoin-dev
other possible future purposes is still useful.
Luke
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Luke Dashjr via bitcoin-dev
2017-10-01 17:36:05 UTC
Permalink
Raw Message
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
Post by Felix Weis via bitcoin-dev
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 <
Post by Mark Friedenbach via bitcoin-dev
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.
Post by Luke Dashjr via bitcoin-dev
Should it perhaps commit to the length of the serialised witness data
instead
Post by Luke Dashjr via bitcoin-dev
or additionally? Now that signatures are no longer variable-length,
that'd be
Post by Luke Dashjr via bitcoin-dev
possible...
As far as tail-call needs are concerned, CLEANSTACK wouldn't have been
checked
Post by Luke Dashjr via bitcoin-dev
until AFTER the tail-call in the first draft. But I suppose eliminating
it for
Post by Luke Dashjr via bitcoin-dev
other possible future purposes is still useful.
Luke
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Russell O'Connor via bitcoin-dev
2017-10-01 19:05:38 UTC
Permalink
Raw Message
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 <
Post by Mark Friedenbach via bitcoin-dev
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.
Post by Luke Dashjr via bitcoin-dev
Should it perhaps commit to the length of the serialised witness data
instead
Post by Luke Dashjr via bitcoin-dev
or additionally? Now that signatures are no longer variable-length,
that'd be
Post by Luke Dashjr via bitcoin-dev
possible...
As far as tail-call needs are concerned, CLEANSTACK wouldn't have been
checked
Post by Luke Dashjr via bitcoin-dev
until AFTER the tail-call in the first draft. But I suppose eliminating
it for
Post by Luke Dashjr via bitcoin-dev
other possible future purposes is still useful.
Luke
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Mark Friedenbach via bitcoin-dev
2017-10-01 19:27:21 UTC
Permalink
Raw Message
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!
Russell O'Connor via bitcoin-dev
2017-10-01 19:41:46 UTC
Permalink
Raw Message
Post by Russell O'Connor via bitcoin-dev
Post by Russell O'Connor via bitcoin-dev
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.
Post by Russell O'Connor via bitcoin-dev
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.
Post by Russell O'Connor via bitcoin-dev
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.
Mark Friedenbach via bitcoin-dev
2017-10-01 20:39:11 UTC
Permalink
Raw Message
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.)
Luke Dashjr via bitcoin-dev
2017-10-01 20:43:18 UTC
Permalink
Raw Message
Post by Mark Friedenbach via bitcoin-dev
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...
Russell O'Connor via bitcoin-dev
2017-10-02 20:38:49 UTC
Permalink
Raw Message
Post by Russell O'Connor via bitcoin-dev
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.
Post by Russell O'Connor via bitcoin-dev
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.
Mark Friedenbach via bitcoin-dev
2017-10-01 18:34:07 UTC
Permalink
Raw Message
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).
Post by Luke Dashjr via bitcoin-dev
I've put together a first draft for what I hope to be a good next step for
https://github.com/luke-jr/bips/blob/witnessv1/bip-witnessv1.mediawiki
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.
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?
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
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Johnson Lau via bitcoin-dev
2017-10-01 21:32:56 UTC
Permalink
Raw Message
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
Mark Friedenbach via bitcoin-dev
2017-10-02 00:35:38 UTC
Permalink
Raw Message
Post by Johnson Lau via bitcoin-dev
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.
Post by Johnson Lau via bitcoin-dev
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.
Post by Johnson Lau via bitcoin-dev
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.
Post by Johnson Lau via bitcoin-dev
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.
Post by Johnson Lau via bitcoin-dev
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.
Luke Dashjr via bitcoin-dev
2017-10-02 02:56:27 UTC
Permalink
Raw Message
Post by Mark Friedenbach via bitcoin-dev
Post by Johnson Lau via bitcoin-dev
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.
Post by Mark Friedenbach via bitcoin-dev
Post by Johnson Lau via bitcoin-dev
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
Sjors Provoost via bitcoin-dev
2017-10-02 09:09:00 UTC
Permalink
Raw Message
Post by Luke Dashjr via bitcoin-dev
Post by Mark Friedenbach via bitcoin-dev
Post by Johnson Lau via bitcoin-dev
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
Luke Dashjr via bitcoin-dev
2017-10-02 00:45:22 UTC
Permalink
Raw Message
Post by Johnson Lau via bitcoin-dev
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).
Post by Johnson Lau via bitcoin-dev
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).
Post by Johnson Lau via bitcoin-dev
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
Mark Friedenbach via bitcoin-dev
2017-10-05 20:33:56 UTC
Permalink
Raw Message
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
Post by Luke Dashjr via bitcoin-dev
I've put together a first draft for what I hope to be a good next step for
https://github.com/luke-jr/bips/blob/witnessv1/bip-witnessv1.mediawiki
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.
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?
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
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Russell O'Connor via bitcoin-dev
2017-10-05 21:28:48 UTC
Permalink
Raw Message
On Thu, Oct 5, 2017 at 4:33 PM, Mark Friedenbach via bitcoin-dev <
For the record, it's Johnson Lau's proposal where I read this idea.
Loading...