Content-Type: text/plain; charset=us-ascii
Mime-Version: 1.0 (Mac OS X Mail 10.3 \(3273\))
From: Mark Friedenbach <mark@friedenbach.org>
In-Reply-To: <DA22C531-2FAE-4332-B158-A3F96BF34002@xbt.hk>
Date: Tue, 12 Sep 2017 12:57:10 -0700
Content-Transfer-Encoding: 7bit
Message-Id: <61D84B62-0F3F-48E1-B749-F628AD91BC12@friedenbach.org>
References: <5B6756D0-6BEF-4A01-BDB8-52C646916E29@friedenbach.org>
	<26AD157C-A5A9-48C3-8D29-0AD1ED35EDDD@xbt.hk>
	<2419914E-E196-44B4-8663-599AF616A897@friedenbach.org>
	<DA22C531-2FAE-4332-B158-A3F96BF34002@xbt.hk>
To: Johnson Lau <jl2012@xbt.hk>
Cc: bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Merkle branch verification & tail-call semantics
 for generalized MAST
Precedence: list

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