MIME-Version: 1.0
References: <CAPg+sBg6Gg8b7hPogC==fehY3ZTHHpQReqym2fb4XXWFpMM-pQ@mail.gmail.com>
	<CAMZUoKkm33U+Rb+x03qUsFDG5CeX2C=nW8vD_8zbiAdsWazofQ@mail.gmail.com>
In-Reply-To: <CAMZUoKkm33U+Rb+x03qUsFDG5CeX2C=nW8vD_8zbiAdsWazofQ@mail.gmail.com>
From: Pieter Wuille <pieter.wuille@gmail.com>
Date: Wed, 22 May 2019 19:06:42 -0700
Message-ID: <CAPg+sBh=VGiBS6Cof_SBKo2aPGURicTRkuaXWwaW0_u8_nWZ1Q@mail.gmail.com>
To: "Russell O'Connor" <roconnor@blockstream.io>,
	John Newbery <john@johnnewbery.com>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>,
	Andrew Poelstra <andrew.poelstra@blockstream.com>
Subject: Re: [bitcoin-dev] Taproot proposal
Precedence: list

On Tue, 21 May 2019 at 10:20, Russell O'Connor <roconnor@blockstream.io> wr=
ote:
>
> Regarding Tapscript, the specification calls for the final value of the s=
tack being a single non-false value:
>
>> The tapscript is executed according to the rules in the following sectio=
n, with the initial stack as input
>>     II. If the execution results in anything but exactly one element on =
the stack which evaluates to true with CastToBool(), fail.
>
> Perhaps it is worth taking this opportunity here to remove a minor wart o=
f the Script language and instead require the stack to be exactly empty upo=
n completion.
>
> In addition to removing a potential malleability vector, I expect it woul=
d simplify development of Bitcoin Script.  A rule requiring an empty stack =
means that the conjunction (logical and) of two policies can be implemented=
 by the simple concatenation of Bitcoin Scripts.  This combined with the ta=
proot ability to form the disjunction (logical or) of policies by having mu=
ltiple Merkle branches, means that the translation of a policy written in d=
isjunctive normal form (the logical ors of logical ands of primitive polici=
es) can be straightforwardly translated to a taproot of tapscript.
>
> That said, I think the developers of miniscript <http://bitcoin.sipa.be/m=
iniscript/miniscript.html> are in a much better position to comment on whet=
her my above intuition is correct given that they've had to implement a hos=
t of various calling conventions.  I understand that at least some of this =
complexity is due to Bitcoin Script's one element stack rule.

IIRC I looked into this a few months ago, and found that the spending
cost (script size + expected witness size) of the optimal script for
every Miniscript policy at most changes by 1 WU (in either direction)
by requiring an empty stack rather than a true value, though in a
(admittedly very arbitrarily biased) distribution, more policies were
improved by it than degraded. This is not taking Taproot into account
(as many of those policies in a Taproot-supporting world should
optimally make use of the internal key and Merkle tree, rather than
turning everything into a monolithic script). I expect that this may
make the impact somewhat larger, but still never more than a 1 WU
gain.

I don't think the spending cost changes justify this change, so the
remaining criteria are complexity ones. In my view, the main benefit
would be to authors of hand-written scripts where the consistency
benefits matter, but this needs to be weighed against the mental cost
of learning the new semantics. For Miniscript itself, this doesn't
make much difference - the top level calling convention would become
'V' instead of 'T', but 'T' would still exist as a calling convention
that may be used internally; it's a few lines change.

So overall this feels like something with marginal costs, but also at
most marginal benefits. Perhaps other people have stronger opinions.

> Even if we choose not to implement the empty stack rule, we should at lea=
st require that the last element be 0x01 to remove a potential malleability=
 vector and bring it in line with MINIMAL_IF semantics.

This feels like the right thing to do; as we're making MINIMALIF part
of consensus for Tapscript it would make sense to apply the same rule
to the "return" value of the script. There is a downside though,
namely that in some places where you'd use "<n>
OP_CHECKSEQUENCEVERIFY" or "<n> OP_CHECKLOCKTIMEVERIFY" you now need
to add an additional OP_0NOTEQUAL to convert the left-over element n
into an exact 0x01. I also can't come up with any practical benefits
that this would have; if the top stack element in a particular code
path comes directly from the input, it's insecure regardless; if there
isn't, it'll generally be a a boolean (or an intentional non-boolean
true value) computed by the script.

On Tue, 21 May 2019 at 13:05, John Newbery <john@johnnewbery.com> wrote:
>
> Hi,
>
> > A Taproot output is a SegWit output [...]  with
> > version number 1, and a 33-byte witness program whose first byte is 0 o=
r 1.
>
> Given a secret key k and public key P=3D(x,y), a signer with the knowledg=
e of k
> can sign for -P=3D(x,p-y) since -k is the secret key for that point. Enco=
ding the
> y value of the public key therefore adds no security.

That's a good point; without security benefit there's no reason to
make pay-to-taproots more expensive. Making them the same cost as
P2WSH is nice in any case.

> As an alternative to
> providing the y value of the taproot output key Q when constructing the t=
aproot
> output, the signer can provide it when signing. We can also restrict the =
y value
> of the internal key P to be even (or high, or a quadratic residue). That =
gives
> us 4 options for how to set the y signs for P and Q.
>
> 1. Q sign is explictly set in the witness program, P sign is explicitly s=
et in the control block
>     =3D> witness program is 33 bytes, 32 possible leaf versions (one for =
each pair of 0xc0..0xff)
> 2. Q sign is explictly set in the witness program, P sign is implicitly e=
ven
>     =3D> witness program is 33 bytes, 64 possible leaf versions (one for =
each 0xc0..0xff)
> 3. Q sign is explictly set in the control block, P sign is explicitly set=
 in the control block
>     =3D> witness program is 32 bytes, 16 possible leaf versions (one for =
each 4-tuple of 0xc0..0xff)
> 4. Q sign is explictly set in the control block, P sign is implicitly eve=
n
>     =3D> witness program is 32 bytes, 32 possible leaf versions (one for =
pair of 0xc0..0xff)
>
> The current proposal uses (1). Using (3) or (4) would reduce the size of =
a
> taproot output by one byte to be the same size as a P2WSH output. That me=
ans
> that it's not more expensive for senders compared to sending to P2WSH.

I prefer (4). There is a slight complexity in needing a conditional
sign swap when signing (to make sure the corresponding key is even),
but I think it's minimal compared to the other changes needed here
already. I'll try to amend the reference code soon to see what impact
this idea has.

> > (native or P2SH-nested, see BIP141)
>
> I'd prefer to not support P2SH-nested TR. P2SH wrapping was useful for se=
gwit
> v0 for compatibility reasons. Most wallets/exchanges/services now support=
 sending
> to native segwit addresses (https://en.bitcoin.it/wiki/Bech32_adoption) a=
nd that
> will be even more true if Schnorr/Taproot activate in 12+ months time.

I'm not sure there is much to gain here. There is perhaps a minimal
fungibility improvement by not having another bit (P2SH or not) that
can leak some information about the software you're using. On the
other hand, until native taproot outputs are common, choosing P2SH
wrapped ones leak less information at output creation time. Apart from
that, I think it would only minimally impact implementation
complexity. Are there other advantages I'm missing?

Cheers,

--=20
Pieter