Re: [bitcoin-dev] cleanstack alt stack & softfork improvements (Was: Merkle branch verification & tail-call semantics for generalized MAST)

[Mark Friedenbach via bitcoin-dev]

There is no harm in the value being a maximum off by a few bytes.

> On Sep 22, 2017, at 2:54 PM, Sergio Demian Lerner  
> wrote:
> 
> If the variable size increase is only a few bytes, then three possibilities 
> arise:
> 
> - one should allow signatures to be zero padded (to reach the maximum size) 
> and abandon strict DER encoding
> 
> - one should allow spare witness stack elements (to pad the size to match the 
> maximum size) and remove the cleanstack rule. But this is tricky because 
> empty stack elements must be counted as 1 byte.
> 
> - signers must loop the generation of signatures until the signature 
> generated is of its maximum size.

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] cleanstack alt stack & softfork improvements (Was: Merkle branch verification & tail-call semantics for generalized MAST)

[Sergio Demian Lerner via bitcoin-dev]

If the variable size increase is only a few bytes, then three possibilities
arise:

- one should allow signatures to be zero padded (to reach the maximum size)
and abandon strict DER encoding

- one should allow spare witness stack elements (to pad the size to match
the maximum size) and remove the cleanstack rule. But this is tricky
because empty stack elements must be counted as 1 byte.

- signers must loop the generation of signatures until the signature
generated is of its maximum size.




On Fri, Sep 22, 2017 at 6:39 PM, Mark Friedenbach 
wrote:

> You generally know the witness size to within a few bytes right before
> signing. Why would you not? You know the size of ECDSA signatures. You can
> be told the size of a hash preimage by the other party. It takes some
> contriving to come up with a scheme where one party has variable-length
> signatures of their chosing
>
> > On Sep 22, 2017, at 2:32 PM, Sergio Demian Lerner <
> sergio.d.ler...@gmail.com> wrote:
> >
> > But generally before one signs a transaction one does not know the
> signature size (which may be variable). One can only estimate the maximum
> size.
>
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] cleanstack alt stack & softfork improvements (Was: Merkle branch verification & tail-call semantics for generalized MAST)

[Mark Friedenbach via bitcoin-dev]

You generally know the witness size to within a few bytes right before signing. 
Why would you not? You know the size of ECDSA signatures. You can be told the 
size of a hash preimage by the other party. It takes some contriving to come up 
with a scheme where one party has variable-length signatures of their chosing

> On Sep 22, 2017, at 2:32 PM, Sergio Demian Lerner  
> wrote:
> 
> But generally before one signs a transaction one does not know the signature 
> size (which may be variable). One can only estimate the maximum size. 

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] cleanstack alt stack & softfork improvements (Was: Merkle branch verification & tail-call semantics for generalized MAST)

[Sergio Demian Lerner via bitcoin-dev]

But generally before one signs a transaction one does not know the
signature size (which may be variable). One can only estimate the maximum
size.

On Fri, Sep 22, 2017 at 6:11 PM, Mark Friedenbach 
wrote:

>
> On Sep 22, 2017, at 1:32 PM, Sergio Demian Lerner <
> sergio.d.ler...@gmail.com> wrote:
>
>
>>
>> There are other solutions to this problem that could have been taken
>> instead, such as committing to the number of items or maximum size of
>> the stack as part of the sighash data, but cleanstack was the approach
>> taken.
>
>
> The lack of signed maximum segwit stack size was one of the objections to
> segwit I presented last year. This together with the unlimited segwit stack
> size.
>
> However, committing to the maximum stack size (in bytes) for an input is
> tricky. The only place where this could be packed is in sequence_no, with a
> soft-fork. E.g. when transaction version is 2 and and only when lock_time
> is zero.
>
> For transactions with locktime >0, we could soft-fork so transactions add
> a last zero-satoshi output whose scriptPub contains OP_RETURN and followed
> by N VarInts, containing the maximum stack size of each input.
> Normally, for a 400 byte, 2-input transaction, this will add 11 bytes, or
> a 2.5% overhead.
>
>
> There’s no need to put it in the transaction itself. You put it in the
> witness and it is either committed to as part of the witness (in which case
> it has to hold for all possible spend paths), or at spend time by including
> it in the data signed by CHECKSIG.
>
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] cleanstack alt stack & softfork improvements (Was: Merkle branch verification & tail-call semantics for generalized MAST)

