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

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

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

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

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

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

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

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

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

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

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

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

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,

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.

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

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

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

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