[bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST

[bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST

[Mark Friedenbach]

I would like to propose two new script features to be added to the
bitcoin protocol by means of soft-fork activation. These features are
a new opcode, MERKLE-BRANCH-VERIFY (MBV) and tail-call execution
semantics.

In brief summary, MERKLE-BRANCH-VERIFY allows script authors to force
redemption to use values selected from a pre-determined set committed
to in the scriptPubKey, but without requiring revelation of unused
elements in the set for both enhanced privacy and smaller script
sizes. Tail-call execution semantics allows a single level of
recursion into a subscript, providing properties similar to P2SH while
at the same time more flexible.

These two features together are enough to enable a range of
applications such as tree signatures (minus Schnorr aggregation) as
described by Pieter Wuille [1], and a generalized MAST useful for
constructing private smart contracts. It also brings privacy and
fungibility improvements to users of counter-signing wallet/vault
services as unique redemption policies need only be revealed if/when
exceptional circumstances demand it, leaving most transactions looking
the same as any other MAST-enabled multi-sig script.

I believe that the implementation of these features is simple enough,
and the use cases compelling enough that we could BIP 8/9 rollout of
these features in relatively short order, perhaps before the end of
the year.

I have written three BIPs to describe these features, and their
associated implementation, for which I now invite public review and
discussion:

Fast Merkle Trees
BIP: https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee0a
Code: https://github.com/maaku/bitcoin/tree/fast-merkle-tree

MERKLEBRANCHVERIFY
BIP: https://gist.github.com/maaku/bcf63a208880bbf8135e453994c0e431
Code: https://github.com/maaku/bitcoin/tree/merkle-branch-verify

Tail-call execution semantics
BIP: https://gist.github.com/maaku/f7b2e710c53f601279549aa74eeb5368
Code: https://github.com/maaku/bitcoin/tree/tail-call-semantics

Note: I have circulated this idea privately among a few people, and I
will note that there is one piece of feedback which I agree with but
is not incorporated yet: there should be a multi-element MBV opcode
that allows verifying multiple items are extracted from a single
tree. It is not obvious how MBV could be modified to support this
without sacrificing important properties, or whether should be a
separate multi-MBV opcode instead.

Kind regards,
Mark Friedenbach

Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST

[Johnson Lau]

Some comments with the tail-call execution semantics BIP:

Tail-call execution semantics require “unclean stake”, i.e. final stake with more than one item. However, “unclean stake” is invalid (not just non-standard) in BIP141, so you could only use it with legacy P2SH (which is totally pointless….). A different design like OP_EVAL might be needed, or you need a new witness script version.

I think you have also missed the sigOp counting of the executed script. As you can’t count it without executing the script, the current static analysability is lost. This was one of the reasons for OP_EVAL being rejected. Since sigOp is a per-block limit, any OP_EVAL-like operation means block validity will depend on the precise outcome of script execution (instead of just pass or fail), which is a layer violation.

(An alternative is to make sigOp a per-input limit instead of per-block limit, just like the 201 nOp limit. But this is a very different security model)

Witness script versioning is by design fully compatible with P2SH and BIP173, so there will be no hurdle for existing wallets to pay to BIP114. Actually it should be completely transparent to them.

For code complexity, the minimal BIP114 could be really simple, like <30 lines of code? It looks complex now because it does much more than simply hiding scripts in a hash.



> On 7 Sep 2017, at 8:38 AM, Mark Friedenbach via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
> I would like to propose two new script features to be added to the
> bitcoin protocol by means of soft-fork activation. These features are
> a new opcode, MERKLE-BRANCH-VERIFY (MBV) and tail-call execution
> semantics.
> 
> In brief summary, MERKLE-BRANCH-VERIFY allows script authors to force
> redemption to use values selected from a pre-determined set committed
> to in the scriptPubKey, but without requiring revelation of unused
> elements in the set for both enhanced privacy and smaller script
> sizes. Tail-call execution semantics allows a single level of
> recursion into a subscript, providing properties similar to P2SH while
> at the same time more flexible.
> 
> These two features together are enough to enable a range of
> applications such as tree signatures (minus Schnorr aggregation) as
> described by Pieter Wuille [1], and a generalized MAST useful for
> constructing private smart contracts. It also brings privacy and
> fungibility improvements to users of counter-signing wallet/vault
> services as unique redemption policies need only be revealed if/when
> exceptional circumstances demand it, leaving most transactions looking
> the same as any other MAST-enabled multi-sig script.
> 
> I believe that the implementation of these features is simple enough,
> and the use cases compelling enough that we could BIP 8/9 rollout of
> these features in relatively short order, perhaps before the end of
> the year.
> 
> I have written three BIPs to describe these features, and their
> associated implementation, for which I now invite public review and
> discussion:
> 
> Fast Merkle Trees
> BIP: https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee0a
> Code: https://github.com/maaku/bitcoin/tree/fast-merkle-tree
> 
> MERKLEBRANCHVERIFY
> BIP: https://gist.github.com/maaku/bcf63a208880bbf8135e453994c0e431
> Code: https://github.com/maaku/bitcoin/tree/merkle-branch-verify
> 
> Tail-call execution semantics
> BIP: https://gist.github.com/maaku/f7b2e710c53f601279549aa74eeb5368
> Code: https://github.com/maaku/bitcoin/tree/tail-call-semantics
> 
> Note: I have circulated this idea privately among a few people, and I
> will note that there is one piece of feedback which I agree with but
> is not incorporated yet: there should be a multi-element MBV opcode
> that allows verifying multiple items are extracted from a single
> tree. It is not obvious how MBV could be modified to support this
> without sacrificing important properties, or whether should be a
> separate multi-MBV opcode instead.
> 
> Kind regards,
> Mark Friedenbach
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST

[Adán Sánchez de Pedro Crespo]

[-- Attachment #1.1: Type: text/plain, Size: 656 bytes --]

Coincidentally, the kind of Merkle tree that Mark describes in his
proposal is exactly the one that we use at Stampery.

The Stampery BTA whitepaper[1] includes pseudocode for many of the
algorithms outlined by this proposal, including fast-SHA256, the tree
building process and the inclusion proving routine.

The wording is slightly different but the logic is just the same, so I
hope it helps future implementations in case of eventual adoption.


[1]
https://s3.amazonaws.com/stampery-cdn/docs/Stampery-BTA-v6-whitepaper.pdf


Best,
-- 
Adán Sánchez de Pedro Crespo
CTO, Stampery Inc.
San Francisco - Madrid
T: +34 663 163 375


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 455 bytes --]

Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST

[Mark Friedenbach]

My apologies for a delay in responding to emails on this list; I have
been fighting a cold.

(Also my apologies to Johnson Lau, as I forgot to forward this to the list.)

On Sep 8, 2017, at 2:21 AM, Johnson Lau <jl2012@xbt.hk> wrote:

> Tail-call execution semantics require "unclean stake" , i.e. final
> stake with more than one item. However, "unclean stake" is invalid
> (not just non-standard) in BIP141, so you could only use it with
> legacy P2SH (which is totally pointless....). A different design
> like OP_EVAL might be needed, or you need a new witness script
> version.

I believe you meant "unclean stack," and you are correct. This was
also pointed out last tuesday by a participant at the in-person
CoreDev meetup where the idea was presented.

This doesn't kill the idea, it just complicates the implementation
slightly. A simple fix would be to allow tail-recursion to occur if
the stack is not clean (as can happen with legacy P2SH as you point
out, or yet to be defined version 1+ forms of segwit script), OR if
there is a single item on the stack and the alt-stack is not empty.
For segwit v0 scripts you then have to move any arguments to the alt
stack before ending the redeem script, leaving just the policy script
on the main stack.

> I think you have also missed the sigOp counting of the executed
> script. As you can't count it without executing the script, the
> current static analysability is lost. This was one of the reasons
> for OP_EVAL being rejected. Since sigOp is a per-block limit, any
> OP_EVAL-like operation means block validity will depend on the
> precise outcome of script execution (instead of just pass or fail),
> which is a layer violation.

I disagree with this design requirement.

The SigOp counting method used by bitcoin is flawed. It incorrectly
limits not the number of signature operations necessary to validate a
block, but rather the number of CHECKSIGs potentially encountered in
script execution, even if in an unexecuted branch. (Admitedly MAST
makes this less of an issue, but there are still useful compact
scripts that use if/else constructs to elide a CHECKSIG.) Nor will it
account for aggregation when that feature is added, or properly
differentiate between signature operations that can be batched and
those that can not.

Additionally there are other resources used by script that should be
globally limited, such as hash operations, which are not accounted for
at this time and cannot be statically assessed, even by the flawed
mechanism by which SigOps are counted. I have maintained for some time
that bitcoin should move from having multiple separate global limits
(weight and sigops, hashed bytes in XT/Classic/BCH) to a single linear
metric that combines all of these factors with appropriate
coefficients.

A better way of handling this problem, which works for both SigOps and
HashOps, is to have the witness commit to the maximum resources
consumed by validation of the spend of the coin, to relay this data
with the transaction and include it in the SigHash, and to use the
committed maximum for block validation. This could be added in a
future script version upgrade. This change would also resolve the
issue that led to the clean stack rule in segwit, allowing future
versions of script to use tail-call recursion without involving the
alt-stack.

Nevertheless it is constructive feedback that the current draft of the
BIP and its implementation do not count SigOps, at all. There are a
couple of ways this can be fixed by evaluating the top-level script
and then doing static analysis of the resulting policy script, or by
running the script and counting operations actually performed.

Additionally, it is possible that we take this time to re-evaluate
whether we should be counting SigOps other than for legacy consensus
rule compliance. The speed of verification in secp256k1 has made
signature operations no longer the chief concern in block validation
times.

> Witness script versioning is by design fully compatible with P2SH
> and BIP173, so there will be no hurdle for existing wallets to pay
> to BIP114. Actually it should be completely transparent to them.

This is correct. Your feedback will be incorporated.

> For code complexity, the minimal BIP114 could be really simple, like
> <30 lines of code? It looks complex now because it does much more
> than simply hiding scripts in a hash.

Is there a repo that contains the latest implementation of BIP 114,
for comparison purposes?

Kind regards,
Mark Friedenbach

Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST

[Bryan Bishop]

On Mon, Sep 11, 2017 at 9:03 PM, Mark Friedenbach via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> I believe you meant "unclean stack," and you are correct. This was
> also pointed out last tuesday by a participant at the in-person
> CoreDev meetup where the idea was presented.

http://diyhpl.us/wiki/transcripts/bitcoin-core-dev-tech/2017-09-07-merkleized-abstract-syntax-trees/

> > For code complexity, the minimal BIP114 could be really simple, like
> > <30 lines of code? It looks complex now because it does much more
> > than simply hiding scripts in a hash.
>
> Is there a repo that contains the latest implementation of BIP 114,
> for comparison purposes?

original bip114:
https://github.com/bitcoin/bips/blob/775f26c02696e772dac4060aa092d35dedbc647c/bip-0114.mediawiki
revised bip114: https://github.com/jl2012/bips/blob/vault/bip-0114.mediawiki
https://github.com/jl2012/bitcoin/commits/vault
from https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/014963.html

- Bryan
http://heybryan.org/
1 512 203 0507

Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST

[Johnson Lau]

> On 12 Sep 2017, at 10:03 AM, Mark Friedenbach <mark@friedenbach.org> wrote:
> 
> My apologies for a delay in responding to emails on this list; I have
> been fighting a cold.
> 
> (Also my apologies to Johnson Lau, as I forgot to forward this to the list.)
> 
> On Sep 8, 2017, at 2:21 AM, Johnson Lau <jl2012@xbt.hk> wrote:
> 
>> Tail-call execution semantics require "unclean stake" , i.e. final
>> stake with more than one item. However, "unclean stake" is invalid
>> (not just non-standard) in BIP141, so you could only use it with
>> legacy P2SH (which is totally pointless....). A different design
>> like OP_EVAL might be needed, or you need a new witness script
>> version.
> 
> I believe you meant "unclean stack," and you are correct. This was
> also pointed out last tuesday by a participant at the in-person
> CoreDev meetup where the idea was presented.
> 
> This doesn't kill the idea, it just complicates the implementation
> slightly. A simple fix would be to allow tail-recursion to occur if
> the stack is not clean (as can happen with legacy P2SH as you point
> out, or yet to be defined version 1+ forms of segwit script), OR if
> there is a single item on the stack and the alt-stack is not empty.
> For segwit v0 scripts you then have to move any arguments to the alt
> stack before ending the redeem script, leaving just the policy script
> on the main stack.

This is ugly and actually broken, as different script path may require different number of stack items, so you don’t know how many OP_TOALTSTACK do you need. Easier to just use a new witness version

> 
>> I think you have also missed the sigOp counting of the executed
>> script. As you can't count it without executing the script, the
>> current static analysability is lost. This was one of the reasons
>> for OP_EVAL being rejected. Since sigOp is a per-block limit, any
>> OP_EVAL-like operation means block validity will depend on the
>> precise outcome of script execution (instead of just pass or fail),
>> which is a layer violation.
> 
> I disagree with this design requirement.
> 
> The SigOp counting method used by bitcoin is flawed. It incorrectly
> limits not the number of signature operations necessary to validate a
> block, but rather the number of CHECKSIGs potentially encountered in
> script execution, even if in an unexecuted branch. (Admitedly MAST
> makes this less of an issue, but there are still useful compact
> scripts that use if/else constructs to elide a CHECKSIG.) Nor will it
> account for aggregation when that feature is added, or properly
> differentiate between signature operations that can be batched and
> those that can not.
> 
> Additionally there are other resources used by script that should be
> globally limited, such as hash operations, which are not accounted for
> at this time and cannot be statically assessed, even by the flawed
> mechanism by which SigOps are counted. I have maintained for some time
> that bitcoin should move from having multiple separate global limits
> (weight and sigops, hashed bytes in XT/Classic/BCH) to a single linear
> metric that combines all of these factors with appropriate
> coefficients.
> 

I like the idea to have an unified global limit and suggested a way to do it (https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-January/013472.html). But I think this is off-topic here.



> A better way of handling this problem, which works for both SigOps and
> HashOps, is to have the witness commit to the maximum resources
> consumed by validation of the spend of the coin, to relay this data
> with the transaction and include it in the SigHash, and to use the
> committed maximum for block validation. This could be added in a
> future script version upgrade. This change would also resolve the
> issue that led to the clean stack rule in segwit, allowing future
> versions of script to use tail-call recursion without involving the
> alt-stack.
> 
> Nevertheless it is constructive feedback that the current draft of the
> BIP and its implementation do not count SigOps, at all. There are a
> couple of ways this can be fixed by evaluating the top-level script
> and then doing static analysis of the resulting policy script, or by
> running the script and counting operations actually performed.


In any case, I think maintaining static analysability for global limit(s) is very important. Ethereum had to give up their DAO softfork plan at the last minute, exactly due to the lack of this: http://hackingdistributed.com/2016/06/28/ethereum-soft-fork-dos-vector/

Otherwise, one could attack relay and mining nodes by sending many small size txs with many sigops, forcing them to validate, and discard due to insufficient fees.

Technically it might be ok if we commit the total validation cost (sigop + hashop + whatever) as the first witness stack item, but that’d take more space and I’m not sure if it is desirable. Anyway, giving up static analysability for scripts is a fundamental change to our existing model.

> 
> Additionally, it is possible that we take this time to re-evaluate
> whether we should be counting SigOps other than for legacy consensus
> rule compliance. The speed of verification in secp256k1 has made
> signature operations no longer the chief concern in block validation
> times.

Without the limit I think we would be DoS-ed to dead


>> Witness script versioning is by design fully compatible with P2SH
>> and BIP173, so there will be no hurdle for existing wallets to pay
>> to BIP114. Actually it should be completely transparent to them.
> 
> This is correct. Your feedback will be incorporated.
> 
>> For code complexity, the minimal BIP114 could be really simple, like
>> <30 lines of code? It looks complex now because it does much more
>> than simply hiding scripts in a hash.
> 
> Is there a repo that contains the latest implementation of BIP 114,
> for comparison purposes?


You can find it here: https://github.com/jl2012/bitcoin/commits/vault
https://github.com/jl2012/bitcoin/commit/f3f201d232d3995db38e09b171e4d1dea8d04ad2

But this does more than your proposal as it allows users adding extra scripts when spending a coin. The rationale is described in the revised BIP114:
https://github.com/jl2012/bips/blob/vault/bip-0114.mediawiki#Additional_scripts_in_witness

So to make it functionally comparable with your proposal, the IsMSV0Stack() function is not needed. The new 249-254 lines in interpreter.cpp could be removed. The new 1480-1519 lines could be replaced by a few lines copied from the existing P2WSH code. I can make a minimal version if you want to see how it looks like


> 
> Kind regards,
> Mark Friedenbach
> 

Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST

[Mark Friedenbach]

On Sep 12, 2017, at 1:55 AM, Johnson Lau <jl2012@xbt.hk> wrote:

> This is ugly and actually broken, as different script path may
> require different number of stack items, so you don't know how many
> OP_TOALTSTACK do you need. Easier to just use a new witness version

DEPTH makes this relatively easy to do. Just repeat the following for
the maximum number of stack elements that might be used:

  DEPTH 1SUB IF SWAP TOALTSTACK ENDIF

There are probably more compact alternatives.

Using a new script version is easier, but not faster. There's a number
of things that might be fixed in a v1 upgrade, and various design
decisions to sort out regarding specification of a witness version
(version in the witness rather than the scriptPubKey).

Tree signatures and MAST are immediately useful to many services,
however, and I would hate to delay usage by six months to a year or
more by serializing dependencies instead of doing them in parallel.

> Otherwise, one could attack relay and mining nodes by sending many
> small size txs with many sigops, forcing them to validate, and
> discard due to insufficient fees.
>
> Technically it might be ok if we commit the total validation cost
> (sigop + hashop + whatever) as the first witness stack item

That is what I'm suggesting. And yes, there are changes that would
have to be made to the p2p layer and transaction processing to handle
this safely. I'm arguing that the cost of doing so is worth it, and a
better path forward.

> Without the limit I think we would be DoS-ed to dead

4MB of secp256k1 signatures takes 10s to validate on my 5 year old
laptop (125,000 signatures, ignoring public keys and other things that
would consume space). That's much less than bad blocks that can be
constructed using other vulnerabilities.

> So to make it functionally comparable with your proposal, the
> IsMSV0Stack() function is not needed. The new 249-254 lines in
> interpreter.cpp could be removed. The new 1480-1519 lines could be
> replaced by a few lines copied from the existing P2WSH code. I can
> make a minimal version if you want to see how it looks like

That's alright, I don't think it's necessary to purposefully restrict
one to compare them head to head with the same features. They are
different proposals with different pros and cons.

Kind regards,
Mark Friedenbach

Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST

[Karl Johan Alm]

On Wed, Sep 13, 2017 at 4:57 AM, Mark Friedenbach via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>> Without the limit I think we would be DoS-ed to dead
>
> 4MB of secp256k1 signatures takes 10s to validate on my 5 year old
> laptop (125,000 signatures, ignoring public keys and other things that
> would consume space). That's much less than bad blocks that can be
> constructed using other vulnerabilities.

Sidenote-ish, but I also believe it would be fairly trivial to keep a
per UTXO tally and demand additional fees when trying to respend a
UTXO which was previously "spent" with an invalid op count. I.e. if
you sign off on an input for a tx that you know is bad, the UTXO in
question will be penalized proportionately to the wasted ops when
included in another transaction later. That would probably kill that
DoS attack as the attacker would effectively lose bitcoin every time,
even if it was postponed until they spent the UTXO. The only thing
clients would need to do is to add a fee rate penalty ivar and a
mapping of outpoint to penalty value, probably stored as a separate
.dat file. I think.

Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST

[Peter Todd]

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

On Wed, Sep 13, 2017 at 08:27:36AM +0900, Karl Johan Alm via bitcoin-dev wrote:
> On Wed, Sep 13, 2017 at 4:57 AM, Mark Friedenbach via bitcoin-dev
> <bitcoin-dev@lists.linuxfoundation.org> wrote:
> >> Without the limit I think we would be DoS-ed to dead
> >
> > 4MB of secp256k1 signatures takes 10s to validate on my 5 year old
> > laptop (125,000 signatures, ignoring public keys and other things that
> > would consume space). That's much less than bad blocks that can be
> > constructed using other vulnerabilities.
> 
> Sidenote-ish, but I also believe it would be fairly trivial to keep a
> per UTXO tally and demand additional fees when trying to respend a
> UTXO which was previously "spent" with an invalid op count. I.e. if
> you sign off on an input for a tx that you know is bad, the UTXO in
> question will be penalized proportionately to the wasted ops when
> included in another transaction later. That would probably kill that
> DoS attack as the attacker would effectively lose bitcoin every time,
> even if it was postponed until they spent the UTXO. The only thing
> clients would need to do is to add a fee rate penalty ivar and a
> mapping of outpoint to penalty value, probably stored as a separate
> .dat file. I think.

Ethereum does something quite like this; it's a very bad idea for a few
reasons:

1) If you bailed out of verifying a script due to wasted ops, how did you know the
transaction trying to spend that txout did in fact come from the owner of it?

2) How do you verify that transactions were penalized correctly without *all*
nodes re-running the DoS script?