[Mark Friedenbach via bitcoin-dev]

> On Sep 22, 2017, at 1:32 PM, Sergio Demian Lerner  
> wrote:
> 
> 
> 
> There are other solutions to this problem that could have been taken
> instead, such as committing to the number of items or maximum size of
> the stack as part of the sighash data, but cleanstack was the approach
> taken. 
> 
> The lack of signed maximum segwit stack size was one of the objections to 
> segwit I presented last year. This together with the unlimited segwit stack 
> size.
> 
> However, committing to the maximum stack size (in bytes) for an input is 
> tricky. The only place where this could be packed is in sequence_no, with a 
> soft-fork. E.g. when transaction version is 2 and and only when lock_time is 
> zero.
> 
> For transactions with locktime >0, we could soft-fork so transactions add a 
> last zero-satoshi output whose scriptPub contains OP_RETURN and followed by N 
> VarInts, containing the maximum stack size of each input. 
> Normally, for a 400 byte, 2-input transaction, this will add 11 bytes, or a 
> 2.5% overhead.

There’s no need to put it in the transaction itself. You put it in the witness 
and it is either committed to as part of the witness (in which case it has to 
hold for all possible spend paths), or at spend time by including it in the 
data signed by CHECKSIG.

___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] cleanstack alt stack & softfork improvements (Was: Merkle branch verification & tail-call semantics for generalized MAST)

[Sergio Demian Lerner via bitcoin-dev]

>
> There are other solutions to this problem that could have been taken
> instead, such as committing to the number of items or maximum size of
> the stack as part of the sighash data, but cleanstack was the approach
> taken.


The lack of signed maximum segwit stack size was one of the objections to
segwit I presented last year. This together with the unlimited segwit stack
size.

However, committing to the maximum stack size (in bytes) for an input is
tricky. The only place where this could be packed is in sequence_no, with a
soft-fork. E.g. when transaction version is 2 and and only when lock_time
is zero.

For transactions with locktime >0, we could soft-fork so transactions add a
last zero-satoshi output whose scriptPub contains OP_RETURN and followed by
N VarInts, containing the maximum stack size of each input.
Normally, for a 400 byte, 2-input transaction, this will add 11 bytes, or a
2.5% overhead.








> Arguably for a future script version upgrade one of these other
> approaches should be taken to allow for shorter tail-call scripts.
>
> Mark
>
> * Well, almost any. You could end the script with DEPTH EQUAL and that
>   is a compact way of ensuring the stack is clean (assuming the script
>   finished with just "true" on the stack). Nobody does this however
>   and burning two witness bytes of every redeem script going forward
>   as a protective measure seems like an unnecessary ask.
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] cleanstack alt stack & softfork improvements (Was: Merkle branch verification & tail-call semantics for generalized MAST)

[Johnson Lau via bitcoin-dev]

> On 22 Sep 2017, at 12:33 AM, Luke Dashjr  wrote:
> 
> On Thursday 21 September 2017 8:02:42 AM Johnson Lau wrote:
>> I think it’s possible only if you spend more witness space to store the
>> (pubkey, message) pairs, so that old clients could understand the
>> aggregation produced by new clients. But this completely defeats the
>> purpose of doing aggregation.
> 
> SigAgg is a softfork, so old clients *won't* understand it... am I missing 
> something?
> 
> For example, perhaps the lookup opcode could have a data payload itself (eg, 
> like pushdata opcodes do), and the script can be parsed independently from 
> execution to collect the applicable ones.

I think the current idea of sigagg is something like this: the new OP_CHECKSIG 
still has 2 arguments: top stack must be a 33-byte public key, and the 2nd top 
stack item is signature. Depends on the sig size, it returns different value:

If sig size is 0, it returns a 0 to the top stack
If sig size is 1, it is treated as a SIGHASH flag, and the SignatureHash() 
“message” is calculated. It sends the (pubkey, message) pair to the aggregator, 
and always returns a 1 to the top stack
If sig size is >1, it is treated as the aggregated signature. The last byte is 
SIGHASH flag. It sends the (pubkey, message) pair and the aggregated signature 
to the aggregator, and always returns a 1 to the top stack.

