path: root/02/c17a737983303447bf46c38023e71c289494de

Return-Path: <bram@chia.net>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id EB118901
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu, 10 May 2018 20:11:08 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wm0-f52.google.com (mail-wm0-f52.google.com [74.125.82.52])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 8AD516AA
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu, 10 May 2018 20:11:06 +0000 (UTC)
Received: by mail-wm0-f52.google.com with SMTP id j5-v6so6422737wme.5
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu, 10 May 2018 13:11:06 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=chia-net.20150623.gappssmtp.com; s=20150623;
	h=mime-version:in-reply-to:references:from:date:message-id:subject:to
	:cc; bh=qfVST4Sz5kQsQYfwW4yUjqJOkbRvFy1To+DSzX442zM=;
	b=Gpe0MMTfrrdVz2Iiy4esTHwd/9p23P2X5Pa44u3Cj/V69EfYac936hXnNWcszs6fOu
	rm5Fvjl2x/HhpToakhth9Fwa0boqPcCFGT+7BDvVacV5fFPrckAsXDn8EsiGnWOExnzd
	/8SppPFPksyITkVAilpnw5+A0xKh2Rzf3Y15mwUCjSO7M5h4hE7/9vIdlcqg/vMm4E/y
	mxy76CTUMy+Nn414HnUctTIHGQ3BI3ZjrvUbUfSTpyJZLy0PmcHecfb7nsVZOWwlmrK6
	PdvZymL55ErWbN2oAR+dnBqB5uWMpPHeEoDQTg0XR7svEhN2IKFpW7BLHDtn6mR/wmZF
	0Acg==
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:cc;
	bh=qfVST4Sz5kQsQYfwW4yUjqJOkbRvFy1To+DSzX442zM=;
	b=Btdj0OhlUPg+3Oi+0MsYb/MES5usU9a3TOD3ehvTb4T2NwDJewREOfZS/m3QMCYgqG
	89GKoP3hBehWRHR6AoZC2CaoPIL5kgCyh8VmCs5+Cm2yK6JlAFOlQJ6DP4QAj1sF+qRc
	oMgrlOB84EvgkGUc/fTgaGsV0WwuOAfVah1uCw4yEID0L1hemT2RyjqTuNGZrU8l0J8i
	btn6J3Ybo5JX9PXUOafHMfbcKGj6sstxPUUn5IsV7DHPFALa25piwRir5bLZSpMjnyx4
	5cOJC3AJd00FHEMHOSjZGACkCmNoyan2AY/y9N9cmprza8KpXVp2/E1dBO7wnYyOJuci
	UUEQ==
X-Gm-Message-State: ALKqPwegHMYUXhTvGem+TepvnL1JOfEeG7q3qCdiqeDJ3Oxxab7BDQ0P
	NK4igEy0cODZQjc+RgtQxOKHplzxy9f6nsbNXTMYHA==
X-Google-Smtp-Source: AB8JxZrbuvaF8wMJQNwPTWYke7yrRZkX4wFREF7mB39j2M/U8AHMXIahWftw3YRKbA4UPI/nLVSstNoHpV16j0XGC3o=
X-Received: by 2002:a1c:e08:: with SMTP id 8-v6mr211711wmo.67.1525983065094;
	Thu, 10 May 2018 13:11:05 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.28.145.4 with HTTP; Thu, 10 May 2018 13:11:04 -0700 (PDT)
X-Originating-IP: [71.202.120.50]
In-Reply-To: <CAMZUoKnPVz+XOq-cQRQuLbCuqn4H28WSMXCK3Rnt8VVivedYCw@mail.gmail.com>
References: <20180510121027.GA17607@erisian.com.au>
	<CAMZUoKnPVz+XOq-cQRQuLbCuqn4H28WSMXCK3Rnt8VVivedYCw@mail.gmail.com>
From: Bram Cohen <bram@chia.net>
Date: Thu, 10 May 2018 13:11:04 -0700
Message-ID: <CAHUJnBDZW4sgic83E=3CQ78i_50qj9N8pATQwCR5T3p_RkpObg@mail.gmail.com>
To: "Russell O'Connor" <roconnor@blockstream.io>, 
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000875a32056bdf9e81"
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID,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
X-Mailman-Approved-At: Fri, 11 May 2018 02:46:41 +0000
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 20:11:09 -0000