3) If the DoS is significant enough to matter on a per-node level, you're going
to have serious problems anyway, quite possibly so serious that the attacker
manages to cause consensus to fail. They can then spend the txouts in a block
that does *not* penalize their outputs, negating the deterrent.

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org

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

Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST

[Mark Friedenbach]

As some of you may know, the MAST proposal I sent to the mailing list
on September 6th was discussed that the in-person CoreDev meetup in
San Francisco. In this email I hope to summarize the outcome of that
discussion. As chatham house rules were in effect, I will refrain from
attributing names to this summary..

* An introductory overview of the BIPs was presented, for the purpose
  of familiarizing the audience with what they are attempting to
  accomplish and how they do so.

* There was a discussion of a single vs multi-element MBV opcode. It
  was put forward that there should perhaps be different opcodes for
  the sake of script analysis, since a multi-element MBV will
  necessarily consume a variable number of inputs. However it was
  countered that if the script encodes the number of elements as an
  integer push to the top of the stack immediately before the opcode,
  then static analyzability is maintained in such instances. I took
  the action item to investigate what an ideal serialization format
  would be for a multi-element proof, which is the only thing holding
  back a multi-element MBV proposal.

* It was pointed out that the non-clean-stack tail-call semantics is
  not compatible with segwit's consensus-enforcement of the clean
  stack rule. Some alternatives were suggested, such as changing
  deployment mechanisms. 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. I
  will be updating the BIP and example implementation accordingly.