If all scripts pass, the aggregator will combine all pairs to obtain the aggkey 
and aggmsg, and verify against aggsig. A tx may have at most 1 aggsig.

(The version I presented above is somewhat simplified but should be enough to 
illustrate my point)

So if we have this script:

OP_1 OP_RETURNTRUE  OP_CHECKSIG

Old clients would stop at the OP_RETURNTRUE, and will not send the pubkey to 
the aggregator

If we softfork OP_RETURNTRUE to something else, even as OP_NOP11, new clients 
will send the (key, msg) pair to the aggregator. Therefore, the aggregator of 
old and new clients will see different data, leading to a hardfork.

OTOH, OP_NOP based softfork would not have this problem because it won’t 
terminate script and return true.


> 
>>> This is another approach, and one that seems like a good idea in general.
>>> I'm not sure it actually needs to take more witness space - in theory,
>>> such stack items could be implied if the Script engine is designed for
>>> it upfront. Then it would behave as if it were non-verify, while
>>> retaining backward compatibility.
>> 
>> Sounds interesting but I don’t get it. For example, how could you make a
>> OP_MUL out of OP_NOP?
> 
> The same as your OP_MULVERIFY at the consensus level, except new clients 
> would 
> execute it as an OP_MUL, and inject pops/pushes when sending such a 
> transaction to older clients. The hash committed to for the script would 
> include the inferred values, but not the actual on-chain data. This would 
> probably need to be part of some kind of MAST-like softfork to be viable, and 
> maybe not even then.
> 
> Luke

I don’t think it’s worth the code complexity, just to save a few bytes of data 
sent over wire; and to be a soft fork, it still takes the block space.

Maybe we could create many OP_DROPs and OP_2DROPs, so new VERIFY operations 
could pop the stack. This saves 1 byte and also looks cleaner.

Another approach is to use a new script version for every new non-verify type 
operation. Problem is we will end up with many versions. Also, signatures from 
different versions can’t be aggregated. (We may have multiple aggregators in a 
transaction)



___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] cleanstack alt stack & softfork improvements (Was: Merkle branch verification & tail-call semantics for generalized MAST)

[Luke Dashjr via bitcoin-dev]

On Thursday 21 September 2017 8:02:42 AM Johnson Lau wrote:
> I think it’s possible only if you spend more witness space to store the
> (pubkey, message) pairs, so that old clients could understand the
> aggregation produced by new clients. But this completely defeats the
> purpose of doing aggregation.

SigAgg is a softfork, so old clients *won't* understand it... am I missing 
something?

For example, perhaps the lookup opcode could have a data payload itself (eg, 
like pushdata opcodes do), and the script can be parsed independently from 
execution to collect the applicable ones.

> > This is another approach, and one that seems like a good idea in general.
> > I'm not sure it actually needs to take more witness space - in theory,
> > such stack items could be implied if the Script engine is designed for
> > it upfront. Then it would behave as if it were non-verify, while
> > retaining backward compatibility.
> 
> Sounds interesting but I don’t get it. For example, how could you make a
> OP_MUL out of OP_NOP?

The same as your OP_MULVERIFY at the consensus level, except new clients would 
execute it as an OP_MUL, and inject pops/pushes when sending such a 
transaction to older clients. The hash committed to for the script would 
include the inferred values, but not the actual on-chain data. This would 
probably need to be part of some kind of MAST-like softfork to be viable, and 
maybe not even then.

Luke
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] cleanstack alt stack & softfork improvements (Was: Merkle branch verification & tail-call semantics for generalized MAST)

[Johnson Lau via bitcoin-dev]

> On 21 Sep 2017, at 12:11 PM, Luke Dashjr  wrote:
> 
> On Wednesday 20 September 2017 5:13:04 AM Johnson Lau wrote:
>> 2. OP_RETURNTRUE does not work well with signature aggregation. Signature
>> aggregation will collect (pubkey, message) pairs in a tx, combine them,
>> and verify with one signature. However, consider the following case:
>> 
>> OP_RETURNTRUE OP_IF  OP_CHECKSIGVERIFY OP_ENDIF OP_TRUE
>> 
>> For old nodes, the script terminates at OP_RETURNTRUE, and it will not
>> collect the (pubkey, message) pair.
>> 
>> If we use a softfork to transform OP_RETURNTRUE into OP_17 (pushing the
>> number 17 to the stack), new nodes will collect the (pubkey, message) pair
>> and try to aggregate with other pairs. This becomes a hardfork.
> 
> This seems like a problem for signature aggregation to address, not a problem 
> for OP_RETURNTRUE... In any case, I don't think it's insurmountable. 
> Signature 
> aggregation can simply be setup upfront, and have the Script verify inclusion 
> of keys in the aggregation?

