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

2017-11-04 Thread Luke Dashjr via bitcoin-dev 
How about using for the first stage, `<...> OP_CALCMERKLEROOT  OP_EQUAL` 
instead of ` OP_CHECKMERKLEBRANCH`? There's maybe 1 or 2 bytes extra, 
but it seems more future-proof (since there could more easily be alternatives 
to ` 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  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  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 
> >>> 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,
> >>>

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

2017-11-01 Thread Mark Friedenbach via bitcoin-dev 
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  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  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 
>>> 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
>>>

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

2017-11-01 Thread Luke Dashjr via bitcoin-dev 
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  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 
> > 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

2017-10-27 Thread Mark Friedenbach via bitcoin-dev 
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  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

2017-10-02 Thread Russell O'Connor via bitcoin-dev 
(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  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  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

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

2017-09-30 Thread Luke Dashjr via bitcoin-dev 
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
___
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

2017-09-18 Thread Mark Friedenbach via bitcoin-dev 
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 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

2017-09-13 Thread Peter Todd via bitcoin-dev 
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
>  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


signature.asc
Description: Digital signature
___
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

2017-09-13 Thread Karl Johan Alm via bitcoin-dev 
On Wed, Sep 13, 2017 at 4:57 AM, Mark Friedenbach via bitcoin-dev
 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.
___
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

2017-09-12 Thread Mark Friedenbach via bitcoin-dev 
On Sep 12, 2017, at 1:55 AM, Johnson Lau  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

___
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

2017-09-12 Thread Johnson Lau via bitcoin-dev 

> On 12 Sep 2017, at 10:03 AM, Mark Friedenbach  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  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

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

2017-09-11 Thread Bryan Bishop via bitcoin-dev 
On Mon, Sep 11, 2017 at 9:03 PM, Mark Friedenbach via bitcoin-dev
 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
___
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

2017-09-11 Thread Adán Sánchez de Pedro Crespo via bitcoin-dev 
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



signature.asc
Description: OpenPGP digital signature
___
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

2017-09-08 Thread Johnson Lau via bitcoin-dev 
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 
>  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


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