--000000000000875a32056bdf9e81
Content-Type: text/plain; charset="UTF-8"

I'm not sure about the best way to approach soft-forking (I've opined on it
before, and still find the details mind-numbing) but the end goal seems
fairly clearly to be an all of the above: Have aggregatable public keys
which support simple signatures, taproot with BIP 114 style taproot, and
Graftroot. And while you're at it, nuke OP_IF from orbit and make all the
unused opcodes be return success.

This all in principle could be done in one fell swoop with a single new
script type. That would be a whole lot of stuff to roll out at once, but at
least it wouldn't have so many painstaking intermediate soft forks to
administer.

On Thu, May 10, 2018 at 7:23 AM, Russell O'Connor via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> 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
>>
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>

--000000000000875a32056bdf9e81
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">I&#39;m not sure about the best way to approach soft-forki=
ng (I&#39;ve opined on it before, and still find the details mind-numbing) =
but the end goal seems fairly clearly to be an all of the above: Have aggre=
gatable public keys which support simple signatures, taproot with BIP 114 s=
tyle taproot, and Graftroot. And while you&#39;re at it, nuke OP_IF from or=
bit and make all the unused opcodes be return success.<div><br></div><div>T=
his all in principle could be done in one fell swoop with a single new scri=
pt type. That would be a whole lot of stuff to roll out at once, but at lea=
st it wouldn&#39;t have so many painstaking intermediate soft forks to admi=
nister.</div></div><div class=3D"gmail_extra"><br><div class=3D"gmail_quote=
">On Thu, May 10, 2018 at 7:23 AM, Russell O&#39;Connor via bitcoin-dev <sp=
an dir=3D"ltr">&lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org"=
 target=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a>&gt;</span> wro=
te:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-=
left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div>Thanks for writ=
ing this up Anthony.<br><br></div>Do you think that a CHECKSIGFROMSTACK pro=
posal should be included within this discussion 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/r=
anjit/papers/scd.pdf" target=3D"_blank">http://people.csail.mit.edu/<wbr>ra=
njit/papers/scd.pdf</a>), enables poor-man&#39;s covenants, and I believe t=
he lightning folks are interested in it as well for some constant space sto=
rage scheme.<br></div><div class=3D"HOEnZb"><div class=3D"h5"><div class=3D=
"gmail_extra"><br><div class=3D"gmail_quote">On Thu, May 10, 2018 at 8:10 A=
M, Anthony Towns via bitcoin-dev <span dir=3D"ltr">&lt;<a href=3D"mailto:bi=
tcoin-dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin-dev@lists.<w=
br>linuxfoundation.org</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_=
quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1=
ex">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&#39;s helpful for others too, so...<br>
<br>
They&#39;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&#39=
;m<br>
using &quot;schnorr&quot; just to describe the signature algorithm, and the=
 terms<br>
&quot;key aggregation&quot; to describe turning an n-of-n key multisig setu=
p into<br>
a single key setup, and &quot;signature aggregation&quot; to describe combi=
ning<br>
signatures from many inputs/transactions together: those are often all<br>
just called &quot;schnorr signatures&quot; in various places.<br>
<br>
<br>
Anyway! I think it&#39;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 &quot;all sigs valid&quot; or &quot;some sig(s) invali=
d&quot; output (rather than<br>
=C2=A0 =C2=A0 =C2=A0 &quot;sig number 5 is invalid&quot;) 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 &quot;pay-to-merkel=
ized-script&quot;<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/t<wbr>aproot=
</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 &quot;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&#39;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&#39;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&#39;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&#39;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 &quot;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&#39;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&#39;s arguments for general opcodes for MAST make me won=
der a bit<br>
=C2=A0 =C2=A0if the &quot;p2pkh&quot; approach isn&#39;t better than the &q=
uot;p2wpkh&quot; 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 &quot;best&quot; 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&#39;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 &quot;easily&quot; 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&#39;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/2018<wbr>-March/015838.html</a><=
br>
<br>
______________________________<wbr>_________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundat<wbr>ion.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-d<wbr>ev</a><br>
</blockquote></div><br></div>
</div></div><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>
<br></blockquote></div><br></div>

--000000000000875a32056bdf9e81--