I think it’s possible only if you spend more witness space to store the 
(pubkey, message) pairs, so that old clients could understand the aggregation 
produced by new clients. But this completely defeats the purpose of doing 
aggregation.

We use different skills to save space. For example, we use 1-byte SIGHASH flag 
to imply the 32-byte message. For maximal space saving, sig aggregation will 
also rely on such skills. However, the assumption is that all signatures 
aggregated must follow exactly the same set of rules.


> 
>> Technically, we could create ANY op code with an OP_NOP. For example, if we
>> want OP_MUL, we could have OP_MULVERIFY, which verifies if the 3rd stack
>> item is the product of the top 2 stack items. Therefore, OP_MULVERIFY
>> OP_2DROP is functionally same as OP_MUL, which removes the top 2 items and
>> returns the product. The problem is it takes more witness space.
> 
> This is another approach, and one that seems like a good idea in general. I'm 
> not sure it actually needs to take more witness space - in theory, such stack 
> items could be implied if the Script engine is designed for it upfront. Then 
> it would behave as if it were non-verify, while retaining backward 
> compatibility.

Sounds interesting but I don’t get it. For example, how could you make a OP_MUL 
out of OP_NOP?


> 
> Luke


___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] cleanstack alt stack & softfork improvements (Was: Merkle branch verification & tail-call semantics for generalized MAST)

[Luke Dashjr via bitcoin-dev]

On Wednesday 20 September 2017 5:13:04 AM Johnson Lau wrote:
> 2. OP_RETURNTRUE does not work well with signature aggregation. Signature
> aggregation will collect (pubkey, message) pairs in a tx, combine them,
> and verify with one signature. However, consider the following case:
> 
> OP_RETURNTRUE OP_IF  OP_CHECKSIGVERIFY OP_ENDIF OP_TRUE
> 
> For old nodes, the script terminates at OP_RETURNTRUE, and it will not
> collect the (pubkey, message) pair.
> 
> If we use a softfork to transform OP_RETURNTRUE into OP_17 (pushing the
> number 17 to the stack), new nodes will collect the (pubkey, message) pair
> and try to aggregate with other pairs. This becomes a hardfork.

This seems like a problem for signature aggregation to address, not a problem 
for OP_RETURNTRUE... In any case, I don't think it's insurmountable. Signature 
aggregation can simply be setup upfront, and have the Script verify inclusion 
of keys in the aggregation?

> Technically, we could create ANY op code with an OP_NOP. For example, if we
> want OP_MUL, we could have OP_MULVERIFY, which verifies if the 3rd stack
> item is the product of the top 2 stack items. Therefore, OP_MULVERIFY
> OP_2DROP is functionally same as OP_MUL, which removes the top 2 items and
> returns the product. The problem is it takes more witness space.

This is another approach, and one that seems like a good idea in general. I'm 
not sure it actually needs to take more witness space - in theory, such stack 
items could be implied if the Script engine is designed for it upfront. Then 
it would behave as if it were non-verify, while retaining backward 
compatibility.

Luke
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] cleanstack alt stack & softfork improvements (Was: Merkle branch verification & tail-call semantics for generalized MAST)

[Johnson Lau via bitcoin-dev]