* The observation was made that single-layer tail-call semantics can
  be thought of as really being P2SH with user-specified hashing. If
  the P2SH script template had been constructed slightly differently
  such as to not consume the script, it would even have been fully
  compatible with tail-call semantics.

* It was mentioned that using script versioning to deploy a MAST
  template allows for saving 32 bytes of witness per input, as the
  root hash is contained directly in the output being spent. The
  downside however is losing the permissionless innovation that comes
  with a programmable hashing mechanism.

* The discussion generally drifted into a wider discussion about
  script version upgrades and related issues, such as whether script
  versions should exist in the witness as well, and the difference in
  meaning between the two. This is an important subject, but only of
  relevance in far as using a script version upgrade to deploy MAST
  would add significant delay from having to sort through these issues
  first.

This feedback led to some minor tweaks to the proposal, which I will
be making, as well as the major feature request of a multi-element
MERKLE-BLOCK-VERIFY opcode which requires a little bit more effort to
accomplish. I will report back to this list again when that work is
done.

Sincerely,
Mark Friedenbach

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

[Luke Dashjr]

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

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

[Mark Friedenbach]

> On Sep 18, 2017, at 8:09 PM, Luke Dashjr <luke@dashjr.org> 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.

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

[Johnson Lau]

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


> On 19 Sep 2017, at 11:09 AM, Luke Dashjr via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> 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 <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 <pubkey> 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.



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

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

[Mark Friedenbach]

> On Sep 19, 2017, at 10:13 PM, Johnson Lau <jl2012@xbt.hk> 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

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

[Johnson Lau]

> On 21 Sep 2017, at 3:29 AM, Mark Friedenbach <mark@friedenbach.org> wrote:
> 
> 
>> On Sep 19, 2017, at 10:13 PM, Johnson Lau <jl2012@xbt.hk> 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

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

[Luke Dashjr]

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

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

[Johnson Lau]

> On 21 Sep 2017, at 12:11 PM, Luke Dashjr <luke@dashjr.org> 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 <pubkey> 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

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

[Luke Dashjr]

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

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

