Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 0EE12D97 for ; Thu, 23 May 2019 02:06:57 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-oi1-f196.google.com (mail-oi1-f196.google.com [209.85.167.196]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id C5BD26C5 for ; Thu, 23 May 2019 02:06:55 +0000 (UTC) Received: by mail-oi1-f196.google.com with SMTP id w9so3186566oic.9 for ; Wed, 22 May 2019 19:06:55 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc:content-transfer-encoding; bh=TOS4ULl0p6txMsPuovOd4EQwfGFTX9VM9HyaSscQZzM=; b=Tb/Xb1yOudfcSI1sDB/Du+B+45CtWtk7OHFVdLRcbsOkj+ba8TobPgXmtSyW6Buf2w zfzWR6ezXPeQu7AF98FZPFBCoABagOIVkfyAxPq2nj/qkJGzOAzvzpFtI38Sx9TFSGE0 pA/mrq3haZLC8NKk+mV7Bsh8957JHlJ1BtvYyHfzpGwK4PVD0ILVTzdQCaxuSgAK7kKG m+Ra16ae9C/8a00yCjT+8tzGYCM6u3JFXjWNfdN+iOLS0VBX51mmVepg+wOduqpFwdsu KK4Nz5thbJUMCDSmnstpZ164YeOfOdcte4C/YQDBBaKVXwOUGyOhMB0irZsqdVZu72BO Vt1w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=TOS4ULl0p6txMsPuovOd4EQwfGFTX9VM9HyaSscQZzM=; b=FEX0r5poCYfmakCV0XwPRKYJUUndL30uhOBD91BmENY8u+4Vz3erhZOaQWyNZHk7EW 4Zu1ICaWz+NZKI/E4dOA5qtSiYKpIzp+/2FoMY2h6dwfgEQmCrK6QtO77y5ZXzPjdYqT 01M/1OzO7+PEmwhL5Rk5gQWHVNPhBglEhqsctO5jkgAmzvCDzcoMgFLM3jmhdYqCIVfY 0mhr3xPrxdhpZM6haG9Um1PpACjs1GdTqwvgcvDgOddtn6GuZJwUTJWjoU3hTCeTXaPX WqSVNxYEv6NTXEw1P0wx9fOE2o310Ln90jC3sEfhovS/+/etGKMf20xcy9HM7/oC2P8e Oe0A== X-Gm-Message-State: APjAAAViB2RN0mYtNtrkWZ8SsDZzu/nafNpTVVT5lDhshBarJPCzCZU0 ue/RYZzQXNr+x2RoXIBCJAdXmF4Go1K3xkVhQvw= X-Google-Smtp-Source: APXvYqzpXo4MXT5B5CgrCdHyoXbv1KlXQXAbHJvLBPu2KOzHWeDhkEjhlcMDaoA/PvIP4Bqg5rV+IOyScRKtb61i3TE= X-Received: by 2002:aca:f089:: with SMTP id o131mr1254960oih.103.1558577214757; Wed, 22 May 2019 19:06:54 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Pieter Wuille Date: Wed, 22 May 2019 19:06:42 -0700 Message-ID: To: "Russell O'Connor" , John Newbery Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Thu, 23 May 2019 13:31:42 +0000 Cc: Bitcoin Protocol Discussion , Andrew Poelstra Subject: Re: [bitcoin-dev] Taproot proposal X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 23 May 2019 02:06:57 -0000 On Tue, 21 May 2019 at 10:20, Russell O'Connor 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 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 " OP_CHECKSEQUENCEVERIFY" or " 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 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