> On 21 Sep 2017, at 3:29 AM, Mark Friedenbach  wrote:
> 
> 
>> On Sep 19, 2017, at 10:13 PM, Johnson Lau  wrote:
>> 
>> If we don’t want this ugliness, we could use a new script version for every 
>> new op code we add. In the new BIP114 (see link above), I suggest to move 
>> the script version to the witness, which is cheaper.
> 
> To be clear, I don’t think it is so much that the version should be moved to 
> the witness, but rather that there are two separate version values here — one 
> in the scriptPubKey which specifies the format and structure of the segwit 
> commitment itself, and another in the witness which gates functionality in 
> script or whatever else is used by that witness type. Segwit just 
> unfortunately didn’t include the latter, an oversight that should be 
> corrected on the on the next upgrade opportunity.
> 
> The address-visible “script version” field should probably be renamed 
> “witness type” as it will only be used in the future to encode how to check 
> the witness commitment in the scriptPubKey against the data provided in the 
> witness. Upgrades and improvements to the features supported by those witness 
> types won’t require new top-level witness types to be defined. Defining a new 
> opcode, even one with modifies the stack, doesn’t change the hashing scheme 
> used by the witness type.
> 
> v0,32-bytes is presently defined to calculate the double-SHA256 hash of the 
> top-most serialized item on the stack, and compare that against the 32-byte 
> commitment value. Arguably it probably should have hashed the top two values, 
> one of which would have been the real script version. This could be fixed 
> however, even without introducing a new witness type. Do a soft-fork upgrade 
> that checks if the witness redeem script is push-only, and if so then pop the 
> last push off as the script version (>= 1), and concatenate the rest to form 
> the actual redeem script. We inherit a little technical debt from having to 
> deal with push limits, but we avoid burning v0 in an upgrade to v1 that does 
> little more than add a script version.
> 
> v1,32-bytes would then be used for a template version of MAST, or whatever 
> other idea comes along that fundamentally changes the way the witness 
> commitment is calculated.
> 
> Mark

This is exactly what I suggest with BIP114. Using v1, 32-byte to define the 
basic structure of Merklized Script, and define the script version inside the 
witness

Johnson
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] cleanstack alt stack & softfork improvements (Was: Merkle branch verification & tail-call semantics for generalized MAST)

[Mark Friedenbach via bitcoin-dev]

> On Sep 19, 2017, at 10:13 PM, Johnson Lau  wrote:
> 
> If we don’t want this ugliness, we could use a new script version for every 
> new op code we add. In the new BIP114 (see link above), I suggest to move the 
> script version to the witness, which is cheaper.

To be clear, I don’t think it is so much that the version should be moved to 
the witness, but rather that there are two separate version values here — one 
in the scriptPubKey which specifies the format and structure of the segwit 
commitment itself, and another in the witness which gates functionality in 
script or whatever else is used by that witness type. Segwit just unfortunately 
didn’t include the latter, an oversight that should be corrected on the on the 
next upgrade opportunity.

The address-visible “script version” field should probably be renamed “witness 
type” as it will only be used in the future to encode how to check the witness 
commitment in the scriptPubKey against the data provided in the witness. 
Upgrades and improvements to the features supported by those witness types 
won’t require new top-level witness types to be defined. Defining a new opcode, 
even one with modifies the stack, doesn’t change the hashing scheme used by the 
witness type.

v0,32-bytes is presently defined to calculate the double-SHA256 hash of the 
top-most serialized item on the stack, and compare that against the 32-byte 
commitment value. Arguably it probably should have hashed the top two values, 
one of which would have been the real script version. This could be fixed 
however, even without introducing a new witness type. Do a soft-fork upgrade 
that checks if the witness redeem script is push-only, and if so then pop the 
last push off as the script version (>= 1), and concatenate the rest to form 
the actual redeem script. We inherit a little technical debt from having to 
deal with push limits, but we avoid burning v0 in an upgrade to v1 that does 
little more than add a script version.

v1,32-bytes would then be used for a template version of MAST, or whatever 
other idea comes along that fundamentally changes the way the witness 
commitment is calculated.

Mark
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] cleanstack alt stack & softfork improvements (Was: Merkle branch verification & tail-call semantics for generalized MAST)

[Johnson Lau via bitcoin-dev]

> On 19 Sep 2017, at 11:09 AM, Luke Dashjr via bitcoin-dev 
>  wrote:
> 
> On Tuesday 19 September 2017 12:46:30 AM Mark Friedenbach via bitcoin-dev 
> wrote:
>> After the main discussion session it was observed that tail-call semantics
>> could still be maintained if the alt stack is used for transferring
>> arguments to the policy script.
> 
> Isn't this a bug in the cleanstack rule?
> 
> (Unrelated...)
> 
> Another thing that came up during the discussion was the idea of replacing 
> all 
> the NOPs and otherwise-unallocated opcodes with a new OP_RETURNTRUE 
> implementation, in future versions of Script. This would immediately exit the 
> program (perhaps performing some semantic checks on the remainder of the 
> Script) with a successful outcome.
> 
> This is similar to CVE-2010-5141 in a sense, but since signatures are no 
> longer Scripts themselves, it shouldn't be exploitable.
> 
> The benefit of this is that it allows softforking in ANY new opcode, not only 
> the -VERIFY opcode variants we've been doing. That is, instead of merely 
> terminating the Script with a failure, the new opcode can also remove or push 
> stack items. This is because old nodes, upon encountering the undefined 
> opcode, will always succeed immediately, allowing the new opcode to do 
> literally anything from that point onward.
> 
> Luke
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