[Johnson Lau]

> On 22 Sep 2017, at 12:33 AM, Luke Dashjr <luke@dashjr.org> 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 <pubkey> 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)

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

[Sergio Demian Lerner]

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

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

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

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

[Mark Friedenbach]

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


> On Sep 22, 2017, at 1:32 PM, Sergio Demian Lerner <sergio.d.lerner@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.


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

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

[Sergio Demian Lerner]

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

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 <mark@friedenbach.org>
wrote:

>
> On Sep 22, 2017, at 1:32 PM, Sergio Demian Lerner <
> sergio.d.lerner@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.
>
>

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

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

[Mark Friedenbach]

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

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

[Sergio Demian Lerner]

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

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 <mark@friedenbach.org>
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.lerner@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.
>
>

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

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

[Mark Friedenbach]

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 <sergio.d.lerner@gmail.com> 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.

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

[Pieter Wuille]

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

On Fri, Sep 22, 2017 at 2:54 PM, Sergio Demian Lerner via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> 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.
>

Or (my preference);

- Get rid of DER encoding alltogether and switch to fixed size signatures.

Cheers,

-- 
Pieter

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

Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST

[Luke Dashjr]

On Thursday 07 September 2017 12:38:55 AM Mark Friedenbach via bitcoin-dev 
wrote:
> Tail-call execution semantics
> BIP: https://gist.github.com/maaku/f7b2e710c53f601279549aa74eeb5368
> Code: https://github.com/maaku/bitcoin/tree/tail-call-semantics

Just noticed this doesn't count sigops toward the block sigop limit.
Is that really safe? How long would it take, to verify a malicious block with 
only inputs such that there is nearly 4 MB of sigops?

(I do already understand the difficulty in supporting the sigop limit.)

Luke

Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST

[Mark Friedenbach]

10s of seconds if no further restrictions are placed. It would be trivial to include a new per input rule that reduces it to ~1s without cutting off any non-attack script (require sigops per input to be limited to witness/sig size). secp256k1 is now fast enough that we don’t need a separate sigop limit.

> On Sep 30, 2017, at 4:23 PM, Luke Dashjr <luke@dashjr.org> wrote:
> 
> On Thursday 07 September 2017 12:38:55 AM Mark Friedenbach via bitcoin-dev 
> wrote:
>> Tail-call execution semantics
>> BIP: https://gist.github.com/maaku/f7b2e710c53f601279549aa74eeb5368
>> Code: https://github.com/maaku/bitcoin/tree/tail-call-semantics
> 
> Just noticed this doesn't count sigops toward the block sigop limit.
> Is that really safe? How long would it take, to verify a malicious block with 
> only inputs such that there is nearly 4 MB of sigops?
> 
> (I do already understand the difficulty in supporting the sigop limit.)
> 
> Luke

Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST

[Russell O'Connor]

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

(Subject was: [bitcoin-dev] Version 1 witness programs (first draft)), but
I'm moving part of that conversation to this thread.

On Sun, Oct 1, 2017 at 5:32 PM, Johnson Lau <jl2012@xbt.hk> wrote:

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


I would very much like to retain the ability to do static analysis.  More
generally, the idea of interpreting arbitrary data as code, as done in
OP_EVAL and in TAILCALL, makes me quite anxious.  This at the root of many
security problems throughout the software industry, and I don't relish
giving more fuel to the underhanded Bitcoin Script contestants.

On Sun, Oct 1, 2017 at 8:45 PM, Luke Dashjr <luke@dashjr.org> wrote:

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

Actually, I have a half-baked idea I've been thinking about along these
lines.

The idea is to add a flag to each stack item in the Script interpreter to
mark whether the item in the stack is "executable" or "non-executable", not
so different from how computers mark pages to implement executable space
protection.  By default, all stack items are marked "non-executable".  We
then redefine OP_PUSHDATA4 as OP_PUSHCODE within ScriptSigs.  The
operational semantics of OP_PUSHCODE would remain the same as OP_PUSHDATA4
except it would set the pushed item's associated flag to "executable".  All
data pushed by OP_PUSHCODE would be subject to the sigops limits and any
other similar static analysis limits.

Segwit v0 doesn't use OP_PUSHDATA codes to create the input stack, so we
would have to mark executable input stack items using a new witness v1
format. But, IIUC, TAILCALL isn't going to be compatible with Segwit v0
anyway.

During a TAILCALL, it is required that the top item on the stack have the
"executable" flag, otherwise TAILCALL is not used (and the script succeeds
or fails based on the top item's data value as usual).

All other operations can treat "executable" items as data, including the
merkle branch verification.  None of the Script operations can create
"executable" items; in particular, OP_PUSHDATA4 within the ScriptPubKey
also would not create "executable" items.  (We can talk about the behaviour
of OP_CAT when that time comes).

One last trick is that when "executable" values are duplicated, by OP_DUP,
OP_IFDUP, OP_PICK. then the newly created copy of the value on top of the
stack is marked "non-executable".

Because we make the "executable" flag non-copyable, we are now free to
allow unbounded uses of TAILCALL (i.e. TAILCALL can be used multiplie times
in a single input).  Why is this safe?  Because the number of "executable"
items decreases by at least one every time TAILCALL is invoked. the number
of OP_PUSHCODE occurrences in the witness puts an upper bound on the number
of invocations of TAILCALL allowed.  Using static analysis of the script
pubkey and the data within the OP_PUSHCODE data, we compute an upper bound
on the number of operations (of any type) that can occur during execution.

Unbounded TAILCALL should let us (in the presence of OP_CHECKSIGFROMSTACK)
have unbounded delegation.

Overall, I believe that OP_PUSHCODE

1. is fully backwards compatible.
2. maintains our ability to perform static analysis with TAILCALL.
3. never lets us interpret computed values as executable code.
4. extends TAILCALL to safely allow multiple TAILCALLs per script.

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

Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST

[Mark Friedenbach]

I have completed updating the three BIPs with all the feedback that I have received so far. In short summary, here is an incomplete list of the changes that were made:

* Modified the hashing function fast-SHA256 so that an internal node cannot be interpreted simultaneously as a leaf.
* Changed MERKLEBRANCHVERIFY to verify a configurable number of elements from the tree, instead of just one.
* Changed MERKLEBRANCHVERIFY to have two modes: one where the inputs are assumed to be hashes, and one where they are run through double-SHA256 first.
* Made tail-call eval compatible with BIP141’s CLEANSTACK consensus rule by allowing parameters to be passed on the alt-stack.
* Restricted tail-call eval to segwit scripts only, so that checking sigop and opcode limits of the policy script would not be necessary.

There were a bunch of other small modifications, typo fixes, and optimizations that were made as well.

I am now ready to submit these BIPs as a PR against the bitcoin/bips repo, and I request that the BIP editor assign numbers.

Thank you,
Mark Friedenbach

> On Sep 6, 2017, at 5:38 PM, Mark Friedenbach <mark@friedenbach.org> wrote:
> 
> I would like to propose two new script features to be added to the
> bitcoin protocol by means of soft-fork activation. These features are
> a new opcode, MERKLE-BRANCH-VERIFY (MBV) and tail-call execution
> semantics.
> 
> In brief summary, MERKLE-BRANCH-VERIFY allows script authors to force
> redemption to use values selected from a pre-determined set committed
> to in the scriptPubKey, but without requiring revelation of unused
> elements in the set for both enhanced privacy and smaller script
> sizes. Tail-call execution semantics allows a single level of
> recursion into a subscript, providing properties similar to P2SH while
> at the same time more flexible.
> 
> These two features together are enough to enable a range of
> applications such as tree signatures (minus Schnorr aggregation) as
> described by Pieter Wuille [1], and a generalized MAST useful for
> constructing private smart contracts. It also brings privacy and
> fungibility improvements to users of counter-signing wallet/vault
> services as unique redemption policies need only be revealed if/when
> exceptional circumstances demand it, leaving most transactions looking
> the same as any other MAST-enabled multi-sig script.
> 
> I believe that the implementation of these features is simple enough,
> and the use cases compelling enough that we could BIP 8/9 rollout of
> these features in relatively short order, perhaps before the end of
> the year.
> 
> I have written three BIPs to describe these features, and their
> associated implementation, for which I now invite public review and
> discussion:
> 
> Fast Merkle Trees
> BIP: https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee0a
> Code: https://github.com/maaku/bitcoin/tree/fast-merkle-tree
> 
> MERKLEBRANCHVERIFY
> BIP: https://gist.github.com/maaku/bcf63a208880bbf8135e453994c0e431
> Code: https://github.com/maaku/bitcoin/tree/merkle-branch-verify
> 
> Tail-call execution semantics
> BIP: https://gist.github.com/maaku/f7b2e710c53f601279549aa74eeb5368
> Code: https://github.com/maaku/bitcoin/tree/tail-call-semantics
> 
> Note: I have circulated this idea privately among a few people, and I
> will note that there is one piece of feedback which I agree with but
> is not incorporated yet: there should be a multi-element MBV opcode
> that allows verifying multiple items are extracted from a single
> tree. It is not obvious how MBV could be modified to support this
> without sacrificing important properties, or whether should be a
> separate multi-MBV opcode instead.
> 
> Kind regards,
> Mark Friedenbach

Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST

[Luke Dashjr]

Mark,

I think I have found an improvement that can be made.

As you recall, a downside to this approach is that one must make two 
commitments: first, to the particular "membership-checking script"; and then 
in that script, to the particular merkle root of possible scripts.

Would there be any harm in, instead of checking membership, *calculating* the 
root? If not, then we could define that instead of the witness program 
committing to H(membership-check script), it rather commits to H(membership-
calculation script | data added by an OP_ADDTOSCRIPTHASH). This would, I 
believe, securely reduce the commitment of both to a single hash.

It also doesn't reduce flexibility, since one could omit OP_ADDTOSCRIPTHASH 
from their "membership-calculation" script to get the previous membership-
check behaviour, and use <hash> OP_EQUAL in its place.

What do you think?

Luke


On Saturday 28 October 2017 4:40:01 AM Mark Friedenbach wrote:
> I have completed updating the three BIPs with all the feedback that I have
> received so far. In short summary, here is an incomplete list of the
> changes that were made:
> 
> * Modified the hashing function fast-SHA256 so that an internal node cannot
> be interpreted simultaneously as a leaf. * Changed MERKLEBRANCHVERIFY to
> verify a configurable number of elements from the tree, instead of just
> one. * Changed MERKLEBRANCHVERIFY to have two modes: one where the inputs
> are assumed to be hashes, and one where they are run through double-SHA256
> first. * Made tail-call eval compatible with BIP141’s CLEANSTACK consensus
> rule by allowing parameters to be passed on the alt-stack. * Restricted
> tail-call eval to segwit scripts only, so that checking sigop and opcode
> limits of the policy script would not be necessary.
> 
> There were a bunch of other small modifications, typo fixes, and
> optimizations that were made as well.
> 
> I am now ready to submit these BIPs as a PR against the bitcoin/bips repo,
> and I request that the BIP editor assign numbers.
> 
> Thank you,
> Mark Friedenbach
> 
> > On Sep 6, 2017, at 5:38 PM, Mark Friedenbach <mark@friedenbach.org>
> > wrote:
> > 
> > I would like to propose two new script features to be added to the
> > bitcoin protocol by means of soft-fork activation. These features are
> > a new opcode, MERKLE-BRANCH-VERIFY (MBV) and tail-call execution
> > semantics.
> > 
> > In brief summary, MERKLE-BRANCH-VERIFY allows script authors to force
> > redemption to use values selected from a pre-determined set committed
> > to in the scriptPubKey, but without requiring revelation of unused
> > elements in the set for both enhanced privacy and smaller script
> > sizes. Tail-call execution semantics allows a single level of
> > recursion into a subscript, providing properties similar to P2SH while
> > at the same time more flexible.
> > 
> > These two features together are enough to enable a range of
> > applications such as tree signatures (minus Schnorr aggregation) as
> > described by Pieter Wuille [1], and a generalized MAST useful for
> > constructing private smart contracts. It also brings privacy and
> > fungibility improvements to users of counter-signing wallet/vault
> > services as unique redemption policies need only be revealed if/when
> > exceptional circumstances demand it, leaving most transactions looking
> > the same as any other MAST-enabled multi-sig script.
> > 
> > I believe that the implementation of these features is simple enough,
> > and the use cases compelling enough that we could BIP 8/9 rollout of
> > these features in relatively short order, perhaps before the end of
> > the year.
> > 
> > I have written three BIPs to describe these features, and their
> > associated implementation, for which I now invite public review and
> > discussion:
> > 
> > Fast Merkle Trees
> > BIP: https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee0a
> > Code: https://github.com/maaku/bitcoin/tree/fast-merkle-tree
> > 
> > MERKLEBRANCHVERIFY
> > BIP: https://gist.github.com/maaku/bcf63a208880bbf8135e453994c0e431
> > Code: https://github.com/maaku/bitcoin/tree/merkle-branch-verify
> > 
> > Tail-call execution semantics
> > BIP: https://gist.github.com/maaku/f7b2e710c53f601279549aa74eeb5368
> > Code: https://github.com/maaku/bitcoin/tree/tail-call-semantics
> > 
> > Note: I have circulated this idea privately among a few people, and I
> > will note that there is one piece of feedback which I agree with but
> > is not incorporated yet: there should be a multi-element MBV opcode
> > that allows verifying multiple items are extracted from a single
> > tree. It is not obvious how MBV could be modified to support this
> > without sacrificing important properties, or whether should be a
> > separate multi-MBV opcode instead.
> > 
> > Kind regards,
> > Mark Friedenbach

Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST

[Mark Friedenbach]

Yes, if you use a witness script version you can save about 40 witness bytes by templating the MBV script, which I think is equivalent to what you are suggesting. 32 bytes from the saved hash, plus another 8 bytes or so from script templates and more efficient serialization.

I believe the conservatively correct approach is to do this in stages, however. First roll out MBV and tail call to witness v0. Then once there is experience with people using it in production, design and deploy a hashing template for script v1. It might be that we learn more and think of something better in the meantime.

> On Nov 1, 2017, at 1:43 AM, Luke Dashjr <luke@dashjr.org> wrote:
> 
> Mark,
> 
> I think I have found an improvement that can be made.
> 
> As you recall, a downside to this approach is that one must make two 
> commitments: first, to the particular "membership-checking script"; and then 
> in that script, to the particular merkle root of possible scripts.
> 
> Would there be any harm in, instead of checking membership, *calculating* the 
> root? If not, then we could define that instead of the witness program 
> committing to H(membership-check script), it rather commits to H(membership-
> calculation script | data added by an OP_ADDTOSCRIPTHASH). This would, I 
> believe, securely reduce the commitment of both to a single hash.
> 
> It also doesn't reduce flexibility, since one could omit OP_ADDTOSCRIPTHASH 
> from their "membership-calculation" script to get the previous membership-
> check behaviour, and use <hash> OP_EQUAL in its place.
> 
> What do you think?
> 
> Luke
> 
> 
>> On Saturday 28 October 2017 4:40:01 AM Mark Friedenbach wrote:
>> I have completed updating the three BIPs with all the feedback that I have
>> received so far. In short summary, here is an incomplete list of the
>> changes that were made:
>> 
>> * Modified the hashing function fast-SHA256 so that an internal node cannot
>> be interpreted simultaneously as a leaf. * Changed MERKLEBRANCHVERIFY to
>> verify a configurable number of elements from the tree, instead of just
>> one. * Changed MERKLEBRANCHVERIFY to have two modes: one where the inputs
>> are assumed to be hashes, and one where they are run through double-SHA256
>> first. * Made tail-call eval compatible with BIP141’s CLEANSTACK consensus
>> rule by allowing parameters to be passed on the alt-stack. * Restricted
>> tail-call eval to segwit scripts only, so that checking sigop and opcode
>> limits of the policy script would not be necessary.
>> 
>> There were a bunch of other small modifications, typo fixes, and
>> optimizations that were made as well.
>> 
>> I am now ready to submit these BIPs as a PR against the bitcoin/bips repo,
>> and I request that the BIP editor assign numbers.
>> 
>> Thank you,
>> Mark Friedenbach
>> 
>>> On Sep 6, 2017, at 5:38 PM, Mark Friedenbach <mark@friedenbach.org>
>>> wrote:
>>> 
>>> I would like to propose two new script features to be added to the
>>> bitcoin protocol by means of soft-fork activation. These features are
>>> a new opcode, MERKLE-BRANCH-VERIFY (MBV) and tail-call execution
>>> semantics.
>>> 
>>> In brief summary, MERKLE-BRANCH-VERIFY allows script authors to force
>>> redemption to use values selected from a pre-determined set committed
>>> to in the scriptPubKey, but without requiring revelation of unused
>>> elements in the set for both enhanced privacy and smaller script
>>> sizes. Tail-call execution semantics allows a single level of
>>> recursion into a subscript, providing properties similar to P2SH while
>>> at the same time more flexible.
>>> 
>>> These two features together are enough to enable a range of
>>> applications such as tree signatures (minus Schnorr aggregation) as
>>> described by Pieter Wuille [1], and a generalized MAST useful for
>>> constructing private smart contracts. It also brings privacy and
>>> fungibility improvements to users of counter-signing wallet/vault
>>> services as unique redemption policies need only be revealed if/when
>>> exceptional circumstances demand it, leaving most transactions looking
>>> the same as any other MAST-enabled multi-sig script.
>>> 
>>> I believe that the implementation of these features is simple enough,
>>> and the use cases compelling enough that we could BIP 8/9 rollout of
>>> these features in relatively short order, perhaps before the end of
>>> the year.
>>> 
>>> I have written three BIPs to describe these features, and their
>>> associated implementation, for which I now invite public review and
>>> discussion:
>>> 
>>> Fast Merkle Trees
>>> BIP: https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee0a
>>> Code: https://github.com/maaku/bitcoin/tree/fast-merkle-tree
>>> 
>>> MERKLEBRANCHVERIFY
>>> BIP: https://gist.github.com/maaku/bcf63a208880bbf8135e453994c0e431
>>> Code: https://github.com/maaku/bitcoin/tree/merkle-branch-verify
>>> 
>>> Tail-call execution semantics
>>> BIP: https://gist.github.com/maaku/f7b2e710c53f601279549aa74eeb5368
>>> Code: https://github.com/maaku/bitcoin/tree/tail-call-semantics
>>> 
>>> Note: I have circulated this idea privately among a few people, and I
>>> will note that there is one piece of feedback which I agree with but
>>> is not incorporated yet: there should be a multi-element MBV opcode
>>> that allows verifying multiple items are extracted from a single
>>> tree. It is not obvious how MBV could be modified to support this
>>> without sacrificing important properties, or whether should be a
>>> separate multi-MBV opcode instead.
>>> 
>>> Kind regards,
>>> Mark Friedenbach

Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST

[Luke Dashjr]

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

How about using for the first stage, `<...> OP_CALCMERKLEROOT <root> OP_EQUAL` 
instead of `<root...> OP_CHECKMERKLEBRANCH`? There's maybe 1 or 2 bytes extra, 
but it seems more future-proof (since there could more easily be alternatives 
to `<root> OP_EQUAL` in future script versions).

OTOH, OP_ADDTOSCRIPTHASH may be fatally incompatible with script versioning... 
Old nodes won't know how to check the witness program, which means an 
undefined version could be used to bypass the correct script entirely.
Need to think more on this still.

Luke


On Wednesday 01 November 2017 3:08:46 PM Mark Friedenbach wrote:
> Yes, if you use a witness script version you can save about 40 witness
> bytes by templating the MBV script, which I think is equivalent to what
> you are suggesting. 32 bytes from the saved hash, plus another 8 bytes or
> so from script templates and more efficient serialization.
> 
> I believe the conservatively correct approach is to do this in stages,
> however. First roll out MBV and tail call to witness v0. Then once there
> is experience with people using it in production, design and deploy a
> hashing template for script v1. It might be that we learn more and think
> of something better in the meantime.
> 
> > On Nov 1, 2017, at 1:43 AM, Luke Dashjr <luke@dashjr.org> wrote:
> > 
> > Mark,
> > 
> > I think I have found an improvement that can be made.
> > 
> > As you recall, a downside to this approach is that one must make two
> > commitments: first, to the particular "membership-checking script"; and
> > then in that script, to the particular merkle root of possible scripts.
> > 
> > Would there be any harm in, instead of checking membership, *calculating*
> > the root? If not, then we could define that instead of the witness
> > program committing to H(membership-check script), it rather commits to
> > H(membership- calculation script | data added by an OP_ADDTOSCRIPTHASH).
> > This would, I believe, securely reduce the commitment of both to a
> > single hash.
> > 
> > It also doesn't reduce flexibility, since one could omit
> > OP_ADDTOSCRIPTHASH from their "membership-calculation" script to get the
> > previous membership- check behaviour, and use <hash> OP_EQUAL in its
> > place.
> > 
> > What do you think?
> > 
> > Luke
> > 
> >> On Saturday 28 October 2017 4:40:01 AM Mark Friedenbach wrote:
> >> I have completed updating the three BIPs with all the feedback that I
> >> have received so far. In short summary, here is an incomplete list of
> >> the changes that were made:
> >> 
> >> * Modified the hashing function fast-SHA256 so that an internal node
> >> cannot be interpreted simultaneously as a leaf. * Changed
> >> MERKLEBRANCHVERIFY to verify a configurable number of elements from the
> >> tree, instead of just one. * Changed MERKLEBRANCHVERIFY to have two
> >> modes: one where the inputs are assumed to be hashes, and one where
> >> they are run through double-SHA256 first. * Made tail-call eval
> >> compatible with BIP141¡¯s CLEANSTACK consensus rule by allowing
> >> parameters to be passed on the alt-stack. * Restricted tail-call eval
> >> to segwit scripts only, so that checking sigop and opcode limits of the
> >> policy script would not be necessary.
> >> 
> >> There were a bunch of other small modifications, typo fixes, and
> >> optimizations that were made as well.
> >> 
> >> I am now ready to submit these BIPs as a PR against the bitcoin/bips
> >> repo, and I request that the BIP editor assign numbers.
> >> 
> >> Thank you,
> >> Mark Friedenbach
> >> 
> >>> On Sep 6, 2017, at 5:38 PM, Mark Friedenbach <mark@friedenbach.org>
> >>> wrote:
> >>> 
> >>> I would like to propose two new script features to be added to the
> >>> bitcoin protocol by means of soft-fork activation. These features are
> >>> a new opcode, MERKLE-BRANCH-VERIFY (MBV) and tail-call execution
> >>> semantics.
> >>> 
> >>> In brief summary, MERKLE-BRANCH-VERIFY allows script authors to force
> >>> redemption to use values selected from a pre-determined set committed
> >>> to in the scriptPubKey, but without requiring revelation of unused
> >>> elements in the set for both enhanced privacy and smaller script
> >>> sizes. Tail-call execution semantics allows a single level of
> >>> recursion into a subscript, providing properties similar to P2SH while
> >>> at the same time more flexible.
> >>> 
> >>> These two features together are enough to enable a range of
> >>> applications such as tree signatures (minus Schnorr aggregation) as
> >>> described by Pieter Wuille [1], and a generalized MAST useful for
> >>> constructing private smart contracts. It also brings privacy and
> >>> fungibility improvements to users of counter-signing wallet/vault
> >>> services as unique redemption policies need only be revealed if/when
> >>> exceptional circumstances demand it, leaving most transactions looking
> >>> the same as any other MAST-enabled multi-sig script.
> >>> 
> >>> I believe that the implementation of these features is simple enough,
> >>> and the use cases compelling enough that we could BIP 8/9 rollout of
> >>> these features in relatively short order, perhaps before the end of
> >>> the year.
> >>> 
> >>> I have written three BIPs to describe these features, and their
> >>> associated implementation, for which I now invite public review and
> >>> discussion:
> >>> 
> >>> Fast Merkle Trees
> >>> BIP: https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee0a
> >>> Code: https://github.com/maaku/bitcoin/tree/fast-merkle-tree
> >>> 
> >>> MERKLEBRANCHVERIFY
> >>> BIP: https://gist.github.com/maaku/bcf63a208880bbf8135e453994c0e431
> >>> Code: https://github.com/maaku/bitcoin/tree/merkle-branch-verify
> >>> 
> >>> Tail-call execution semantics
> >>> BIP: https://gist.github.com/maaku/f7b2e710c53f601279549aa74eeb5368
> >>> Code: https://github.com/maaku/bitcoin/tree/tail-call-semantics
> >>> 
> >>> Note: I have circulated this idea privately among a few people, and I
> >>> will note that there is one piece of feedback which I agree with but
> >>> is not incorporated yet: there should be a multi-element MBV opcode
> >>> that allows verifying multiple items are extracted from a single
> >>> tree. It is not obvious how MBV could be modified to support this
> >>> without sacrificing important properties, or whether should be a
> >>> separate multi-MBV opcode instead.
> >>> 
> >>> Kind regards,
> >>> Mark Friedenbach

[bitcoin-dev] maximum block height on transaction

[Erik Aronesty]

is there any way to specify a maximum block height on a transaction?

ie: this tx is only valid if included in a block with a certain height or less

i feel like this would be useful

Re: [bitcoin-dev] maximum block height on transaction

[Russell O'Connor]

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

From https://bitcointalk.org/index.php?topic=1786.msg22119#msg22119:

We can't safely do OP_BLOCKNUMBER.  In the event of a block chain reorg
> after a segmentation, transactions need to be able to get into the chain in
> a later block.  The OP_BLOCKNUMBER transaction and all its dependants would
> become invalid.  This wouldn't be fair to later owners of the coins who
> weren't involved in the time limited transaction.
>
> nTimeLock does the reverse.  It's an open transaction that can be replaced
> with new versions until the deadline.  It can't be recorded until it
> locks.  The highest version when the deadline hits gets recorded.  It could
> be used, for example, to write an escrow transaction that will
> automatically permanently lock and go through unless it is revoked before
> the deadline.  The feature isn't enabled or used yet, but the support is
> there so it could be implemented later.
>

Unfortunately, limiting the maximum block height for a specific transaction
would have exactly the same problem as cited above for OP_BLOCKNUMBER.

On Fri, Apr 9, 2021 at 7:21 AM Erik Aronesty via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> is there any way to specify a maximum block height on a transaction?
>
> ie: this tx is only valid if included in a block with a certain height or
> less
>
> i feel like this would be useful
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

Re: [bitcoin-dev] maximum block height on transaction

[Jeremy]

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

You could accomplish your rough goal by having:



tx A: desired expiry at H
tx B: nlocktime H, use same inputs as A, create outputs equivalent to
inputs (have to be sure no relative timelocks)

Thus after a timeout the participants in A can cancel the action using TX B.

The difference is the coins have to move, without knowing your use case
this may or may not help you.

On Fri, Apr 9, 2021, 4:40 AM Russell O'Connor via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> From https://bitcointalk.org/index.php?topic=1786.msg22119#msg22119:
>
> We can't safely do OP_BLOCKNUMBER.  In the event of a block chain reorg
>> after a segmentation, transactions need to be able to get into the chain in
>> a later block.  The OP_BLOCKNUMBER transaction and all its dependants would
>> become invalid.  This wouldn't be fair to later owners of the coins who
>> weren't involved in the time limited transaction.
>>
>> nTimeLock does the reverse.  It's an open transaction that can be
>> replaced with new versions until the deadline.  It can't be recorded until
>> it locks.  The highest version when the deadline hits gets recorded.  It
>> could be used, for example, to write an escrow transaction that will
>> automatically permanently lock and go through unless it is revoked before
>> the deadline.  The feature isn't enabled or used yet, but the support is
>> there so it could be implemented later.
>>
>
> Unfortunately, limiting the maximum block height for a specific
> transaction would have exactly the same problem as cited above for
> OP_BLOCKNUMBER.
>
> On Fri, Apr 9, 2021 at 7:21 AM Erik Aronesty via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> is there any way to specify a maximum block height on a transaction?
>>
>> ie: this tx is only valid if included in a block with a certain height or
>> less
>>
>> i feel like this would be useful
>> _______________________________________________
>> 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
>

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

Re: [bitcoin-dev] maximum block height on transaction

[Billy Tetrud]

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

@Russell I think there were sound arguments against Satoshi's statement
made in that very thread. Especially that software can be written to warn
the user about edge cases.

If a person waited for the standard 6 blocks before accepting a transaction
as confirmed, there should be no significantly likely scenario where any
finalized transaction needs to be reverted. If 6 blocks is indeed a safe
threshold for finalization, then any transaction that has 5 or fewer
confirmations should be considered fair game for reversal. I don't agree
that this is "unfair". In fact, I think that's pretty standard, is it not?
Any chain of transactions that happen in the span of 5 blocks shouldn't be
doing anything that expects those transactions to become finalized until
the relevant transactions get 6 confirmations.

I don't think the possibility of buggy software is a good reason to block
an opcode. Not that I'm hankering for OP_BLOCKNUMBER specifically. However,
I think there are good use cases for spend paths that expire (eg for more
effective wallet vaults).

I've come across this argument before, and it seems kind of like Satoshi's
word here is held as gospel. I haven't heard any deep discussion of this
topic, and I even asked a question on the bitcoin SE
<https://bitcoin.stackexchange.com/questions/96366/what-are-the-reasons-to-avoid-spend-paths-that-become-invalid-over-time-without>
about it. Sorry to hijack this conversation, but I'm very curious if
there's something more to this or if the thinking was simply decided that
OP_BLOCKNUMBER wasn't useful enough to warrant the (dubious) potential
footgun of people accepting sub-6-block transactions from a transaction
that uses an expired spend-path?

On Fri, Apr 9, 2021 at 5:55 AM Jeremy via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> You could accomplish your rough goal by having:
>
>
>
> tx A: desired expiry at H
> tx B: nlocktime H, use same inputs as A, create outputs equivalent to
> inputs (have to be sure no relative timelocks)
>
> Thus after a timeout the participants in A can cancel the action using TX
> B.
>
> The difference is the coins have to move, without knowing your use case
> this may or may not help you.
>
> On Fri, Apr 9, 2021, 4:40 AM Russell O'Connor via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> From https://bitcointalk.org/index.php?topic=1786.msg22119#msg22119:
>>
>> We can't safely do OP_BLOCKNUMBER.  In the event of a block chain reorg
>>> after a segmentation, transactions need to be able to get into the chain in
>>> a later block.  The OP_BLOCKNUMBER transaction and all its dependants would
>>> become invalid.  This wouldn't be fair to later owners of the coins who
>>> weren't involved in the time limited transaction.
>>>
>>> nTimeLock does the reverse.  It's an open transaction that can be
>>> replaced with new versions until the deadline.  It can't be recorded until
>>> it locks.  The highest version when the deadline hits gets recorded.  It
>>> could be used, for example, to write an escrow transaction that will
>>> automatically permanently lock and go through unless it is revoked before
>>> the deadline.  The feature isn't enabled or used yet, but the support is
>>> there so it could be implemented later.
>>>
>>
>> Unfortunately, limiting the maximum block height for a specific
>> transaction would have exactly the same problem as cited above for
>> OP_BLOCKNUMBER.
>>
>> On Fri, Apr 9, 2021 at 7:21 AM Erik Aronesty via bitcoin-dev <
>> bitcoin-dev@lists.linuxfoundation.org> wrote:
>>
>>> is there any way to specify a maximum block height on a transaction?
>>>
>>> ie: this tx is only valid if included in a block with a certain height
>>> or less
>>>
>>> i feel like this would be useful
>>> _______________________________________________
>>> 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
>>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

Re: [bitcoin-dev] maximum block height on transaction

[ZmnSCPxj]

Good morning Billy,


> I've come across this argument before, and it seems kind of like Satoshi's word here is held as gospel. I haven't heard any deep discussion of this topic, and I even asked a question on the bitcoin SE about it. Sorry to hijack this conversation, but I'm very curious if there's something more to this or if the thinking was simply decided that OP_BLOCKNUMBER wasn't useful enough to warrant the (dubious) potential footgun of people accepting sub-6-block transactions from a transaction that uses an expired spend-path?

Another argument I have encountered has to do with the implementation of Bitcoin Core.

As an optimization, SCRIPT is evaluated only when a transaction enters the mempool.
It is not evaluated at any other time.
Indeed, when accepting a new block, if a transaction in that block is in the mempool, its SCRIPT is not re-evaluated.

If the max-blockheight-constraint is implemented as a SCRIPT opcode, then at each block, every SCRIPT in every transaction in the mempool must be re-evaluated, as the SCRIPT might not reject.
During times of high chain bloat, there will be large numbers of transactions in the mempool, only a tiny fraction will be removed at each block before the mempool finally clears, leading to effective O(n^2) CPU time spent (n blocks are needed in order to empty a mempool with n transactions, each block triggers re-evaluation of SCRIPT of n transactions in the mempool).
That O(n^2) assumes a single SCRIPT is O(1), which is untrue as well (but is generally approached in practice as most transactions are simple singlesig or `OP_CHECKMULTISIG` affairs).

That is, the mempool assumes that once a SCRIPT accepts, it will always accept in the future.
Thus, any SCRIPT opcode cannot change from "accept" (because at the current blockheight the max-block is not yet reached) to "reject" (because the max-block constraint is now violated).

Thus, we cannot use an opcode to impose the max-block cosntraint.

The alternative is to add a new field `maxtime` to the transaction.
Then possibly, we can have an `OP_CHECKMAXTIMEVERIFY` opcode that checks that the field has a particular value.
Then the mempool can have a separate index according to `maxtime` fields, where it can remove the indexed transactions at each block.
The index will be likely O(log n), and the filtering at each block would be O(n log n), which is an improvement.
Note in particular that the index itself would require O(n) storage.

However, adding a new field to the transaction format would require techniques similar to what was used in SegWit, i.e. post-maxtime nodes have to "baby talk" to pre-maxtime nodes and pretend transactions do not have this field, in much the same way post-SegWit nodes "baby talk" to pre-SegWit nodes and pretend transactions do not have a `witness` field.
We would then need a third Merkle Tree to hold the "really real" transaction ID that contains the `maxtime` field as well.

Thus, it seems to me that the tradeoffs are simply not good enough, when you can get 99% of what you need using just another transaction with `nLockTime`:

* Using an opcode would greatly increase CPU usage because the script cache would need to be reworked (and probably cannot be made to work).
* Adding a field would greatly increase the code complexity to the level of SegWit, without all the important bugfixes+features (tx malleability, quadratic sighash, well-defined extensible outputs) that SegWit provides.
* You can do what you want with a second `nLockTime`d transaction that spends the output anyway.

Indeed, it is helpful to realize *why* `OP_CHECKLOCKTIMEVERIFY` and `OP_CHECKSEQUENCEVERIFY` work the way they are implemented.
They are typically discussed and described as if they were imposing time-based constraints, but the *real* implementation only imposes constraints on `nLockTime` and `nSequence` fields --- the SCRIPT interpreter itself does not look at the block that the transaction is in (because that is not available, as the SCRIPT interpreter is invoked at mempool entry, when the transaction *has* no block it is contained in).
There is instead a separate layer (the entry into the mempool) that implements the *actual* time-based cosntraints, based on the fields and not the SCRIPT opcodes.

Regards,
ZmnSCPxj

>
> On Fri, Apr 9, 2021 at 5:55 AM Jeremy via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> > You could accomplish your rough goal by having:
> >
> > tx A: desired expiry at H
> > tx B: nlocktime H, use same inputs as A, create outputs equivalent to inputs (have to be sure no relative timelocks)
> >
> > Thus after a timeout the participants in A can cancel the action using TX B.
> >
> > The difference is the coins have to move, without knowing your use case this may or may not help you. 
> >
> > On Fri, Apr 9, 2021, 4:40 AM Russell O'Connor via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> >
> > > From https://bitcointalk.org/index.php?topic=1786.msg22119#msg22119:
> > >
> > > > We can't safely do OP_BLOCKNUMBER.  In the event of a block chain reorg after a segmentation, transactions need to be able to get into the chain in a later block.  The OP_BLOCKNUMBER transaction and all its dependants would become invalid.  This wouldn't be fair to later owners of the coins who weren't involved in the time limited transaction.
> > > >
> > > > nTimeLock does the reverse.  It's an open transaction that can be replaced with new versions until the deadline.  It can't be recorded until it locks.  The highest version when the deadline hits gets recorded.  It could be used, for example, to write an escrow transaction that will automatically permanently lock and go through unless it is revoked before the deadline.  The feature isn't enabled or used yet, but the support is there so it could be implemented later.
> > >
> > > Unfortunately, limiting the maximum block height for a specific transaction would have exactly the same problem as cited above for OP_BLOCKNUMBER.
> > >
> > > On Fri, Apr 9, 2021 at 7:21 AM Erik Aronesty via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> > >
> > > > is there any way to specify a maximum block height on a transaction?
> > > >
> > > > ie: this tx is only valid if included in a block with a certain height or less
> > > >
> > > > i feel like this would be useful
> > > > _______________________________________________
> > > > 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
> >
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] maximum block height on transaction

[ZmnSCPxj]

Good morning Billy, and list,

> -   Using an opcode would greatly increase CPU usage because the script cache would need to be reworked (and probably cannot be made to work).
> -   Adding a field would greatly increase the code complexity to the level of SegWit, without all the important bugfixes+features (tx malleability, quadratic sighash, well-defined extensible outputs) that SegWit provides.

Sometimes, the only way out is through.

A general idea to get around this would be:

* Define a "hidden" field of a transaction, which is not existent in *any* serialization of the transaction.
* Set a default value for this field that would be compatible with pre-softfork rules.
* Have an opcode that manipulates this field, carefully designed so it is idempotent.

The above general idea is not original to me, I believe.
I think I have seen it elsewhere on the list, possibly in discussions around sidechains, though my primary cache is unable to fetch and additional searches through unindexed storage is taking too long.

So, for this particular case, here is a (non-serious) proposal to implement a maximum block height on transactions.

* Create a new field `u32 nMaxHeight` on `CTransaction` that is not serialized in any transaction format.
  * A block is not valid if any transaction in it has an `nMaxHeight` larger than the block height of the block.
  * Default value is `0xFFFFFFFF`.
* Add a new opcode `OP_SETMAXHEIGHT` that replaces an existing `OP_NOP`.
  * The opcode must be followed by an `OP_PUSH` of a 32-bit value, else script validation fails.
    * This prevents using a computed value, instead the value must be given as a constant in the script text.
      This is a precaution to reduce the risk that execution of the script at a different time or different computer or etc will result in a different value that the `OP_SETMAXHEIGHT` opcode uses, which can cause consensus divergence.
      If we figure out later that this precaution is not necessary, we can just use another `OP_NOP` for `OP_SETMAXHEIGHTFROMSTACK`.
  * If the current `nMaxHeight` is larger than the given value, then the `nMaxHeight` is set to the given value.

The above avoids issues with opcodes --- the script interpreter can continue to be executed in the only place it is in, i.e. at entry into the mempool.
It also avoids some of the code complexity with fields, since the field is non-existent in any serialization of the transaction, but is instead implied by the scripts that the transaction causes to be executed, reducing the need to identify pre-softfork peers and baby-talk to them --- the baby-talk simply contains "parental bonuses" that are understood by upgraded nodes who are "in the know".

Additional complications, such as the need for an index of `nMaxHeight` for transactions in the mempool (to remove transactions whose `nMaxHeight` is now in the past), and the additional checks needed when receiving an in-block transaction that is not in the mempool, are left to the reader.
Similar field and opcode for `CTransactionInput` for a relative-time max height are also left as an exercise to the reader.

> -   You can do what you want with a second `nLockTime`d transaction that spends the output anyway.

The advantage of this functionality is that you can be safely offline at the time the timeout occurs in any complicated timeout-based contract.

Typically, when using say an HTLC, the contractor who holds lien on the timelock branch, has to be online at the time the timelock becomes valid, in order to impose a timeout on the hashlock branch.
However, if instead the hashlock branch includes an `OP_SETMAXHEIGHT`, then the contractor holding lien on the timelock branch does not have this risk.

However, the contractor holding the lien on the hashlock branch now has increased risk.
If the timeout is approaching, and suddenly there is high mempool usage at the time, then a claim of the hashlock branch may fall off the mempool due to `nMaxHeight` violation.
But the transaction claiming the hashlock branch has been published and the preimage has been published in mempools all over the world, thus the contractor holding lien on the hashlock branch risks not being compensated for revelation of the preimage.

Whereas with the current way things are, the timelock-holder is at risk, and the hashlock-holder has reduced risk since even if the timeout arrives, there is still the possibility that the hashlock branch is what gets confirmed, whereas with `OP_SETMAXHEIGHT` the hashlock-holder has 0 chance of getting the hashlock branch confirmed in case of sudden spike in onchain usaage.

Thus it seems to me that this scheme does not really *improve* Bitcoin significantly, it only moves risks from one participant to another in a two-participant contract.
Thus, this proposal is not particularly serious.

Regards,
ZmnSCPxj