diff options
| author | Russell O'Connor <roconnor@blockstream.io> | 2018-05-10 10:23:09 -0400 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2018-05-10 14:23:33 +0000 |
| commit | 1b02c5cbee6d11bef9df2515059364f2517ee4b6 (patch) | |
| tree | 58254e223eb58478cf06de902d2569266e2cbf21 | |
| parent | 02b561859e071165da9e0c970c7acc5d139eced8 (diff) | |
| download | pi-bitcoindev-1b02c5cbee6d11bef9df2515059364f2517ee4b6.tar.gz pi-bitcoindev-1b02c5cbee6d11bef9df2515059364f2517ee4b6.zip | |
Re: [bitcoin-dev] MAST/Schnorr related soft-forks
| -rw-r--r-- | a1/3833b2048ba35f7cce87bf022164cc41903fbf | 728 |
1 files changed, 728 insertions, 0 deletions
diff --git a/a1/3833b2048ba35f7cce87bf022164cc41903fbf b/a1/3833b2048ba35f7cce87bf022164cc41903fbf new file mode 100644 index 000000000..a6f509f4c --- /dev/null +++ b/a1/3833b2048ba35f7cce87bf022164cc41903fbf @@ -0,0 +1,728 @@ +Return-Path: <roconnor@blockstream.io> +Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org + [172.17.192.35]) + by mail.linuxfoundation.org (Postfix) with ESMTPS id 21B6A97A + for <bitcoin-dev@lists.linuxfoundation.org>; + Thu, 10 May 2018 14:23:33 +0000 (UTC) +X-Greylist: whitelisted by SQLgrey-1.7.6 +Received: from mail-it0-f52.google.com (mail-it0-f52.google.com + [209.85.214.52]) + by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 62EA3685 + for <bitcoin-dev@lists.linuxfoundation.org>; + Thu, 10 May 2018 14:23:31 +0000 (UTC) +Received: by mail-it0-f52.google.com with SMTP id n202-v6so3314273ita.1 + for <bitcoin-dev@lists.linuxfoundation.org>; + Thu, 10 May 2018 07:23:31 -0700 (PDT) +DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; + d=blockstream.io; s=google; + h=mime-version:in-reply-to:references:from:date:message-id:subject:to; + bh=Cs2udz2wg4m9v4wxdNzmcJ1kPNVvyVDjVufBGzI9kxU=; + b=GkpG4Uc4VFyOlpYoJEuRw0uz+rHmRT6NbtPM01gRpl4Sgvg0UsAnZUQ/fR6w8wbn9O + t4gHA1hL3JCVlub5taF1PWm8fZqMyGdAM0sBPH+inzIQV8qavcOb3s2AIB1JwkCPugpm + 1pRa4GVwEqVSWvgcvjieSmkMmh/Bp7Lb6eY9A= +X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; + d=1e100.net; s=20161025; + h=x-gm-message-state:mime-version:in-reply-to:references:from:date + :message-id:subject:to; + bh=Cs2udz2wg4m9v4wxdNzmcJ1kPNVvyVDjVufBGzI9kxU=; + b=GuvL3PkRbCqjbdZjkaAz4gk6qijN1EiBwjeoYmXHEF8Me+rg+ibHfL46hAMk4KTymi + GNdxAsIK7AA0sn8KGwGPS+SRKAkKLAcW2GmAZNqtoiDFdgTdyz8/2FdvjumN+djSDHn2 + QTdyFpFOFZVIap+i/myGqoc0Jpa+RF5FA/oAVAWcJUJ+kDlAIl0ah3KCxclmumaZ0UwY + jsEvvNO0UHel2kCmr5W94tMusDQJFsOi5W4s+078/xt00t5rMQixQHsAXnGurxR5hb5d + GmFfIIa3V1C1iRRNsK1EM09c/I42UwTnhkfz21+rTNa/SbeKT73SubkTrMsjN+CMWeNa + mMaA== +X-Gm-Message-State: ALKqPwcVkwOkfFBJEr5CdQ+EqF8IOAaABbP6GNLBN3eaKdW4rH5WVw/0 + t0I6UZoJch1bV1vzCR7MERZEPKGit+r9sJZseN0AT2aVLDU= +X-Google-Smtp-Source: AB8JxZo0/1DLOrXwXlntkEcjgXGpg2fAhDDVmwJmA0fIX8mRMueF44eqghqB+pi5NxnVdb9I5Gix58wLI6rfwd+ZrCk= +X-Received: by 2002:a24:4522:: with SMTP id + y34-v6mr2118357ita.74.1525962210486; + Thu, 10 May 2018 07:23:30 -0700 (PDT) +MIME-Version: 1.0 +Received: by 2002:a02:1086:0:0:0:0:0 with HTTP; Thu, 10 May 2018 07:23:09 + -0700 (PDT) +In-Reply-To: <20180510121027.GA17607@erisian.com.au> +References: <20180510121027.GA17607@erisian.com.au> +From: "Russell O'Connor" <roconnor@blockstream.io> +Date: Thu, 10 May 2018 10:23:09 -0400 +Message-ID: <CAMZUoKnPVz+XOq-cQRQuLbCuqn4H28WSMXCK3Rnt8VVivedYCw@mail.gmail.com> +To: Anthony Towns <aj@erisian.com.au>, + Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org> +Content-Type: multipart/alternative; boundary="0000000000007f475b056bdac37d" +X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, + DKIM_VALID,DKIM_VALID_AU,HTML_MESSAGE,RCVD_IN_DNSWL_NONE, + T_TVD_FUZZY_SECURITIES autolearn=ham version=3.3.1 +X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on + smtp1.linux-foundation.org +Subject: Re: [bitcoin-dev] MAST/Schnorr related soft-forks +X-BeenThere: bitcoin-dev@lists.linuxfoundation.org +X-Mailman-Version: 2.1.12 +Precedence: list +List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org> +List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, + <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe> +List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/> +List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org> +List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help> +List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, + <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe> +X-List-Received-Date: Thu, 10 May 2018 14:23:33 -0000 + +--0000000000007f475b056bdac37d +Content-Type: text/plain; charset="UTF-8" + +Thanks for writing this up Anthony. + +Do you think that a CHECKSIGFROMSTACK proposal should be included within +this discussion of signature soft-forks, or do you see it as an unrelated +issue? + +CHECKSIGFROMSTACK enables some forms of (more) efficent MPC (See +http://people.csail.mit.edu/ranjit/papers/scd.pdf), enables poor-man's +covenants, and I believe the lightning folks are interested in it as well +for some constant space storage scheme. + +On Thu, May 10, 2018 at 8:10 AM, Anthony Towns via bitcoin-dev < +bitcoin-dev@lists.linuxfoundation.org> wrote: + +> Hello world, +> +> After the core dev meetup in March I wrote up some notes of where I +> think things stand for signing stuff post-Schnorr. It was mostly for my +> own benefit but maybe it's helpful for others too, so... +> +> They're just notes, so may assume a fair bit of background to be able to +> understand the meaning of the bullet points. In particular, note that I'm +> using "schnorr" just to describe the signature algorithm, and the terms +> "key aggregation" to describe turning an n-of-n key multisig setup into +> a single key setup, and "signature aggregation" to describe combining +> signatures from many inputs/transactions together: those are often all +> just called "schnorr signatures" in various places. +> +> +> Anyway! I think it's fair to split the ideas around up as follows: +> +> 1) Schnorr CHECKSIG +> +> Benefits: +> - opportunity to change signature encoding from DER to save a few +> bytes per signature, and have fixed size signatures making tx size +> calculations easier +> +> - enables n-of-n multisig key aggregation (a single pubkey and +> signature gives n-of-n security; setup non-interactively via muSig, +> or semi-interactively via proof of possession of private key; +> interactive signature protocol) +> +> - enables m-of-n multisig key aggregation with interactive setup and +> interactive signature protocol, and possibly substantial storage +> requirements for participating signers +> +> - enables scriptless scripts and discreet log contracts via +> key aggregation and interactive +> +> - enables payment decorrelation for lightning +> +> - enables batch validation of signatures, which substantially reduces +> computational cost of signature verification, provided a single +> "all sigs valid" or "some sig(s) invalid" output (rather than +> "sig number 5 is invalid") is sufficient +> +> - better than ecdsa due to reducing signature malleability +> (and possibly due to having a security proof that has had more +> review?) +> +> Approaches: +> - bump segwit version to replace P2WPKH +> - replace an existing OP_NOP with OP_CHECKSCHNORRVERIFY +> - hardfork to allowing existing addresses to be solved via Schnorr sig +> as alternative to ECDSA +> +> 2) Merkelized Abstract Syntax Trees +> +> Two main benefits for enabling MAST: +> - logarithmic scaling for scripts with many alternative paths +> - only reveals (approximate) number of alternative execution branches, +> not what they may have been +> +> Approaches: +> - replace an existing OP_NOP with OP_MERKLE_TREE_VERIFY, and treat an +> item remaining on the alt stack at the end of script exeution as a +> script and do tail-recursion into it (BIP 116, 117) +> - bump the segwit version and introduce a "pay-to-merkelized-script" +> address form (BIP 114) +> +> 3) Taproot +> +> Requirements: +> - only feasible if Schnorr is available (required in order to make the +> pubkey spend actually be a multisig spend) +> - andytoshi has written up a security proof at +> https://github.com/apoelstra/taproot +> +> Benefits: +> - combines pay-to-pubkey and pay-to-script in a single address, +> improving privacy +> - allows choice of whether to use pubkey or script at spend time, +> allowing for more efficient spends (via pubkey) without reducing +> flexibility (via script) +> +> Approaches: +> - bump segwit version and introduce a "pay-to-taproot" address form +> +> 4) Graftroot +> +> Requirements: +> - only really feasible if Schnorr is implemented first, so that +> multiple signers can be required via a single pubkey/signature +> - people seem to want a security proof for this; not sure if that's +> hard or straightforward +> +> Benefits: +> - allows delegation of authorisation to spend an output already +> on the blockchain +> - constant scaling for scripts with many alternative paths +> (better than MAST's logarithmic scaling) +> - only reveals the possibility of alternative execution branches, +> not what they may have been or if any actually existed +> +> Drawbacks: +> - requires signing keys to be online when constructing scripts (cannot +> do complicated pay to cold wallet without warming it up) +> - requires storing signatures for scripts (if you were able to +> reconstruct the sigs, you could just sign the tx directly and +> wouldn't +> use a script) +> - cannot prove that alternative methods of spending are not +> possible to anyone who doesn't exclusively hold (part of) the +> output address private key +> - adds an extra signature check on script spends +> +> Approaches: +> - bump segwit version and introduce a "pay-to-graftroot" address form +> +> 5) Interactive Signature Aggregation +> +> Requirements: +> - needs Schnorr +> +> Description: +> - allows signers to interactively collaborate when constructing a +> transaction to produce a single signature that covers multiple +> inputs and/or OP_CHECKSIG invocations that are resolved by Schnorr +> signatures +> +> Benefits: +> - reduces computational cost of additional signatures (i think?) +> - reduces witness storage needed for additional signatures to just the +> sighash flag byte (or bytes, if it's expanded) +> - transaction batching and coinjoins potentially become cheaper than +> independent transactions, indirectly improving on-chain privacy +> +> Drawbacks: +> - each soft-fork introduces a checkpoint, such that signatures that +> are not validated by versions prior to the soft-fork cannot be +> aggregated with signatures that are validated by versions prior to +> the soft-fork (see [0] for discussion about avoiding that drawback) +> +> Approaches: +> - crypto logic can be implemented either by Bellare-Neven or MuSig +> - needs a new p2wpkh output format, so likely warrants a segwit +> version bump +> - may warrant allowing multiple aggregation buckets +> - may warrant peer-to-peer changes and a new per-tx witness +> +> 6) Non-interactive half-signature aggregation within transaction +> +> Requirements: +> - needs Schnorr +> - needs a security proof before deployment +> +> Benefits: +> - can halve the size of non-aggregatable signatures in a transaction +> - in particular implies the size overhead of a graftroot script +> is just 32B, the same as a taproot script +> +> Drawbacks: +> - cannot be used with scriptless-script signatures +> +> Approaches: +> - ideally best combined with interactive aggregate signatures, as it +> has similar implementation requirements +> +> 7) New SIGHASH modes +> +> These will also need a new segwit version (for p2pk/p2pkh) and probably +> need to be considered at the same time. +> +> 8) p2pk versus p2pkh +> +> Whether to stick with a pubkeyhash for the address or just have a pubkey +> needs to be decided for any new segwit version. +> +> 9) Other new opcodes +> +> Should additional opcodes in new segwit versions be reserved as OP_NOP +> or +> as OP_RETURN_VALID, or something else? +> +> Should any meaningful new opcodes be supported or re-enabled? +> +> 10) Hard-fork automatic upgrade of p2pkh to be spendable via segwit +> +> Making existing p2pk or p2pkh outputs spendable via Schnorr with +> interactive signature aggregation would likely be a big win for people +> with old UTXOs, without any decrease in security, especially if done +> a significant time after those features were supported for new outputs. +> +> 11) Should addresses be hashes or scripts? +> +> maaku's arguments for general opcodes for MAST make me wonder a bit +> if the "p2pkh" approach isn't better than the "p2wpkh" approach; ie +> should we have script opcodes as the top level way to write addresses, +> rather than picking the "best" form of address everyone should use, +> and having people have to opt-out of that. probably already too late +> to actually have that debate though. +> +> Anyway, I think what that adds up to is: +> +> - Everything other than MAST and maybe some misc new CHECKVERIFY opcodes +> really needs to be done via new segwit versions +> +> - We can evaluate MAST in segwit v0 independently -- use the existing +> BIPs to deploy MAST for v0; and re-evaluate entirely for v1 and later +> segwit versions. +> +> - There is no point deploying any of this for non-segwit scripts +> +> - Having the taproot script be a MAST root probably makes sense. If so, +> a separate OP_MERKLE_MEMBERSHIP_CHECK opcode still probably makes +> sense at some point. +> +> So I think that adds up to: +> +> a) soft-fork for MAST in segwit v0 anytime if there's community/economic +> support for it? +> +> b) soft-fork for OP_CHECK_SCHNORR_SIG_VERIFY in segwit v0 anytime +> +> c) soft-fork for segwit v1 providing Schnorr p2pk(h) addresses and +> taproot+mast addresses in not too much time +> +> d) soft-fork for segwit v2 introducing further upgrades, particularly +> graftroot +> +> e) soft-fork for segwit v2 to support interactive signature aggregation +> +> f) soft-fork for segwit v3 including non-interactive sig aggregation +> +> The rationale there is: +> +> (a) and (b) are self-contained and we could do them now. My feeling is +> better to skip them and go straight to (c) +> +> (c) is the collection of stuff that would be a huge win, and seems +> "easily" technically feasible. signature aggregation seems too +> complicated to fit in here, and getting the other stuff done while we +> finish thinking about sigagg seems completely worthwhile. +> +> (d) is a followon for (c), in case signature aggregation takes a +> *really* long while. It could conceivably be done as a different +> variation of segwit v1, really. It might turn out that there's no +> urgency for graftroot and it should be delayed until non-interactive +> sig aggregation is implementable. +> +> (e) and (f) are separated just because I worry that non-interactive +> sig aggregation might not turn out to be possible; doing them as a +> single upgrade would be preferrable. +> +> Cheers, +> aj +> +> [0] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/ +> 2018-March/015838.html +> +> _______________________________________________ +> bitcoin-dev mailing list +> bitcoin-dev@lists.linuxfoundation.org +> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev +> + +--0000000000007f475b056bdac37d +Content-Type: text/html; charset="UTF-8" +Content-Transfer-Encoding: quoted-printable + +<div dir=3D"ltr"><div>Thanks for writing this up Anthony.<br><br></div>Do y= +ou think that a CHECKSIGFROMSTACK proposal should be included within this d= +iscussion of signature soft-forks, or do you see it as an unrelated issue?<= +br><br>CHECKSIGFROMSTACK enables some forms of (more) efficent MPC (See <a = +href=3D"http://people.csail.mit.edu/ranjit/papers/scd.pdf">http://people.cs= +ail.mit.edu/ranjit/papers/scd.pdf</a>), enables poor-man's covenants, a= +nd I believe the lightning folks are interested in it as well for some cons= +tant space storage scheme.<br></div><div class=3D"gmail_extra"><br><div cla= +ss=3D"gmail_quote">On Thu, May 10, 2018 at 8:10 AM, Anthony Towns via bitco= +in-dev <span dir=3D"ltr"><<a href=3D"mailto:bitcoin-dev@lists.linuxfound= +ation.org" target=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a>><= +/span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8= +ex;border-left:1px #ccc solid;padding-left:1ex">Hello world,<br> +<br> +After the core dev meetup in March I wrote up some notes of where I<br> +think things stand for signing stuff post-Schnorr. It was mostly for my<br> +own benefit but maybe it's helpful for others too, so...<br> +<br> +They're just notes, so may assume a fair bit of background to be able t= +o<br> +understand the meaning of the bullet points. In particular, note that I'= +;m<br> +using "schnorr" just to describe the signature algorithm, and the= + terms<br> +"key aggregation" to describe turning an n-of-n key multisig setu= +p into<br> +a single key setup, and "signature aggregation" to describe combi= +ning<br> +signatures from many inputs/transactions together: those are often all<br> +just called "schnorr signatures" in various places.<br> +<br> +<br> +Anyway! I think it's fair to split the ideas around up as follows:<br> +<br> +1) Schnorr CHECKSIG<br> +<br> +=C2=A0 Benefits:<br> +=C2=A0 =C2=A0 - opportunity to change signature encoding from DER to save a= + few<br> +=C2=A0 =C2=A0 =C2=A0 bytes per signature, and have fixed size signatures ma= +king tx size<br> +=C2=A0 =C2=A0 =C2=A0 calculations easier<br> +<br> +=C2=A0 =C2=A0 - enables n-of-n multisig key aggregation (a single pubkey an= +d<br> +=C2=A0 =C2=A0 =C2=A0 signature gives n-of-n security; setup non-interactive= +ly via muSig,<br> +=C2=A0 =C2=A0 =C2=A0 or semi-interactively via proof of possession of priva= +te key;<br> +=C2=A0 =C2=A0 =C2=A0 interactive signature protocol)<br> +<br> +=C2=A0 =C2=A0 - enables m-of-n multisig key aggregation with interactive se= +tup and<br> +=C2=A0 =C2=A0 =C2=A0 interactive signature protocol, and possibly substanti= +al storage<br> +=C2=A0 =C2=A0 =C2=A0 requirements for participating signers<br> +<br> +=C2=A0 =C2=A0 - enables scriptless scripts and discreet log contracts via<b= +r> +=C2=A0 =C2=A0 =C2=A0 key aggregation and interactive<br> +<br> +=C2=A0 =C2=A0 - enables payment decorrelation for lightning<br> +<br> +=C2=A0 =C2=A0 - enables batch validation of signatures, which substantially= + reduces<br> +=C2=A0 =C2=A0 =C2=A0 computational cost of signature verification, provided= + a single<br> +=C2=A0 =C2=A0 =C2=A0 "all sigs valid" or "some sig(s) invali= +d" output (rather than<br> +=C2=A0 =C2=A0 =C2=A0 "sig number 5 is invalid") is sufficient<br> +<br> +=C2=A0 =C2=A0 - better than ecdsa due to reducing signature malleability<br= +> +=C2=A0 =C2=A0 =C2=A0 (and possibly due to having a security proof that has = +had more<br> +=C2=A0 =C2=A0 =C2=A0 review?)<br> +<br> +=C2=A0 =C2=A0Approaches:<br> +=C2=A0 =C2=A0 =C2=A0- bump segwit version to replace P2WPKH<br> +=C2=A0 =C2=A0 =C2=A0- replace an existing OP_NOP with OP_CHECKSCHNORRVERIFY= +<br> +=C2=A0 =C2=A0 =C2=A0- hardfork to allowing existing addresses to be solved = +via Schnorr sig<br> +=C2=A0 =C2=A0 =C2=A0 =C2=A0as alternative to ECDSA<br> +<br> +2) Merkelized Abstract Syntax Trees<br> +<br> +=C2=A0 =C2=A0Two main benefits for enabling MAST:<br> +=C2=A0 =C2=A0 - logarithmic scaling for scripts with many alternative paths= +<br> +=C2=A0 =C2=A0 - only reveals (approximate) number of alternative execution = +branches,<br> +=C2=A0 =C2=A0 =C2=A0 not what they may have been<br> +<br> +=C2=A0 =C2=A0Approaches:<br> +=C2=A0 =C2=A0 - replace an existing OP_NOP with OP_MERKLE_TREE_VERIFY, and = +treat an<br> +=C2=A0 =C2=A0 =C2=A0 item remaining on the alt stack at the end of script e= +xeution as a<br> +=C2=A0 =C2=A0 =C2=A0 script and do tail-recursion into it (BIP 116, 117)<br= +> +=C2=A0 =C2=A0 - bump the segwit version and introduce a "pay-to-merkel= +ized-script"<br> +=C2=A0 =C2=A0 =C2=A0 address form (BIP 114)<br> +<br> +3) Taproot<br> +<br> +=C2=A0 =C2=A0Requirements:<br> +=C2=A0 =C2=A0 - only feasible if Schnorr is available (required in order to= + make the<br> +=C2=A0 =C2=A0 =C2=A0 pubkey spend actually be a multisig spend)<br> +=C2=A0 =C2=A0 - andytoshi has written up a security proof at<br> +=C2=A0 =C2=A0 =C2=A0 <a href=3D"https://github.com/apoelstra/taproot" rel= +=3D"noreferrer" target=3D"_blank">https://github.com/apoelstra/<wbr>taproot= +</a><br> +<br> +=C2=A0 =C2=A0Benefits:<br> +=C2=A0 =C2=A0 - combines pay-to-pubkey and pay-to-script in a single addres= +s,<br> +=C2=A0 =C2=A0 =C2=A0 improving privacy<br> +=C2=A0 =C2=A0 - allows choice of whether to use pubkey or script at spend t= +ime,<br> +=C2=A0 =C2=A0 =C2=A0 allowing for more efficient spends (via pubkey) withou= +t reducing<br> +=C2=A0 =C2=A0 =C2=A0 flexibility (via script)<br> +<br> +=C2=A0 =C2=A0Approaches:<br> +=C2=A0 =C2=A0 - bump segwit version and introduce a "pay-to-taproot&qu= +ot; address form<br> +<br> +4) Graftroot<br> +<br> +=C2=A0 =C2=A0Requirements:<br> +=C2=A0 =C2=A0 - only really feasible if Schnorr is implemented first, so th= +at<br> +=C2=A0 =C2=A0 =C2=A0 multiple signers can be required via a single pubkey/s= +ignature<br> +=C2=A0 =C2=A0 - people seem to want a security proof for this; not sure if = +that's<br> +=C2=A0 =C2=A0 =C2=A0 hard or straightforward<br> +<br> +=C2=A0 =C2=A0Benefits:<br> +=C2=A0 =C2=A0 - allows delegation of authorisation to spend an output alrea= +dy<br> +=C2=A0 =C2=A0 =C2=A0 on the blockchain<br> +=C2=A0 =C2=A0 - constant scaling for scripts with many alternative paths<br= +> +=C2=A0 =C2=A0 =C2=A0 (better than MAST's logarithmic scaling)<br> +=C2=A0 =C2=A0 - only reveals the possibility of alternative execution branc= +hes, <br> +=C2=A0 =C2=A0 =C2=A0 not what they may have been or if any actually existed= +<br> +<br> +=C2=A0 =C2=A0Drawbacks:<br> +=C2=A0 =C2=A0 - requires signing keys to be online when constructing script= +s (cannot<br> +=C2=A0 =C2=A0 =C2=A0 do complicated pay to cold wallet without warming it u= +p)<br> +=C2=A0 =C2=A0 - requires storing signatures for scripts (if you were able t= +o<br> +=C2=A0 =C2=A0 =C2=A0 reconstruct the sigs, you could just sign the tx direc= +tly and wouldn't<br> +=C2=A0 =C2=A0 =C2=A0 use a script)<br> +=C2=A0 =C2=A0 - cannot prove that alternative methods of spending are not<b= +r> +=C2=A0 =C2=A0 =C2=A0 possible to anyone who doesn't exclusively hold (p= +art of) the<br> +=C2=A0 =C2=A0 =C2=A0 output address private key<br> +=C2=A0 =C2=A0 - adds an extra signature check on script spends<br> +<br> +=C2=A0 =C2=A0Approaches:<br> +=C2=A0 =C2=A0 - bump segwit version and introduce a "pay-to-graftroot&= +quot; address form<br> +<br> +5) Interactive Signature Aggregation<br> +<br> +=C2=A0 =C2=A0Requirements:<br> +=C2=A0 =C2=A0 - needs Schnorr<br> +<br> +=C2=A0 =C2=A0Description:<br> +=C2=A0 =C2=A0 - allows signers to interactively collaborate when constructi= +ng a<br> +=C2=A0 =C2=A0 =C2=A0 transaction to produce a single signature that covers = +multiple<br> +=C2=A0 =C2=A0 =C2=A0 inputs and/or OP_CHECKSIG invocations that are resolve= +d by Schnorr<br> +=C2=A0 =C2=A0 =C2=A0 signatures<br> +<br> +=C2=A0 =C2=A0Benefits:<br> +=C2=A0 =C2=A0 - reduces computational cost of additional signatures (i thin= +k?)<br> +=C2=A0 =C2=A0 - reduces witness storage needed for additional signatures to= + just the<br> +=C2=A0 =C2=A0 =C2=A0 sighash flag byte (or bytes, if it's expanded)<br> +=C2=A0 =C2=A0 - transaction batching and coinjoins potentially become cheap= +er than<br> +=C2=A0 =C2=A0 =C2=A0 independent transactions, indirectly improving on-chai= +n privacy<br> +<br> +=C2=A0 =C2=A0Drawbacks:<br> +=C2=A0 =C2=A0 - each soft-fork introduces a checkpoint, such that signature= +s that<br> +=C2=A0 =C2=A0 =C2=A0 are not validated by versions prior to the soft-fork c= +annot be<br> +=C2=A0 =C2=A0 =C2=A0 aggregated with signatures that are validated by versi= +ons prior to<br> +=C2=A0 =C2=A0 =C2=A0 the soft-fork (see [0] for discussion about avoiding t= +hat drawback)<br> +<br> +=C2=A0 =C2=A0Approaches:<br> +=C2=A0 =C2=A0 - crypto logic can be implemented either by Bellare-Neven or = +MuSig<br> +=C2=A0 =C2=A0 - needs a new p2wpkh output format, so likely warrants a segw= +it<br> +=C2=A0 =C2=A0 =C2=A0 version bump<br> +=C2=A0 =C2=A0 - may warrant allowing multiple aggregation buckets<br> +=C2=A0 =C2=A0 - may warrant peer-to-peer changes and a new per-tx witness<b= +r> +<br> +6) Non-interactive half-signature aggregation within transaction<br> +<br> +=C2=A0 =C2=A0Requirements:<br> +=C2=A0 =C2=A0 =C2=A0- needs Schnorr<br> +=C2=A0 =C2=A0 =C2=A0- needs a security proof before deployment<br> +<br> +=C2=A0 =C2=A0Benefits:<br> +=C2=A0 =C2=A0 =C2=A0- can halve the size of non-aggregatable signatures in = +a transaction<br> +=C2=A0 =C2=A0 =C2=A0- in particular implies the size overhead of a graftroo= +t script<br> +=C2=A0 =C2=A0 =C2=A0 =C2=A0is just 32B, the same as a taproot script<br> +<br> +=C2=A0 =C2=A0Drawbacks:<br> +=C2=A0 =C2=A0 =C2=A0- cannot be used with scriptless-script signatures<br> +<br> +=C2=A0 =C2=A0Approaches:<br> +=C2=A0 =C2=A0 =C2=A0- ideally best combined with interactive aggregate sign= +atures, as it<br> +=C2=A0 =C2=A0 =C2=A0 =C2=A0has similar implementation requirements<br> +<br> +7) New SIGHASH modes<br> +<br> +=C2=A0 =C2=A0These will also need a new segwit version (for p2pk/p2pkh) and= + probably<br> +=C2=A0 =C2=A0need to be considered at the same time.<br> +<br> +8) p2pk versus p2pkh<br> +<br> +=C2=A0 =C2=A0Whether to stick with a pubkeyhash for the address or just hav= +e a pubkey<br> +=C2=A0 =C2=A0needs to be decided for any new segwit version.<br> +<br> +9) Other new opcodes<br> +<br> +=C2=A0 =C2=A0Should additional opcodes in new segwit versions be reserved a= +s OP_NOP or<br> +=C2=A0 =C2=A0as OP_RETURN_VALID, or something else?<br> +<br> +=C2=A0 =C2=A0Should any meaningful new opcodes be supported or re-enabled?<= +br> +<br> +10) Hard-fork automatic upgrade of p2pkh to be spendable via segwit<br> +<br> +=C2=A0 =C2=A0Making existing p2pk or p2pkh outputs spendable via Schnorr wi= +th<br> +=C2=A0 =C2=A0interactive signature aggregation would likely be a big win fo= +r people<br> +=C2=A0 =C2=A0with old UTXOs, without any decrease in security, especially i= +f done<br> +=C2=A0 =C2=A0a significant time after those features were supported for new= + outputs.<br> +<br> +11) Should addresses be hashes or scripts?<br> +<br> +=C2=A0 =C2=A0maaku's arguments for general opcodes for MAST make me won= +der a bit<br> +=C2=A0 =C2=A0if the "p2pkh" approach isn't better than the &q= +uot;p2wpkh" approach; ie<br> +=C2=A0 =C2=A0should we have script opcodes as the top level way to write ad= +dresses,<br> +=C2=A0 =C2=A0rather than picking the "best" form of address every= +one should use,<br> +=C2=A0 =C2=A0and having people have to opt-out of that. probably already to= +o late<br> +=C2=A0 =C2=A0to actually have that debate though.<br> +<br> +Anyway, I think what that adds up to is:<br> +<br> +=C2=A0- Everything other than MAST and maybe some misc new CHECKVERIFY opco= +des<br> +=C2=A0 =C2=A0really needs to be done via new segwit versions<br> +<br> +=C2=A0- We can evaluate MAST in segwit v0 independently -- use the existing= +<br> +=C2=A0 =C2=A0BIPs to deploy MAST for v0; and re-evaluate entirely for v1 an= +d later<br> +=C2=A0 =C2=A0segwit versions.<br> +<br> +=C2=A0- There is no point deploying any of this for non-segwit scripts<br> +<br> +=C2=A0- Having the taproot script be a MAST root probably makes sense. If s= +o,<br> +=C2=A0 =C2=A0a separate OP_MERKLE_MEMBERSHIP_CHECK opcode still probably ma= +kes<br> +=C2=A0 =C2=A0sense at some point.<br> +<br> +So I think that adds up to:<br> +<br> +=C2=A0a) soft-fork for MAST in segwit v0 anytime if there's community/e= +conomic<br> +=C2=A0 =C2=A0 support for it?<br> +<br> +=C2=A0b) soft-fork for OP_CHECK_SCHNORR_SIG_VERIFY in segwit v0 anytime<br> +<br> +=C2=A0c) soft-fork for segwit v1 providing Schnorr p2pk(h) addresses and<br= +> +=C2=A0 =C2=A0 taproot+mast addresses in not too much time<br> +<br> +=C2=A0d) soft-fork for segwit v2 introducing further upgrades, particularly= +<br> +=C2=A0 =C2=A0 graftroot<br> +<br> +=C2=A0e) soft-fork for segwit v2 to support interactive signature aggregati= +on<br> +<br> +=C2=A0f) soft-fork for segwit v3 including non-interactive sig aggregation<= +br> +<br> +The rationale there is:<br> +<br> +=C2=A0 (a) and (b) are self-contained and we could do them now. My feeling = +is<br> +=C2=A0 better to skip them and go straight to (c)<br> +<br> +=C2=A0 (c) is the collection of stuff that would be a huge win, and seems<b= +r> +=C2=A0 "easily" technically feasible. signature aggregation seems= + too<br> +=C2=A0 complicated to fit in here, and getting the other stuff done while w= +e<br> +=C2=A0 finish thinking about sigagg seems completely worthwhile.<br> +<br> +=C2=A0 (d) is a followon for (c), in case signature aggregation takes a<br> +=C2=A0 *really* long while. It could conceivably be done as a different<br> +=C2=A0 variation of segwit v1, really. It might turn out that there's n= +o<br> +=C2=A0 urgency for graftroot and it should be delayed until non-interactive= +<br> +=C2=A0 sig aggregation is implementable.<br> +<br> +=C2=A0 (e) and (f) are separated just because I worry that non-interactive<= +br> +=C2=A0 sig aggregation might not turn out to be possible; doing them as a<b= +r> +=C2=A0 single upgrade would be preferrable.<br> +<br> +Cheers,<br> +aj<br> +<br> +[0] <a href=3D"https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018= +-March/015838.html" rel=3D"noreferrer" target=3D"_blank">https://lists.linu= +xfoundation.<wbr>org/pipermail/bitcoin-dev/<wbr>2018-March/015838.html</a><= +br> +<br> +______________________________<wbr>_________________<br> +bitcoin-dev mailing list<br> +<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.= +<wbr>linuxfoundation.org</a><br> +<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" = +rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.<wbr>org= +/mailman/listinfo/bitcoin-<wbr>dev</a><br> +</blockquote></div><br></div> + +--0000000000007f475b056bdac37d-- + |