I have implemented OP_RETURNTRUE in an earlier version of MAST (BIP114) but 
have given up the idea, for 2 reasons:

1. I’ve updated BIP114 to allow inclusion of scripts in witness, and require 
them to be signed. In this way users could add additional conditions for the 
validity of a signature. For example, with OP_CHECKBLOCKHASH, it is possible to 
make the transaction valid only in the specified chain. (More discussion in 
https://github.com/jl2012/bips/blob/vault/bip-0114.mediawiki#Additional_scripts_in_witness
 

 )

2. OP_RETURNTRUE does not work well with signature aggregation. Signature 
aggregation will collect (pubkey, message) pairs in a tx, combine them, and 
verify with one signature. However, consider the following case:

OP_RETURNTRUE OP_IF  OP_CHECKSIGVERIFY OP_ENDIF OP_TRUE

For old nodes, the script terminates at OP_RETURNTRUE, and it will not collect 
the (pubkey, message) pair.

If we use a softfork to transform OP_RETURNTRUE into OP_17 (pushing the number 
17 to the stack), new nodes will collect the (pubkey, message) pair and try to 
aggregate with other pairs. This becomes a hardfork.


Technically, we could create ANY op code with an OP_NOP. For example, if we 
want OP_MUL, we could have OP_MULVERIFY, which verifies if the 3rd stack item 
is the product of the top 2 stack items. Therefore, OP_MULVERIFY OP_2DROP is 
functionally same as OP_MUL, which removes the top 2 items and returns the 
product. The problem is it takes more witness space.

If we don’t want this ugliness, we could use a new script version for every new 
op code we add. In the new BIP114 (see link above), I suggest to move the 
script version to the witness, which is cheaper.


___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] cleanstack alt stack & softfork improvements (Was: Merkle branch verification & tail-call semantics for generalized MAST)

[Mark Friedenbach via bitcoin-dev]

> On Sep 18, 2017, at 8:09 PM, Luke Dashjr  wrote:
> 
> On Tuesday 19 September 2017 12:46:30 AM Mark Friedenbach via bitcoin-dev 
> wrote:
>> After the main discussion session it was observed that tail-call semantics
>> could still be maintained if the alt stack is used for transferring
>> arguments to the policy script.
> 
> Isn't this a bug in the cleanstack rule?

Well in the sense that "cleanstack" doesn't do what it says, sure.

However cleanstack was introduced as a consensus rule to prevent a
possible denial of service vulnerability where a third party could
intercept any* transaction broadcast and arbitrarily add data to the
witness stack, since witness data is not covered by a checksig.

Cleanstack as-is accomplishes this because any extra items on the
stack would pass through all realistic scripts, remaining on the stack
and thereby violating the rule. There is no reason to prohibit extra
items on the altstack as those items can only arrive there
purposefully as an action of the script itself, not a third party
malleation of witness data. You could of course use DEPTH to write a
script that takes a variable number of parameters and sends them to
the altstack. Such a script would be malleable if those extra
parameters are not used. But that is predicated on the script being
specifically written in such a way as to be vulnerable; why protect
against that?

There are other solutions to this problem that could have been taken
instead, such as committing to the number of items or maximum size of
the stack as part of the sighash data, but cleanstack was the approach
taken. Arguably for a future script version upgrade one of these other
approaches should be taken to allow for shorter tail-call scripts.

Mark

* Well, almost any. You could end the script with DEPTH EQUAL and that
  is a compact way of ensuring the stack is clean (assuming the script
  finished with just "true" on the stack). Nobody does this however
  and burning two witness bytes of every redeem script going forward
  as a protective measure seems like an unnecessary ask.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev